基于知识驱动的自适应延迟接受迭代爬山启发式算法求解巴士与自主配送机器人协同配送问题

本文系统研究了巴士与自主配送机器人（ADR）协同配送问题（BACDP），提出一种创新的三阶段迭代优化框架，结合自适应延迟接受爬山启发式（ALAHH）算法。通过k-means++聚类、变邻域搜索和求解器协同机制，有效解决了城乡客货融合运输中的"最后一公里"配送难题，为智能物流系统优化提供了新范式。

　　

亮点 (Highlights)

• 提出新型巴士与自主配送机器人（ADR）协同配送系统（BACDP），开创性地将公共交通网络与智能配送机器人进行多模态融合

• 构建可分解为主问题与子问题的数学模型，并严格证明主问题最优解即为原问题全局最优解的条件

• 设计知识驱动的三阶段迭代优化框架，融合自适应延迟接受爬山启发式（ALAHH）算法实现智能搜索

• 开发评估调用机制（EIM），显著提升求解器的计算效率与资源利用率

引言 (Introduction)

过去数十年间，传统城市物流配送模式长期由卡车和厢式货车主导。大量配送车辆不仅加剧空气污染和城市拥堵，更与公众对环境保护和便捷出行的诉求背道而驰。在乡村地区，物流需求呈现分布稀疏、距离遥远的特点，导致货运系统效率低下且盈利困难。由此，客货协同运输模式（IPTF）应运而生，该模式通过共享车辆、站点和线路等基础设施，可有效减少运输车辆对道路资源的占用，降低能耗排放并节约总体运营成本。

例如在中国广泛应用的客货邮融合巴士（PFPB），通过改造乘客空间并加装载货工具，实现了"客货同运"的创新模式。截至2024年，中国已有超过1.1万条农村公交线路开通货运服务。而FreightBus（FB）概念车则采用双层设计（图1.a），配备可折叠悬挂座椅（图1.b），为城市客货运输提供了全新解决方案。

然而无论是PFPB还是F*B，均无法提供门到门配送服务，主要原因在于：1）运输网络和站点覆盖有限；2）上门配送耗时易引起乘客不满；3）巴士体型庞大难以适应社区道路环境。

随着自动驾驶技术迅猛发展，自主配送机器人（ADR）近年来取得重大突破。研究表明ADR特别适用于最后一公里配送场景：相比无人机配送，机器人在地面运行更安全且受限制更少；可自主通行人行道和自行车道，并能通过远程控制应对异常情况；到达配送点后通过验证码或人脸识别解锁货舱。数据显示，全球11个主要ADR品牌的载重能力达22-220磅（10-100kg），时速4-96公里，可配送食品、药品、文件等多种物品。行业领军企业Starship Technologies已在伦敦和华盛顿开展包裹与杂货配送服务。

受卡车挂车路由问题（TTRP）和卡车-机器人协同配送（CTRD）启发，我们提出基于"巴士集群+多ADR"的协同配送问题（BACDP）。在该模型中，ADR利用巴士线路在配送子区域与 depot 间移动，实现长距离准时配送（图2）。巴士不直接参与配送，而是由ADR在子区域内完成多包裹投递。ADR早晨7:00搭乘BUS1前往子区域，7:30到达目的地站点，完成配送后于8:30乘坐BUS2返回 depot。

与TTRP或CTRD不同（卡车需在卫星点等待挂车/机器人完成配送），BACDP采用时刻表调度模式，ADR乘坐不同巴士往返，具有更高灵活性和能效。利用现有公交系统剩余运力，巴士-ADR协同配送成本显著低于其他两阶段配送模式（如TTRP、CTRD、卡车-无人机配送TDD等）。同时ADR具备极强适应性，可轻松进入城市社区电梯和乡村崎岖道路，使BACDP具有显著便利性优势。

该协同配送模式具有广阔应用前景：在乡村物流中，配备ADR的PFPB可实现包裹上门配送；在城市物流中，F*B与ADR组合可提升同城快递效率。近期中国行深智能推出的"袋鼠妈妈"无人配送系统（图3），由母ADR和子ADR组成：母ADR按固定线路运行，停靠楼宇附近；子ADR则负责将包裹配送至不同楼层的客户手中。

BACDP本质是TTRP的拓展创新，属于新型两阶段车辆路径问题（2E-VRP）。在第一阶段，BACDP采用ADR乘巴士模式替代传统卡车/大型无人机路由；第二阶段则与其他2E-VRP共享子路由问题。因此传统2E-VRP求解方法无法直接适用，需要重新设计高效优化算法。

结论 (Conclusion)

近年来，客货协同运输模式与自主配送机器人技术蓬勃发展。受卡车挂车路由问题和卡车-机器人协同配送启发，我们提出巴士与ADR协同配送问题（BACDP）。该新型配送模式具备四大特征：1）客货邮融合巴士（PFPB）辅助ADR进行包裹配送；2）单ADR单次行程可配送多个包裹；3）允许ADR乘坐不同巴士往返；4）充分利用公交系统剩余运力。通过构建数学模型并设计自适应延迟接受爬山启发式（ALAHH）算法，有效解决了这一NP难问题。实验结果表明，该算法在目标值和计算时间上显著优于模拟退火（SA）和延迟接受爬山（LAHC）算法，至今已在16个问题上取得最优解。