Abstract：With requirements of continuous improvements to customers’ service, Vehicle Routing Problems with Time Windows (VRPTW) attracted more and more attention. Aiming to minimize the total cost and to maximize customers’ satisfaction, a bi-objective integer programming model is established. A Hybrid Ant Colony Optimization (HACO) is designed to solve it. An elitist-ant strategy is set up to explore the bi-objective functions respectively and to get better non-dominant solutions. The evaporation factors are redefined to balance local and global search capabilities of the algorithm and to avoid premature convergence. NSGA-Ⅱ is used to guide the bi-objective optimizing process, a variable neighborhood search algorithm is used to expand the search space, in order to obtain the better Pareto solution set. The optimal parameter combination was determined by an orthogonal experiment, and the Solomon standard instances are used to test the performance of the algorithm. The simulation results show that the HACO can effectively solve the vehicle routing problem with time windows, and the performance of HACO has a significant improvement.
邓丽娟, 张纪会. 混合蚁群算法求解双目标时间窗VRP[J]. 复杂系统与复杂性科学, 2020, 17(4): 73-84.
DENG Lijuan, ZHANG Jihui. A Hybrid Ant Colony Optimization for Bi-Objective VRP with Time Windows. Complex Systems and Complexity Science, 2020, 17(4): 73-84.
[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. [2] Savelsbergh M W P. Local search in routing problems with time windows [J]. Annals of Operations Research, 1985, 4 (1): 285-305. [3] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265. [4] Hadjiconstantinou E, Christofides N, Mingozzi A. A new exact algorithm for the vehicle routing problem based on q-paths and k-shortest paths relaxations[J]. Annals of Operations Research, 1995, 61(1): 21-43 [5] Laporte G, Nobert Y. Exact algorithm for the vehicle routing problem[J]. Annals of Discrete Mathematics, 1987, 132: 147-184. [6] Fisher M L, Jørnsten K O, Madsen O B G. Vehicle routing with time windows: two optimization algorithms[J]. Operations Research, 1997, 45: 488-492. [7] Azi N, Gendreau M, Potvin J Y. An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J]. European Journal of Operational Research, 2007, 178(3): 755-766. [8] Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581. [9] Glover F. Tabu Search-Part Ⅰ[J]. Orsa Journal on Computing, 1989, 1(3): 190-206. [10] 林清国.基于混合遗传算法的有时间窗车辆路径问题研究[D].济南:山东大学,2007. Lin Qingguo. Research on vehicle path problem with time window based on hybrid genetic algorithm[D]. Ji′nan: Shandong University, 2007. [11] 张智海,吴星玮.带时间窗车辆路径问题的并行遗传算法[J].工业工程, 2007,10(3): 111-114. Zhang Zhihai, Wu Xingwei. Parallel genetic algorithm for vehicle routing problem with time window [J]. Industrial Engineering, 2007,10(3): 111-114. [12] 蒋波.基于遗传算法的带时间窗车辆路径优化问题研究[D].北京:北京交通大学, 2010. Jiang Bo. Research on vehicle path optimization with time window based on genetic algorithm[D]. Beijing:Beijing Jiaotong University, 2010. [13] Zhang Z G, Gong Y C. Improved genetic algorithm of vehicle routing problems with time window for military logistic distribution[J]. Applied Mechanics and Materials, 2011(135/136): 585-591. [14] Shi Y, Boudouh T, Grunder O. A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand [J]. Expert Systems with Applications, 2017, 72: 160-176. [15] 李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践, 2004,24(4): 130-135. LI Ning, Zou Tong, Sun Debao. Particle swarm optimization for vehicle routing problem with time window[J]. Systems Engineering Theory and Practice, 2004,24(4): 130-135. [16] 吴耀华,张念志.带时间窗车辆路径问题的改进粒子群算法研究[J].计算机工程与应用, 2010, 46(15): 230-234. Wu Yaohua, Zhang Nianzhi. Research on improved particle swarm optimization for vehicle routing problem with time window[J]. Computer Engineering and Application, 2010, 46 (15): 230-234. [17] 王飞.带时间窗车辆调度问题的改进粒子群算法[J].计算机工程与应用, 2014, 50(6): 226-229. Wang Fei. Improved particle swarm optimization for vehicle scheduling problem with time window [J]. Computer Engineering and Applications, 2014, 50(6): 226-229. [18] 罗耀. 基于改进粒子群算法的配送中心车辆优化调度问题研究[D]. 兰州:兰州交通大学, 2017. Luo Yao. Research on vehicle scheduling optimization in distribution centers based on improved particle swarm optimization algorithm [D]. Lanzhou: Lanzhou Jiaotong University, 2017. [19] Tohidifard M, Tavakkoli-Moghaddam M, Navazi F, et al. A multi-depot home care routing problem with time windows and fuzzy demands solving by particle swarm optimization and genetic algorithm[J]. IFAC Papers OnLine, 2018, 51(11): 358-363. [20] 殷亚, 张惠珍. 求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法[J]. 计算机应用研究, 2017, 34 (12): 1-8. Yin Ya, Zhang Huizhen. Multiple hybrid bat algorithms for solving multi-objective vehicle path problem with hard time window[J]. Computer Application Research, 2017, 34 (12): 1-8. [21] 李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策, 2010, 25(9): 1379-1383. Li Lin, Liu Shixin, Tang Jiafu. Improved ant colony algorithm for vehicle routing problem with time window [J]. Control and Decision, 2010, 25(9): 1379-1383. [22] 孙小军,介科伟.求解带时间窗动态车辆路径问题的改进蚁群算法[J].大连理工大学学报, 2018, 58(5): 539-546. Sun Xiaojun, Jie Kewei. Improved ant colony algorithm for dynamic vehicle routing problem with time window[J]. Journal of Dalian University of Technology, 2018, 58(5): 539-546. [23] Wang J, Li H Y, Chen H. Mixed ant colony algorithm for vehicle routing problem with time windows [J]. Advanced Materials Research, 2013, 706-708(1): 855-858. [24] 柴获,何瑞春,苏江省,等.求解双目标带时间窗车辆路径问题的蚁群算法[J].交通运输系统工程与信息,2018, 18(4): 156-162. Chai Huo, He Ruichun, Su Jiangsheng, et al. Ant colony algorithm for solving dual objective vehicle routing problem with time window [J]. Transportation System Engineering and Information, 2018, 18(4): 156-162. [25] Zhang Q, Xiong S W. Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm[J]. Applied Soft Computing Journal, 2018. 71: 917-925. [26] Zhang H Z, Zhang Q W, Ma L, et al. A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows[J]. Information Sciences, 2019, 490: 166-190. [27] Vidal T,Laporte G, Matl P. A concise guide to existing and emerging vehicle routing problem variants [J]. European Journal of Operational Research, 2020, 286(2): 401-416. [28] Mladenovi N, Hansen P. Variable neighborhood search[J]. Computers & Operations Research, 1997, 24(11): 1097-1100. [29] Zitzler E, Thiele L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271. [30] 李小川,刘媛华,王影歌.求解多目标带时间窗VRP的文化狼群算法[J].计算机应用研究, 2020, 37(4): 1025-1029. LiXiaochuan, Liu Yuanhua, Wang Ying Ge. Cultural wolf pack algorithm for solving multi-objective VRP with time window [J]. Computer Application Research, 2020, 37(4): 1025-1029. [31] 魏小迪,郑洪清.求解带时间窗车辆路径问题的改进离散花朵授粉算法[J].数学的实践与认识, 2020, 50(2): 193-200. WeiXiaodi, Zheng Hongqing. Improved discrete flower pollination algorithm for vehicle routing problem with time window [J]. Practice and Understanding of Mathematics, 2020, 50(2): 193-200. [32] 刘云,张惠珍.多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J].公路交通科技, 2016, 33(6): 95-100,106. Liu Yun, ZhangHuizhen. Single-parent genetic hybrid ant colony algorithm for multi-objective vehicle routing problem with time window [J]. Road Traffic Technology, 2016, 33(6): 95-100,106.
