Analysis of distance between vehicle routing problem solutions generated by memetic algorithms

• Autorzy: Kubiak M.
• Konferencja: Evolutionary Computation and Global Optimization 2006 / National Conference (9 ; 31.05-2.06.2006 ; Murzasichle, Poland)
• Języki publikacji: EN

Abstrakty

EN

This paper focuses on analysis of distance between solutions of the capacitated vehicle routing problem generated by memetic algorithms with different crossover operators. The goal of the analysis is to see what are relative positions of such solutions in search spaces and if different algorithms explore different parts of these spaces. In the described memetic algorithms five different crossover operators are used. The conducted computational experiment shows that solutions generated by the algorithms have very similar, very good quality. From the distance analysis it appears that there are two types of instances of the considered problem: 10 instances have very similar solutions, concentrated in small regions of spaces ('big valleys'), while other 12 have good solutions which reside in different parts of search spaces, implying wide and flat regions of good solutions.

Słowa kluczowe

EN

evolutionary computation; evolutionary algorithm; EA; vehicle routing problem; memetic algorithm; optimization

PL

obliczenia ewolucyjne; algorytm ewolucyjny; problem marszrutyzacji; algorytm memetyczny; optymalizacja

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2006
• Tom: z. 156
• Strony: 223--236
• Opis fizyczny: Bibliogr. 19 poz., tab., rys., wykr.

Twórcy

autor

Kubiak M.

• Poznań University of Technology, Institute of Computing Science, Poznań, Poland,

Bibliografia

• [1] Boese, K.D. (1995): "Cost versus distance in the traveling salesman problem". Technical Report [TR-950018]. UCLA CS Department, California, USA.
• [2] Clarke, G. and Wright, J. (1964): "Scheduling of vehicles from a central depot to a number of delivery points". In: Operations Research, 12, 568-582.
• [3] Fisher, M.L. (1994): "Optimal solution of vehicle routing problems using minimum K-trees". In: Operations Research, 42, 626-642.
• [4] Gillet, B.E. and Miller, L.R. (1974): "A heuristic algorithm for the vehicle dispatch problem". In: Operations Research, 22, 340-349.
• [5] Jaszkiewicz, A. and Kominek, P. (2003): "Genetic local search with distance preserving recombination operator for a vehicle routing problem". In: European Journal of Operational Research, 151, 352-364.
• [6] Jaszkiewicz, A., Kominek, P. and Kubiak, M. (2004): "Adaptation of the genetic local search algorithm to a car sequencing problem". In: Proceedings of the 2004 National Conference on Evolutionary Algorithms and Global Optimization, Kazimierz Dolny, Poland, May 2004.
• [7] Jones, T. and Forrest, S. (1995): "Fitness distance correlation as a measure of problem difficulty for genetic algorithms". Santa Fe Institute Working Paper 95-02-022.
• [8] Jozefowicz, N., Semet, F. and Talbi, E. (2002): "Parallel and hybrid models for multi-objective optimization: application to the vehicle routing problem". In: Proceedings of the Parallel Problem Solving from Nature.
• [9] Kubiak, M. (2004): "Systematic construction of recombination operators for the vehicle routing problem". In: Foundations of Computing and Decision Sciences, 29 (3), 205-226.
• [10] Kubiak, M. (2005): "Distance metrics and fitness-distance analysis for the capacitated vehicle routing problem". In: MIC2005, 6th Metaheuristics International Conference, Vienna, Austria, July 2005.
• [11] Merz, P. (2004): "Advanced fitness landscape analysis and the performance of memetic algorithms". In: Evolutionary Computation, 12 (3), 303-325.
• [12] Merz, P. and Freisleben, B. (1999): "Fitness landscapes and memetic algorithms design". In: D. Corne, et al. (eds.), New Ideas in Optimization, McGraw-Hill.
• [13] Merz, P. and Freisleben, B. (2000): "Fitness landscape analysis and memetic algorithms for the quadratic assignment problem". In: IEEE Transactions on Evolutionary Computation, 4 (4), 337-352.
• [14] Potvin, J.-Y. and Bengio, S. (1996): "The vehicle routing problem with time windows part II: genetic search". In: INFORMS Journal of Computing, 8 (2).
• [15] Prins, C. (2001): "A simple and effective evolutionary algorithm for the vehicle routing problem. In: MIC2001, 4th Metaheuristics International Conference, July 2001.
• [16] Rochat, Y. and Taillard, E.D. (1995): "Probabilistic diversification and intensification in local search for vehicle routing". In: Journal of Heuristics, 1, 147-167.
• [17] Sneath, P.H.A. and Sokal, R.R. (1973): "Numerical Taxonomy". Freeman & Co., San Francisco.
• [18] Tavares, J., et al. (2003): "On the influence of GVR in vehicle routing". SAC'2003, Melbourne, Florida, USA.
• [19] Watson, J.P, et al. (1998): "The travelling salesrep problem, edge assembly crossover and 2-opt". In: Parallel Problem Solving from Nature (PPSN-V).