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

B. Li; D. Krushynskyi; T. van Woensel; H.A. Reijers

doi:10.1016/j.cor.2015.08.008

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

B. Li
, D. Krushynskyi
, T. van Woensel
, H.A. Reijers

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

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.

Original language	English
Pages (from-to)	170-180
Journal	Computers and Operations Research
Volume	66
DOIs	https://doi.org/10.1016/j.cor.2015.08.008
Publication status	Published - 2016

Access to Document

10.1016/j.cor.2015.08.008

Persistent URL (handle)

Persistent link

Cite this

@article{8b20fe1add144bf9a49ac3c6f478e82f,

title = "An adaptive large neighborhood search heuristic for the share-a-ride problem",

abstract = "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.",

author = "B. Li and D. Krushynskyi and \{van Woensel\}, T. and H.A. Reijers",

year = "2016",

doi = "10.1016/j.cor.2015.08.008",

language = "English",

volume = "66",

pages = "170--180",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

TY - JOUR

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

AU - Li, B.

AU - Krushynskyi, D.

AU - van Woensel, T.

AU - Reijers, H.A.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1016/j.cor.2015.08.008

DO - 10.1016/j.cor.2015.08.008

M3 - Article

SN - 0305-0548

VL - 66

SP - 170

EP - 180

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

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

Abstract

Access to Document

Persistent URL (handle)

Fingerprint

Cite this