Stochastic Demand Vehicle Routing Problem on Immune and Genetic Algorithm

Abstract:

In this paper, stochastic demand vehicle routing problem and model are studied. Hybrid algorithm based on immune algorithm and genetic algorithm is proposed in order to gain solution. IA-GA use basic principles and processes of genetic algorithm, and includes the promotion-inhibition function and memory function of immune algorithm. The premature convergence problem of genetic algorithm is conquered, and we can get different offspring with improved crossover. Comparing experiment shows that IA-GA has better computing performance.

• Periodical: Advanced Materials Research (Volumes 452-453)
• Pages: 823-828
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.452-453.823
• Online since: January 2012
• Authors: Qun Zhang, Rui Yan
• Keywords: Genetic Algorithm (GA), Immune Algorithm, Stochastic Demand Vehicle Routing Problem

References

[1] Dantzing G, Fulkerson R, Johnson S. Solution of a Large-scale Traveling Salesman Problem. Operation Research (1954), p.393.

[2] Dantzing G, Ramser J. The Truck Dispatching Problem, Management Science Vol. 6 (1959), p.80.

[3] Eilon S, Watson C, Christofides N: Distribution Management: Mathematical Modeling and Practical Analysis (Hafner Publication, New York 1987).

[4] Solomon M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operation Research Vol. 35-2 (1987), p.254.

DOI: 10.1287/opre.35.2.254

[5] Eksioglu B, Vural A, Reisman A. The Vehicle Routing Problem: a Taxonomic review, Computers & Industrial Engineering Vol. 57 (2009), p.1472.

DOI: 10.1016/j.cie.2009.05.009

[6] Dror M, Trudeau P. Stochastic Vehicle Routing with Modified Savings Algorithm, European Journal of Operational Research Vol. 23 (1986), p.228.

DOI: 10.1016/0377-2217(86)90242-0

[7] XUAN Guang-nan, CHENG Run-wei: Genetic Algorithm and Engineering Optimization (Tsinghua University Press, Bei Jing 2004).

[8] MO Hong-wei, ZUO Xing-quan: Artificial Immune System (Science Press, Bei Jing 2009).

[9] ZHANG Li-ping, CHAI Yue-ting. Improved Genetic Algorithm for Vehicle Routing Problem, Systems Engineering-Theory & Practice Vol. 8 (2002), p.79.

[10] XU Zong-ben; Nie Zan-kan; ZAHNG Wen-xiu. Almost Sure Strong Convergence of a Class of Genetic Algorithms with Parent-offsprings Competition, Acta Mathematicae Applicatae Sinica Vol. 25-1 (2002), p.167.

[11] MING Liang, WANG Yu-ping. A Study of Convergence Rate in a Class of Genetic Algorithms, Mathematica Numerica Sinica Vol. 29-1 (2007), p.15.

[12] YUAN Jian; LIU Jin; LU Hou-qing. Annealed Neural Networks Approach to the Vehicle Routing Problem with Stochastic Demands, Systems Engineering-Theory & Practice Vol. 3 (2002), p.109.