有时间窗的车辆路径问题的近似算法研究

• 论文 •

有时间窗的车辆路径问题的近似算法研究

刘小兰，郝志峰，汪国强，符克强

华南理工大学应用数学系，广东广州510640

出版日期:2004-07-15 发布日期:2004-07-25

Improved large neighborhood search algorithm for vehicle routing problem with time windows

LIU Xiao-lan, HAO Zhi-feng, WANG Guo-qiang, FU Ke-qiang

Dep.of Applied Mathematics, South China Univ.of Tech., Guangzhou510640, China

Online:2004-07-15 Published:2004-07-25

摘要/Abstract

摘要： 为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽的车辆路径问题的缺陷，介绍了有时间窗的车辆路径问题（VRPTW）的通用数学模型。通过分析各主要变量之间的关系，构造了一种简单、快速的确定性初始算法。通过引入“短路径优先策略”，构造了一种改进的大规模邻域搜索算法，该策略也可嵌入到求解时间窗比较窄的车辆路径问题中，达到加速搜索的目的。试验结果表明，改进的算法可以在较短的时间内有效地求得VRPTW 的优化解，是求解VRPTW的一个较好方案。

关键词: 有时间窗的车辆路径问题, 大规模邻域搜索算法, 初始算法

Abstract: The vehicle routing problem with time windows (VRPTW) cannot be solved effectively by using the existing Large Neighborhood Search (LNS) algorithm. A universal mathematical model of VRPTW was built. By analyzing the relation of several main variables, a simple, fast deterministic initial algorithm was proposed. An improved LNS algorithm was put forward based on the shortest route priority strategy, which could solve the problems with long scheduling horizon effectively. The strategy could also be applied to solving the problems with short scheduling horizon to accelerate searching process. Experiment results show that the improved algorithm can find the optimal or near optimal solution to VRPTW in short time.

Key words: vehicle routing problem with time windows, large neighborhood search algorithm, initial algorithm

中图分类号:

TP29

刘小兰，郝志峰，汪国强，符克强. 有时间窗的车辆路径问题的近似算法研究[J]. .

LIU Xiao-lan, HAO Zhi-feng, WANG Guo-qiang, FU Ke-qiang. Improved large neighborhood search algorithm for vehicle routing problem with time windows[J]. .

参考文献

[1]DANTZIG G, RAMSER J. The truck dispatching problem[J]. Management Science, 1959, 10（6）:80-91.

[2]SAVELSBERG M W P. Local search for routing problem with time windows[J]. Ann. of Operations Research, 1985, 16（4）:285-305.

[3]SHAW P. Using constraint programming and local search methods to solve vehicle routing problems[A]. Principles of the Fourth International Conference on Principles and Practice of Constraint Programming［C］.1998.417-431.

[4]LARSEN J. Parallelization of the vehicle routing problem with time windows[D]. Denmark:Technical University of Denmark, 1999.

[5]ZHANG Liping, CHAI Yueting, CAO Rui. Improved genetic algorithm for vehicle routing problem with time windows[J]．Computer Integrated Manufacturing Systems, 2002, 8（6）:451-454（in Chinese）.[张丽萍，柴跃廷，曹瑞．有时间窗车辆路径问题的改进遗传算法[J]．计算机集成制造系统，2002，8(6)：451－454.]

[6]CLARKE G,WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research ,1964, 12:568-581.

[7]BENT R,HENTENRYCK Van P. A two-stage hybrid local search for the vehicle routing problem with time windows[R]. U S A:Brown University, 2001.

[8]XIE Zheng, LI Jianping. Network algorithm and complexity theory[M]. Changsha:National University of Defence Technology Publish House,1995（in Chinese）.[谢政，李建平.网络算法与复杂性理论[M].长沙：国防科技大学出版社，1995.]

[9]LI Bangyi, YAO Enyu. The constrained minimum spanning tree problem:complexity and estimationof the bound[J]. Journal of Zhejiang of University（Sciences Edition）, 2000, 27（3）: 237-242（in Chinese）.[李帮义，姚恩瑜．约束最小支撑树（C－MST）问题：复杂性和上下界估计[J]．浙江大学学报(理学版)，2000，27(3)：237-242.]

[10]HARVEY W D,GINSBERG M L. Limited discrepancy search[A].Proceedings of the 14th International Joint Conference on Artificial Intelligence［C］.1995.