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

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 3 min). 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.