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 条

[21] Data-Oriented Approach for the Dial-A-Ride Problem [J].

Alisoltani, Negin ;

Zargayouna, Mandi ;

Leclercq, Ludovic .

2019 IEEE/ACS 16TH INTERNATIONAL CONFERENCE ON COMPUTER SYSTEMS AND APPLICATIONS (AICCSA 2019), 2019,

[22] A deterministic annealing local search for the electric autonomous dial-a-ride problem [J].

Su, Yue ;

Dupin, Nicolas ;

Puchinger, Jakob .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 309 (03) :1091-1111

[23] The Dial-a-Ride Problem with School Bell Time Adjustment [J].

Vercraene, Samuel ;

Lehuede, Fabien ;

Monteiro, Thibaud ;

Peton, Olivier .

TRANSPORTATION SCIENCE, 2023, 57 (01) :156-173

[24] Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem [J].

Gschwind, Timo ;

Irnich, Stefan .

TRANSPORTATION SCIENCE, 2015, 49 (02) :335-354

[25] A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare [J].

Detti, Paolo ;

Papalini, Francesco ;

de lara, Garazi Zabalo Manrique .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2017, 70 :1-14

[26] Letting a Large Neighborhood Search for an Electric Dial-A-Ride Problem Fly: On-The-Fly Charging Station Insertion [J].

Bresich, Maria ;

Raidl, Guenther R. ;

Limmer, Steffen .

PROCEEDINGS OF THE 2024 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, GECCO 2024, 2024, :142-150

[27] Interrelated trips in the rural dial-a-ride problem with autonomous vehicles [J].

Johnsen, Lennart C. ;

Meisel, Frank .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 303 (01) :201-219

[28] Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem [J].

Gschwind, Timo ;

Drexl, Michael .

TRANSPORTATION SCIENCE, 2019, 53 (02) :480-491

[29] A multi-period dial-a-ride problem with driver consistency [J].

Braekers, Kris ;

Kovacs, Attila A. .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2016, 94 :355-377

[30] Multi-objective optimization in dial-a-ride public transportation [J].

Guerriero, Francesca ;

Pezzella, Ferdinando ;

Pisacane, Ornella ;

Trollini, Luigi .

17TH MEETING OF THE EURO WORKING GROUP ON TRANSPORTATION, EWGT2014, 2014, 3 :299-308

← 1 2 3 4 5 →