 Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depotsKris Braekers, An Caris and Gerrit K. Janssens Transportation Research Part B: Methodological, 2014, vol. 67, issue C, 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. Keywords: Dial-a-ride; Demand responsive transportation; Heterogeneous users and vehicles; Branch-and-cut algorithm; Deterministic annealing meta-heuristic; Vehicle routing (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:67:y:2014:i:c:p:166-186 Ordering information: This journal article can be ordered from DOI: 10.1016/j.trb.2014.05.007 Access Statistics for this article Transportation Research Part B: Methodological is currently edited by Fred Mannering More articles in Transportation Research Part B: Methodological from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.