A Matheuristic for the Dial-a-Ride Problem

被引：0

作者：

Calvo, Roberto Wolfler ^{[1
]}

Touati-Moungla, Nora ^{[2
]}

机构：

[1] 99 Ave J-B Clement, F-93430 Villetaneuse, France

[2] Ecole Polytech, Lab Informat LIX, F-91128 Palaiseau, France

来源：

NETWORK OPTIMIZATION | 2011年 / 6701卷

关键词：

VEHICLE-ROUTING PROBLEM; TABU SEARCH; TIME WINDOWS; DELIVERY PROBLEM; ALGORITHMS; PICKUP; BRANCH; CUT;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Dial-a-Ride is a transport system on demand. A fleet of vehicles, without fixed routes and schedules, carries people from their pickup points to their delivery points, during a pre-specified time interval. It can be modeled as an NP-hard routing and scheduling problem, with a suitable mixed integer programming formulation. Exact approaches to this problem are too limited to tackle real-life instances: time dependent network, requests received on-line, different objective functions. In this paper we propose an algorithm to solve the off-line Dial-a-Ride Problem (DARP), based on a Granular Tabu Search method. This algorithm was fast and effective, when tested on instances created ad hoc using the Milan network.

引用

页码：450 / 463

页数：14

共 50 条

[31] Dial-a-ride problem with modular platooning and en-route transfers [J].

Fu, Zhexi ;

Chow, Joseph Y. J. .

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2023, 152

[32] Taxi-sharing: Parameterized complexity and approximability of the dial-a-ride problem with money as an incentive [J].

Watel, Dimitri ;

Faye, Alain .

THEORETICAL COMPUTER SCIENCE, 2018, 745 :202-223

[33] Local search heuristics for the probabilistic dial-a-ride problem [J].

Ho, Sin C. ;

Haugland, Dag .

OR SPECTRUM, 2011, 33 (04) :961-988

[34] A hybrid Genetic Algorithm for the Heterogeneous Dial-A-Ride Problem [J].

Masmoudi, Mohamed Amine ;

Braekers, Kris ;

Masmoudi, Malek ;

Dammak, Abdelaziz .

COMPUTERS & OPERATIONS RESEARCH, 2017, 81 :1-13

[35] Adaptive large neighborhood search for the time-dependent profitable dial-a-ride problem [J].

Zhao, Jingyi ;

Poon, Mark ;

Zhang, Zhenzhen ;

Gu, Ruixue .

COMPUTERS & OPERATIONS RESEARCH, 2022, 147

[36] An integer L-shaped algorithm for the Dial-a-Ride Problem with stochastic customer delays [J].

Heilporn, Geraldine ;

Cordeau, Jean-Francois ;

Laporte, Gilbert .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (09) :883-895

[37] A Sample Average Approximation Approach for the Stochastic Dial-A-Ride Problem on a Multigraph with User Satisfaction [J].

Lu, Chang ;

Wu, Yuehui ;

Yu, Shanchuan .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 302 (03) :1031-1044

[38] The multi-vehicle dial-a-ride problem with interchange and perceived passenger travel times [J].

Gkiotsalitis, K. ;

Nikolopoulou, A. .

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2023, 156

[39] Anticipation in the Dial-a-Ride Problem: an introduction to the robustness [J].

Deleplanque, Samuel ;

Derutin, Jean-Pierre ;

Quilliot, Alain .

2013 FEDERATED CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS (FEDCSIS), 2013, :299-305

[40] An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization [J].

Pfeiffer, Christian ;

Schulz, Arne .

OR SPECTRUM, 2022, 44 (01) :87-119

← 1 2 3 4 5 →