A Memetic Algorithm for a Tour Planning in the Selective Travelling Salesman Problem on a Road Network

The selective travelling salesman problem (STSP) appears in various applications. The paper presents a new version of this problem called the selective travelling salesman problem on a road network (R-STSP). While in the classical STSP a graph is complete and each vertex can be visited at most once, in R-STSP these two constraints are not obligatory which makes the problem more real-life and applicable. To solve the problem, the memetic algorithm (MA) is proposed. After implementing the MA, computer experiments were conducted on the real transport network in Poland. The comparative study of the MA with the genetic algorithm (GA) shows that the MA outperforms the GA.