Solving the dial-a- ride problem (DARP) using an agent based simulation approach and heuristic methods

Abstract

The Dial-a-Ride Problem (DARP) requires a set of customers to be transported by a limited fleet of vehicles between unique origins and destinations under several service constraints, most notably, within defined time windows. The problem is considered NP-hard and has typically been solved using metaheuristics methods. An agent based simulation (ABS) model was developed, where each vehicle bids to service customers based on a weighted objective function that considers the cost to service the customer, and time quality of the service that would be achieved. The approach applied a pre-processing technique to reduce the search space given the service time window constraints. Tests of the model show significantly better customer transit and waiting times than the benchmark datasets. The ABS was able to obtain solutions for much larger problem sizes than the benchmark solutions, with this work being the first known application of ABS to the DARP.