In this paper we consider the Prize Collecting Travelling Salesman Problem (PCTSP), that is a variant of the Travelling Salesman Problem (TSP) where a tour visiting each node at most once in a given graph has to be computed, such that a prize is associated with each node and a penalty has to be paid for every unvisited node; moreover, a knapsack constraint guarantees that a sufficiently large prize is collected. We develop a Lagrangean heuristic and obtain an upper bound in the form of a feasible solution starting from a lower bound to the problem recently proposed in the literature. We evaluate these bounds utilizing both randomly generated instances and real ones with very satisfactory results.

A Lagrangean Heuristic for Prize Collecting Travelling Salesman Problem / Dell'Amico, Mauro; F., Maffioli; A., Sciomachen. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - STAMPA. - 81:(1998), pp. 289-305.

A Lagrangean Heuristic for Prize Collecting Travelling Salesman Problem

DELL'AMICO, Mauro;
1998-01-01

Abstract

In this paper we consider the Prize Collecting Travelling Salesman Problem (PCTSP), that is a variant of the Travelling Salesman Problem (TSP) where a tour visiting each node at most once in a given graph has to be computed, such that a prize is associated with each node and a penalty has to be paid for every unvisited node; moreover, a knapsack constraint guarantees that a sufficiently large prize is collected. We develop a Lagrangean heuristic and obtain an upper bound in the form of a feasible solution starting from a lower bound to the problem recently proposed in the literature. We evaluate these bounds utilizing both randomly generated instances and real ones with very satisfactory results.
81
289
305
A Lagrangean Heuristic for Prize Collecting Travelling Salesman Problem / Dell'Amico, Mauro; F., Maffioli; A., Sciomachen. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - STAMPA. - 81:(1998), pp. 289-305.
Dell'Amico, Mauro; F., Maffioli; A., Sciomachen
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/770491
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 34
  • ???jsp.display-item.citation.isi??? ND
social impact