车辆路径问题
计算机科学
多路径等成本路由
静态路由
链路状态路由协议
最短路径问题
目的地顺序距离矢量路由
数学优化
布线(电子设计自动化)
图形
算法
数学
理论计算机科学
计算机网络
路由协议
作者
Ruslan Sadykov,Eduardo Uchoa,Artur Alves Pessoa
出处
期刊:Transportation Science
[Institute for Operations Research and the Management Sciences]
日期:2020-10-05
卷期号:55 (1): 4-28
被引量:60
标识
DOI:10.1287/trsc.2020.0985
摘要
We consider the shortest path problem with resource constraints arising as a subproblem in state-of-the-art branch-cut-and-price algorithms for vehicle routing problems. We propose a variant of the bidirectional label-correcting algorithm in which the labels are stored and extended according to the so-called bucket graph. This organization of labels helps to significantly decrease the number of dominance checks and the running time of the algorithm. We also show how the forward/backward route symmetry can be exploited and how to eliminate arcs from the bucket graph using reduced costs. The proposed algorithm can be especially beneficial for vehicle routing instances with large vehicle capacity and/or with time window constraints. Computational experiments were performed on instances from the distance-constrained vehicle routing problem, including multidepot and site-dependent variants, on the vehicle routing problem with time windows, and on the “nightmare” instances of the heterogeneous fleet vehicle routing problem. Significant improvements over the best algorithms in the literature were achieved, and many instances could be solved for the first time.
科研通智能强力驱动
Strongly Powered by AbleSci AI