提出新分解与元启发式结合方法，解决带时间窗的车辆中途交接配送难题。
Pickup & Delivery with Time Windows and Transfers: combining decomposition with metaheuristics
- 用逻辑贝德尔分解法提升求解精度，缩小最优性间隙。
- 在25~100个请求规模下均实现近优解，大样本仍具可扩展性。
- 自建实例生成器，填补现有基准数据不足，适合物流优化研究者。
本文研究允许车辆在途中进行负载交接并严格遵守各点时间窗的广义取送货问题。提出一种新型逻辑基于贝德尔分解（LBBD），显著改善文献中所有基准实例的最优性间隙，并可处理更大规模问题。为应对更大型实例，引入改进的大型邻域搜索（LNS）算法，增强其适应性，突破以往依赖特定配置的局限。为弥补基准数据不足，开发了实例生成器以支持广泛实验。针对中等规模数据集（25和50个请求），评估了LBBD与LNS性能：前者可闭合差距，后者可提供近优解。对于大规模实例（75和100个请求），重构当前先进元启发式方法以凸显本LNS改进带来的性能提升，并验证其可扩展性。
原文摘要 · Abstract (English)
This paper examines the generalisation of the Pickup and Delivery Problem that allows mid-route load exchanges among vehicles and obeys strict time-windows at all locations. We propose a novel Logic-Based Benders Decomposition (LBBD) that improves optimality gaps for all benchmarks in the literature and scales up to handle larger ones. To tackle even larger instances, we introduce a refined Large Neighborhood Search (LNS) algorithm that improves the adaptability of LNS beyond case-specific configurations appearing in related literature. To bridge the gap in benchmark availability, we develop an instance generator that allows for extensive experimentation. For moderate datasets (25 and 50 requests), we evaluate the performance of both LBBD and LNS, the former being able to close the gap and the latter capable of providing near-optimal solutions. For larger instances (75 and 100 requests), we recreate indicative state-of-the-art metaheuristics to highlight the improvements introduced by our LNS refinements, while establishing its scalability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。