The Research on Vehicle Routing Problem Based on Improved Ant Colony Algorithm

Article Preview

Abstract:

Vehicle Routing Problem (VRP) plays a vital role in mathematical and logistics research. Its a typical NP-Hard problem, and ant colony algorithm has been proven to be an effect way in solving these problems. An improved ant colony algorithm is proposed to solve VRP on the basis of depth analyzing VRP and ant colony algorithm. It proposes the mathematical model of VRP and designs an improved ant colony algorithm, considering the inefficient solving, easy to partial stagnation shortcomings of ant colony algorithm and the attraction, repulsion, time constraint phenomena in VRP. This paper redesigns the pheromone update rule and the state transition rule and then it makes a simulation experiment by MATLAB programming, the results show that the improved ant colony is feasible and very valid in solving VRP.

You might also be interested in these eBooks

Info:

Periodical:

Pages:

2439-2446

Citation:

Online since:

September 2013

Export:

Price:

Permissions CCC:

Permissions PLS:

Сopyright:

© 2013 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

[1] Dantzig G B. The truck dispatching problem [J]. Management science, 1959, 6(1): 80-91.

Google Scholar

[2] George A, Rajakumar B R. Fuzzy Aided Ant Colony Optimization Algorithm to Solve Optimization Problem [M]/Intelligent Informatics. Springer Berlin Heidelberg, 2013: 207-215.

DOI: 10.1007/978-3-642-32063-7_23

Google Scholar

[3] Balseiro S R, Loiseau I, Ramonet J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows [J]. Computers & Operations Research, 2011, 38(6): 954-966.

DOI: 10.1016/j.cor.2010.10.011

Google Scholar

[4] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]/Proceedings of the first European conference on artificial life. 1991, 142: 134-142.

Google Scholar

[5] Doerner K F, Schmid V. Survey: matheuristics for rich vehicle routing problems [M]/Hybrid Metaheuristics. Springer Berlin Heidelberg, 2010: 206-221.

DOI: 10.1007/978-3-642-16054-7_15

Google Scholar

[6] Dorigo M, Luca M. A Study of Some Properties of An-t Q[C]. Proc. of 4th Int. Conf. on Parallel Problem Solving form Nature (PPSN). Springer Verlag, Berlin, 1996. 656-665.

Google Scholar

[7] Stutzle T, Hoos H H H H. MAX-MIN ant system [J]. Future generations computer systems, 2000, 16(8): 889-914.

Google Scholar

[8] Gambardella L M, Dorigo M. An ant colony system hybridized with a new local search for the sequential ordering problem [J]. INFORMS Journal on Computing, 2000, 12(3): 237-255.

DOI: 10.1287/ijoc.12.3.237.12636

Google Scholar

[9] Ciornei I, Kyriakides E. Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization [J]. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 2012, 42(1): 234-245.

DOI: 10.1109/tsmcb.2011.2164245

Google Scholar

[10] Yu B, Yang Z Z, Yao B. An improved ant colony optimization for vehicle routing problem [J]. European journal of operational research, 2009, 196(1): 171-176.

DOI: 10.1016/j.ejor.2008.02.028

Google Scholar

[11] Chen C H, Ting C J. An improved ant colony system algorithm for the vehicle routing problem [J]. Journal of the Chinese institute of industrial engineers, 2006, 23(2): 115-126.

DOI: 10.1080/10170660609509001

Google Scholar

[12] Gulczynski D, Golden B, Wasil E. The split delivery vehicle routing problem with minimum delivery amounts [J]. Transportation Research Part E: Logistics and Transportation Review, 2010, 46(5): 612-626.

DOI: 10.1016/j.tre.2009.12.007

Google Scholar

[13] Azi N, Gendreau M, Potvin J Y. An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles [J]. European Journal of Operational Research, 2010, 202(3): 756-763.

DOI: 10.1016/j.ejor.2009.06.034

Google Scholar

[14] Duhamel C, Lacomme P, Prodhon C. A hybrid evolutionary local search with depth first search split procedure for the heterogeneous vehicle routing problems [J]. Engineering Applications of Artificial Intelligence, 2012, 25(2): 345-358.

DOI: 10.1016/j.engappai.2011.10.002

Google Scholar

[15] Erera A L, Morales J C, Savelsbergh M. The vehicle routing problem with stochastic demand and duration constraints| NOVA. The University of Newcastle's Digital Repository [J]. (2010).

DOI: 10.1287/trsc.1100.0324

Google Scholar

[16] Anbuudayasankar S P, Ganesh K, Lenny Koh S C, et al. Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls [J]. Expert Systems with Applications, 2012, 39(3): 2296-2305.

DOI: 10.1016/j.eswa.2011.08.009

Google Scholar

[17] Karlaftis M G, Kepaptsoglou K, Sambracos E. Containership routing with time deadlines and simultaneous deliveries and pick-ups[J]. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(1): 210-221.

DOI: 10.1016/j.tre.2008.05.001

Google Scholar