Synchronized dial-a-ride transportation of disabled passengers at airports

被引:55
作者
Reinhardt, Line Blander [1 ]
Clausen, Tommy [1 ,2 ]
Pisinger, David [1 ]
机构
[1] Tech Univ Denmark, DK-2800 Lyngby, Denmark
[2] SITA WorkBridge AS, DK-1127 Copenhagen K, Denmark
关键词
Airport operations; Transportation planning; PRM; Heuristics; Simulated annealing; Dial-a-ride; TIME WINDOWS; CONSTRAINTS; ALGORITHMS; BRANCH; MODELS;
D O I
10.1016/j.ejor.2012.09.008
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The largest airports have a daily average throughput of more than 500 passengers with reduced mobility. The problem of transporting these passengers is in some cases a multi-modal transportation problem with synchronization constraints. A description of the problem together with a mathematical model is presented. The objective is to schedule as many of the passengers as possible, while ensuring a smooth transport with short waiting times. A simulated annealing based heuristic for solving the problem is presented. The algorithm makes use of an abstract representation of a candidate solution which in each step is transformed to an actual schedule by use of a greedy heuristic. Local search is performed on the abstract representation using advanced neighborhoods which modify large parts of the candidate solution. Computational results show that the algorithm is able to find good solutions within a couple of minutes, making the algorithm applicable for dynamic scheduling. Moreover high-quality solutions can be obtained by running the algorithm for 10 minutes. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:106 / 117
页数:12
相关论文
共 18 条
[1]   Intractability of the dial-a-ride problem and a multiobjective solution using simulated annealing [J].
Baugh, JW ;
Kakivaya, GKR ;
Stone, JR .
ENGINEERING OPTIMIZATION, 1998, 30 (02) :91-123
[2]   Multiple crossdocks with inventory and time windows [J].
Chen, P ;
Guo, YS ;
Lim, A ;
Rodrigues, B .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (01) :43-63
[3]   The dial-a-ride problem: models and algorithms [J].
Cordeau, Jean-Francois ;
Laporte, Gilbert .
ANNALS OF OPERATIONS RESEARCH, 2007, 153 (01) :29-46
[4]   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
[5]   The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method [J].
Cortes, Cristian E. ;
Matamala, Martin ;
Contardo, Claudio .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (03) :711-724
[6]   Models for Evaluating and Planning City Logistics Systems [J].
Crainic, Teodor Gabriel ;
Ricciardi, Nicoletta ;
Storchi, Giovanni .
TRANSPORTATION SCIENCE, 2009, 43 (04) :432-454
[7]   A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows [J].
Diana, M ;
Dessouky, MM .
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2004, 38 (06) :539-557
[8]   The Vehicle Routing Problem with Time Windows and Temporal Dependencies [J].
Dohn, Anders ;
Rasmussen, Matias Sevel ;
Larsen, Jesper .
NETWORKS, 2011, 58 (04) :273-289
[9]  
Flower A., 2009, GATWICK MANAGING DIR
[10]   Fleet assignment and routing with schedule synchronization constraints [J].
Ioachim, I ;
Desrosiers, J ;
Soumis, F ;
Bélanger, N .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 119 (01) :75-90