一种用于具有时间窗口的多件商品取货与配送问题的、基于增强记忆功能的贪婪随机自适应搜索算法

《Computers & Operations Research》：A memory-enhanced Greedy Randomized Adaptive Search Procedure for the Multi-Pickup and Delivery Problem with Time Windows

多取货交付问题时间窗口约束的求解方法及实验分析。本文提出基于GRASP的记忆增强框架，集成长期记忆存储可行路线和无效请求集，约束传播加速可行性检查，并引入集合覆盖重组策略优化解集。实验表明该框架在标准基准数据上平均优于现有方法0.41%，有效解决大规模复杂约束问题。

　　

萨尔玛·布赫拉（Salma Bouhlla）| 里姆·内斯琳·吉巴杰（Rym Nesrine Guibadj）| 阿齐兹·穆克里姆（Aziz Moukrim）

法国加莱市Littoral C?te d’Opale大学，EA 4491 - LISIC项目 - 加莱海岸信号与图像信息实验室，邮编F-62228

摘要

本文研究了具有时间窗口的多次取货和送货问题（MPDPTW），这是传统取货和送货问题的一个复杂扩展版本，它在优先级和时间窗口约束下涉及每个请求的多次取货。

我们引入了一个基于贪婪随机自适应搜索算法（GRASP）的记忆增强型启发式框架。与传统的GRASP实现不同，后者依赖于独立的多起点构造和后续的局部搜索，所提出的框架嵌入了一个结构化的长期记忆系统，该系统记录了可行的路线和不可行的请求子集。这种机制防止了对相同请求组合的重复评估，并在整个搜索过程中加速了可行性检查。然后应用基于集合覆盖的重组合阶段来整合高质量路线，进一步提高整体解决方案的质量。

在标准基准实例上的计算实验表明，所提出的方法能够一致地找到文献中报告的所有已知最佳解决方案，并且平均提高了0.41%。这些结果证明了将累积记忆指导与全局路线重组合相结合在解决大规模和高度受限的MPDPTW问题中的有效性。

引言

在工业和服务物流中，许多操作要求车辆在完成相应的送货之前执行多次连续的取货。这种情况在电子商务、城市配送和按需服务中很常见，其中车辆从多个上游地点汇总货物到单一目的地，以减少运输频率和运营成本。一个关键的运营规则是，只有在所有相关的取货完成后才能进行送货，这在每条路线中引入了强烈的优先级和时间依赖性。例如，在收取停车费时，车辆必须访问多个收费站，然后才能将所有收取的现金送到指定地点。同样，在线食品配送平台必须在将所有餐食送到客户之前协调多次从餐厅的取货。类似的挑战也出现在零售配送中，其中商店从多个仓库补充货物。将这些操作整合到单一的协调路线中可以减少冗余行程并提高资源利用率。这些例子说明了需要有效的解决方案方法来管理在优先级和时间窗口约束下与单一送货相关联的多次取货。具有时间窗口的多次取货和送货问题（MPDPTW）通过强制同一辆车完成属于同一请求的所有取货，并且这些取货严格先于相关的送货来捕捉这一运营现实。这种表述有效地模拟了现代物流系统中遇到的排序要求，其中协调直接影响成本效率和服务质量。

与传统的取货和送货问题（PDP）相比，MPDPTW引入了额外的结构复杂性。每个送货节点都与多个取货节点相关联，加强了优先级和时间窗口约束。这种耦合创造了一个组合挑战，因为可行性同时取决于这两个因素。目标是构建一组可行的路线，以最小化总运输成本，同时满足所有优先级和时间窗口限制。

以往的研究主要集中在传统的PDP或其扩展上，通常采用精确方法，如分支定界法（S. Ropke和D. Pisinger，2006年）和整数线性规划（Cordeau等人，2008年）。尽管这些方法可以为小规模问题提供最优解，但它们在处理现实世界中的大规模问题时在计算上是不切实际的。为了解决这些限制，人们广泛探索了启发式和元启发式方法，如禁忌搜索、遗传算法和蚁群优化（S. Ropke和D. Pisinger，2006年）。

MPDPTW主要通过基于分支定界和分支剪枝框架的精确方法来解决（Aziez等人，2020年；Amit和Kumar，2021年；Kohar等人，2023年）。尽管这些方法提供了有价值的理论见解，但它们在可扩展性方面存在显著限制，无法在合理的计算时间内解决大规模问题。到目前为止，只有Naccache等人（2018年）提出了一种基于自适应大邻域搜索（ALNS）的启发式方法。所提出的ALNS方法依赖于带有重复可行性检查的自适应邻域探索。在本文中，我们提出了一个专门设计用于利用MPDPTW结构特性的可扩展GRASP框架。我们的框架引入了可行性学习和重组阶段，能够修剪不可行的请求子集并全局整合高质量路线。

本文的主要贡献可以总结如下：

• 我们提出了一个基于GRASP的框架，在构建过程中强制执行优先级和时间窗口的可行性，从而能够及早检测并丢弃不可行的部分路线。
• 我们引入了一个全局长期记忆系统，以克服无记忆启发式方法的缺点。这个嵌入式记忆系统存储了可行路线和不可行的请求子集，防止了重复评估。
• 我们开发了一种专门的局部搜索程序，其中包含了通过约束传播机制增强的高级插入操作。该机制在每次移动后动态传播时间窗口约束，加速了可行性检查。
• 我们应用了一个基于集合覆盖的重组合阶段，从全局记忆中整合高质量路线，特别是在大规模实例上提高了解决方案的质量。

本文的其余部分组织如下：第2节回顾了有关MPDPTW及相关问题的相关文献。第3节提供了问题的详细表述。第4节介绍了提出的解决方案方法。第5节报告了计算实验并讨论了结果。最后，第7节总结了研究发现并概述了未来研究的潜在方向。

节选

文献综述

在本节中，我们概述了具有时间窗口的取货和送货问题（PDPTW）和MPDPTW，回顾了最先进的表述、算法和最新研究。

车辆路径问题（VRP）最初由Dantzig和Ramser（1959年）提出，由于其對物流和运输优化的重大影响而成为广泛研究的主题。多年来，研究扩展了原始问题，涵盖了各种扩展，例如

问题定义

本节介绍了MPDPTW的正式定义，包括其集合、参数、约束和目标函数。

一个MPDPTW实例涉及一组$n$个请求，这些请求将由$R=r_1，\dots ，r_n个$，由$K=1，\dots ，m$辆车提供服务。取货节点由集合表示，而送货节点由集合表示。每个请求$r$与一组取货节点$P_{}?P$相关联，且与一个送货节点$d_{}\in$相关联。重要的是

解决方案方法

本节介绍了我们用于解决MPDPTW的优化框架，结合了GRASP进行解决方案构建，长期记忆用于搜索增强，以及集合覆盖用于优化后处理。

如图2所示，GRASP在框架内用于探索搜索空间。它通过约束传播检测不可行的路线。探索到的路线（包括可行和不可行的路线）被存储在长期记忆中。这种记忆系统用于通过绕过

实验结果与分析

本节对我们的基于记忆增强的GRASP框架（ME-GRASP）进行了全面评估，并将其性能与文献中的最先进算法进行了比较。实验是在配备AMD Ryzen 5 PRO 5650U处理器（12核，4.29 GHz）和C++实现的Linux环境下进行的。为了严格评估性能，我们使用了两个关键指标：相对百分比误差（rpe）和平均相对百分比误差

讨论与局限性

所提出的ME-GRASP框架旨在明确利用MPDPTW的结构特性，并在标准基准测试中表现出强大的性能。与任何先进的启发式框架一样，其表现受实例大小和底层约束性质的影响。

从计算角度来看，随着请求数量的增加和时间窗口约束的放宽，计算工作量也会增加。虽然约束传播在

结论

在本文中，我们提出了一种高效的框架来解决具有时间窗口的多次取货和送货问题。我们的优化框架整合了贪婪随机自适应搜索算法来探索解决方案空间，利用长期记忆避免重复评估的加速机制，以及一个优化后阶段，应用集合覆盖方法来重组高质量路线并完善最终解决方案。为了进一步提高解决方案质量，我们的方法

CRediT作者贡献声明

萨尔玛·布赫拉（Salma Bouhlla）：撰写 – 审稿与编辑，撰写 – 原稿，可视化，软件，方法论，调查，形式分析，数据管理，概念化。里姆·内斯琳·吉巴杰（Rym Nesrine Guibadj）：撰写 – 审稿与编辑，可视化，验证，监督，软件，资源管理，方法论，调查，资金获取，形式分析，数据管理，概念化。阿齐兹·穆克里姆（Aziz Moukrim）：撰写 – 审稿与编辑，可视化，验证，监督，资源管理，

致谢

本研究得到了法国国家研究和技术协会（ANRT）通过CIFRE资助计划的支持。我们还要感谢Mobivia集团的支持和合作。此外，本文中介绍的实验是在CALCO计算平台上进行的，该平台得到了DSI/ULCO（Littoral C?te d’Opale大学信息系统部门）的支持。