Artykuły :: Telematics :: ATST**Tunning Parameters of Evolutionary Algorithm in Travelling Salesman Problem with Profits and Returns** J. KOSZELEW, A. PIWOĹSKA | 2011-06-27 13:39:17 |

J. KOSZELEW, A. PIWOĹSKA

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

Title:

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

Keywords:

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

Abstract:

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

Bibliography:

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.