Title :
A Genetic Algorithm with a Penalty Function in the Selective Travelling Salesman Problem on a Road Network
Author :
Piwonska, Anna ; Seredynski, Franciszek
Author_Institution :
Fac. of Comput. Sci., Bialystok Univ. of Technol., Bialystok, Poland
Abstract :
The Selective Travelling Salesman Problem (STSP) is a version of the Travelling Salesman Problem (TSP) where it is not necessary to visit all vertices. Instead of it, with each vertex a number meaning a profit is associated. The problem is to find a cycle which maximizes collected profit but does not exceed a given cost constraint. A direct application of the STSP, e.g. in Intelligent Transportation Systems, is finding an optimal tour in road networks. However, while the classic STSP is defined on a complete graph, a road network is in general not complete and often has a rather sparse edge set. This paper presents the STSP defined on a road network (R-STSP). Since R-STSP is NP-hard and stands the problem with a constraint, the genetic algorithm (GA) with a penalty function is proposed. Computer experiments performed on the real road network in Poland have shown that this GA outperforms the GA searching only the feasible solution space.
Keywords :
genetic algorithms; road traffic; travelling salesman problems; GA penalty function; Poland; genetic algorithm; intelligent transportation system; road network; selective travelling salesman problem; Biological cells; Cities and towns; Computer science; Genetic algorithms; Genetics; Roads; Search problems;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.177