Solving a Ride-Sharing Problem for Dutch Ministry of Defence

Abstract

In this master thesis, we investigate a ride-sharing problem within the Dutch Ministry of Defence, characterized by multiple heterogeneous vehicles and depots, strict time constraints, consideration of user preferences, limitations on vehicle capacity, and flexible roles of drivers and riders. With a fleet of thousands of pool vehicles spread across multiple pool locations, optimizing vehicle usage becomes crucial due to emissions concerns and limited vehicle availability. One possibility to achieve this is by introducing ride-sharing, wherein individuals are permitted to take a brief detour for the purpose of dropping off and picking up others. We propose a static simulated annealing algorithm to generate schedules that facilitate this ride-sharing and apply it in an iterated local search. Besides, we introduce the concept of decoupling vehicles from their original pool locations, resulting in the possibility of returning vehicles to different pool locations than their point of origin. The multi-objective function aims to minimize the number of non-served users, the ratio of the total distance travelled to that without ride-sharing, the number of non-empty vehicles, and the deviation from the desirable occupation of vehicles at pool locations. Comparing our algorithm to the current manual approach, we observe significant improvements: increased number of planned users and reduced mileage through ride-sharing, while utilizing fewer vehicles and maintaining minimal deviation from the desired vehicle occupation at pool locations. Furthermore, combining ride-sharing and vehicle decoupling results in superior solutions, outperforming either approach alone. Secondly, we show the successful incorporation of single rides, which are rides from one pool location to another pool location without a return, and show that these increase the degree of ride-sharing. Lastly, our work presents a robustness analysis which demonstrates that rides can be effectively added to the generated schedules in a dynamic context. Moreover, although cancellations and delays cause a notable number of routes to become infeasible, a substantial portion remains feasible.