Document Server@UHasselt >
Research >
Research publications >

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
Issue Date: 2014
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.
URI: http://hdl.handle.net/1942/17692
DOI: 10.1016/j.trb.2014.05.007
ISI #: 000341462100009
ISSN: 0191-2615
Category: A1
Type: Journal Contribution
Validation: ecoom, 2015
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version317.42 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.