一类动态车辆路径问题模型和两阶段算法

交通运输系统工程与信息 ›› 2015, Vol. 15 ›› Issue (1): 159-166.

一类动态车辆路径问题模型和两阶段算法

饶卫振^*1，金淳²，刘锋³，杨磊¹

1. 山东科技大学经济管理学院，山东青岛266590；2. 大连理工大学系统工程研究所，辽宁，大连116024； 3. 东北财经大学管理科学与工学院，辽宁，大连116025

收稿日期:2014-08-08 修回日期:2014-09-23 出版日期:2015-02-25 发布日期:2016-02-25
作者简介:饶卫振（1981-），男，江西丰城人，讲师.
基金资助:
国家自然科学基金（71271041）；山东省优秀中青年科学家科研奖励基金（BS2014SF001）；山东科技大学人才引进基金（RCJJ2013020）；山东省软科学研究计划项目（2014RKB01506 ）.

Model and Two-stage Algorithm on Dynamic Vehicle Routing Problem

RAOWei-zhen¹，JIN Chun²，LIU Feng³，YANG Lei¹

1. College of Economics and Management, Shandong University of Science and Technology, Qingdao 266590, Shandong, China; 2. Institute of Systems and Engineering, Dalian University of Technology, Dalian 116024, Liaoning, China; 3. College of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian 116025, Liaoning, China

Received:2014-08-08 Revised:2014-09-23 Online:2015-02-25 Published:2016-02-25

摘要/Abstract

摘要：

针对一类动态车辆路径问题，分析4 种主要类型动态信息对传统车辆路径问题的本质影响，将动态车辆路径问题(Dynamic Vehicle Routing Problem, DVRP)转化为多个静态的多车型开放式车辆路径问题(The Fleet Size and Mixed Open Vehicle Routing Problem, FSMOVRP)，并进一步转化为多个带能力约束车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)，基于CVRP模型建立了DVRP模型；然后，在分析DVRP 问题特点基础上，提出两阶段算法，第一阶段基于利用K-d trees 对配送区域进行分割的策略，提出了复杂度仅为O(nlogn)的快速构建型算法，第二阶段通过分析算法搜索解空间结构原理，设计混合局部搜索算法；最后，基于现有12 个大规模CVRP标准算例，设计并求解36个DVRP算例.求解结果表明了模型和两阶段算法的有效性.

关键词: 物流工程, 两阶段算法, 动态车辆路径问题, K-d树分割策略, 算法搜索解空间

Abstract:

In order to effectively solve dynamic vehicle routing problem (DVRP), this paper analyzes the substantial effect of four main categories of dynamic information on classical vehicle routing problem, and transform DVRP into multiple static fleet size and mixed open vehicle routing problems (FSMOVRP). And FSMOVRP could be further converted to multiple capacitated vehicle routing problems (CVRP). The model based on CVRP is built up for DVRP. After that a two-stage algorithm is proposed to solve DVRP model according to the analysis of DVRP characteristics. In the first stage, a fast construction algorithm with merely O(nlogn) complexity is proposed on the basis of delivery region cutting strategy by K-d trees method. In the second stage, a hybrid local search algorithm is designed by analysis of structural principal of algorithm’s solution searching space. Finally for the purpose of algorithm verification, we design and solve 36 DVRP instances generated from 12 large scale CVRP benchmark instances. The results demonstrate the effectiveness of the model and two-stage solving algorithm.

Key words: logistics engineering, two- stage algorithm, DVRP, K- d trees, algorithm searching solution space

中图分类号:

U491

饶卫振，金淳，刘锋，杨磊. 一类动态车辆路径问题模型和两阶段算法[J]. 交通运输系统工程与信息, 2015, 15(1): 159-166.

RAOWei-zhen，JIN Chun，LIU Feng，YANG Lei. Model and Two-stage Algorithm on Dynamic Vehicle Routing Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(1): 159-166.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18939.shtml

http://www.tseit.org.cn/CN/Y2015/V15/I1/159

参考文献

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.

[2] Psaraftis H N. Dynamic vehicle routing problems[M]. North-Holland: Elsevier, 1988.

[3] Psaraftis H N. Dynamic vehicle routing: Status and prospects[J]. Annal of Operations Research, 1995, 61 (1): 143-164.

[4] Pillac V, Gendreau M, Guéret C, et al. A review of dynamic vehicle routing problems[J]. European Journal of Operational Research, 2013, 225(1): 1-11.

[5] Larsen A. The dynamic vehicle routing problem[D]. Technical University of Denmark, 2001.

[6] Brotcorne L, Laporte G, Semet F. Ambulance location and relocation models[J]. European Journal of Operational Research, 2003, 147(3): 451-463.

[7] Taniguchi E, Shimamoto H. Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times[J]. Transportation Research Part C: Emerging Technologies, 2004, 12(3-4): 235- 250.

[8] Fleischmann B, Gnutzmann S, Sandvoss E. Dynamic vehicle routing based on online traffic information[J]. Transportation Science, 2004, 38(4): 420-433.

[9] Melachrinoudis E, Ilhan A B, Min H. A dial-a-ride problem for client transportation in a health-care organization[J]. Computers & Operations Research, 2007, 34(3): 742-759.

[10] Khouadjia M R, Sarasola B, Alba E, et al. A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests[J]. Applied Soft Computing, 2012, 12(4): 1426-1439.

[11] Ferrucci F, Bock S, Gendreau M. A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods[J]. European Journal of Operational Research, 2013, 225(1): 130- 141.

[12] Albareda-Sambola M, Fernández E, Laporte G. The dynamic multiperiod vehicle routing problem with probabilistic information[J]. Computers & Operations Research, 2014, 48(2): 31-39.

[13] Ghannadpour S F, Noori S, Tavakkoli-Moghaddam R, et al. A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application[J]. Applied Soft Computing, 2014, 14 (1): 504-527.

[14] 谢秉磊, 郭耀煌, 郭强. 动态车辆路径问题:现状与展望[J]. 系统工程理论方法应用, 2002, 11(2): 116-120. [XIE B L, GUO Y H, GUO Q. Dynamic vehicle routing problems: status and prospect[J]. Systems Engineering Theory Methodology Applications, 2002, 11(2): 116- 120.]

[15] 郭耀煌, 谢秉磊. 一类随机动态车辆路径问题的策略分析[J]. 管理工程学报, 2003, 17(4): 114-115. [GUO Y H, XIE B L. Policy analysis on a stochastic dynamic vehicle routing problem[J]. Journal of Industrial Engineering Engineering Management, 2003, 17(4): 114-115.]

[16] 郭耀煌, 钟小鹏. 动态车辆路径问题排队模型分析[J]. 管理科学学报, 2006, 9(1): 33-37. [GUO Y H, ZHONG X P. Analysis of the queuing model of dynamic vehicle routing problem[J]. Journal of Management Sciences in China, 2006, 9(1): 33-37.]

[17] 刘霞, 齐欢. 带时间窗的动态车辆路径问题的局部搜索算法[J]. 交通运输工程学报, 2008, 8(5): 114-120. [LIU X, QI H. Local search algorithm of dynamic vehicle routing problem with time window[J]. Journal of Traffic and Transportation Engineering, 2008, 8(5): 114- 120.]

[18] Hong L X. An improved LNS algorithm for real- time vehicle routing problem with time windows[J]. Computers & Operations Research, 2012, 39(2): 151- 163.

[19] 陈久梅, 张旭梅, 肖剑, 等. 随机动态装卸混合问题的分区求解策略[J]. 管理科学学报, 2012, 15(1): 43-53. [CHEN J M, ZHANG X M, XIAO J，et al. Region partitioning policy for stochastic dynamic pick-up and delivery problem[J]. Journal of Management Sciences in China, 2012, 15(1): 43-53.]

[20] 葛显龙, 王旭, 邓蕾. 基于联合配送的开放式动态车辆路径问题及算法研究[J]. 管理工程学报, 2013, 27 (03): 60-68. [GE X L, WANG X, DENG L. Research on open and dynamic vehicle routing problems based on joint distribution[J]. Journal of Industrial Engineering Management, 2013, 27(03): 60-68.]

[21] Bentley J L. K-d trees for semidynamic point sets[C]// Proc. 6th Ann． ACM Symp on Computational Geometry, 1990: 187-197.

[22] 饶卫振, 金淳. 求解大规模CVRP问题的快速贪婪算法[J]. 管理工程学报, 2014, 28(02): 45-54. [RAO W Z, JIN C. An efficient greedy heuristic for solving largescale capacitated vehicle routing problem[J]. Journal of Industrial Engineering Management, 2014, 28(02): 45- 54.]

[23] Rao W Z, Jin C. A method for analyzing solution space of traveling salesman problem based on complex network[J]. International Journal of Innovative Computing Information and Control, 2013, 9(9): 3685- 3700.

[24] Costa L D, Oliveira O N, Travieso G, et al. Analyzing and modeling real-world phenomena with complex networks: A survey of applications[J]. Advances in Physics, 2011, 60(3): 329-412.

[25] Li F Y, Golden B, Wasil E. Very large- scale vehicle routing: New test problems, algorithms, and results[J]. Computers & Operations Research, 2005, 32(5): 1165- 1179. 166