Traveling salesman problems with profits

被引：408

作者：

Feillet, D

Dejax, P

Gendreau, M

机构：

[1] Lab Informat Avignon, F-84000 Avignon, France

[2] Ecole Mines Nantes, Commun & Cybernet Res Inst Nantes, F-44307 Nantes, France

[3] Univ Montreal, Ctr Res Transportat, Montreal, PQ H3C 3J7, Canada

来源：

TRANSPORTATION SCIENCE | 2005年 / 39卷 / 02期

关键词：

vehicle routing; traveling salesman problem; selective TSP; weighted girth problem; prize-collecting TSP;

D O I：

10.1287/trsc.1030.0079

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：188 / 205

页数：18

共 99 条

[1] Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].