Metaheuristic Approaches for Solving the Dial-A-Ride Problem in Demand-Responsive Transit Systems.

The Dial-a-Ride Problem (DARP) is an NP-hard combinatorial problem. The DARP is a variation of the Vehicle Routing Problem (VRP) focusing on passenger transit. It entails, giving a set of requests for pick-up and delivery, to optimize the assignment of requests. The focus is to use a group of homogeneous vehicles and serve all requests while offering optimal routes and adhering to problem constraints such as route length, vehicle capacity, passenger trip time, departure and arrival time, time windows, and request aggregations. This work provides solutions for DARP that employ the Iterated Local Search, which has already been used to solve various variations of the VRP and using different metaheuristics as simulated annealing, tabu search and greedy descent. This research aimed to assess the applicability of the DARP solution in real-case scenarios, considering the possibility of aggregating different points to asses a more practical real-case scenario. A comparison of the obtained result is offered as evidence of the results.