[1] Tang Yalian, Cai Yanguang, Yang Qijiang,. Improved ant colony optimization for multi-depot heterogeneousvehicle routing problem with soft time windows [J]. Journal of Southeast University (English Edition), 2015, 31 (1): 94-99. [doi:10.3969/j.issn.1003-7985.2015.01.016]
Copy
Improved ant colony optimization for multi-depot heterogeneousvehicle routing problem with soft time windows(
)
求解带软时间窗多车场多车型车辆路径问题的一种改进蚁群算法
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 31
- Issue:
- 2015 1
- Page:
- 94-99
- Research Field:
- Computer Science and Engineering
- Publishing date:
- 2015-03-30
Info
- Title:
- Improved ant colony optimization for multi-depot heterogeneousvehicle routing problem with soft time windows
- 求解带软时间窗多车场多车型车辆路径问题的一种改进蚁群算法
- Author(s):
- Tang Yalian1; Cai Yanguang1; Yang Qijiang2
-
1School of Automation, Guangdong University of Technology, Guangzhou 510006, China
2School of Machinery and Automobile Engineering, South China University of Technology, Guangzhou 510641, China
- Keywords:
- vehicle routing problem; soft time window; improved ant colony optimization; customer service priority; genetic algorithm
- PACS:
- TP301
- DOI:
- 10.3969/j.issn.1003-7985.2015.01.016
- Abstract:
- 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种算法, 证明提出的算法是有效可行的, 且提出的模型具有一定的实际意义.
References:
[1] Gulczynski D, Golden B, Wasil E. The multi-depot split delivery vehicle routing problem: an integer programming-based heuristic, new test problems, and computational results[J]. Computers & Industrial Engineering, 2011, 61(3): 794-804.
[2] Rahimi-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.
[3] Ho W, Ho G T S, Ji P, et al. A hybrid genetic algorithm for the multi-depot vehicle routing problem[J]. Engineering Applications of Artificial Intelligence, 2008, 21(4): 548-557.
[4] Tu W, Fang Z, Li Q, et al. A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 61: 84-97.
[5] Yu B, Ma N, Cai W J, et al. Improved ant colony optimisation for the dynamic multi-depot vehicle routing problem[J]. International Journal of Logistics Research and Applications, 2013, 16(2): 144-157.
[6] Geetha S, Poonthalir G, Vanathi P T. Nested particle swarm optimisation for multi-depot vehicle routing problem[J]. International Journal of Operational Research, 2013, 16(3): 329-348.
[7] Mirabi M, Fatemi Ghomi S M T F, Jolai F. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing, 2010, 26(6): 564-569.
[8] Yu B, Yang Z Z, Xie J X. A parallel improved ant colony optimization for multi-depot vehicle routing problem[J]. Journal of the Operational Research Society, 2011, 62(1): 183-188.
[9] Kuo 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.
[10] Bettinelli A, Ceselli A, Righini G. A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2011, 19(5): 723-740.
[11] Surekha P, Sumathi S. Solution to multi-depot vehicle routing problem using genetic algorithms[J]. World Applied Programming, 2011, 1(3): 118-131.
[12] Gillett B E, Miller L R. A heuristic algorithm for the vehicle-dispatching problem[J]. Operations Research, 1974, 22:340-349.
Memo
- Memo:
-
Biographies: Tang Yalian(1986—), female, graduate; Cai Yanguang(corresponding author), male, doctor, professor, caiyg99@163.com.
Foundation items: 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).
Citation: Tang Yalian, Cai Yanguang, Yang Qijiang.Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows[J].Journal of Southeast University(English Edition), 2015, 31(1):94-99.[doi:10.3969/j.issn.1003-7985.2015.01.016]