链上镖师 / Chain Biaoshi
TRE|顾客选择下机器人配送：混合设施选址路径联合优化
把包裹柜、多功能配送站、上门时窗和自取补偿放进同一个位置-路径模型
这篇论文研究末端机器人配送中包裹柜与多功能配送站如何协同布点，并在客户上门、自取和灵活选择并存时联合优化设施类型、客户分配和机器人路线。
- 01：研究对象是带客户选择和混合设施的机器人配送位置-路径问题，设施包括只支持自取的无人包裹柜和兼具自取、机器人上门配送功能的多功能配送站。
- 02：模型把上门配送时窗、自取距离补偿、设施容量、机器人容量与最大行驶距离纳入同一成本最小化框架。
- 03：作者设计改进变量邻域搜索算法，在LRP和LoRP基准上验证竞争力，并用真实应用背景生成实例分析设施组合、补偿系数、机器人参数和客户结构的影响。
研究背景
电商包裹量继续增长，末端配送面对分散客户、小批量订单和高服务要求。论文引用的背景数据显示，2024年全球零售电商销售额预计达到6万亿美元，全球包裹投递量超过2680亿件，末端配送约占供应链总成本的41%。
客户需求也在分化：有人需要带时窗的上门配送，有人愿意去附近设施自取，还有一部分客户可在两种服务之间灵活分配。论文关注的核心场景是，在同一城市服务区里同时配置无人包裹柜和多功能配送站。
Fig. 2：两级末端配送网络应用场景及HF-LCRP-PR示例解，展示设施选址、客户分配和机器人路线如何组成同一个决策问题。来源：Fig. 2。
这类系统的难点在于设施功能存在重叠：包裹柜成本低、只服务自取；多功能配送站成本更高，可作为自取点，也可派出机器人完成上门配送。
核心问题
论文把问题定义为LRP-RD-CC-HF：Location-routing problem for robot deliveries with customer choices and hybrid facilities。决策者需要决定哪些候选点开放为UPL，哪些开放为MDS，哪些客户自取，哪些客户由机器人上门服务。
01HD客户必须由MDS机器人上门服务，并满足服务时间窗。
02CP客户必须分配到开放设施自取，超过期望取件距离会产生线性补偿。
03FS客户可选择自取或机器人上门，模型根据成本、容量、路径和补偿统一决定服务方式。
设施功能
UPL自取；MDS自取+机器人配送
目标函数
固定设施成本+机器人固定成本+路径成本+取件补偿
约束层面，模型要求每个候选设施至多选择一种类型，CP和FS客户只能分配到已开放设施，HD和被上门服务的FS客户只能由MDS服务，同时满足设施容量、机器人容量、最大行驶距离、流守恒和时间窗。
方法框架
作者设计改进变量邻域搜索MVNS。算法先用两阶段构造启发式生成初始解：第一阶段暂时开放所有候选设施并按距离或补偿分配客户，第二阶段为每个MDS构造机器人路线并处理FS客户的服务方式。
Fig. 3：Fig. 2(b)示例解的方案表示，把设施类型、客户归属和路线安排编码成算法可搜索的数据结构。来源：Fig. 3。
1构造初始解：定位UPL和MDS，完成客户分配与机器人路线初排。
2适应性扰动：根据邻域历史贡献动态调整扰动算子的使用权重。
3VND局部搜索：使用路线内、路线间、设施类型转换和服务方式转换等邻域改进方案。
4动态接受与回溯：允许部分非改进解进入搜索，并定期回到历史最好解纠偏。
Algorithm 4：改进变量邻域搜索MVNS的整体流程，覆盖初始解、适应性扰动、VND、动态接受和回溯。来源：Algorithm 4。
Fig. 4：遗憾与回溯策略的搜索轨迹示意，用于解释算法在搜索偏离时如何返回更有希望的解。来源：Fig. 4。
案例或实验设置
实验分为三类。第一类使用Prins等人提出的LRP基准实例，检验MVNS在经典位置-路径问题上的竞争力；第二类使用Arslan和Haghi等人采用的LoRP实例，检验方法在带配送选项问题上的适应性。
第三类是作者根据真实应用背景生成的HF-LCRP-PR实例，用于分析混合设施、补偿覆盖模型、期望取件距离、机器人行驶距离与容量、客户请求量和客户结构等因素。
Fig. 5：实例100-8-8a的设施与客户分布示意，展示候选设施点和不同客户类型在服务区域中的空间分布。来源：Fig. 5。
参数校准中，作者先测试主搜索控制参数，再测试VND和路线局部搜索迭代次数，最终选择I_nimp=30、I_shaking=20、I_rtb=15、I_VND=50、I_LSr=20，并设置动态接受相关参数。
结果分析
在LRP基准上，MVNS与九类已有先进启发式进行比较。汇总结果显示，MVNS找到14个最佳已知解，平均Gap为0.33%，平均计算时间为212.3秒，整体处于已有高水平方法的竞争区间。
Table 3：LRP实例上MVNS与已有先进方法的nBKS、Gap和耗时汇总比较。来源：Table 3。
在LoRP基准上，MVNS与分支定价B&P和自适应大邻域搜索ALNS比较。162个实例汇总中，MVNS找到133个最佳已知解，平均Gap为0.011%，并报告16个新解，显示该算法可迁移到相近配送选项问题。
Table 4：LoRP实例上MVNS与B&P、ALNS的比较，按机器人最大行驶距离分组展示nBKS、Gap和耗时。来源：Table 4。
Fig. 8：补偿系数敏感性分析，显示补偿系数升高会推高不同实例的总成本。来源：Fig. 8。
管理启示
混合设施的价值来自功能分工。UPL适合承担低成本自取覆盖，MDS适合处理上门时窗客户和部分灵活客户；当两类设施一起进入网络设计，系统可以在固定成本、取件补偿和机器人路径成本之间寻找平衡。
Table 7：各实例的设施开启数量、MDS/UPL构成和机器人路线信息，用于观察混合设施配置与机器人多路线使用。来源：Table 7。
Fig. 7：不同实例规模下的覆盖模型比较，展示覆盖假设变化对方案成本的影响。来源：Fig. 7。
Fig. 12：机器人最大行驶距离与容量对目标值的影响，支撑MDS机器人续航和装载能力的选型分析。来源：Fig. 12。
Fig. 15：不同HD客户比例下开启设施数量的变化，说明客户服务偏好结构会改变MDS和UPL组合。来源：Fig. 15。
论文：Location-routing problem for robot deliveries with customer choices and hybrid facilities
作者：Lin Zhou，Roberto Baldacci，Ayman R. Mohammed
期刊：Transportation Research Part E
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
