Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/17692
Title: | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots | Authors: | BRAEKERS, Kris CARIS, An JANSSENS, Gerrit K. |
Issue Date: | 2014 | Publisher: | PERGAMON-ELSEVIER SCIENCE LTD | Source: | TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 67, p. 166-186 | Abstract: | Dial-a-ride problems are concerned with the design of efficient vehicle routes for transporting individual persons from specific origin to specific destination locations. In real-life this operational planning problem is often complicated by several factors. Users may have special requirements (e.g. to be transported in a wheelchair) while service providers operate a heterogeneous fleet of vehicles from multiple depots in their service area. In this paper, a general dial-a-ride problem in which these three real-life aspects may simultaneously be taken into account is introduced: the Multi-Depot Heterogeneous Dial-A-Ride Problem (MD-H-DARP). Both a three- and two-index formulation are discussed. A branch-and-cut algorithm for the standard dial-a-ride problem is adapted to exactly solve small problem instances of the MD-H-DARP. To be able to solve larger problem instances, a new deterministic annealing meta-heuristic is proposed. Extensive numerical experiments are presented on different sets of benchmark instances for the homogeneous and the heterogeneous single depot dial-a-ride problem. Instances for the MD-H-DARP are introduced as well. The branch-and-cut algorithm provides considerably better results than an existing algorithm which uses a less compact formulation. All seven previously unsolved benchmark instances for the heterogeneous dial-a-ride problem could be solved to optimality within a matter of seconds. While computation times of the exact algorithm increase drastically with problem size, the proposed meta-heuristic algorithm provides near-optimal solutions within limited computation time for all instances. Several best known solutions for unsolved instances are improved and the algorithm clearly outperforms current state-of-the-art heuristics for the homogeneous and heterogeneous dial-a-ride problem, both in terms of solution quality and computation time. (C) 2014 Elsevier Ltd. All rights reserved. | Notes: | [Braekers, Kris; Canis, An; Janssens, Gerrit K.] Hasselt Univ, Res Grp Logist, B-3590 Diepenbeek, Belgium. [Canis, An] Res Fdn Flanders FWO, B-1000 Brussels, Belgium. | Keywords: | Dial-a-ride; Demand responsive transportation; Heterogeneous users and vehicles; Branch-and-cut algorithm; Deterministic annealing meta-heuristic; Vehicle routing;dial-a-ride; demand responsive transportation; heterogeneous users and vehicles; branch-and-cut algorithm; deterministic annealing meta-heuristic; vehicle routing | Document URI: | http://hdl.handle.net/1942/17692 | ISSN: | 0191-2615 | e-ISSN: | 1879-2367 | DOI: | 10.1016/j.trb.2014.05.007 | ISI #: | 000341462100009 | Rights: | © 2014 Elsevier Ltd. All rights reserved. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2015 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
braekers 1.pdf Restricted Access | Published version | 317.42 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
77
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
149
checked on Oct 10, 2024
Page view(s)
258
checked on Sep 5, 2022
Download(s)
230
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.