[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()

Share：

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 Yalian¹;  Cai Yanguang¹;  Yang Qijiang²

¹School of Automation, Guangdong University of Technology, Guangzhou 510006, China
²School 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.

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]

Common functions