Premium
On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
Author(s) -
Dell'Amico M.,
Maffioli F.,
Värbrand P.
Publication year - 1995
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1995.tb00023.x
Subject(s) - travelling salesman problem , knapsack problem , lin–kernighan heuristic , vertex (graph theory) , mathematical optimization , computer science , graph , combinatorial optimization , mathematics , combinatorics , bottleneck traveling salesman problem
We consider a variant of the Travelling Salesman Problem which is to determine a tour visiting each vertex in the graph at most at one time; if a vertex is left unrouted a given penalty has to be paid. The objective function is to find a balance between these penalties and the cost of the tour. We call this problem the Profitable Tour Problem(PTP). If, in addition, each vertex is associated with a prize and there is a knapsack constraint which guarantees that a sufficiently large prize is collected, we have the well‐known Prize‐collecting Travelling Salesman Problem (PCTSP). In this paper we summarize the main results presented in the literature, then we give lower bounds for the asymmetric version of PTP and PCTSP. Moreover, we show, through computational experiments, that large size instances of the asymmetric PTP can be solved exactly.