A New Multi Objective Genetic Algorithm: Fitness Aggregated Genetic Algorithm (FAGA) for Vehicle Routing Problem

Abstract:

This paper presents multi objective vehicle routing problem in which the total distance travelled by the vehicles and total number of vehicles used are minimized. In general, fitness assignment procedure, as one of the important operators, influences the effectiveness of multi objective genetic algorithms. In this paper genetic algorithm with different fitness assignment approach and specialized crossover called Fitness Aggregated Genetic Algorithm (FAGA) is introduced for solving the problem. The suggested algorithm is investigated on large number of popular benchmarks for vehicle routing problem. It is observed from the results that the suggested new algorithm is very effective and the solutions are competitive with the best known results.

• Periodical: Advanced Materials Research (Volumes 984-985)
• Pages: 1261-1268
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.984-985.1261
• Online since: July 2014
• Authors: V. Sivaram Kumar*, M.R. Thansekhar, R. Saravanan
• Keywords: Fitness Evaluation for Multi Objectives, Multi Objective Genetic Algorithm, Multi-Objective Optimization (MOP), Vehicle Routing Problem

References

[1] B. Eksioglu, A. V. Vural and A. Reisman, The vehicle routing problem: A taxonomic review, Comput. Ind. Eng. 57 (2009) 1472-1483.

DOI: 10.1016/j.cie.2009.05.009

[2] N. Jozefowiez, F. Semet and E. Talbi, Multi-objective vehicle routing problems, Eur. J. Oper. Res. 189 (2008) 293-309.

DOI: 10.1016/j.ejor.2007.05.055

[3] M. Garza-Fabre, G. T. Pulido and C. A. Coello Coello, Ranking Methods for Many-Objective Optimization, Lect. Notes Artif. Int. 5845 (2009) 633-645.

DOI: 10.1007/978-3-642-05258-3_56

[4] C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Comput. Oper. Res. 31 (2004) 1985-(2002).

[5] T. J. Ai and V. Kachitvichyanukul, Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem, Comput. Ind. Eng. 56 (2009) 380-387.

DOI: 10.1016/j.cie.2008.06.012

[6] S. Mazzeo and I. Loiseau, An Ant Colony Algorithm for the Capacitated Vehicle Routing, Electron. Notes Discrete Math. 18 (2004) 181-186.

DOI: 10.1016/j.endm.2004.06.029

[7] C. Lee, Z. Lee, S. Lin and K. Ying, An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem, Appl. Intell. 32 (2010) 88-95.

DOI: 10.1007/s10489-008-0136-9

[8] W.Y. Szeto, Y. Wu and S. C. Ho, An artificial bee colony algorithm for the capacitated vehicle routing problem, Eur. J. Oper. Res. 215 (2011) 126-135.

DOI: 10.1016/j.ejor.2011.06.006

[9] S. Lin, Z. Lee, K. Ying and C. Lee, Applying hybrid meta-heuristics for capacitated vehicle routing problem, Expert Syst. Appl. 36 (2009) 1505-1512.

DOI: 10.1016/j.eswa.2007.11.060

[10] H. Nazif and L. S. Lee, Optimised crossover genetic algorithm for capacitated vehicle routing problem, Appl. Math. Model. 36 (2012) 2110-2117.

DOI: 10.1016/j.apm.2011.08.010

[11] N. Jozefowiez, F. Semet and E. Talbi, Target aiming Pareto search and its application to the vehicle routing problem with route balancing, J. Heuristics. 13 (2007) 455-469.

DOI: 10.1007/s10732-007-9022-6

[12] N. Jozefowiez, F. Semet and E. Talbi, An evolutionary algorithm for the vehicle routing problem with route balancing, Eur. J. Oper. Res. 195 (2009) 761-769.

DOI: 10.1016/j.ejor.2007.06.065

[13] A. Konak, D. W. Coit and A. E. Smith, Multi-objective optimization using genetic algorithms: A tutorial, Reliab. Eng. Syst. Safe. 91 (2006) 992-1007.

DOI: 10.1016/j.ress.2005.11.018

[14] K. Ghoseiri and S. F. Ghannadpour, Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Appl. Soft Comput. 10 (2010) 1096-1107.

DOI: 10.1016/j.asoc.2010.04.001

[15] Benchmark instances and optimal solutions on http: /www. branchandcut. org/VRP/data.