设施选址装箱博弈问题的机制设计与分析.pdfVIP

2025年6月这筹学学报(中英文)第29卷第2期

June,2025OperationsResearchTransactionsVol.29No.2

DOI:10.15960/j.cnki.issn.1007-6093.2025.02.004

设施选址装箱博奔问题的机制设计与分析*

2李闽溟3,

盖玲1张威伟2

摘要本文创新性地将设施选址博奔与装箱问题相结合，定义了一类新的设施选址装箱

博奔问题。与经典模型不同，我们首次分析了物品在访问设施后仍需进一步接受服务的情形，

并将优化目标设定为最小化所有物品的访问距离与所需装箱总数之和。在此模型中，物品是

博奔参与者，各自拥有位置信息和尺寸信息。首先，我们研究了物品尺寸为私有信息的情形，

物品的费用由装箱成本分摊。针对此情形下的纯装箱博奔和选址装箱博奔，我们分别设计了

具有策略证明性（防策略）的机制，其近似比分别介于[1,691,2]和[5/3,7/4]之间。其次，针

对物品尺寸信息与位置信息均为私有信息且相互关联的更复杂情形，我们考虑物品费用即为

访问设施的实际距离。在此设定下，我们设计了三个策略证明机制，并分别严格证明了它们的

本研究拓展了设施选址博奔的理论框架，提出的机制设计方法能够有效处理物品访问设施距

离优化与其后续装箱服务资源优化协同的问题，并在参与者拥有私有信息且可能策略行事的

复杂环境下，保证方案的防策略性和近似效率。

关键词设施选址博奔，装箱，防策略机制，近似比

中图分类号0225,F224.32

2020数学分类号90B80,90C27,91A10

Mechanismdesignandanalysisforfacilitylocation

binpackinggames*

GAILinglZ

ZHANGWeiwei?LIMinming.

AbstractThispaperinnovativelyintegratesfacilitylocationgameswiththebin

packingproblem,defininganovelclassoffacilitylocationbinpackinggames(FLBPG).

Departingfromclassicalmodels,wearethefirsttoanalyzeascenarioinwhichitems

requirefurtherserviceaftervisitingafacility.Ouroptimizationobjectiveistominimize

thetotalaccessdistancesofallitemstothefacilities,aswellastheoverallnumberof

binsrequiredforthissubsequentservice.Inthismodel,itemsactasstrategicagents,

eachpossessinginformationabouttheirlocationandsize.First,westudythescenario

inwhichitemsizeisprivateinformation,andtheitemcostisdeterminedbysharing

thebinpackingcost.Fortheresultingpurebinpackinggameandfacilitylocationbin

packinggame,wedesignstrategy-proofmechanism