Systematic construction of recombination operators for the vehicle routing problem

• Autorzy: Kubiak M.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a way of systematic construction of recombination operators for the vehicle routing problem by global convexity tests. It describes the vehicle routing problem and defines similarity measures for its solutions, and presents the results of global convexity tests; it has been demonstrated here that strong global convexity exists in almost all instances of the problem. Based on results of the tests some distance preserving recombination operators are defined. Computational experiments with a genetic local search indicate that these operators significantly ameliorate the search process and generate very good solutions. It is also shown that preservation, by an operator, of both of important features of solutions found in global convexity tests speeds up computation. The paper is, therefore, another evidence that systematic construction of recombination operators is a good means of adaptation of the genetic local search to a problem.

Słowa kluczowe

EN

vehicle routing problem; recombination operators

PL

trasowanie

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2004
• Tom: Vol. 29, No. 3
• Strony: 205--226
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Kubiak M.

• Poznań University of Technology, Institute of Computing Science, Piotrowo 3A, 60-965 Poznań, Poland,

Bibliografia

• [1] Aronson L. D., Algorithms for Vehicle Routing - a Survey, Report 96-21, Delft University of Technology, 1996.
• [2] Boese K. D., Cost Versus Distance in the Traveling Salesman Problem, Tech. Rep. TR-950018, UCLA CS Departament, 1995.
• [3] Christofides N., et al. (eds.), Combinatorial Optimization, John Wiley, Chichester, 1979.
• [4] Clarke G., Wright J., Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research, 12, 1964, 568-582.
• [5] Davis L., Adapting Operator Probabilities in Genetic Algorithms, in: J. Schaffer (ed.). Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, Morgan Kaufmann, San Mateo, CA, 1989, 61-69.
• [6] Fisher M. L., Optimal solution of vehicle routing problems using minimum K-trees, Operations Research, 42, 1994, 626-642.
• [7] Gillet B. E., Miller L. R., A Heuristic Algorithm for the Vehicle Dispatch Problem, Operations Research, 22, 1974, 340-349.
• [8] Jaszkiewicz A., Improving performance of genetic local search by changing local search space topology. Foundations of Computing and Decision Sciences, 24, 2, 1999.
• [9] Jaszkiewicz A., Kominek P., Genetic Local Search with Distance Preserving Recombination Operator for a Vehicle Routing Problem, European Journal of Operational Research, 2003, in preparation.
• [10] Jones T., Forrest S., Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, in: L. J. Eshelman (ed.). Proceedings of the 6th Int. Conference on Genetic Algorithms, Kaufmann, 1995, 184-192.
• [11] Lawler E. L., et al. (eds.), The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization, John Wiley & Sons, 1985.
• [12] Lenstra J. K., Rinnooy Kan A. H. G., Complexity of vehicle routing and scheduling problem. Networks, 11, 1981, 221-227.
• [13] Merz P., Freisleben B., Fitness Landscapes and Memetic Algorithms Design, in: D. Corne, et al. (eds.). New Ideas in Optimization, McGraw-Hill, 1999.
• [14] Merz P., Freisleben B., Fitness Landscape Analysis and Memetic Algorithms for the Quadratic Assignment Problem, IEEE Transactions on Evolutionary Computation, 4, 4, 2000, 337-352.
• [15] Merz P., Freisleben B., New Genetic Local Search Operators for the Traveling Salesman Problem, in: H.-M. Voigt, et al. (eds.), Proceedings of the 4th International Conference on Parallel Problem Solving from Nature - PPSN IV, Springer, 1996, 890-900.
• [16] Merz P, Freisleben B., Genetic Local Search for the TSP: New Results, in: Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, IEEE Press, 1997, 159-164.
• [17] Michalewicz Z., A Hierarchy of Evolution Programs: An Experimental Study, Evolutionary Computation, 1, 1, 1993, 51-76.
• [18] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Berlin Heidelberg, 1992.
• [19] Potvin J.-Y., Bengio S., The vehicle routing problem with time windows part ii: genetic search, INFORMS Journal of Computing, 8, 2, 1996.
• [20] Prins C., A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem, MIC’2001 - 4th Metaheuristics International Conference, July 2001.
• [21] Rochat Y., Taillard É. D., Probabilistic Diversification and Intensification in Local Search for Vehicle Routing, Journal of Heuristics, 1, 1995, 147-167.
• [22] Stadler P. F., Landscapes and their Correlation Functions, J. Math. Chem., 20, 1996, 1-45.
• [23] Taillard É. D., website with instances of VRP, http://www.eivd.ch/ina/Collaborateurs/etd/problemes.dir/vrp.dir/vrp.html.
• [24] Weinberger E. D., Correlated and Uncorrected Landscapes and How to Tell the Difference, Biological Cybernetics, 63, 1990, 325-336.
• [25] Wolpert D. H., Macready W. G., No Free Lunch Theorem for Optimization, IEEE Transactions on Evolutionary Computation, 1, I, 1997, 67-82.