A double dynamic fast algorithm to solve multi-vehicle Dial a Ride Problem

Abstract In this work a two level heuristic algorithm is described for a nearly real-time multi-vehicle many-to-many Dial-A-Ride Problem (DARP). This algorithm is ready to support a Demand Responsive Transportation System in which we face the problem of quickly evaluate a good-quality schedule for the vehicles and provide fast response to the users. The insertion heuristic is double dynamic nearly real-time and the objective function is to minimize the variance between the requested and scheduled time of pickup and delivery. In the first level, after a customer web-request, the heuristic returns an answer about the possibility to insert the request into the accepted reservations, and therefore in a vehicle schedule, or reject the request. In the second level, during the time elapsed between a request and the following, and after a reshuffling of the order of the incoming accepted requests, the same heuristic works for the whole set of accepted requests, trying to optimize the solution. We intensively tested the algorithm with a requests-generating software that has allowed us to show the competitive advantage of this web-based architecture