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

• Published in: Transportation research. Part B: methodological 2013-10, Vol.56, p.120-135
• Main Authors: Kirchler, Dominik, Wolfler Calvo, Roberto
• Format: Article
• Language: English
• Subjects: Applied sciences; Dial-a-Ride Problem; Exact sciences and technology; Granular Tabu Search; Ground, air and sea transportation, marine construction; Road transportation and traffic; Transportation planning, management and economics
• ISSN: 0191-2615; 1879-2367
• DOI: 10.1016/j.trb.2013.07.014

•Granular Tabu Search for the static Dial-a-Ride Problem.•Optimization of number of passengers served, quality of service and operation costs.•Granular neighborhood constructed by solving an assignment problem.•Good results in 2–3min of computation time. 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.