A Granular Tabu Search algorithm for the Dial-a-Ride Problem

Dominik Kirchler and Roberto Wolfler Calvo

Transportation Research Part B: Methodological, 2013, vol. 56, issue C, 120-135

Abstract: In a Dial-a-Ride system, a fleet of vehicles without fixed routes and schedules carries people from their pick-up point to their delivery point. Pre-specified time windows must be respected, and service levels for passengers as well as operation costs should be optimized. The resulting routing and scheduling problem is NP-hard and can be modeled by a mixed integer linear programming formulation. In this paper, we propose a Granular Tabu Search algorithm for the static Dial-a-Ride Problem with the objective of producing good solutions in a short amount of time (up to 3min). We evaluate the algorithm on test instances from the literature. Our new algorithm performs well in comparison with a classical Tabu Search algorithm, a Genetic Algorithm, and a Variable Neighborhood Search.

Keywords: Granular Tabu Search; Dial-a-Ride Problem (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S019126151300129X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:56:y:2013:i:c:p:120-135

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2013.07.014

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
Bibliographic data for series maintained by Catherine Liu ().