链上镖师 / Chain Biaoshi
EJOR|卡车与配送机器人取送货：协同路径优化
把门店取货、仓库发货、机器人自配送放进同一套取送货路由模型，用自适应遗传算法求解城市末端配送网络。
这篇论文把门店取货纳入卡车-机器人配送系统，提出TnR-PDP模型和自适应遗传算法，在算例中相对替代方案最高给出81%的成本节约潜力。
- 01：研究对象是第三方物流服务商在城市末端配送中同时处理仓库订单和门店订单。
- 02：核心机制是卡车携带机器人，机器人可从卡车、机器人仓或门店相关节点发起服务。
- 03：算法结果显示，AGA在小规模算例上接近精确或枚举方法，并在200客户实例中可在30分钟内处理。
研究背景
电商订单增长、城市拥堵、短时窗服务和劳动力压力共同抬高末端配送成本。论文关注的场景是零售商把近场门店接入第三方物流网络，让门店订单和仓库订单在同一套城市配送系统中协同处理。
来源：Table 1，卡车-机器人配送概念相关研究比较；本文同时覆盖取送货、时间窗、多次访问和最多200个客户规模。
已有卡车-机器人研究多把机器人视作卡车释放的末端服务工具，较少处理来自不同门店的取货请求。本文把机器人配送从单纯仓库发货扩展为仓库、门店和机器人仓共同参与的取送货系统。
核心问题
论文提出的Truck-and-Robot Pickup-and-Delivery Problem要求同时决定卡车停靠点、停靠顺序、机器人调度和配送模式。难点来自卡车停靠点没有预先给定，同一位置可被多次访问，也可能完全不访问。
来源：Fig. 2，基础与扩展卡车-机器人路径中的取货、配送和机器人自配送关系。
01Mode I：仓库发货，包裹随卡车出发，由机器人从卡车停靠点配送给常规客户。
02Mode II：卡车到门店取货，随后由卡车携带或现场释放机器人完成门店客户配送。
03Mode III：卡车释放空机器人，机器人到门店取货后直接配送给对应客户。
04Mode IV：机器人从机器人仓独立出发，到门店取货并完成配送，全程不需要卡车参与。
这个问题的本质是把第一公里取货和最后一公里配送合并规划，让每个门店客户在卡车取货、机器人取货和机器人自配送之间选择成本更低的服务方式。
方法框架
论文先建立混合整数规划模型，目标函数最小化卡车时间成本、卡车距离成本、机器人使用成本、机器人等待和延误成本。约束覆盖客户唯一服务、门店取货前后关系、机器人可用量、卡车机器人载量和包裹载量。
来源：Fig. 3，Adaptive Genetic Algorithm框架总览，覆盖初始化、路线评价、重组搜索、自适应机制和精英优化。
1初始化每个潜在停靠位置的访问频率范围VFR，并生成随机卡车路线种群。
2先检查路线是否满足机器人可用性，再用MIP为给定卡车路线安排机器人服务。
3通过定制交叉和变异算子改进路线，并依据优秀候选解调整VFR上下界。
4搜索前期侧重识别有价值停靠点，后期侧重优化已收敛停靠点的访问顺序。
案例或实验设置
基础算例位于德国慕尼黑市中心4平方公里区域，包含100个客户，其中20%为门店订单。网络设置为25个等距机器人仓、50个随机投放点、3家门店和一个仓库，客户时间窗为10分钟。
来源：Table 7，论文分析的三种配送概念及其求解方式，包括TnR-PDP、TnR+TSP和TSP-PD。
机器人仓数量
25
基础算例中等距布设
投放点数量
50
在配送区域内随机分布
参数设置中，卡车速度为30 km/h，机器人速度为5 km/h；卡车最多携带8台机器人和100件包裹，出发时装满8台机器人，并携带80件常规客户包裹。成本参数来自既有研究设定。
结果分析
来源：Table 5，MIP、枚举法与AGA在20到50客户实例下的成本和时间比较；AGA平均154秒求解，时间相对枚举法改善97.92%。
来源：Fig. 5，LS与AGA在平均成本和计算时间上的比较，展示客户规模扩大后AGA的效率优势。
在20到50客户的小规模测试中，MIP达到3小时时限后仍有较高gap，枚举法可作为更强基准。AGA平均成本为38.60，枚举法平均成本为38.59，平均差异仅为-0.02%，并在99%的实例中达到相等或更好的解。
来源：Fig. 8，不同门店客户占比下与分离式卡车和机器人配送方案的比较；门店订单占比越高，集成取送货方案的节约潜力越明显。
来源：Fig. 9，不同门店客户占比下与标准卡车配送方案的比较；25个客户场景最高降低71%，50个客户场景最高降低81%。
管理启示
实验显示，机器人自配送是门店订单整合后的关键杠杆。基础算例中，平均77%的门店客户通过机器人自配送完成；在更大客户规模下，这一比例最高达到95%，说明卡车无需为每个门店订单承担取货绕行。
来源：Fig. 10，机器人自配送对运营成本的影响；客户密度和每店客户数改变时，自配送比例与成本结构同步变化。
来源：Fig. 11，机器人取货配送模式对运营成本的影响；禁用机器人取货模式时，200客户算例成本可上升40%，小订单量场景最高体现46%的节约潜力。
✓门店订单分散且单店订单量较低时，应优先让机器人直接到店取货并配送。
✓同一门店订单聚集时，卡车到店取货更容易摊薄停靠成本，并减少机器人延误。
✓第三方物流接入门店订单时，需要同时评估门店密度、客户密度、时间窗压力和机器人仓覆盖范围。
论文给出的管理结论是，门店取货适合进入卡车-机器人联合网络；价值大小取决于机器人自配送与机器人取货模式能否在订单密度和时间窗约束下被充分调用。
论文：The truck-and-robot routing problem with pickups and deliveries
作者：Manuel Ostermeier，Tobias Huf
期刊：European Journal of Operational Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
