An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows

被引:40
作者
Hame, Lauri [1 ]
机构
[1] Aalto Univ, Sch Sci & Technol, Aalto 00076, Finland
关键词
Transportation; Dial-a-ride problem; Exact algorithm; Heuristics; DESIRED DELIVERY TIMES; TO-MANY OPERATIONS; HEURISTIC ALGORITHM; PICKUP; TRANSPORTATION;
D O I
10.1016/j.ejor.2010.08.021
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The dial-a-ride problem (DARP) is a widely studied theoretical challenge related to dispatching vehicles in demand-responsive transport services, in which customers contact a vehicle operator requesting to be carried from specified origins to specified destinations. An important subproblem arising in dynamic dial-a-ride services can be identified as the single-vehicle DARP, in which the goal is to determine the optimal route for a single vehicle with respect to a generalized objective function. The main result of this work is an adaptive insertion algorithm capable of producing optimal solutions for a time constrained version of this problem, which was first studied by Psaraftis in the early 1980s. The complexity of the algorithm is analyzed and evaluated by means of computational experiments, implying that a significant advantage of the proposed method can be identified as the possibility of controlling computational work smoothly, making the algorithm applicable to any problem size. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码:11 / 22
页数:12
相关论文
共 36 条
[1]  
Attanasio A, 2004, PARALLEL COMPUT, V30, P377, DOI [10.1016/j.parco.2003.12.001, 10.1016/j.parco.2004.12.001]
[2]   A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows [J].
Bent, R ;
Van Hentenryck, P .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (04) :875-893
[3]   Dynamic pickup and delivery problems [J].
Berbeglia, Gerardo ;
Cordeau, Jean-Francois ;
Laporte, Gilbert .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (01) :8-15
[4]  
BIANCO L, 1994, INFOR, V32, P19
[5]  
Cordeau JF, 2007, HBK OPERAT RES MANAG, V14, P429, DOI 10.1016/S0927-0507(06)14007-4
[6]   The dial-a-ride problem: models and algorithms [J].
Cordeau, Jean-Francois ;
Laporte, Gilbert .
ANNALS OF OPERATIONS RESEARCH, 2007, 153 (01) :29-46
[7]   A branch-and-cut algorithm for the dial-a-ride problem [J].
Cordeau, Jean-Francois .
OPERATIONS RESEARCH, 2006, 54 (03) :573-586
[8]   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
[9]   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
[10]  
CORI R, 2009, SERIES A, V116, P1326