"Najlepszą metodą przewidywania przyszłości jest jej tworzenie" - Peter Drucker   

Główne Menu

Strona Główna

· O Stowarzyszeniu
· Wydarzenia
· Statut

Redakcja wortalu
· O Nas
· Kontakt

· Telematics
· Transport

· Słownik telematyczny
· Konferencje
· Polecamy
· Do pobrania



Artykuły :: Telematics :: ATST

Tunning Parameters of Evolutionary Algorithm in Travelling Salesman Problem with Profits and Returns
2011-06-27 13:39:17

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

Tunning Parameters of Evolutionary Algorithm in Travelling Salesman Problem with Profits and Returns

routing in transport networks, travelling salesman problem with profits, evolutionary algorithm

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

FEILETT D., DEJAX P., GENDREAU M. : Traveling salesman problems with profits. In Transportation Science. Vol. 39, No. 2, pp. 188 205, 2005
GOLDBERG D. E: Genetic algorithms and their applications. The publishing company, Warsaw, 2nd edition, 2005
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
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
MICHALEWICZ Z.: Genetic Algorithms+Data Structures=Evolution Programs. WNT, Warsaw, 2nd edition, 1996
MITCHELL M.: An Introduction to Genetic Algorithms. MIT Press, Massachussets, 1st edition, 1998
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
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
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
TONCI C., HRVOJE G., GALIC A., CAVAR I.: Vehicle Routing Problem Solving System as a CRO-GRID Application, Proceedings 4th European Congress on Intelligent Transport Systems, 24-26 May 2004, Budapest.




Załóż konto

Zapomniałem hasła

Nowe artykuły


Ogółem głosów: 0

Wyniki poprzednich ankiet