动态车辆配送优化调度问题的两阶段算法

交通运输系统工程与信息 ›› 2009, Vol. 9 ›› Issue (4): 140-144 .

动态车辆配送优化调度问题的两阶段算法

郎茂祥^*

北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京 100044

收稿日期:2008-12-22 修回日期:2009-04-07 出版日期:2009-08-25 发布日期:2009-08-25
通讯作者: 郎茂祥
作者简介:郎茂祥（1969-），男，山东省高唐县人，教授，博士生导师.
基金资助:
国家自然科学基金项目（60870014）；科技部“国家攻关”项目（2006BAJ07b03）

Two-Phase Algorithm for Dynamic Distribution Vehicle Schedulinging Problem

LANG Mao-xiang

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Received:2008-12-22 Revised:2009-04-07 Online:2009-08-25 Published:2009-08-25
Contact: LANG Mao-xiang

摘要/Abstract

摘要： 研究了动态车辆配送优化调度问题的高效求解算法。在分析配送车辆调度中造成车辆动态性的原因的基础上，提出了一种考虑车辆故障和车辆多次巡回配送的动态车辆配送优化调度问题。在对该问题进行描述的基础上，制定了求解该问题的两阶段策略：第一阶段制定整体优化计划；第二阶段进行实时局部优化调度。设计和实现了求解该问题的两阶段算法：第一阶段采用禁忌搜索算法制定优化的配送计划；第二阶段采用局部搜索算法实时进行优化调度。既充分利用了禁忌搜索算法全局搜索能力强的优势，又充分利用局部搜索算法收敛速度快的优势。最后，通过实验计算验证了算法的良好的性能。

关键词: 配送, 车辆路径问题, 动态车辆调度问题, 禁忌搜索算法, 局部搜索算法

Abstract: The effective solving algorithm for dynamic distribution vehicle scheduling problem is studied. On the basis of analyzing the dynamic factors of vehicles in physical distribution, the paper proposed a new dynamic distribution vehicle scheduling problem considering vehicles’ malfunction and multi-circular distribution. With describing this problem briefly, a two-phase solving strategy is put forward, namely, the first phase for making optimal distribution plan and the second phase for real time optimal scheduling. Then a two-phase algorithm for the problem is designed and implemented. The tabu search algorithm is used in the first phase and the local search algorithm is used in the second phase. In this way, the powerful global searching ability of tabu search algorithm and the high convergence speed of the local search algorithm are fully utilized. The effectiveness of this algorithm is finally demonstrated by experimental computations.

Key words: physical distribution, vehicle routing problem, dynamic vehicle scheduling problem, tabu search algorithm, local search algorithm

中图分类号:

TP391

郎茂祥. 动态车辆配送优化调度问题的两阶段算法[J]. 交通运输系统工程与信息, 2009, 9(4): 140-144 .

LANG Mao-xiang. Two-Phase Algorithm for Dynamic Distribution Vehicle Schedulinging Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2009, 9(4): 140-144 .

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

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

http://www.tseit.org.cn/CN/Y2009/V9/I4/140

参考文献

[1] 谢秉磊, 郭耀煌, 郭强. 动态车辆路径问题：现状与展望[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]

[2] Christiansen C H, Lysgaard J. A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[J]. Operations Research Letters, 2007, 35 (6), 773 – 781.

[3] Haugland D, Ho S C, Laporte G. Designing delivery districts for the vehicle routing problem with stochastic demands[J]. European Journal of Operational Research, 2007, 180 (3), 997–1010.

[4] Tan K C, Cheong C Y, Goh C K. Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation[J]. European Journal of Operational Research, 2007, 177 (2) , 813–839.

[5] Fabri A, Recht P. On dynamic pickup and delivery vehicle routing with several time windows and waiting times[J]. Transportation Research Part B, 2006, 40 (4), 335-350.

[6] 陈保文, 宋申民, 陈兴林. 随机需求车辆路径问题及其启发式算法[J]. 计算机工程与设计, 2007, 28(1), 138-148. [CHEN B W, SONG S M, CHEN X L. Vehicle routing problem with stochastic demands and its modify ant colony system[J]. Computer Engineering and Design, 2007, 28(1), 138-148]

[7] Haghani A, Jung S. A dynamic vehicle routing problem with time-dependent travel times[J]. Computers & Operations Research, 2005, 32 (11), 2959–2986.

[8] Potvin J Y, Xu Y, Benyahia I. Vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research, 2006, 33 (4), 1129–1137.

[9] Hashimoto H, Yagiura M, Ibaraki T. An iterated local search algorithm for the time-dependent vehicle routing problem with time windows[J]. Discrete Optimization, 2008, 5 (2), 434-456.

[10] 肖增敏, 李军. 动态网络车辆路径问题：研究现状及展望[J]. 系统工程, 2004, 22(7), 68-71. [XIAO Z M，LI J. Vehicle routing problem in dynamic networks：Research status and prospect[J]. Systems Engineering, 2004, 22(7), 68-71]

[11] 邹彤, 李宁, 孙德宝．不确定车辆数的有时间窗车辆路径问题的遗传算法[J]．系统工程理论与实践, 2004, 24(6): 134-138．[ZOU T, LI N, SUN D B．Genetic algorithm for variable fleet vehicle routing problem with time window[J]．System Engineering-Theory & Practice, 2004, 24(6), 134-138]

[12] 张涛, 张玥杰, 王梦光．不确定车辆数的车辆路径问题模型和混合算法[J]．系统工程理论方法应用, 2002, 11(2), 121-130. [ZHANG T, ZHANG Y J，WANG M G. Model and hybrid algorithm for vehicle routing problem with uncertain vehicle number[J]. Systems Engineering-Theory Methodology Applications, 2002, 11(2), 121-130]

[13] 郎茂祥, 胡思继. 车辆路径问题的禁忌搜索算法研究[J]. 管理工程学报, 2004, 18(1), 81-84. [LANG M X, HU S J. Study on the tabu search algorthm for vehicle routing problem[J]. Journal of Industrial Engineering／Engineering Management, 2004, 18(1), 81-84]

[1]	柳伍生, 李旺, 周清, 迭纤. “无人机-车辆”配送路径优化模型与算法[J]. 交通运输系统工程与信息, 2021, 21(6): 176-186.
[2]	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
[3]	杨森炎，宁连举，商攀. 基于时空状态网络的电动物流车辆路径优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 196-204.
[4]	辛禹辰，施胜男，杨华龙. 基于订单拆分的线上到线下连锁门店配送优化模型[J]. 交通运输系统工程与信息, 2020, 20(5): 212-217.
[5]	赵志学，李夏苗. 时变交通下生鲜配送电动车辆路径优化方法[J]. 交通运输系统工程与信息, 2020, 20(5): 218-225.
[6]	于江霞，杜红亚，罗太波. 基于客户分类的即时配送路径优化研究[J]. 交通运输系统工程与信息, 2020, 20(4): 202-208.
[7]	周晓晔，崔瑶，何亮，马小云，王思聪. 基于地铁—货车联运的物流配送路径优化[J]. 交通运输系统工程与信息, 2020, 20(3): 111-117.
[8]	陆华，袁敏，刘玉霞，杜志平. 共同配送对城市货运交通系统的效益研究[J]. 交通运输系统工程与信息, 2019, 19(6): 6-12.
[9]	申婵，崔洪军. 基于可靠性最短路的实时定制公交线路优化研究[J]. 交通运输系统工程与信息, 2019, 19(6): 99-104.
[10]	尹小庆，莫宇迪，董陈晨，林云. 考虑行程时间可靠性的城市冷链末端配送站选址研究[J]. 交通运输系统工程与信息, 2019, 19(6): 176-183.
[11]	马冰山，胡大伟，陈希琼，胡卉. 半开放式的多配送中心纯电动车辆路径优化问题[J]. 交通运输系统工程与信息, 2019, 19(6): 199-205.
[12]	卫振林，李世龙. 城市配送中心布局政府干预机制研究[J]. 交通运输系统工程与信息, 2019, 19(5): 7-12.
[13]	冯霞，唐菱，卢敏. 面向层次资质的机场外航服务人员排班研究[J]. 交通运输系统工程与信息, 2019, 19(2): 231-237.
[14]	周芳汀，张锦，周国华. 带时间窗的地铁配送网络路径优化问题[J]. 交通运输系统工程与信息, 2018, 18(5): 88-94.
[15]	柴获，何瑞春，苏江省，宋宇博，代存杰，马昌喜. 求解双目标带时间窗车辆路径问题的蚁群算法[J]. 交通运输系统工程与信息, 2018, 18(4): 156-162.