2005/04/29 by Dominique Feillet, Pierre Dejax, Michel Gendreau · 4 citations
Computer Science · Engineering · #Metaheuristic Optimization Algorithms Research #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · doi:10.1287/trsc.1030.0079
openalex publication_date 2005/04/29 · crossref created 2005/04/29 · crossref issued 2005/05/01 · crossref published 2005/05/01 · crossref published-print 2005/05/01 · crossref deposited 2023/04/02 · openalex created_date 2025/10/10 · crossref indexed 2026/07/31 · openalex updated_date 2026/07/31
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.