期刊文献+

Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows 被引量:10

求解带软时间窗多车场多车型车辆路径问题的一种改进蚁群算法(英文)
下载PDF
导出
摘要 Considering that the vehicle routing problem (VRP) with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a mathematical model for multi-depot heterogeneous vehicle routing problem with soft time windows (MDHVRPSTW) is established. An improved ant colony optimization (IACO) is proposed for solving this model. First, MDHVRPSTW is transferred into different groups according to the nearest principle, and then the initial route is constructed by the scanning algorithm (SA). Secondly, genetic operators are introduced, and crossover probability and mutation probability are adaptively adjusted in order to improve the global search ability of the algorithm. Moreover, the smooth mechanism is used to improve the performance of the ant colony optimization (ACO). Finally, the 3-opt strategy is used to improve the local search ability. The proposed IACO was tested on three new instances that were generated randomly. The experimental results show that IACO is superior to the other three existing algorithms in terms of convergence speed and solution quality. Thus, the proposed method is effective and feasible, and the proposed model is meaningful. 考虑实际生活中带多种扩展特征(如多车场、多车型、客户服务优先级、时间窗等)的车辆路径问题应用广泛,建立带软时间窗多车场多车型车辆路径问题的数学模型,并提出一种改进的蚁群优化算法(IACO)求解该模型.首先,根据就近原则将客户分组,并通过扫描算法构造初始路径;其次,通过引入遗传算子并自适应地调整交叉概率和变异概率来提高算法的全局收敛能力,且采用平滑机制来提高蚁群优化算法的性能;最后,采用3-opt策略来提高算法的局部搜索能力.将提出的算法应用在3个随机产生的实例中,仿真表明提出的IACO在收敛速度和解质量两方面都优于现有的3种算法,证明提出的算法是有效可行的,且提出的模型具有一定的实际意义.
出处 《Journal of Southeast University(English Edition)》 EI CAS 2015年第1期94-99,共6页 东南大学学报(英文版)
基金 The National Natural Science Foundation of China(No.61074147) the Natural Science Foundation of Guangdong Province(No.S2011010005059) the Foundation of Enterprise-University-Research Institute Cooperation from Guangdong Province and Ministry of Education of China(No.2012B091000171,2011B090400460) the Science and Technology Program of Guangdong Province(No.2012B050600028) the Science and Technology Program of Huadu District,Guangzhou(No.HD14ZD001)
关键词 vehicle routing problem soft time window improved ant colony optimization customer service priority genetic algorithm 车辆路径问题 软时间窗 改进蚁群优化算法 客户服务优先级 遗传算法
  • 相关文献

参考文献12

  • 1Gulczynski D, Golden B, Wasil E. The multi-depot split delivery vehicle routing problem: an integer programming- based heuristic, new test problems, and computational re- suits[ J]. Computers & Industrial Engineering, 2011, 61 (3) : 794 - 804.
  • 2Rahimi-Vahed A, Crainic T G, Gendreau M, et al. A path relinking algorithm for a multi-depot periodic vehicle routing problem[J]. Journal of Heuristics, 2013, 19(3): 497 - 524.
  • 3Ho W, Ho G T S, Ji P, et al. A hybrid genetic algorithm for the multi-depot vehicle routing problem[ J]. Engineer- ing Applications of Artificial Intelligence, 2008, 21 (4) : 548 - 557.
  • 4Tu W, Fang Z, Li Q, et al. A hi-level Voronoi diagram- based metaheuristic for a large-scale multi-depot vehicle routing problem[ J]. Transportation Research Part E: Lo- gistics and Transportation Review, 2014, 61:84 -97.
  • 5Yu B, Ma N, Cai W J, et al. Improved ant colony op- timisation for the dynamic multi-depot vehicle routing problem[ J]. International Journal of Logistics Research and Applications, 2013, 16(2) : 144 - 157.
  • 6Geetha S, Poonthalir G, Vanathi P T. Nested particle swarm optimisation for multi-depot vehicle routing prob- lem[ J]. International Journal of Operational Research, 2013, 16(3): 329-348.
  • 7Mirabi M, Fatemi Ghomi S M T F, Jolai F. Efficient sto- chastic hybrid heuristics for the multi-depot vehicle routing problem[ J]. Robotics and Computer-Integrated Manufac- turing, 2010, 26(6): 564-569.
  • 8Yu B, Yang Z Z, Xie J X. A parallel improved ant colo- ny optimization for multi-depot vehicle routing problem [J]. Journal of the Operational Research Society, 2011, 62(1): 183 - 188.
  • 9Kuo Y, Wang C C. A variable neighborhood search for the multi-depot vehicle routing problem with loading cost [J]. Expert Systems with Applications, 2012, 39(8): 6949 - 6954.
  • 10Bettinelli A, Ceselli A, Righini G. A branch-and-cut- and-price algorithm for the multi-depot heterogeneous ve- hicle routing problem with time windows[ J]. Transporta- tion Research Part C: Emerging Technologies, 2011, 19 (5): 723-740.

同被引文献71

引证文献10

二级引证文献42

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部