Tunning parameters of evolutionary algorithm in Travelling Salesman Problem with profits and returns

• Autorzy: Koszelew J. , Piwońska A.
• Języki publikacji: EN

Abstrakty

EN

A huge number of papers studies Travelling Salesman Problem (TSP) in classical version. In standard TSP all cities must be visited and graph is completed. While this is indeed the case in many practical problems, there are many other practical problems where these assumptions are not valid. This paper presents a new evolutionary algorithm (EA) which solves TSP with profits and returns (TSPwPR). This version of TSP is often applied in Intelligent Transport Systems, especially in Vehicle Routing Problem (VRP). TSPwPR consists in finding a cycle which maximizes collected profit but does not exceed a given cost constraint. A graph which is considered in this problem can be not completed, salesman doesn't have to visit all cities and he can repeat (with zero profit) cities in his tour. The method was implemented and tested on real network which consists of 160 cities in eastern and central voivodeships of Poland. The main parameter which has the highest influence on quality of obtaining results is the size of population and our experiments are directed to determine an optimal value of this parameter.

Słowa kluczowe

EN

routing in transport networks; travelling salesman problem with profits; TSP; evolutionary algorithm

PL

sieć transportowa; TSP; algorytm ewolucyjny

• Wydawca: Polskie Stowarzyszenie Telematyki Transportu
• Czasopismo: Archives of Transport System Telematics
• Rocznik: 2010
• Tom: Vol. 3, iss. 1
• Strony: 17--22
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Koszelew J.

autor

Piwońska A.

• Faculty of Computer Science, Bialystok University of Technology, Wiejska 45a, 15-351 Białystok, Poland,

Bibliografia

• [1] FEILETT D., DEJAX P., GENDREAU M. : Traveling salesman problems with profits. In Transportation Science. Vol. 39, No. 2, pp. 188 205, 2005
• [2] GOLDBERG D. E: Genetic algorithms and their applications. The publishing company, Warsaw, 2nd edition, 2005
• [3] JOZEFOWICZ N. F. G., LAGUNA M.: Traveling salesman problems with profits. In Journal of Mathematical Modeling and Algorithms. Vol. 7, No. 2, pp. 177-195, 2008
• [4] LAWLER E., LENSTRA J., SHYMOYS A. H. G.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley&Sons, Chichester New York Brisbane Toronto Singapore, 1st edition, 1985
• [5] MICHALEWICZ Z.: Genetic Algorithms+Data Structures=Evolution Programs. WNT, Warsaw, 2nd edition, 1996
• [6] MITCHELL M.: An Introduction to Genetic Algorithms. MIT Press, Massachussets, 1st edition, 1998
• [7] QIN H., LIM A., XU, D.: The selective traveling salesman problem with regular working time windows. In Studies in Computational Intelligence. Vol. 214, pp. 291-296, 2009
• [8] SEVKLI Z., SEVILGEN F. E.: Variable neighbor hood search for the orienteering problem. In Lecture Notes on Computer Science. Vol. 4263, pp. 134-143, 2006
• [9] TASGETIREN M. F. :A genetic algorithm with an adaptive penalty function. In Journal of Economic and Social Research. Vol. 4 (2), pp. 1-26. , 2002
• [10] TONCI C., HRVOJE G., GALIC A., CAVAR I.: Vehicle Routing Problem Solving System as a CROGRID Application, Proceedings 4th European Congress on Intelligent Transport Systems, 24-26 May 2004, Budapest.