Incomplete Service and Split Deliveries in a Routing Problem with Profits

被引：8

作者：

Archetti, Claudia ^{[1
]}

Bianchessi, Nicola ^{[1
]}

Speranza, M. Grazia ^{[1
]}

Hertz, Alain ^{[2
,3
]}

机构：

[1] Univ Brescia, Dept Quantitat Methods, Brescia, Italy

[2] Ecole Polytech, Dept Math & Ind Engn, Montreal, PQ H3C 3A7, Canada

[3] HEC, Gerad, Montreal, PQ, Canada

来源：

NETWORKS | 2014年 / 63卷 / 02期

关键词：

routing problems with profits; worst-case analysis; branch-and-price algorithm; tabu search; split delivery; ORIENTEERING PROBLEM;

D O I：

10.1002/net.21529

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this article, we study a variant of the capacitated team orienteering problem, that is the problem where a fleet of vehicles, each with a constraint on the time available, is given to serve profitable customers with the objective of maximizing the collected profit. We study the variant where customers may be only partially served (incomplete service) and, if beneficial, also by more than one vehicle (split deliveries). We will analyze the maximum theoretical increase of the profit due to the incomplete service and to the split deliveries. We also computationally measure such increase on a set of instances, by means of an exact algorithm on small/medium size instances and of two heuristics on instances of larger size. (c) 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 135-145 2014

引用

页码：135 / 145

页数：11

共 14 条

[1]

[Anonymous], 2002, The vehicle routing problem pp

[2] Worst-case analysis for split delivery vehicle routing problems [J].

Archetti, C ;

Savelsbergh, MWP ;

Speranza, MG .

TRANSPORTATION SCIENCE, 2006, 40 (02) :226-234

[3] A tabu search algorithm for the split delivery vehicle routing problem [J].

Archetti, C ;

Speranza, MG ;

Hertz, A .

TRANSPORTATION SCIENCE, 2006, 40 (01) :64-73

[4] A Column Generation Approach for the Split Delivery Vehicle Routing Problem [J].

Archetti, C. ;

Bianchessi, N. ;

Speranza, M. G. .

NETWORKS, 2011, 58 (04) :241-254

[5] The capacitated team orienteering and profitable tour problems [J].

Archetti, C. ;

Feillet, D. ;

Hertz, A. ;

Speranza, M. G. .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2009, 60 (06) :831-842

[6]

Archetti C., NETWORKS IN PRESS

[7]

Archetti C, 2008, OPER RES COMPUT SCI, V43, P103, DOI 10.1007/978-0-387-77778-8_5

[8] A lower bound for the split delivery vehicle routing problem [J].

Belenguer, JM ;

Martinez, MC ;

Mota, E .

OPERATIONS RESEARCH, 2000, 48 (05) :801-810

[9] A HEURISTIC FOR THE MULTIPLE TOUR MAXIMUM COLLECTION PROBLEM [J].

BUTT, SE ;

CAVALIER, TM .

COMPUTERS & OPERATIONS RESEARCH, 1994, 21 (01) :101-111

[10] The team orienteering problem [J].

Chao, IM ;

Golden, BL ;

Wasil, EA .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (03) :464-474

← 1 2 →