Model and algorithm of vehicle routing problem under dynamic traffic
Article Text (Baidu Translation)
-
摘要: 为优化动态交通下物流配送成本及服务水平, 依据交通流量将运输时间分为不同时段的不同分布, 建立了具有时间窗约束与物流成本最小的车辆路径混合整数非线性模型, 设计了自然数插值编码的遗传算法对模型进行求解, 对不同交通状况下配送方案选择进行了仿真比较。仿真结果显示遗传算法是收敛的, 依据交通状况选择相应的配送方案, 不仅物流成本降低了2%, 而且服务水平也提高了5%。Abstract: In order to optimize logistics delivery cost and consumer service level under dynamic traffic, transportation time was assorted into different distributions according to traffic, a mixed integer non-linear model of vehicle routing choice with time window constraints was set up to minimize logistics cost, a genetic algorithm with natural number coding was designed to solve the model, the simulation results of different delivery projects were compared. Comparison result shows that the algorithm is convergent, the logistics cost is reduced by 2%, the service level is improved by 5% to vehicle routing choice according to traffic condition.
-
Key words:
- traffic planning /
- dynamic traffic /
- vehicle routing problem /
- time window /
- genetic algorithm
-
[1] Charnes A, Cooper W. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. doi: 10.1287/mnsc.6.1.80 [2] Gillett B, Miller L. Aheuristic algorithm for the vehicle dispatch problem[J]. Operations Research, 1974, 22(2): 340-349. doi: 10.1287/opre.22.2.340 [3] Gilbert L. The vehicle routing problem: an overviewof exact approxi mate algorithms[J]. European Journal of Operational Research, 1992, 59(3): 345-358. doi: 10.1016/0377-2217(92)90192-C [4] Michel G, Gilbert L, Rene S. Invited review: stochastic vehicle routing[J]. European Journal of Operational Research, 1996, 88(1): 3-12. doi: 10.1016/0377-2217(95)00050-X [5] Eiichi T. An evaluation methodology for city logistics[J]. Transport Reviews, 2000, 20(1): 65-90. doi: 10.1080/014416400295347 [6] 杨瑞臣, 周永付, 云庆夏. 寻找车辆最优路径的混合算法[J]. 交通运输工程学报, 2005, 5(1): 102-105. doi: 10.3321/j.issn:1671-1637.2005.01.024Yang Rui-chen, Zhou Yong-fu, Yun Qing-xia. Hybrid algorithm of vehicle's optimal route[J]. Journal of Traffic and Transportation Engineering, 2005, 5(1): 102-105. (in Chinese) doi: 10.3321/j.issn:1671-1637.2005.01.024 [7] 牛永亮, 王金妹. 物流配送车辆路线求解算法[J]. 交通运输工程学报, 2006, 6(2): 83-87. doi: 10.3321/j.issn:1671-1637.2006.02.019Niu Yong-liang, Wang Jin-mei. Vehicle route algorithm of logistics distribution[J]. Journal of Traffic and Transportation Engineering, 2006, 6(2): 83-87. (in Chinese) doi: 10.3321/j.issn:1671-1637.2006.02.019 [8] 胡大伟, 朱志强, 胡勇. 车辆路径问题的模拟退火算法[J]. 中国公路学报, 2006, 19(4): 123-126. doi: 10.3321/j.issn:1001-7372.2006.04.023Hu Da-wei, Zhu Zhi-qiang, Hu Yong. Si mulated annealing algorithm for vehicle routing problem[J]. China Journal of Highway and Transport, 2006, 19(4): 123-126. (in Chi-nese). doi: 10.3321/j.issn:1001-7372.2006.04.023 [9] 陈松岩, 今井昭夫. 物流网络选址与路径优化问题的模型与启发式解法[J]. 交通运输工程学报, 2006, 6(3): 118-121. doi: 10.3321/j.issn:1671-1637.2006.03.025Chen Song-yan, I mai Akio. Model and heuristic solution for location routing problems of logistics network[J]. Journal of Traffic and Transportation Engineering, 2006, 6(3): 118-121. (in Chinese) doi: 10.3321/j.issn:1671-1637.2006.03.025 [10] Orda A, Rom R. Shortestpath and mini mumdelay algorithms in networks with time-dependent edgelength[J]. Journal of the ACM, 1990, 37(3): 607-625. doi: 10.1145/79147.214078 [11] Halpern J. The shortest-route withtimedependent length of edges and li mited delay possibilities in nodes[J]. Mathematical Methods of Operations Research, 1977, 21(10): 117-124. [12] Hill A, Benton W. Modelling intra-city time-dependent travel speeds for vehicle's cheduling problems[J]. Journal of the Operations Research Society, 1992, 43(4): 343-351. doi: 10.1057/jors.1992.49 [13] Soumia I, Michel G, Jean Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396. doi: 10.1016/S0377-2217(02)00147-9 [14] 徐同连, 栾昆, 贾洪飞. 共同配送合并策略及其配送成本[J]. 长安大学学报: 自然科学版, 2006, 26(3): 68-71. doi: 10.3321/j.issn:1671-8879.2006.03.017Xu Tong-lian, Luan Kun, Jia Hong-fei. Consolidation strategy and distribution cost of joint distribution[J]. Journal of Chang an University: Natural Science Edition, 2006, 26(3): 68-71. (in Chinese) doi: 10.3321/j.issn:1671-8879.2006.03.017 [15] 姜桂艳, 冮龙晖, 王江锋. 城市快速路交通拥挤识别方法[J]. 交通运输工程学报, 2006, 6(3): 88-91. http://transport.chd.edu.cn/article/id/200603019Jian Gui-yan, Gang Long-hui, Wang Jiang-feng. Traffic congestion identification method of urban expressway[J]. Journal of Traffic and Transportation Engineering, 2006, 6(3): 88-91. (in Chinese) http://transport.chd.edu.cn/article/id/200603019 [16] 熊烈强, 王富, 李杰. 路段交通流的动力学模型及其仿真[J]. 中国公路学报, 2006, 19(2): 92-94. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200602015.htmXiong Lie-qiang, Wang Fu, Li Jie. Dynamical model of traffic flow on segment and its simulation[J]. China Journal of Highway and Transport, 2006, 19(2): 92-94. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200602015.htm -
下载:
点击查看大图
图(5) / 表(3)
计量
- 文章访问数: 463
- HTML全文浏览量: 166
- PDF下载量: 290
- 被引次数: 0
