We consider a special version of the Travelling Salesman Problemwhich is to determine a tour visitingeach vertex in the graph at most one time;if a vertex is left unrouted a given penalty has to be paid.The objectivefunction is to find a balance between these penalties and the cost of thetour. We call this problem the Profitable Tour Problem (PTP). If,in addition, to each vertex is associated a price andthere is a knapsack constraint which guarantees that a sufficiently largeprice is collected, we have the well knownPrice-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. Moreoverwe show, through computational experiments, that large size instances of theAsymmetric PTP can be solved exactly.
On Prize-CollectingTours and the Asymmetric Travelling Salesman Problem / Dell'Amico, Mauro; F., Maffioli; P., Varbrand. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - STAMPA. - 2:(1995), pp. 297-308.
On Prize-CollectingTours and the Asymmetric Travelling Salesman Problem
DELL'AMICO, Mauro;
1995
Abstract
We consider a special version of the Travelling Salesman Problemwhich is to determine a tour visitingeach vertex in the graph at most one time;if a vertex is left unrouted a given penalty has to be paid.The objectivefunction is to find a balance between these penalties and the cost of thetour. We call this problem the Profitable Tour Problem (PTP). If,in addition, to each vertex is associated a price andthere is a knapsack constraint which guarantees that a sufficiently largeprice is collected, we have the well knownPrice-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. Moreoverwe show, through computational experiments, that large size instances of theAsymmetric PTP can be solved exactly.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris