A tabu search algorithm for the Dial-a-Ride Problem with Transfers

The Dial-a-Ride Problem (DARP) consists in determining and scheduling routes serviced by a set of vehicles in order to satisfy transportation requests from pickup points to delivery This paper introduces a variant of the DARP where the client can be transferred from one vehicle to another on specic points called \transfer points. Solving this variant of the DARP yields new algorithmic diculties. In this paper, we propose a tabu search algorithm for the Dial-a-Ride Problem with Transfers (DARPT) with a special emphasis on checking whether a modication of the current solution is feasible or not. The method is evaluated over generated and real instances.