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

• 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–3 min 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 NPNP-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.