基于分解的大规模取送货问题方法

《European Journal of Operational Research》:A decomposition-based approach for large-scale pickup and delivery problems

【字体: 大 中 小 】 时间:2026年02月02日 来源:European Journal of Operational Research 7.0

编辑推荐:

  随着自动驾驶汽车的出现,专家们认为自主移动出行(autonomous mobility-on-demand, AMoD)服务是改善超负荷交通系统现状的一种有前景的解决方案。在此背景下,研究人员对解决按需出行背景下出现的大规模取送货路径问题(pickup and

  
随着自动驾驶汽车的出现,专家们认为自主移动出行(autonomous mobility-on-demand, AMoD)服务是改善超负荷交通系统现状的一种有前景的解决方案。在此背景下,研究人员对解决按需出行背景下出现的大规模取送货路径问题(pickup and delivery routing problems)感兴趣。研究人员提供了一个算法框架,该框架在解决超过20,000个请求的实例方面达到了新的技术水平。该框架包括一个基于分解的元启发式(matheuristic)、一个迭代局部搜索(iterative local search, ILS)和一个混合算法,该算法使用元启发式来热启动ILS。研究人员对每种算法的性能、优点和缺点进行了全面的计算分析。此外,研究人员表明,该算法框架能够改进现有大规模基准实例的最优解。研究人员通过从全信息视角提供基于系统改进边界的管理见解,并分析一个包含超过20,000个请求的真实世界案例研究,来完善分析。
**论文解读文章**

**研究背景、问题与意义**

全球城市交通系统面临持续挑战,包括拥堵、生产率损失和环境外部性。共享经济的兴起推动了新型移动出行服务的发展,特别是移动出行(mobility-on-demand, MoD)系统,该系统服务于个人乘客运输请求。随着自动驾驶车辆的出现,这些服务有望演变为自主移动出行(autonomous mobility-on-demand, AMoD)系统,提供更高效、更低成本的解决方案,并可能被公众广泛采用。通过允许请求拼车、考虑拥堵的路径规划以及与公共交通的更好整合,此类系统有望减轻城市交通的负面影响。然而,其净影响仍不确定,因为便利性的增加可能诱导额外需求,从而抵消收益甚至转移而非减少外部性。

无论这一争论如何,普遍共识是高效运营对于释放自主移动出行(AMoD)系统的最大改进潜力至关重要。为此,需要开发有效的、可能具有前瞻性的控制算法来处理相关运营规划任务:拼车(如果可能)、将拼车行程分配给车辆以及重新平衡车辆以预测未来需求。这些规划问题引起了最优控制、运输优化和运筹学领域科学家的兴趣,并产生了多种算法方法,从在线控制算法(通常遵循部分规划任务分解方案)到旨在全信息环境中一次性解决所有规划任务的集成算法,以确定系统改进的上限。

在此背景下,现有方法通常至少存在一个缺点:(分解的)在线控制算法可扩展到非常大的真实世界实例(高达20,000个请求),但隐含地假设顺序决策的性能损失有限,且未进一步讨论。因此,系统改进分析仅限于与现状或(简单的)基线进行比较。虽然这种设置揭示了许多有趣的见解,但不足以严格分析系统改进潜力的上限,而这对于战术性和战略性交通系统分析和规划具有重要意义。全信息环境中解决集成规划问题的算法通常可扩展性有限,因此获得的完整信息边界从实践者角度来看意义不大,因为有限的问题规模削弱了结果的可靠性。在运筹学中,存在针对大规模(高达2,500个请求)取送货问题的初步方法,主要受货运运输启发。然而,这些实例规模较小,并且与自主移动出行(AMoD)中的需求模式和时间窗口明显不同,这引发了对现有(通常高度专业化)算法在此背景下有效性的质疑。

针对这一背景,研究人员旨在开发一个算法框架,能够解决自主移动出行(AMoD)系统中集成请求拼车和车辆到请求调度背景下出现的大规模取送货路径问题,涉及高达21,000个请求和2,000辆车。专注于离线全信息问题设置,研究人员设计该算法框架,使其不仅可以分析系统性能改进的全信息边界,还可以分析顺序或集成式拼车和调度决策的影响。

**研究内容、结论与意义**

研究人员提出了一个算法框架,包含三种方法:i) 基于分解的元启发式(matheuristic, MATH),能在几分钟内解决高达5,000个请求的实例;ii) 基于迭代局部搜索(iterative local search, ILS)的元启发式,采用解引导分解策略来处理超过20,000个请求的极大规模实例;iii) 混合方法(hybrid, COMB),其中使用元启发式解来热启动元启发式。

通过全面的计算研究,研究人员表明,在15分钟的时间限制内,元启发式(ILS)改进了元启发式(MATH)的解。热启动的混合方法(COMB)产生了更好的结果,与单独的元启发式相比,平均未分配请求减少高达6.8%。随后,研究人员将元启发式方法与包含多达2,500个请求的取送货问题(PDPTW)基准数据集的结果进行比较。结果表明算法的竞争力,并提供了107个新的最优解,其中90个解减少了车辆数。最后,将算法应用于高达21,375个请求的极大规模实例,以提供管理分析。结果表明,通过要求乘客允许交付时间仅2分钟的灵活性,出行提供者可以提供相当于60%更大车队规模的服务水平。

该论文发表在《European Journal of Operational Research》。

**关键技术方法**

研究人员为开展研究使用了以下主要关键技术方法:
- **基于分解的元启发式(MATH)**:将规划问题分解为顺序的拼车和调度决策。拼车阶段通过构建超图(hypergraph)并求解最大加权匹配(maximum weighted matching)来生成可行拼车组合(超边,hyperedge),超边权重兼顾成本和时间重叠。调度阶段将拼车结果转化为调度图(dispatching graph),通过求解k-不相交最短路径问题(k-disjoint shortest path problem, k-dSPP)进行车辆分配,使用多项式时间算法。
- **迭代局部搜索元启发式(ILS)**:采用解引导分解(solution-guided decomposition)策略,将当前解中的路径随机分割成子问题,每个子问题包含平均χ个请求,使用破坏重建(ruin & recreate, R&R)方法并行改进子问题,然后通过求解k-不相交最短路径问题(k-dSPP)重新组合获得完整解。破坏操作使用邻接字符串移除(adjacent string removal),重建操作使用带眨眼(blinks)的贪婪插入(greedy insertion)。还使用了基于Balas & Simonetti (2001)的路径内局部搜索(intra-route local search)进行强化。
- **混合方法(COMB)**:将元启发式(MATH)的求解结果作为迭代局部搜索(ILS)的初始解(热启动),以加速收敛并提高最终解质量。

样本队列来源:纽约市出租车和豪华轿车委员会(NYC Taxi and Limousine Commission)2015年1月5日至9日(周一至周五)的历史出租车行程数据,提取六个时段(夜间2-3点、清晨6-7点、上午10-11点、下午2-3点、傍晚6-7点、深夜10-11点)的请求。车辆初始位置按请求起源的空间分布比例采样,容量设定为3(拼车时)或1(出租车时),基准车队规模为1,000辆。

**研究结果**

**5.1 Computational analyses(计算分析)**
通过比较元启发式(MATH)、迭代局部搜索(ILS)和混合方法(COMB)在中等规模实例(MID25,约5,000个请求,25%样本)上的性能,发现:在主要目标(最小化未分配请求数)上,ILS和COMB均优于MATH;在次要目标(最小化总成本)上,当主要目标值相同时,COMB优于ILS。在车辆供应充足(800辆)时,三种算法性能相近;当车辆成为瓶颈(200或500辆)时,差异显著。对于500辆车的场景,ILS平均在10分钟内达到并改进MATH的解,COMB在1小时内产生优于ILS的解,且随缓冲时长(δ)增加,差异缩小。COMB从MATH解热启动后,在搜索初期总成本有所增加,但随后未分配请求减少而总成本未显著增加,表明能找到更高效的路径决策。最终,COMB平均比ILS减少6.8%的未分配请求。

**5.2 PDPTW benchmark(PDPTW基准测试)**
将ILS方法应用于Sartori & Buriol (2020)的基准实例(包含100至5,000个节点,即50至2,500个请求),并与现有最优解对比。结果显示了算法的竞争力,尤其是在较大规模实例上,累计车辆数比之前结果改进3.1%。共提供了107个新的最优解,其中90个解减少了车辆数。该基准测试基于真实道路网络数据,涵盖巴塞罗那、柏林、纽约市和阿雷格里港。

**5.3 Managerial analyses(管理分析)**
利用ILS研究极大规模实例(高达21,375个请求)的管理见解。首先,比较车队规模增加与拼车灵活性对服务水平的影响:将车队从1,000辆增加到2,000辆,服务水平仅增加最多27%;而允许交付时间仅2分钟灵活性(拼车场景)即可达到相当于将传统出租车车队规模增加60%(至1,600辆)的服务水平。其次,分析缓冲时长(δ)对拼车运营的影响:在1,000辆车的限制下,对于密集时段(如傍晚6点),2分钟缓冲即可将服务水平从约60%提升至80%;平均乘客经历延迟始终低于允许延迟的一半,即使允许20分钟延迟,平均延迟也仅约6分钟。成本分析显示,每请求成本随灵活性增加先上升后趋于平稳,与服务水平的提升无直接相关性。

**总结讨论与结论翻译**

**总结讨论**:
本文提出了一个算法框架,用于解决城市拼车系统中出现的极大规模取送货问题(PDPTW)变体。该框架包含三种方法:基于分解的元启发式(MATH),可在几分钟内解决高达5,000个请求的实例;基于迭代局部搜索(ILS)的元启发式,采用解引导分解处理超过20,000个请求的实例;以及混合方法(COMB),即用元启发式解热启动元启发式。计算研究表明,元启发式在15分钟内优于元启发式,热启动的混合方法平均减少6.8%的未分配请求。在基准测试中,算法提供了107个新最优解,其中90个减少了车辆数。管理分析表明,允许乘客仅2分钟的交付灵活性,可使出行提供者获得相当于60%更大车队规模的服务水平。

**结论翻译**:
在本文中,研究人员提出了一个算法框架,用于解决城市拼车系统中出现的极大规模取送货问题(PDPTW)变体实例。为了获得高质量解,研究人员提出了一个包含三种方法的算法框架:i) 基于分解的元启发式(matheuristic),可在几分钟内解决高达5,000个请求的实例;ii) 基于迭代局部搜索(iterative local search, ILS)的元启发式,采用解引导分解来处理超过20,000个请求的极大规模实例;iii) 混合方法,即使用元启发式的解来热启动元启发式。研究人员利用该算法框架进行了全面的计算研究,以深入了解所提出算法的特性。研究表明,在15分钟的时间限制内,元启发式改进了元启发式的解。热启动的混合方法产生了更好的结果,与单独的元启发式相比,平均未分配请求减少高达6.8%。接下来,研究人员将元启发式方法与取送货问题(PDPTW)基准数据集(包含多达2,500个请求的实例)的结果进行比较。结果表明算法的竞争力,并提供了107个新的最优解,其中90个解减少了车辆数。最后,将算法应用于高达21,375个请求的极大规模实例,以提供管理分析。结果表明,通过要求乘客允许交付时间仅2分钟的灵活性,出行提供者可以提供相当于60%更大车队规模的服务水平。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号