A Novel Method for Prize Collecting Traveling Salesman Problem with Time Windows

Abstract

Traveling salesman problem (TSP) is a well-known problem that has been studied for a long time. Prize Collecting Traveling Salesman Problem with Time Windows (PCTSPTW) is a variant of TSP that includes time windows constraints for each customer to be visited and prize for visited nodes. This paper presents a novel method for solving the PCTSPTW. There are two stages in the proposed method. First stage is a novel constructive heuristic for finding solutions by using a three dimensional distance matrix with time windows. Third dimension of the distance matrix is generated dynamically by the time window constraints defined on the nodes. In the constructive heuristic phase, an initial population of solutions is generated which contain solutions that are close to the best generated solution within a threshold value. Then, in the second stage, a genetic algorithm is implemented for making improvements on generated solutions. Results of computational experiments present that our approach outperforms the ones given in the literature. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.