An adaptive large neighborhood search heuristic for the share-a-ride problem

被引：85

作者：

Li, Baoxiang ^{[1
]}

Krushinsky, Dmitry ^{[1
]}

Van Woensel, Tom ^{[1
]}

Reijers, Hajo A. ^{[2
,3
]}

机构：

[1] Eindhoven Univ Technol, Dept Ind Engn & Innovat Sci, NL-5612 AZ Eindhoven, Netherlands

[2] Vrije Univ Amsterdam, Dept Comp Sci, Amsterdam, Netherlands

[3] Eindhoven Univ Technol, Dept Math & Comp Sci, NL-5612 AZ Eindhoven, Netherlands

来源：

COMPUTERS & OPERATIONS RESEARCH | 2016年 / 66卷

关键词：

Transportation; The Share-a-Ride Problem (SARP); Adaptive large neighborhood search; Slack time; DELIVERY PROBLEM; PICKUP;

D O I：

10.1016/j.cor.2015.08.008

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The Share-a-Ride Problem (SARP) aims at maximizing the profit of serving a set of passengers and parcels using a set of homogeneous vehicles. We propose an adaptive large neighborhood search (ALNS) heuristic to address the SARP. Furthermore, we study the problem of determining the time slack in a SARP schedule. Our proposed solution approach is tested on three sets of realistic instances. The performance of our heuristic is benchmarked against a mixed integer programming (MIP) solver and the Dial-a-Ride Problem (DARP) test instances. Compared to the MIP solver, our heuristic is superior in both the solution times and the quality of the obtained solutions if the CPU time is limited. We also report new best results for two out of twenty benchmark DARP instances. (c) 2015 Elsevier Ltd. All rights reserved.

引用

页码：170 / 180

页数：11

共 16 条

[1]

Battarra M, 2014, MOS-SIAM SER OPTIMIZ, P161

[2] 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

[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] 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

[5] 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

[6] An adaptive large neighborhood search heuristic for the Pollution-Routing Problem [J].

Demir, Emrah ;

Bektas, Tolga ;

Laporte, Gilbert .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 223 (02) :346-359

[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] An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows [J].

Hame, Lauri .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 209 (01) :11-22

[9] Heuristics for the one-commodity pickup-and-delivery traveling salesman problem [J].

Hernández-Pérez, H ;

Salazar-González, JJ .

TRANSPORTATION SCIENCE, 2004, 38 (02) :245-255

[10] The Share-a-Ride Problem: People and parcels sharing taxis [J].

Li, Baoxiang ;

Krushinsky, Dmitry ;

Reijers, Hajo A. ;

Van Woensel, Tom .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 238 (01) :31-40

← 1 2 →