The dial-a-ride problem: models and algorithms

被引:580
作者
Cordeau, Jean-Francois [1 ]
Laporte, Gilbert [1 ]
机构
[1] Ecole Hautes Etud Commerciales, Gerad, Montreal, PQ H3T 2A7, Canada
关键词
dial-a-ride problem; survey; static and dynamic pickup and delivery problems;
D O I
10.1007/s10479-007-0170-8
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pickup and delivery requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and a summary of the most important models and algorithms is provided.
引用
收藏
页码:29 / 46
页数:18
相关论文
共 43 条
[1]   Hybrid scheduling methods for paratransit operations [J].
Aldaihani, M ;
Dessouky, MM .
COMPUTERS & INDUSTRIAL ENGINEERING, 2003, 45 (01) :75-96
[2]  
Barnhart C, 2007, HBK OPERAT RES MANAG, V14, P1
[3]  
Bodin L.D., 1986, TIMS Studies in the Management Sciences, V2, P73
[4]  
BORNDORFER R, 1997, SC9723 KONR ZUS ZENT
[5]   Ambulance location and relocation models [J].
Brotcorne, L ;
Laporte, G ;
Semet, F .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 147 (03) :451-463
[6]   An effective and fast heuristic for the Dial-a-Ride problem [J].
Calvo, Roberto Wolfler ;
Colorni, Alberto .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (01) :61-73
[7]  
Colorni A., 2001, International Transactions in Operational Research, V8, P155, DOI 10.1111/1475-3995.00256
[8]   A branch-and-cut algorithm for the dial-a-ride problem [J].
Cordeau, Jean-Francois .
OPERATIONS RESEARCH, 2006, 54 (03) :573-586
[9]   The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms [J].
Cordeau, Jean-Francois ;
Laporte, Gilbert .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (02) :89-101
[10]   A tabu search heuristic for the static multi-vehicle dial-a-ride problem [J].
Cordeau, JF ;
Laporte, G .
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2003, 37 (06) :579-594