物流配送中的车辆路径优化问题研究
|
摘要
物流配送是物流活动中直接与消费者相连的重要环节。在物流的各项成本中,配送成本占了相当高的比例。运输线路是否合理直接影响着配送速度、成本和效益。随着商品运输呈现小批量、多品种、多频次、及时性等趋势,多用户运输路径的确定更为复杂。因此,车辆路径优化问题成为研究者们竞相研究的热门话题。
本文首先分析了车辆路径优化问题的研究现状,介绍了车辆路径优化问题的基本概念和车辆路径优化问题的分类及优化方法,使得对车辆路径优化问题有了整体认识。对带时间窗的车辆路径优化问题进行了数学建模,明确了问题的目标函数及约束条件,在比较多种方法之后采用遗传算法,采用扫描法生成问题的一个初始解,然后用遗传算法对初始解进行优化,得到了最优解或近似最优解。针对研究问题的特点,在遗传算法优化初始解的过程中,设计了遗传编码、适应度函数以及遗传操作策略。借助于MATLAB软件实现该算法,并通过实例证明了该算法是求解车辆路径优化问题的一个较好方案。计算结果表明了遗传算法解决此类问题的有效性。
Logistics distribution is an important link with consumer directly, and takes account for considerable proportion in variable costs in logistics. The planning of vehicle routing in distribution will take great effect on the efficiency, cost and benefit. With a new trend of more kinds, less batch, high frequency and time restriction in materials distribution, the optimizations of the delivery route for multi consumers become more and more complicated. So, vehicle routing problem had become focus of many scholars to study.
This paper gives a review of the past researches on vehicle routing problems and their solution methods. First, we introduce the concept of vehicle routing problems, classify vehicle routing problems and optimized methods, which make us understand the whole vehicle routing problems. Meanwhile, we construct a mathematical model, define an objective function and constraint mathematically then solve it based on Genetic Algorithms. An initial solution is constructed by the Sweep Algorithms. Then GA is used to improve it to acquire a best or better solution. We propose coding strategy, fitness function and three genetic operations when using GA. Finally, this method is implemented on computer with MATLAB. GA in this paper can obtain an optimized solution effectively and has been proved to be a good scheme to solve vehicle routing problems.
本文首先分析了车辆路径优化问题的研究现状,介绍了车辆路径优化问题的基本概念和车辆路径优化问题的分类及优化方法,使得对车辆路径优化问题有了整体认识。对带时间窗的车辆路径优化问题进行了数学建模,明确了问题的目标函数及约束条件,在比较多种方法之后采用遗传算法,采用扫描法生成问题的一个初始解,然后用遗传算法对初始解进行优化,得到了最优解或近似最优解。针对研究问题的特点,在遗传算法优化初始解的过程中,设计了遗传编码、适应度函数以及遗传操作策略。借助于MATLAB软件实现该算法,并通过实例证明了该算法是求解车辆路径优化问题的一个较好方案。计算结果表明了遗传算法解决此类问题的有效性。
Logistics distribution is an important link with consumer directly, and takes account for considerable proportion in variable costs in logistics. The planning of vehicle routing in distribution will take great effect on the efficiency, cost and benefit. With a new trend of more kinds, less batch, high frequency and time restriction in materials distribution, the optimizations of the delivery route for multi consumers become more and more complicated. So, vehicle routing problem had become focus of many scholars to study.
This paper gives a review of the past researches on vehicle routing problems and their solution methods. First, we introduce the concept of vehicle routing problems, classify vehicle routing problems and optimized methods, which make us understand the whole vehicle routing problems. Meanwhile, we construct a mathematical model, define an objective function and constraint mathematically then solve it based on Genetic Algorithms. An initial solution is constructed by the Sweep Algorithms. Then GA is used to improve it to acquire a best or better solution. We propose coding strategy, fitness function and three genetic operations when using GA. Finally, this method is implemented on computer with MATLAB. GA in this paper can obtain an optimized solution effectively and has been proved to be a good scheme to solve vehicle routing problems.
引文
1王惠.引入顾客满意度求解车辆优化调度问题.大连海事大学硕士论文. 2006:1~13
2赵鲁华.城市配送中心车辆调度优化研究.吉林大学硕士论文. 2005:37~52
3 Fisher M L. Vehicle routing problem with time windows. Two optimization algorithms [J]. Operations Research. 1997, 45(3):488~492
4刘敏.多目标遗传算法在车辆路径优化中的应用研究.湘潭大学硕士论文. 2006:1~9
5 Balinski M, Quand R. On an integer program for a delivery problem [J]. Operations Research. 1962, (12):300~304
6 Eilon S, Watson-Gandy CDT, Christofides N. Distribution management: mathematical modeling and practical analysis [M]. 1971:357~361
7 Gillett B, Miller L. A heuristic algorithm for the vehicle dispatch problem [J]. Operations Research. 1974, (22):340~349
8 Christofides N, Mingozzi A, Toth P. Exact algorithms for the vehicle routing problem, based on spanning the shortest path relaxation [J]. Mathematical programming. 1981, (20):255~282
9 Kohl. N, O. B. G. Madsen. An Optimization Algorithm for the Vehicle Routing with Time Windows based on Lagrangrian Relaxation. Operations Research. 1997, (45):395~406.
10 Taillard E, P. Badeau, M. Gendreau, F. Guertin et al. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science. 1997, (2):170~186
11 Solomon M, De_srosiers J. Time Window Constrained Routing and Scheduling Problems: A Survey [J]. Transportation Science. 1988, 22(1):1~11
12覃俊,蓝雯飞,兰华荣.用遗传算法求解旅行商问题.中南民族学院学报(自然版). 2000, (1):25~28.
13马良,旅行销售员问题的算法综述.数学的实践与认识. 2000, (2):156~165
14汪林林.对“货郎担问题”的研究.重庆邮电学院学报. 1999, (2):5~8
15张涛,王梦光.遗传算法和3-OPT结合求解带有能力约束的VRP [J].东北大学学报(自然科学版). 1999, 20(3):253~256
16李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径问题上的应用.系统工程理论与实践. 1999:65~69
17冷德惠,张金海,李大卫.遗传算法在有时间窗车辆路径问题上的应用.鞍山钢铁学院学报. 1999, 22(3):129~132
18李军.有时间窗的车辆路线安排问题的启发式算法[J].系统工程. 1996, 14(5):40~50
19李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践. 2004, (4):130~135
20程卫国,冯峰,姚东,徐昕. MATLAB应用指南.人民邮电出版社. 1999:410~463
21方霞等.基于免疫遗传算法的物流配送车辆路径优化问题研究[J].土木工程学报. 2003, 36(7):43~46
22尚华艳.物流配送中车辆路径问题研究.武汉理工大学大学硕士论文. 2005:10~40
23 Thangiah S R. Vehicle routing problem with time windows using genetic algorithms [A]. Application Handbook of Genetic Algorithms: New Frontiers (Volume H) [C]. Boca Raton CRC Press. 1995:253~277
24 Braysy, O. A new algorithm for the vehicle routing problem with time windows based on the hybridization of a genetic algorithm and route construction heuristics. Varian yliopiston julkaisuja. Tutkimuksia. 1999, 227:33~44
25 Jean Berger, Mohamed Barkaoui. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows [J]. Computers & Operations Research. 2004, 31(12):2037~2053.
26 Tan K C, Lee L H, Zhu Q L, et al. Heuristic methods for vehicle routing problem with time windows [J]. Artificial Intelligence in Engineering. 2001:281~295
27熊英.有时间窗的车辆路径问题仿真模型研究.大连理工大学硕士论文. 2006:2~12
28张丽萍,柴跃进,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统. 2002, 8(6):451~454
29张丽萍,柴跃进.车辆路径问题的改进遗传算法.系统工程理论与实践. 2002, (8):79~84
30李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践. 2004, (4):130~135
31宾松,符卓.求解带软时间窗的车辆路径问题的改进遗传算法[J].系统工程. 2003, 21(6):12~15
32袁庆达,杜文,周再玲.带软时间窗的混合车队车辆路线问题的模型和算法研究[J].西南交通大学学报. 2001, 36(4):401~406
33占书芳.并行遗传算法在带软时间窗车辆路径中的应用研究.武汉理工大学硕士论文. 2006:8~57
34 S. C. Ho, D. Haugland. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries [J]. Computers & Operations Research. 2004, 31(12):1947~1964.
35杨瑞陈.有时间窗和在前约束车辆路径问题的蚁群算法.西安建筑科技大学硕士论文. 2005:2~10
36 Braysy O, Hasle G, Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows [J]. European Journal of Operational Research. 2004, 159(3):586~605.
37 Brian Kallehauge, Jesper Larsen, Oli B.G.. Madsen. Lagrangian duality applied to the vehicle routing problem with time windows [J]. Computers & Operations Research. 2006, 33:1464~1487.
38 Giselher Pankratz. A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows. European Journal of Operational Research [J]. 2005, (27):21~41
39张翠军,刘坤起,刘永军.求解一般车辆优化调度问题的一种改进遗传算法.计算机工程与应用. 2004, (33):207~211
40 Holland J H. Adaptations in Natural and Artificial Systems [M]. University of Michigan press. Ann Arbor. 1976:256~262
41 Robert A, Russell, Wen_Chvuan. Chiang. Scatter search for the vehicle routing problem with time windows [J]. European Journal of Operational Research. 2006, 169(2):606~622.
42 David Pisinger, Stefan Ropke. A general heuristic for vehicle routing problems. Computers & Operations Research. 2005:24~26
43张文修,梁怡.遗传算法的数学基础.西安交通大学出版社. 2000:3~20
44盛丽俊.带有时间窗的车辆路径问题的优化研究.大连海事大学硕士论文. 2002:13~57
45牟燕妮.物流配送中路径优化的选择研究.沈阳工业大学硕士论文.2006:28~41
46周明,孙树栋.遗传算法原理及应用.国防工业出版社. 1999:130~137
47张先君.不确定运输问题的模型与算法.重庆大学硕士论文. 2006:1~8
48李勇.供应链中分销配送优化模型及其算法研究.重庆大学博士论文. 2005:55~87
49冯萍.退火遗传算法在运输路线规划中的应用.西安交通大学硕士论文. 2000:24~36
50 C. D. Tarantilis, C. T. Kiranoudis. A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of Food Engineering. Department of Chemical Engineering. National Technical University of Athens. Greece, 2001, 50(6):1~9
51邹彤,李宁,孙德宝.不确定车辆数的有时间窗的车辆路径问题的遗传算法.系统工程理论与实践. 2004, (6):134~138
52周森.基于遗传算法的物流运输中的车辆路径问题研究.对外经贸大学硕士论文. 2006:24~28
53王美琼.遗传算法在物流配送路径规划问题中的应用.南京理工大学硕士论文. 2006:33~40
54 Shabayek A A, Yeung W W. A Simulation Model for the Kwai Chung Container Terminals in Hong Kong. European Journal of Operational Research. 2002, 140(1):1~11
55玄光男,程润伟.遗传算法与工程优化.清华大学出版社. 2004:23
2赵鲁华.城市配送中心车辆调度优化研究.吉林大学硕士论文. 2005:37~52
3 Fisher M L. Vehicle routing problem with time windows. Two optimization algorithms [J]. Operations Research. 1997, 45(3):488~492
4刘敏.多目标遗传算法在车辆路径优化中的应用研究.湘潭大学硕士论文. 2006:1~9
5 Balinski M, Quand R. On an integer program for a delivery problem [J]. Operations Research. 1962, (12):300~304
6 Eilon S, Watson-Gandy CDT, Christofides N. Distribution management: mathematical modeling and practical analysis [M]. 1971:357~361
7 Gillett B, Miller L. A heuristic algorithm for the vehicle dispatch problem [J]. Operations Research. 1974, (22):340~349
8 Christofides N, Mingozzi A, Toth P. Exact algorithms for the vehicle routing problem, based on spanning the shortest path relaxation [J]. Mathematical programming. 1981, (20):255~282
9 Kohl. N, O. B. G. Madsen. An Optimization Algorithm for the Vehicle Routing with Time Windows based on Lagrangrian Relaxation. Operations Research. 1997, (45):395~406.
10 Taillard E, P. Badeau, M. Gendreau, F. Guertin et al. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science. 1997, (2):170~186
11 Solomon M, De_srosiers J. Time Window Constrained Routing and Scheduling Problems: A Survey [J]. Transportation Science. 1988, 22(1):1~11
12覃俊,蓝雯飞,兰华荣.用遗传算法求解旅行商问题.中南民族学院学报(自然版). 2000, (1):25~28.
13马良,旅行销售员问题的算法综述.数学的实践与认识. 2000, (2):156~165
14汪林林.对“货郎担问题”的研究.重庆邮电学院学报. 1999, (2):5~8
15张涛,王梦光.遗传算法和3-OPT结合求解带有能力约束的VRP [J].东北大学学报(自然科学版). 1999, 20(3):253~256
16李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径问题上的应用.系统工程理论与实践. 1999:65~69
17冷德惠,张金海,李大卫.遗传算法在有时间窗车辆路径问题上的应用.鞍山钢铁学院学报. 1999, 22(3):129~132
18李军.有时间窗的车辆路线安排问题的启发式算法[J].系统工程. 1996, 14(5):40~50
19李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践. 2004, (4):130~135
20程卫国,冯峰,姚东,徐昕. MATLAB应用指南.人民邮电出版社. 1999:410~463
21方霞等.基于免疫遗传算法的物流配送车辆路径优化问题研究[J].土木工程学报. 2003, 36(7):43~46
22尚华艳.物流配送中车辆路径问题研究.武汉理工大学大学硕士论文. 2005:10~40
23 Thangiah S R. Vehicle routing problem with time windows using genetic algorithms [A]. Application Handbook of Genetic Algorithms: New Frontiers (Volume H) [C]. Boca Raton CRC Press. 1995:253~277
24 Braysy, O. A new algorithm for the vehicle routing problem with time windows based on the hybridization of a genetic algorithm and route construction heuristics. Varian yliopiston julkaisuja. Tutkimuksia. 1999, 227:33~44
25 Jean Berger, Mohamed Barkaoui. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows [J]. Computers & Operations Research. 2004, 31(12):2037~2053.
26 Tan K C, Lee L H, Zhu Q L, et al. Heuristic methods for vehicle routing problem with time windows [J]. Artificial Intelligence in Engineering. 2001:281~295
27熊英.有时间窗的车辆路径问题仿真模型研究.大连理工大学硕士论文. 2006:2~12
28张丽萍,柴跃进,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统. 2002, 8(6):451~454
29张丽萍,柴跃进.车辆路径问题的改进遗传算法.系统工程理论与实践. 2002, (8):79~84
30李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践. 2004, (4):130~135
31宾松,符卓.求解带软时间窗的车辆路径问题的改进遗传算法[J].系统工程. 2003, 21(6):12~15
32袁庆达,杜文,周再玲.带软时间窗的混合车队车辆路线问题的模型和算法研究[J].西南交通大学学报. 2001, 36(4):401~406
33占书芳.并行遗传算法在带软时间窗车辆路径中的应用研究.武汉理工大学硕士论文. 2006:8~57
34 S. C. Ho, D. Haugland. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries [J]. Computers & Operations Research. 2004, 31(12):1947~1964.
35杨瑞陈.有时间窗和在前约束车辆路径问题的蚁群算法.西安建筑科技大学硕士论文. 2005:2~10
36 Braysy O, Hasle G, Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows [J]. European Journal of Operational Research. 2004, 159(3):586~605.
37 Brian Kallehauge, Jesper Larsen, Oli B.G.. Madsen. Lagrangian duality applied to the vehicle routing problem with time windows [J]. Computers & Operations Research. 2006, 33:1464~1487.
38 Giselher Pankratz. A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows. European Journal of Operational Research [J]. 2005, (27):21~41
39张翠军,刘坤起,刘永军.求解一般车辆优化调度问题的一种改进遗传算法.计算机工程与应用. 2004, (33):207~211
40 Holland J H. Adaptations in Natural and Artificial Systems [M]. University of Michigan press. Ann Arbor. 1976:256~262
41 Robert A, Russell, Wen_Chvuan. Chiang. Scatter search for the vehicle routing problem with time windows [J]. European Journal of Operational Research. 2006, 169(2):606~622.
42 David Pisinger, Stefan Ropke. A general heuristic for vehicle routing problems. Computers & Operations Research. 2005:24~26
43张文修,梁怡.遗传算法的数学基础.西安交通大学出版社. 2000:3~20
44盛丽俊.带有时间窗的车辆路径问题的优化研究.大连海事大学硕士论文. 2002:13~57
45牟燕妮.物流配送中路径优化的选择研究.沈阳工业大学硕士论文.2006:28~41
46周明,孙树栋.遗传算法原理及应用.国防工业出版社. 1999:130~137
47张先君.不确定运输问题的模型与算法.重庆大学硕士论文. 2006:1~8
48李勇.供应链中分销配送优化模型及其算法研究.重庆大学博士论文. 2005:55~87
49冯萍.退火遗传算法在运输路线规划中的应用.西安交通大学硕士论文. 2000:24~36
50 C. D. Tarantilis, C. T. Kiranoudis. A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of Food Engineering. Department of Chemical Engineering. National Technical University of Athens. Greece, 2001, 50(6):1~9
51邹彤,李宁,孙德宝.不确定车辆数的有时间窗的车辆路径问题的遗传算法.系统工程理论与实践. 2004, (6):134~138
52周森.基于遗传算法的物流运输中的车辆路径问题研究.对外经贸大学硕士论文. 2006:24~28
53王美琼.遗传算法在物流配送路径规划问题中的应用.南京理工大学硕士论文. 2006:33~40
54 Shabayek A A, Yeung W W. A Simulation Model for the Kwai Chung Container Terminals in Hong Kong. European Journal of Operational Research. 2002, 140(1):1~11
55玄光男,程润伟.遗传算法与工程优化.清华大学出版社. 2004:23