时变路网下异型车辆动态配置与路径优化

范厚明, 张跃光, 田攀俊, 曹宇, 任晓雪

系统工程理论与实践 ›› 2022, Vol. 42 ›› Issue (2) : 455-470.

PDF(1363 KB)
PDF(1363 KB)
系统工程理论与实践 ›› 2022, Vol. 42 ›› Issue (2) : 455-470. DOI: 10.12011/SETP2020-0017
论文

时变路网下异型车辆动态配置与路径优化

    范厚明1, 张跃光1, 田攀俊1, 曹宇2, 任晓雪1
作者信息 +

Dynamic vehicle routing problem of heterogeneous fleets with time-dependent networks

    FAN Houming1, ZHANG Yueguang1, TIAN Panjun1, CAO Yu2, REN Xiaoxue1
Author information +
文章历史 +

摘要

针对配送中心车型多样、客户需求动态变化且车辆行驶时间依赖配送区域路网速度变化特征的动态车辆路径问题,基于先预优化后动态调整的思想建立了以配送成本最小化为目标的两阶段优化模型.在预优化阶段,设计改进自适应遗传算法获得初始配送方案;在动态调整阶段,综合考虑客户需求变化和配送路网速度的变化,制定连续性和周期性相结合的优化策略,将问题转化为多中心车辆路径问题进行求解.通过实验分析验证了模型与算法的有效性,研究成果可丰富车辆路径问题的相关研究,为物流企业优化决策配送方案提供理论依据.

Abstract

In order to effectively solve the dynamic vehicle routing problem of heterogeneous fleets, customers' dynamic requests and real-time variations in travel times between nodes in distribution networks, a two-stage mathematical model with the goal of minimizing distribution costs was established based on the idea of pre-optimization and dynamic adjustment in this paper. In the pre-optimization stage, an improved adaptive genetic algorithm is designed to gain the initial distribution scheme; In the dynamic adjustment stage, comprehensively consider the customers' dynamic requests and the speed of the distribution networks, formulate an optimization strategy that combines continuity and periodicity, and turn the problem into multi-depot vehicle routing problem for solution. The effectiveness of the model and algorithm is verified by example analysis. The research results can enrich the relevant research on vehicle routing problem and provide theoretical basis for logistics enterprises to optimize realistic distribution schemes.

关键词

车辆路径问题 / 时变路网 / 异型车辆 / 动态需求 / 自适应遗传算法

Key words

vehicle routing problem / time-dependent networks / heterogeneous fleets / dynamic demand / adaptive genetic algorithm

引用本文

导出引用
范厚明 , 张跃光 , 田攀俊 , 曹宇 , 任晓雪. 时变路网下异型车辆动态配置与路径优化. 系统工程理论与实践, 2022, 42(2): 455-470 https://doi.org/10.12011/SETP2020-0017
FAN Houming , ZHANG Yueguang , TIAN Panjun , CAO Yu , REN Xiaoxue. Dynamic vehicle routing problem of heterogeneous fleets with time-dependent networks. Systems Engineering - Theory & Practice, 2022, 42(2): 455-470 https://doi.org/10.12011/SETP2020-0017
中图分类号: U116.2   

参考文献

[1] Yang J, Jaillet P, Mahmassani H. Real-Time multivehicle truckload pickup and delivery problems[J]. Transportation Science, 2004, 38(2):135-148.
[2] 李兵, 郑四发, 曹剑东, 等. 求解客户需求动态变化的车辆路径规划方法[J]. 交通运输工程学报, 2007(1):106-110.Li B, Zheng S F, Cao J D, et al. Method of solving vehicle routing problem with customers' dynamic requests[J]. Journal of Traffic and Transportation Engineering, 2007(1):106-110.
[3] 张景玲, 赵燕伟, 王海燕, 等. 多车型动态需求车辆路径问题建模及优化[J]. 计算机集成制造系统, 2010, 16(3):543-550.Zhang J L, Zhao Y W, Wang H Y, et al. Modeling and algorithms for a dynamic multi-vehicle routing problem with customers' dynamic requests[J]. Computer Integrated Manufacturing Systems, 2010, 16(3):543-550.
[4] 张婷, 赖平仲, 何琴飞, 等. 基于实时信息的城市配送车辆动态路径优化[J]. 系统工程, 2015, 33(7):58-64.Zhang T, Lai P Z, He Q F, et al. Optimization of dynamic vehicle routing of urban distribution based on the real-time information[J]. Systems Engineering, 2015, 33(7):58-64.
[5] 张文博, 苏秦, 程光路. 基于动态需求的带时间窗的车辆路径问题[J]. 工业工程与管理, 2016, 21(6):68-74.Zhang W B, Su Q, Cheng G L. Vehicle routing problem with time windows based on dynamic demands[J]. Industrial Engineering and Management, 2016, 21(6):68-74.
[6] 孙小军, 介科伟. 求解带时间窗动态车辆路径问题的改进蚁群算法[J]. 大连理工大学学报, 2018, 58(5):539-546.Sun X J, Jie K W. Improved ant colony optimization algorithm for solving dynamic vehicle routing problem with time windows[J]. Journal of Dalian University of Technology, 2018, 58(5):539-546.
[7] Abdallah A M F M, Essam D L, Sarker R A. On solving periodic re-optimization dynamic vehicle routing problems[J]. Applied Soft Computing, 2017, 55(6):1-12.
[8] 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.
[9] 马华伟, 靳鹏, 杨善林. 时变车辆路径问题的启发式算法[J]. 系统工程学报, 2012, 27(2):256-262.Ma H W, Jin P, Yang S L. Heuristic methods for time-dependent vehicle routing problem[J]. Journal of Systems Engineering, 2012, 27(2):256-262.
[10] Liao T Y, Hu T Y. An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information[J]. Expert Systems with Applications, 2011, 38(10):12548-12558.
[11] Mancini S. Time dependent travel speed vehicle routing and scheduling on a real road network:The case of Torino[J]. Transportation Research Procedia, 2014, 3:433-441.
[12] 蔡延光, 汤雅连, 蔡颢. 时变路网条件下车辆路径问题的自适应蚁群算法[J]. 计算机应用研究, 2015, 32(8):2309-2312+2346.Cai Y G, Tang Y L, Cai H. Adaptive ant colony optimization for vehicle routing problem in time varying networks environment[J]. Application Research of Computers, 2015, 32(8):2309-2312+2346.
[13] 李妍峰, 高自友, 李军. 动态网络车辆路径派送问题研究[J]. 管理科学学报, 2014, 17(8):1-9.Li Y F, Gao Z Y, Li J. Dynamic vehicle routing and dispatching problem[J]. Journal of Management Sciences in China, 2014, 17(8):1-9.
[14] 葛显龙, 张慧. 城市实时交通路网车辆路径优化问题研究[J]. 工业工程与管理, 2018, 23(3):140-149+156.Ge X L, Zhang H. Study on the optimization of vehicle routing problem in urban real time traffic network[J]. Industrial Engineering and Management, 2018, 23(3):140-149+156.
[15] Liu C S, Kou G, Zhou X C, et al. Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach[J]. Knowledge-Based Systems, 2020, 188:104813.
[16] Sabar N R, Bhaskar A, Chung E, et al. A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion[J]. Swarm and Evolutionary Computation, 2019, 44(2):1018-1027.
[17] Haghani A, Jung S. A dynamic vehicle routing problem with time-dependent travel times[J]. Computers & Operations Research, 2005, 32(11):2959-2986.
[18] Chen H K, Hsueh C F, Chang M S. The real-time time-dependent vehicle routing problem[J]. Transportation Research Part E:Logistics and Transportation Review, 2006, 42(5):383-408.
[19] 饶卫振, 金淳, 刘锋, 等. 一类动态车辆路径问题模型和两阶段算法[J]. 交通运输系统工程与信息, 2015, 15(1):159-166.Rao W Z, Jin C, Liu F, et al. Model and two-stage algorithm on dynamic vehicle routing problem[J]. Journal of Transporation Systems Engineering & Information Technology, 2015, 15(1):159-166.
[20] 孙宝凤, 史俊妍, 杨雪, 等. 基于实时信息的取送货动态车辆路径问题研究[J]. 宁波大学学报(理工版), 2019, 32(3):87-94.Sun B F, Shi J Y, Yang X, et al. Solution for dynamic pickup and delivery problem based on real-time information[J]. Journal of Ningbo University (Natural Science & Engineering Edition), 2019, 32(3):87-94.
[21] Xu Z T, Elomri A, Pokharel S, et al. A model for capacitated green vehicle routing problem with the time varying vehicle speed and soft time windows[J]. Computers & Industrial Engineering, 2019, 137:106011.
[22] 杨海强. 基于出租车GPS数据的城市常发性交通拥堵演变研究[D]. 哈尔滨:哈尔滨工业大学, 2018.Yang H Q. Research of urban recurrent congestion evolution based on taxi GPS date[D]. Harbin:Harbin Institute of Technology, 2018.
[23] Hickman A J. Methodology for calculating transport emissions and energy consumption[R]. European:Cold Starts, 1999.
[24] Alinaghian M, Naderipour M. A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption:A case study[J]. Computers & Industrial Engineering, 2016, 99(9):210-222.
[25] Elhassania M, Jaouad B, Ahmed E A. A new hybrid algorithm to solve the vehicle routing problem in the dynamic environment[J]. International Journal of Soft Computing, 2013, 8(8):327-334.
[26] Hanshar F T, Ombuki-Berman B M. Dynamic vehicle routing using genetic algorithms[J]. Applied Intelligence, 2007, 27(1):89-99.
[27] 吴聪, 陈侃松, 姚静. 基于改进自适应遗传算法的物流配送路径优化研究[J]. 计算机测量与控制, 2018, 26(2):236-240.Wu C, Chen K S, Yao J. Study on optimization of logistics distribution route based on improved adaptive genetic algorithm[J]. Computer Measurement & Control, 2018, 26(2):236-240.
[28] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on System, Man, and Cybernetics, 1994, 24(4):656-667.

基金

国家社科基金应急管理体系建设研究专项(20VYJ024)
PDF(1363 KB)

1954

Accesses

0

Citation

Detail

段落导航
相关文章

/