《Computers & Operations Research》：An exact pruned route-enumeration and set-partitioning approach for the multi-pickup and delivery problem with time windows
编辑推荐：
在按需物流应用中，每个配送任务对应一个或多个取货任务，且所有取货必须在配送前完成，由此产生多取送货问题带时间窗（MPDPTW）。现有MPDPTW精确方法通常依赖大规模混合整数规划（MIP）模型并辅以大量分支与割平面操作。本文提出PRE-SP，一种精确的先验剪枝
在按需物流应用中，每个配送任务对应一个或多个取货任务，且所有取货必须在配送前完成，由此产生多取送货问题带时间窗（MPDPTW）。现有MPDPTW精确方法通常依赖大规模混合整数规划（MIP）模型并辅以大量分支与割平面操作。本文提出PRE-SP，一种精确的先验剪枝路径枚举与集合划分框架：先对候选单车请求子集进行先验评估，利用保持精确性的剪枝规则丢弃不可行子集，再在所得可行路径上求解集合划分主问题。在120个经典MPDPTW基准实例上的计算结果表明，PRE-SP在1小时时限内对116个实例证明最优，剩余4个实例在24小时时限内全部证明最优，优于该基准集上已有精确方法。对搜索空间的附加分析揭示了实例规模、请求长度与时间窗结构如何影响枚举过程的实际行为。在30个更大规模200节点实例上的实验进一步阐明了框架的可扩展性极限。总体而言，结果表明：保持精确性的剪枝路径枚举结合集合划分，在所研究的基准类别上构成一种具有竞争力的MPDPTW精确求解框架。
研究背景方面，按需物流系统（如快递平台与外卖服务）要求车辆在严格服务时间承诺下协同处理每车多个取货请求，由此形成多取送货问题带时间窗（MPDPTW, multi-pickup and delivery problem with time windows）。该问题在每个请求可含多个取货点再单一配送的情形下，显著增加了优先级与时序复杂度。现有精确方法多以大规模混合整数规划（MIP）配合分支切割（branch-and-cut）为主，在宽时间窗（W型）等弱时序结构实例上因可行路径空间爆炸且线性松弛薄弱而难以扩展。启发式与元启发式虽快却无法证明最优性。因此，研究人员开展本研究，旨在提供在现实规模下仍具可证明最优保证的精确框架。
研究人员提出PRE-SP框架，将单车请求子集通过路径级可行性子问题评估，施以保持精确性的安全剪枝规则剔除不可行子集，再将所得可行路径交由集合划分（set-partitioning）主问题组合，车辆容量经修正过程对最终入选路径重新校验。该文发表于《Computers & Operations Research》期刊语境下的表述为论文发表在《Computers 》。计算实验显示，在Naccache等2018年提出的120个标准基准实例（按时间窗窄N、松L、宽W分类，请求取送节点数25/35/50/100，每请求最多4或8个取货点）中，PRE-SP于1小时时限证优116例，余4例延至24小时全证优，超越Naccache等2018、Aziez等2020、Kohar与Jakhar 2021、Kohar等2023等分支切割方法，且在最难的W型实例上表现突出。额外30个200节点大实例实验刻画了框架扩展边界。研究意义在于用路径优先分解+精确性保持剪枝+集合划分主问题替代单体分支切割，为MPDPTW提供新精确范式，并公开无容量与有容量最优路径集供复现。
关键技术方法上，研究人员采用：一、先验单车请求子集枚举与路径级可行性子问题判定；二、保持精确性（exactness-preserving）的剪枝规则，依据时序窗口、请求长度与优先级丢弃无效子集；三、集合划分主问题整合可行路径；四、容量修正过程（correction procedure）对主问题解所选路径重验容量；五、基于Naccache等2018基准120例及自建30例200节点实例的实证队列。
研究结果按原文小节归纳。第1节引言指出MPDPTW源于按需物流，现有branch-and-cut难以扩展至W型，引出PRE-SP动机。第2节问题定义与记号形式化有向图G=(V,A)，顶点集V=P∪D∪{0,p+n+1}，P为取货点集{p≥n}，D为配送点集，请求r∈R关联Pr?P与单配送点dr∈D，每点i∈V有服务时长si≥0与时间窗[ai,bi]，允许等待。第3节文献综述对比既有MIP-branch-and-cut路线。第4节给出PRE-SP剪枝路径枚举框架与剪枝规则（含子集时序冲突、请求未闭合等判据）。第5节计算结果显示120基准中1小时证优116、24小时全证优120，W型提升最显；搜索空间分析表明实例规模、请求长度、时间窗结构主导枚举开销；200节点实验示可扩展性极限。第6节结论认为路由优先分解+精确性保持剪枝+集合划分是MPDPTW有竞争力精确框架。
讨论与结论翻译总结：研究人员得出结论，PRE-SP以路径枚举配精确性保持剪枝再接集合划分，在标准MPDPTW基准上比既有精确方法证优更多实例，尤擅宽时间窗类；框架计算行为受实例规模、请求长度与时间窗结构影响明确；200节点实验揭示其扩展上限；该精确框架兼顾可证明最优与实用规模，释放的路径集利于后续比较。整体表明route-first分解、exactness-preserving pruning与set-partitioning master结合，对所研基准类MPDPTW构成竞争性精确解框架。
