|本期目录/Table of Contents|

[1]孟庆欣,韩曙光.距离受限车辆路径问题的近似算法[J].浙江理工大学学报,2022,47-48(自科二):273-282.
　MENG Qingxin,HAN Shuguang.The approximation algorithm for distance constrained vehicle routing problem[J].Journal of Zhejiang Sci-Tech University,2022,47-48(自科二):273-282.
点击复制

距离受限车辆路径问题的近似算法()
分享到：

浙江理工大学学报[ISSN:1673-3851/CN:33-1338/TS]

卷:
第47-48卷
期数:
2022年自科第二期
页码:
273-282
栏目:
出版日期:
2022-03-10

文章信息/Info

Title:
The approximation algorithm for distance constrained vehicle routing problem
文章编号:
1673-3851 (2022) 03-0273-10
作者:
孟庆欣; 韩曙光
浙江理工大学理学院，杭州 310018
Author(s):
MENG Qingxin;  HAN Shuguang
School of Science, Zhejiang Sci-Tech University, Hangzhou 310018, China
关键词:
车辆路径问题; 距离受限; 近似算法; 环游拆分; 环游整合
分类号:
O223
文献标志码:
A
摘要:
针对无向完全图上以极小化行驶路线（环游）总距离为目标函数的距离受限车辆路径问题，将最小二元2 匹配问题与环游拆分和环游整合相结合，提出了一种近似算法。该算法将松弛问题最小二元2 匹配的最优解中距离超过限制的环游进行拆分，距离未超过限制的环游进行整合，以得到距离受限车辆路径问题的环游集合。针对该近似算法，首先通过分析该问题最优解下界与近似算法的上界，证明了算法参数形式的近似比上界；然后通过对近似比上界的证明，说明最大行驶距离与顾客点规模的取值对算法参数近似比的影响较小；最后通过构造实例，进一步说明该算法在此种情况下性能更优。该算法可为城市无人物流配送高效快速算法的设计提供思路参考。

参考文献/References:

［1］ Konstantakopoulos G D, Gayialis S P, Kechagias E P. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational Research, 2020. (2020-09-09)［2021-07-15］.
［2］ Yadav U, Sharma S K, Routroy S. Vehicle routing problem: recent literature review of its variants. International Journal of Operational Research, 2018, 33(1): 1-31［2021-07-15］.
［3］ Dantzig G B, Ramser J H. The truck dispatching problem［J］. Management Science, 1959, 6(1): 80-91.
［4］ Amous M, Toumi S, Jarboui B, et al. A variable neighborhood search algorithm for the capacitated vehicle routing problem［J］. Electronic Notes in Discrete Mathematics, 2017, 58: 231-238.
［5］ Yu W, Liu Z H, Bao X G. Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity. Journal of Combinatorial Optimization, 2020, 5: 1-18［2021-07-15］.
［6］ Papadimitriou C H. The Euclidean travelling salesman problem is NPcomplete［J］. Theoretical Computer Science, 1977, 4(3): 237-244.
［7］ Haimovich M, Rinnooy Kan A H G. Bounds and heuristics for capacitated routing problems［J］. Mathematics of Operations Research, 1985, 10(4): 527-542.
［8］ Khachay M, Ogorodnikov Y. Polynomial capacity guarantees PTAS for the euclidean capacitated vehicle routing problem even for nonuniform nonsplittable demand［C］//International Conference on Optimization and Applications, 2019. Cham: Springer International Publishing, 2020, 1145: 415-426.
［9］ Becker A. A tight 4/3 approximation for capacitated vehicle routing in trees. (2018-08-25) ［2021-07-15］.
［10］ Lenstra J K, Kan A H G R. Complexity of vehicle routing and scheduling problems［J］. Networks, 2010, 11(2): 221-227.

备注/Memo

备注/Memo:
收稿日期： 2021-07-15
网络出版日期： 2021-11-08
基金项目：国家自然科学基金项目(12071436)
作者简介：孟庆欣 (1996-)，女，内蒙古赤峰人，硕士研究生，主要从事组合优化和路径规划方面的研究
通信作者：韩曙光，E-mail：zist001@163.com
更新日期/Last Update: 2022-03-09