Content area
Full Text
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.
Key words: vehicle routing; traveling salesman problem; selective TSP; weighted girth problem; prize-collecting TSP
History: Received: June 2001; revision received: April 2003; accepted: April 2003.
1. Introduction
The traveling salesman problem (TSP) and the vehicle routing problem (VRP) are among the most widely studied combinatorial optimization problems. Both problems, as well as their numerous extensions, deal with optimally visiting customers from a central depot. A very large number of papers and books deal with these problems (Gutin and Punnen 2002; Toth and Vigo 2001). Two usual characteristics of these problems are that every customer has to be serviced and that, consequently, no value is associated to the service. However, some variant problems propose to select customers depending on a profit value that is gained when the visit occurs. This feature gives rise to a number of problems that we gather together under the name of traveling salesman problems with profits (TSPs with profits), when a single vehicle is involved. More general problems in which several vehicles might be involved are called routing problems with profits. In this article we review the existing literature on these problems, with a focus on TSPs with profits, which have been more widely studied.
TSPs with profits may be seen as bicriteria TSPs with two opposite objectives, one pushing the salesman to travel (to collect profit) and the other inciting him to minimize travel costs (with the right to drop vertices). Viewed in this light, solving TSPs with profits should result in finding a noninferior solution set, i.e., a set of feasible solutions such that neither...