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.
1995
2
297
308
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.
Dell'Amico, Mauro; F., Maffioli; P., Varbrand
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/770498
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 89
  • ???jsp.display-item.citation.isi??? ND
social impact