带释放日期与无人机再补给的旅行商问题（TSP-RD-DR）：新混合整数线性规划公式与数学启发式方法

《Computers & Operations Research》：The traveling salesman problem with release dates and drone resupply: A new formulation and a matheuristic approach

　　

无人机（drones）在最后一英里物流（last-mile logistics）中日益用于简化最终且常复杂的配送环节。尽管同步卡车-无人机系统（synchronized truck-and-drone systems）已被广泛研究，直接无人机配送仍面临监管与安全挑战。一种新兴替代方案是使用无人机在途再补给配送卡车（resupply delivery trucks in transit），从而缓解部分监管与安全障碍，并在不直接面向客户部署的情况下提升效率。该新系统减少对集中式仓库（centralized depots）的依赖，提高配送速度，支持实时订单履行（real-time order fulfillment），并增强灵活性、成本效益与可持续性。通过向在途卡车递送新包裹，无人机可减少绕行与燃料使用，尤其在农村地区，同时更好地匹配波动需求。在此背景下，研究人员处理带释放日期与无人机再补给的旅行商问题（Traveling Salesman Problem with Release Dates and Drone Resupply, TSP-RD-DR），其目标是在遵循客户释放日期（release dates）的条件下，确定卡车路径与无人机再补给计划，以服务所有客户，同时最小化配送完成时间。研究人员为该TSP-RD-DR提出一种新公式（formulation），并提出一种利用该公式的数学启发式方法（matheuristic approach）。所提出的方法在基准实例（benchmark instances）上测试，并与TSP-RD-DR的最先进方法（state of the art）进行比较。该新公式可在1小时时间限制（time limit）内求解最多20个客户的基准实例。该数学启发式方法在有限计算时间内提供高质量解，并可有效扩展至最多100个客户的实例。

Claudia Archetti、Maurizio Boccia、Adriano Masone与Claudio Sterle围绕带释放日期与无人机再补给的旅行商问题（Traveling Salesman Problem with Release Dates and Drone Resupply, TSP-RD-DR）开展研究。电子商务快速增长强化了对快速、可靠最后一英里配送的需求。无人机（drones）相比纯卡车配送可缩短时间、规避交通、降低运营成本并免除驾驶员需求，但其有限载荷与电池续航使长路径不切实际，纯无人机系统很少可行。已有混合卡车-无人机配送系统被提出，并形成运筹学中新的路径问题，主要包括并行无人机调度旅行商问题（parallel drone-scheduling traveling salesman problems, PDSTSPs）与带无人机的旅行商问题（traveling salesman problems with drone, TSPDs）。然而，直接面向客户的无人机配送仍面临监管、安全、隐私与公众接受等障碍。新兴替代方案是无人机在途再补给卡车，从而减少与客户直接交互相关的不确定性，并可与实时重优化或最优控制结合。该系统的实际背景包括同日配送、按订单生产、需要准备活动的装运等；释放日期可预先已知，或可足够可靠估计。TSP-RD-DR由Pina-Pardo et al. (2021)定义，其中释放日期表示客户包裹可用时间。文献综述表明，TSP-RD-DR及其变体相比PDSTSP与TSPD仍有限，且基本版嵌入多数后续扩展中，因此深入研究基本TSP-RD-DR具有价值。研究人员关注Pina-Pardo et al. (2021)定义的TSP-RD-DR，并提出新混合整数线性规划（Mixed Integer Linear Programming, MILP）公式与数学启发式方法（matheuristic）。

在问题描述与数学模型中，研究人员考虑单个卡车与单个无人机。客户订单按已知释放日期在仓库可用，每个客户每天至多一个订单。卡车载荷与里程无限制，无人机受载荷容量与飞行续航限制，且不能直接向客户配送，只能在客户位置与卡车会合并再补给。无人机不能在卡车不在场时卸下订单，卡车可在会合点等待无人机，每个客户仅访问一次。再补给时存在固定准备时间（setup time），装载卡车初始离仓时间可忽略。主要模型不考虑卡车开始路径后返回仓库，附录则提出允许两车均被再补给的公式。研究人员以服务腿（service legs, legs）为核心构建新MILP：节点集包括客户集C与仓库o，每个客户i∈C有释放日期r_i，每条弧(i,j)有卡车旅行时间t_ij，每个客户i有无人机旅行时间d_i；无人机续航为D_tl，最大载荷容量为Cap，固定准备时间为s_time。腿集合K={1,…,k_max}，最坏情况下k_max=|V|。决策变量包括卡车在腿k是否走弧(i,j)的x_kij、客户i是否在腿k由卡车服务的y_ki、客户i的订单是否在腿k开始时装上卡车的z_ki、腿k前再补给是否发生在节点i的δ_ki，以及腿k开始与结束时间τ_k^start与τ_k^end。目标为最小化τ_kmax+1^end，即配送完成时间。约束分为路由、再补给、无人机操作、释放日期、同步、一致性与对称破缺等族。该公式的结构性优势是释放日期与卡车-无人机同步约束不使用big-M系数，而通过有序服务腿及其开始/结束时间直接表示时间结构，避免实例相关M系数校准、松弛弱化与数值问题。为控制规模，研究人员基于“无人机出发时尽可能装载可用包裹”的观察设计算法计算再补给次数上界R^Oub，并令k_max=R^Oub+1。

关键技术方法可概括为：建立基于服务腿、无big-M释放日期与同步约束的新MILP；设计k_max上界算法；开发数学启发式，先通过结合p-median与p-center元素的聚类MILP识别客户簇，再以带时间窗旅行商问题MILP确定簇顺序，随后在固定有序腿的MILP中得到初始解；使用第一局部搜索固定访问序列优化再补给，使用第二局部搜索进行单客户重定位，并迭代反馈。实例来源包括：Set 1基于Solomon基准C101、C201、R101、RC101生成的72个实例；Set 2取自Pina-Pardo et al. (2021)的30、40、50客户共120个实例；Set 3为本研究生成的60至100客户共200个实例并公开。

研究结果部分保留原文小标题如下。5.1 实例细节：Set 1为小实例，客户数10、15、20，释放日期受β控制，β取0.5至3.0，卡车速度30 km/h、无人机速度60 km/h，无人机容量4，续航90 min，准备时间5 min。Set 2为中等实例，客户数30、40、50，共120个，无人机速度60或45 km/h，仓库位于中心A或外围B，释放日期从[0,480]均匀抽取。Set 3为大实例，客户数60、70、80、90、100，共200个，设置与Set 2相同，仅客户规模不同。5.2 小规模实例结果：研究人员将新公式ABMS与Pina-Pardo et al. (2021)的PSS21比较。72个实例中，ABMS求解98.61%至最优，PSS21为79.16%；平均最优性间隙从2.62%降至0.05%，平均运行时间约减少75%。在25客户实例上，PSS21仅解5个至最优，平均间隙13.32%；ABMS解7个至最优，平均间隙10.47%。因此，20客户被认为是公式有效处理的最大规模。数学启发式在Set 1上平均%Diff约2%，运行时间约2 s；贪婪分解初始解质量较差，平均%Diff略高于10%，第一局部搜索后平均%Diff为2.69%，第二局部搜索后为2.18%，并得到更多最优解。5.3 中等/大规模实例结果：在5.3.1 Set 2中，与RR方法比较，分解方法平均比RR差8.39%，第一局部搜索后基本持平（+0.02%），完整数学启发式比RR好2.41%；随客户数增加优势增大，30、40、50客户分别改进0.58%、2.94%、3.71%。无人机速度影响较小，仓库中心时完整方法改进3.65%，外围时改进1.18%。运行时间随规模从16.16 s增至62.63 s，中心仓库平均50.22 s，外围仓库平均26.71 s；RR时间因计算平台不同仅作背景信息。在5.3.2 Set 3中，完成时间随客户规模增加而增加，但变异性略降；无人机速度对完成时间影响不显著，卡车是主要瓶颈；中心仓库通常完成时间更低。第一局部搜索相比贪婪分解平均节省约10%，第二局部搜索额外节省约1.5%，规模越大节省越明显。数学启发式平均总运行时间145.83 s，200个Set 3实例中仅13个达到300 s限制。5.4 无人机容量与续航管理启示：研究人员在100客户实例上测试容量4或8、续航45或90 min。容量增加对完成时间影响大于续航：容量从4增至8时，续航45 min下完成时间平均减少约5.0%，续航90 min下减少约3.7%；续航从45增至90 min时，容量4下完成时间平均减少约1.5%，容量8下影响可忽略。运行时间方面，容量4时续航90 min计算更耗时；容量8时45与90 min运行时间分布几乎相同。结果表明，投资更大载荷容量通常比投资更长飞行续航带来更大运营收益，但当仓库远离服务区且无人机速度较低时，续航仍可能相关。

讨论与结论部分：研究人员的方法在多个基准集上表现稳健，与最先进方法相比具有竞争力且常优于最先进方法，为许多此前未解实例提供最优解或更紧界。敏感性分析表明，在测试配置下，提高无人机载荷容量通常比提高飞行续航更能降低完成时间。未来工作将把公式扩展到更广泛的卡车-无人机再补给设定，尤其是动态释放日期，并探索将数学启发式方法与机器学习和数据科学组件集成，以进一步提高解质量并减少计算时间。研究结论翻译如下：在本研究中，研究人员研究一种配送系统，其中无人机用客户订单再补给卡车，这些订单在运营期间于中央仓库释放。为求解由此产生的优化问题TSP-RD-DR，研究人员开发了精确方法与启发式方法。精确方法求解为该设定定制的新MILP公式，而数学启发式方法先聚类客户，然后通过固定精确模型中的部分决策求解一系列MILP子问题。两种方法均可容易地调整以允许卡车返回仓库进行再补给。在多个基准集上的计算结果证实了该方法的稳健性以及公式和数学启发式方法的有效性。研究人员的方法与最先进方法具有竞争力，且常常优于最先进方法，为许多先前未解实例提供最优解或更紧界。此外，敏感性分析还表明，在测试配置下，增加无人机载荷容量通常比增加飞行续航更能减少完成时间。未来工作将把公式扩展到更广泛的卡车-无人机再补给设定，尤其是动态释放日期，并探索将数学启发式方法与机器学习和数据科学组件集成，以进一步提高解质量并减少计算时间。