Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem

The prize collecting traveling salesman problem (PCTSP) is a generalization of the traveling salesman problem (TSP) in which a tour starting at a root node must visit a subset of nodes to collect a prescribed amount of total prize minimizing the summation of travel costs and penalty costs associated with nonvisited nodes. We propose new formulations and compare them with adaptations to the PCTSP of strong formulations from the literature for the asymmetric TSP. One of the formulations proposed in this paper provided the tighter linear relaxation bounds on computational experiments based on benchmark instances for the asymmetric TSP. We then develop a Lagrangian relaxation approach embedding heuristic schemes to obtain both lower and upper bounds. The proposed heuristic has shown to be successful in obtaining optimal or near-optimal solutions with information from the Lagrangian subproblems. Our Lagrangian approach can thereupon provide small optimality gaps, being an efficient alternative to bound optimal values of large instances.

Automated summary

This study focuses on the prize collecting traveling salesman problem, proposing new formulations and comparing them with adaptations of strong formulations. By using a Lagrangian relaxation approach with heuristic schemes, the study successfully obtains optimal or near-optimal solutions.