View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Solving a Ride-Sharing Problem for Dutch Ministry of Defence

        Thumbnail
        View/Open
        Master_Thesis_CS_van_Rees_6419135.pdf (3.116Mb)
        Publication date
        2024
        Author
        Rees, Samuel van
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/45769
        Collections
        • Theses
        Utrecht university logo