Traveling Salesman Problems with Profits

Dominique Feillet (), Pierre Dejax () and Michel Gendreau ()
Additional contact information
Dominique Feillet: Laboratoire d’Informatique d’Avignon, 339 Chemin des Meinajariés, BP 1228, 84000 Avignon, France
Pierre Dejax: École des Mines de Nantes, and Communications and Cybernetic Research Institute of Nantes, 4, rue Alfred Kastler, 44307 Nantes, France
Michel Gendreau: Center for Research on Transportation, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, Canada H3C 3J7

Transportation Science, 2005, vol. 39, issue 2, 188-205

Abstract: Traveling salesman problems with profits (TSPs with profits) are a generalization of the traveling salesman problem (TSP), where it is not necessary to visit all vertices. A profit is associated with each vertex. The overall goal is the simultaneous optimization of the collected profit and the travel costs. These two optimization criteria appear either in the objective function or as a constraint. In this paper, a classification of TSPs with profits is proposed, and the existing literature is surveyed. Different classes of applications, modeling approaches, and exact or heuristic solution techniques are identified and compared. Conclusions emphasize the interest of this class of problems, with respect to applications as well as theoretical results.

Keywords: vehicle routing; traveling salesman problem; selective TSP; weighted girth problem; prize-collecting TSP (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (92)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0079 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:39:y:2005:i:2:p:188-205

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().