Optimization model of distribution network with multiple distribution centers and multiple demand points considering traffic flow change
-
摘要: 基于城市道路网结构与交通流特征, 以总配送耗时最小为目标函数, 以交通流为约束条件, 构建了双层配送网络优化模型。上层模型计算配送车辆的配送路径, 下层模型为用户均衡交通分配模型, 通过上层模型的计算结果改变下层模型中的OD出行数据, 通过下层模型的计算结果改变上层模型中的路段通行时间。利用混合式分组法、遗传算法与Frank-Wolf算法求解模型, 并以大连市某带有31个交通小区、27个需求点和4个配送中心的交通网络为例进行实例验证。计算结果表明: 当利用最短距离法求得配送方案时, 27个需求点的总配送距离为94.8km, 总配送耗时为425.2min, 计算时间为13s;考虑交通流变化后, 利用提出的双层优化模型, 27个需求点的总配送距离为109.7km, 总配送耗时为329.1min, 计算时间为256s。利用提出的双层优化模型, 虽然总配送距离增加14.9km, 但总配送耗时却缩短96.1min, 并可以一次性达到配送车辆和其他车辆相互平衡的过程, 计算速度和效率并不是最重要的因素, 可以得到更符合实际的计算结果。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 4distribution 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.8km, the total distribution time is 425.2min, and the calculation time is 13 s.Using the bi-level optimization model with the consideration oftraffic flow change, the total distribution distance for 27 demand points is 109.7km, the total distribution time is 329.1min, and the calculation time is 256 s.After using the bi-level optimization model, the total distribution distance increases 14.9km, but the total distribution time decreases 96.1min, 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 基于最短距离法的S1向N1的配送路径
Figure 1. Distribution routing from S1 to N1 based on minimum distance method
图 2 考虑交通流变化后的S1向N1的配送路径
Figure 2. Distribution routing from S1 to N1 after considering traffic flow change
图 4 配送中心、需求点与交通小区划分情况
Figure 4. Division condition of distribution centers, demand points and traffic zones
图 7 基于最短距离法配送中心1向需求点21的配送路径
Figure 7. Distribution routing from deistribution center 1 to demand point 21 based on minimum distance method
图 8 考虑交通流变化后配送中心1向需求点21的配送路径
Figure 8. Distribution routing from deistribution center 1 to demand point 21 after considering traffic flow change
图 10 考虑道路交通流变化后的交通流状态
Figure 10. Traffic flow state after considering traffic flow change
表 1 需求点与需求量
Table 1. Demand points and demand amounts
-
[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. doi: 10.1287/opre.12.4.568 [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. doi: 10.1287/mnsc.18.11.664 [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. doi: 10.1016/0305-0548(94)00083-K [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. doi: 10.1016/0305-0548(95)O0026-P [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. doi: 10.1108/09576069910247609 [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. doi: 10.1057/palgrave.jors.2601426 [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. doi: 10.1007/s10732-005-5432-5 [9] 郎茂祥. 多配送中心车辆调度问题的模型与算法研究[J]. 交通运输系统工程与信息, 2006, 10(6): 65-69. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT200605010.htmLANG 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) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT200605010.htm [10] 戴树贵, 陈文兰, 潘荫荣, 等. 多配送中心车辆路径安排问题混合蚁群算法[J]. 四川大学学报: 工程科学版, 2008, 40(6): 154-158. https://www.cnki.com.cn/Article/CJFDTOTAL-SCLH200806027.htmDAI 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) https://www.cnki.com.cn/Article/CJFDTOTAL-SCLH200806027.htm [11] 谢天保, 雷西玲, 席文玲. 多物流中心协同配送车辆调度模型研究[J]. 计算机工程与应用, 2010, 46(29): 203-210. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201029059.htmXIE 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) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201029059.htm [12] 于滨, 靳鹏欢, 杨忠振. 两阶段启发式算法求解带时间窗的多中心车辆路径问题[J]. 系统工程理论与实践, 2012, 32(8): 1793-1800. doi: 10.3969/j.issn.1000-6788.2012.08.020YU 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) doi: 10.3969/j.issn.1000-6788.2012.08.020 [13] CHRISTOFIDES N, EILON S. An algorithm for one vehicle-dispatching problem[J]. Operational Research Society, 1969, 20(3): 309-318. doi: 10.1057/jors.1969.75 [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. doi: 10.1057/jors.1972.53 [16] GILLETT B E, JOHNSON J G. Multi-terminal vehicle-dispatch algorithm[J]. Omega, 1976, 4(6): 711-718. doi: 10.1016/0305-0483(76)90097-9 [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. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200303015.htmWANG 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) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200303015.htm [20] 李敏, 郭强, 刘红丽. 多车场多配送中心的物流配送问题研究[J]. 计算机工程与应用, 2007, 43(8): 202-204, 208. doi: 10.3321/j.issn:1002-8331.2007.08.063LI 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) doi: 10.3321/j.issn:1002-8331.2007.08.063 [21] 程志强. 多配送中心车辆调度问题的模型及其遗传算法研究[J]. 铁路采购与物流, 2011, 5(4): 34-36. https://www.cnki.com.cn/Article/CJFDTOTAL-TDWZ201105013.htmCHENG 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) https://www.cnki.com.cn/Article/CJFDTOTAL-TDWZ201105013.htm [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. -
下载:
点击查看大图
图(10) / 表(1)
计量
- 文章访问数: 764
- HTML全文浏览量: 111
- PDF下载量: 763
- 被引次数: 0
