近日，深圳市大数据研究院、华为GTS运筹优化实验室与香港中文大学（深圳）联合团队在优化求解技术方向取得重大突破，打破了由HEC等欧美团队保持的35项Sartori和Buriol PDPTW基准实例世界纪录[1]。该PDPTW基准是Sartori和Buriol 2020提出的基于实际工业场景的新基准，极具挑战性并包含多个开放问题，是业界最具权威性和公信度的榜单之一。此前加拿大蒙特利尔HEC、慕尼黑工大等欧美高校为主的世界顶尖团队在榜单上保持着众多世界领先记录。
作为NP-hard问题的典型代表，PDPTW问题一直是学术界研究的焦点，同时也是工业界常见的问题。它在资源规划、人员调度、物流配送等多个领域有着广泛的应用，刷新现有世界最佳纪录的难度不断攀升。面对这一挑战，团队介绍他们并没有选择传统路径，而是采用了基于NPU算力，矩阵重构传统求解算法，把经典启发式算子高耗时部分转为矩阵范式运算，结合昇腾NPU算力，突破了传统求解技术大规模问题的重大瓶颈，目前通过官方校验器，成功刷新了榜单中的35项最佳纪录，其中部分实例的优化幅度甚至超过了5%。
这也是继英伟达cuOPT在Li&Lim基准上突破23项记录、杉数科技cuPDLP在对传统LP加速60倍之后，业界在AI求解方向上的一个新的重大进展。展现了NPU/GPU为代表的AI算力和传统优化技术融合在未来智能决策领域的潜力和价值。
01 PDPTW问题背景
带时间窗口的取货和配送问题（PDPTW）是经典路径优化问题（VRP）的变体，一个涉及路线规划和时间管理的物流优化问题。此问题的核心是安排车辆在规定的时间窗口内完成取货和送货任务，以满足客户需求、优化路线效率，同时尽可能降低运输成本。PDPTW广泛应用于资源规划、物流、配送等工业场景。
02 算法介绍
该研究团队提出的算法核心是将经典的基于种群做有效交叉(SREX和EAX)进化的启发式搜索方法与基于NPU大规模矩阵运算结合，通过交叉算子(SREX和EAX)进化生成大量路径，然后把传统将可行性评估、目标函数评估等高耗时环节转为矩阵算法，基于NPU极大的加速效率，部分加速率可达100倍，接着通过基于NPU加速求解集合划分问题(SPP)，快速得到高质量solution，同时外层也对种群管理机制探索了新的多种群Diversity机制极大提升寻优能力。
算法整体框架
关键技术点1：基于NPU技术批量快速精确评估技术
在该研究团队开发的最新算法框架中，他们专门为高耗时的路径和解评估设计了一项创新技术：将评估转化成矩阵运算，通过调用昇腾矩阵运算算子进行高效评估。通过这一技术能够对传统约束可行性、目标评估高耗时环节极大的加速，部分可达100倍加速比。
Capacity约束矩阵化评估：
计算总需求：对于每条路径，路径中所有客户的需求，可以通过累积来计算总需求：
检查是否超过最大载重：如果总需求超过了载重，进行超载量计算：
计算惩罚：如果路径超载，使用一个惩罚系数来计算超载惩罚，最终的超载惩罚为：
时间窗约束矩阵化评估:
累积距离：计算路径上各个客户点之间的累积距离：
计算时间窗约束违反：根据路径上的行驶距离，计算每个客户的到达时间，并与其时间窗约束进行比较。如果存在违反，计算最大延迟：
计算违反时间窗的惩罚：使用惩罚系数来计算时间窗违反的惩罚：
整体评估：
将载重和时间窗违反的矩阵传入NPU，进行批量处理和加速计算。首先，对所有路径进行累加，得出最终的成本矩阵：
对于所有路径，可以得到总的路径成本：
路径成本和距离矩阵累加得到最终成本：
路径总成本：在计算出所有路径的最终成本后，我们将所有路径的最终成本进行累加，得到总的路径成本：
昇腾矩阵算子的调用
昇腾矩阵算子的调用-续
关键技术点2：交叉运算与NPU加速SPP模型的结合
为了高效生成高质量的解决方案，该研究团队引入了两种先进的交叉算子：SREX（选择性随机边交换）和EAX（基于“边”的重组方法）。这两种算子通过对当前解进行策略性的破坏和重组，能够生成大量潜在的优质路径，显著提升了解的多样性和覆盖范围。然而，由于交叉算子的高效生成能力，传统方法评估这些新生成路径的计算代价过高，限制了此类交叉方法的实际应用。
该团队的创新之处在于将交叉运算与集合划分模型相结合，并充分利用昇腾NPU算力，显著提升了路径评估的效率，使得对大量路径的批量评估成为可能。具体而言，他们通过交叉算子生成大量多样化的新路径，并将其存储到路径池中，作为后续优化和选择的基础。引入了集合划分模型(SPP)来优化路径组合，确保最终得到的是一个更好地满足所有需求的路径集合，且将SPP问题的求解转化成矩阵运算，用NPU实现了高效求解。
SPP问题模型如下：
通过基于NPU快速求解上述模型，可以在每次迭代中得到高质量解集，保持解的多样性的同时显著提升了解的整体质量。
关键技术点3：多种群管理机制
在基于种群进化的启发式搜索方法中，为了避免算法早熟收敛到局部最优解，该研究一个重要的问题是如何保持迭代过程中种群的多样性。多样性种群能够不断地朝着不同的方向探索解空间的区域，从而提高找到全局最优解的可能性。值得注意的是，该团队对种群管理机制做了进一步的创新改进，包括以下技术思路：
多样种群机制：
•双种群进化策略:与传统进化算法不同，该团队在进化过程中维护了两个种群它们包含的初始解差异性较大，如果当前种群的多样性较差，或者较长时间无法搜索到更优解，会通过交换、杂交、重启等多个操作来提升种群的多样性。
•自适应参数调整:在算法的选代过程中自动调整参数，包括约束的惩罚系数、交叉算子权重等，以应对在搜索解空间的不同阶段对探索度和可行性的不同需求。
•个体选择策略:结合随机性和贪心策略，从多个随机个体中选择较优个体进行交叉操作，向更加有希望的方向进行探索，同时避免过于贪心导致陷入局部最优。
榜单链接: https://github.com/cssartori/pdptw-instances/tree/master
通过这一系列关键技术的结合，该研究团队在PDPTW问题上取得了显著的成果，不仅刷新了多个最佳解纪录，还为未来的研究和应用提供了新的思路和方法，该成果也近期会发表在业界期刊，敬请大家期待更多细节内容。
参考文献：
[1]Sartori C S, Buriol L S. A study on the pickup and delivery problem with time windows: Matheuristics and new instances[J]. Computers & Operations Research, 2020, 124: 105065.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
微信编辑：疑疑
关注我们
FOLLOW US
