|Table of Contents|

Optimization model of distribution network with multiple distribution centers and multiple demand points considering traffic flow change(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2015年01期
Page:
100-107
Research Field:
交通运输规划与管理
Publishing date:

Info

Title:
Optimization model of distribution network with multiple distribution centers and multiple demand points considering traffic flow change
Author(s):
YANG Zhong-zhen;  MU Xue;  ZHU Xiao-cong
School of Transportation Management, Dalian Maritime University, Dalian 116026, Liaoning, China
Keywords:
traffic planning;  road network;  vehicle routing problem;  traffic flow;  distribution routing;  user equilibrium model;  hybrid grouping
PACS:
U491.51
DOI:
-
Abstract:
Based on the structure of urban road network and the characteristic of traffic flow, the minimum total distribution time was taken as objective function, the traffic flow was taken as constraint condition, and the optimization model of bi-level distribution network was developed. The distribution routing of distribution vehicle was calculated by using the upper model, the lower model was user equilibrium traffic assignment model, the OD trip data in the lower model could be changed by using the calculation result of upper model, and the transit time of road section in the upper model could be changed by using the calculation result of lower model. The hybrid grouping, genetic algorithm and Frank-Wolf algorithm were used to solve the bi-level optimization model, and example verification was carried out through a traffic network with 31 traffic zones, 27 demand points and 4 distribution centers in Dalian City. Calculation result shows that when the distribution plan is obtained through the minimum distance method, the total distribution distance for 27 demand points is 94.8 km, the total distribution time is 425.2 min, and the calculation time is 13 s. Using the bi-level optimization model with the consideration of traffic flow change, the total distribution distance for 27 demand points is 109.7 km, the total distribution time is 329.1 min, and the calculation time is 256 s. After using the bi-level optimization model, the total distribution distance increases 14.9 km, but the total distribution time decreases 96.1 min, the mutual balance process of distribution vehicles and other vehicles can one-off reaches, the calculation speed and efficiency are not the most important factors, and the calculation result more in line with the actual situation can be gotten. 1 tab, 10 figs, 22 refs.

References:

[1] CLARK G, WRIGHT J. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581.
[2] TILLMAN F A, CAIN T M. An upper bound algorithm for the single and multiple terminal delivery problem[J]. Management Science, 1972, 18(11): 664-682.
[3] SUMICHRAST R T, MARKHAM I S. A heuristic and lower bound for a multi-depot routing problem[J]. Computers and Operations Research, 1995, 22(10): 1047-1056.
[4] RENAUD J, LAPORTE G, BOCTOR F F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers and Operations Research, 1996, 23(3): 229-235.
[5] CORDEAN J F, GOLDE B L, LAPORTE G. A tabu search heuristic for periodic and multi-depot vehicle routing problems[J]. Networks, 1997, 30(1): 105-119.
[6] SU C T. Dynamic vehicle control and scheduling of a multi-depot physical distribution system[J]. Integrated Manufacturing Systems, 1999, 10(1): 56-65.
[7] GIOSA I D, TANSINI I L, VIERA I O. New assignment algorithms for the multi-depot vehicle routing problem[J]. Journal of the Operational Research Society, 2002, 53(9): 977-984.
[8] MICHAEL P, RICHARD F, KARL D. A variable neighborhood search for the multi-depot vehicle routing problem with time windows[J]. Journal of Heuristics, 2004, 10(6): 613-627.
[9] 郎茂祥.多配送中心车辆调度问题的模型与算法研究[J].交通运输系统工程与信息,2006,10(6):65-69.LANG Mao-xiang. Study on the model and algorithm for multi-depot vehicle scheduling problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2006, 10(6): 65-69.(in Chinese)
[10] 戴树贵,陈文兰,潘荫荣,等.多配送中心车辆路径安排问题混合蚁群算法[J].四川大学学报:工程科学版,2008,40(6):154-158.DAI Shu-gui, CHEN Wen-lan, PAN Yin-rong, et al. A hybrid ant colony algorithm for multiple depot vehicle routing problem[J]. Journal of Sichuan University: Engineering Science Edition, 2008, 40(6): 154-158.(in Chinese)
[11] 谢天保,雷西玲,席文玲.多物流中心协同配送车辆调度模型研究[J].计算机工程与应用,2010,46(29):203-210.XIE Tian-bao, LEI Xi-ling, XI Wen-ling. Study of logistics cooperating distribution scheduling mode[J]. Computer Engineering and Applications, 2010, 46(29): 203-210.(in Chinese)
[12] 于 滨,靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题[J].系统工程理论与实践,2012,32(8):1793-1800.YU Bin, JIN Peng-huan, YANG Zhong-zhen. Two-stage heuristic algorithm for multi-depot vehicle routing problem with time windows[J]. Systems Engineering—Theory and Practice, 2012, 32(8): 1793-1800.(in Chinese)
[13] CHRISTOFIDES N, EILON S. An algorithm for one vehicle-dispatching problem[J]. Operational Research Society, 1969, 20(3): 309-318.
[14] TILLMAN F A, HERING R W. A study of a look-aheed procedure for solving the multiterminal delivery problem[J]. Transportation Research, 1971, 5(1): 225-229.
[15] WREN A, HOLLIDAY A. Computer scheduling of vehicles from one or more depots to a number of delivery points[J]. Operational Research Society, 1972, 23(3): 333-344.
[16] GILLETT B E, JOHNSON J G. Multi-terminal vehicle-dispatch algorithm[J]. Omega, 1976, 4(6): 711-718.
[17] CHAO I M, GOLDEN B L, WALL E. A new heuristic forth multi-depot vehicle routing problem that improves upon best-known solutions[J]. American Journal of Mathematical and Management Sciences, 1993, 13(4): 371-406.
[18] CREVIER B, CORDEAU J F, LAPORTE G. The multi-depot vehicle routing problem with inter-depot routes[J]. European Journal of Operational Research, 2007, 76(2): 756-773.
[19] 王 平,唐喜平,李 云.一类多源点物流配送优化模型的探讨[J].系统工程理论与实践,2003,23(3):87-91.WANG Ping, TANG Xi-ping, LI Yun. Approach for a multi-source logistics delivery optimum model[J]. Systems Engineering—Theory and Practice, 2003, 23(3): 87-91.(in Chinese)
[20] 李 敏,郭 强,刘红丽.多车场多配送中心的物流配送问题研究[J].计算机工程与应用,2007,43(8):202-204,208.LI Min, GUO Qiang, LIU Hong-li. Multiple depot multi-logistics center distribution problem[J]. Computer Engineering and Applications, 2007, 43(8): 202-204, 208.(in Chinese)
[21] 程志强.多配送中心车辆调度问题的模型及其遗传算法研究[J].铁路采购与物流,2011,5(4):34-36.CHENG Zhen-qiang. Study of the multi-depot vehicle scheduling problem model and its gemetic algorithm[J]. Railway Purchasing and Logistics, 2011, 5(4): 34-36.(in Chinese)
[22] OKUDEA M K, TANIGUCHI E C. An approximation algorithm for vehicle routing problems with hierarchized traffic network[J]. Procedia-Social and Behavioral Sciences, 2012, 39(1): 369-386.

Memo

Memo:
-
Last Update: 2015-02-25