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 条

[41] Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints [J].

Parragh, Sophie N. ;

Cordeau, Jean-Francois ;

Doerner, Karl F. ;

Hartl, Richard F. .

OR SPECTRUM, 2012, 34 (03) :593-633

[42] New online reinsertion approaches for a dynamic Dial-a-Ride Problem [J].

Vallee, S. ;

Oulamara, A. ;

Cherif-Khettaf, W. Ramdane .

JOURNAL OF COMPUTATIONAL SCIENCE, 2020, 47

[43] Solving a selective dial-a-ride problem with logic-based Benders decomposition [J].

Riedler, Martin ;

Raidl, Guenther .

COMPUTERS & OPERATIONS RESEARCH, 2018, 96 :30-54

[44] A HYBRID GREEDY RANDOMIZED ADAPTIVE SEARCH HEURISTIC TO SOLVE THE DIAL-A-RIDE PROBLEM [J].

Guerriero, Francesca ;

Bruni, Maria Elena ;

Greco, Francesca .

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2013, 30 (01)

[45] A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem [J].

Berbeglia, Gerardo ;

Cordeau, Jean-Francois ;

Laporte, Gilbert .

INFORMS JOURNAL ON COMPUTING, 2012, 24 (03) :343-355

[46] Choice-driven dial-a-ride problem for demand responsive mobility service [J].

Azadeh, Sh. Sharif ;

Atasoy, Bilge ;

Ben-Akiva, Moshe E. ;

Bierlaire, M. ;

Maknoon, M. Y. .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2022, 161 :128-149

[47] An Asymmetric Multiple Traveling Salesman Problem with Backhauls to solve a Dial-a-Ride Problem [J].

Osaba, E. ;

Onieva, E. ;

Diaz, F. ;

Carballedo, R. ;

Lopez, P. ;

Perallos, A. .

2015 IEEE 13TH INTERNATIONAL SYMPOSIUM ON APPLIED MACHINE INTELLIGENCE AND INFORMATICS (SAMI), 2015, :151-156

[48] The dial-a-ride problem in primary care with flexible scheduling [J].

Rauh, Felix ;

Ahrens, Emma ;

Buesing, Christina ;

Comis, Martin ;

Engelhardt, Felix .

OR SPECTRUM, 2025,

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

Sin C. Ho ;

Dag Haugland .

OR Spectrum, 2011, 33 :961-988

[50] Dynamic programming based metaheuristics for the dial-a-ride problem [J].

Ritzinger, Ulrike ;

Puchinger, Jakob ;

Hartl, Richard F. .

ANNALS OF OPERATIONS RESEARCH, 2016, 236 (02) :341-358

← 1 2 3 4 5 →