The capacitated team orienteering and profitable tour problems

被引：109

作者：

Archetti, C. ^{[1
]}

Feillet, D. ^{[2
]}

Hertz, A. ^{[3
,4
]}

Speranza, M. G.

机构：

[1] Univ Brescia, Dept Quantitat Methods, I-25122 Brescia, Italy

[2] Univ Avignon & Pays Vaucluse, Avignon, France

[3] Ecole Polytech, Montreal, PQ H3C 3A7, Canada

[4] Ecole Hautes Etud Commerciales, Gerad, Montreal, PQ, Canada

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 2009年 / 60卷 / 06期

关键词：

team orienteering problem; profitable tour problem; column generation; branch and price; tabu search; variable neighbourhood search; EXACT ALGORITHM; SEARCH;

D O I：

10.1057/palgrave.jors.2602603

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we study the capacitated team orienteering and profitable tour problems (CTOP and CPTP). The interest in these problems comes from recent developments in the use of the Internet for a better matching of demand and offer of transportation services. We propose exact and heuristic procedures for the CTOP and the CPTP. The computational results show that the heuristic procedures often find the optimal solution and in general cause very limited errors. Journal of the Operational Research Society (2009) 60, 831-842. doi: 10.1057/palgrave.jors.2602603 Published online 28 May 2008

引用

页码：831 / 842

页数：12

共 13 条

[1] Metaheuristics for the team orienteering problem
Archetti, Claudia
Hertz, Alain
Speranza, Maria Grazia
[J]. JOURNAL OF HEURISTICS, 2007, 13 (01) : 49 - 76
[2] An exact algorithm for team orienteering problems
Boussier, Sylvain
Feillet, Dominique
Gendreau, Michel
[J]. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (03): : 211 - 230
[3] A HEURISTIC FOR THE MULTIPLE TOUR MAXIMUM COLLECTION PROBLEM
BUTT, SE
CAVALIER, TM
[J]. COMPUTERS & OPERATIONS RESEARCH, 1994, 21 (01) : 101 - 111
[4] The team orienteering problem
Chao, IM
Golden, BL
Wasil, EA
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (03) : 464 - 474
[5] Christofides N., 1979, Combinatorial optimization, P315
[6] DESAULNIERS G, 2005, GERAD 25 ANNIVERSARY
[7] Traveling salesman problems with profits
Feillet, D
Dejax, P
Gendreau, M
[J]. TRANSPORTATION SCIENCE, 2005, 39 (02) : 188 - 205
[8] An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
Feillet, D
Dejax, P
Gendreau, M
Gueguen, C
[J]. NETWORKS, 2004, 44 (03) : 216 - 229
[9] FEILLET D, 2005, CRT200508
[10] A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM
GENDREAU, M
HERTZ, A
LAPORTE, G
[J]. MANAGEMENT SCIENCE, 1994, 40 (10) : 1276 - 1290

← 1 2 →