Operational research and simulation methods for autonomous ride-sourcing
File(s)
Author(s)
Karamanis, Renos
Type
Thesis
Abstract
Ride-sourcing platforms provide on-demand shared transport services by solving decision problems related to ride-matching and pricing. The anticipated commercialisation of autonomous vehicles could transform these platforms to fleet operators and broaden their decision-making by introducing problems such as fleet sizing and empty vehicle redistribution. These problems have been frequently represented in research using aggregated mathematical programs, and alternative practises such as agent-based models. In this context, this study is set at the intersection between operational research and simulation methods to solve the multitude of autonomous ride-sourcing problems.
The study begins by providing a framework for building bespoke agent-based models for ride-sourcing fleets, derived from the principles of agent-based modelling theory, which is used to tackle the non-linear problem of minimum fleet size. The minimum fleet size problem is tackled by investigating the relationship of system parameters based on queuing theory principles and by deriving and validating a novel model for pickup wait times. Simulating the fleet function in different urban areas shows that ride-sourcing fleets operate queues with zero assignment times above the critical fleet size. The results also highlight that pickup wait times have a pivotal role in estimating the minimum fleet size in ride-sourcing operations, with agent-based modelling being a more reliable estimation method.
The focus is then shifted to empty vehicle redistribution, where the omission of market structure and underlying customer acumen, compromises the effectiveness of existing models. As a solution, the vehicle redistribution problem is formulated as a non-linear convex minimum cost flow problem that accounts for the relationship of supply and demand of rides by assuming a customer discrete choice model and a market structure. An edge splitting algorithm is then introduced to solve a transformed convex minimum cost flow problem for vehicle redistribution. Results of simulated tests show that the redistribution algorithm can significantly decrease wait times and increase profits with a moderate increase in vehicle mileage.
The study is concluded by considering the operational time-horizon decision problems of ride-matching and pricing at periods of peak travel demand. Combinatorial double auctions have been identified as a suitable alternative to surge pricing in research, as they maximise social welfare by relying on stated customer and driver valuations. However, a shortcoming of current models is the exclusion of trip detour effects in pricing estimates. The study formulates a shared-ride assignment and pricing algorithm using combinatorial double auctions to resolve the above problem. The model is reduced to the maximum weighted independent set problem, which is APX-hard. Therefore, a fast local search heuristic is proposed, producing solutions within 10\% of the exact approach for practical implementations.
The study begins by providing a framework for building bespoke agent-based models for ride-sourcing fleets, derived from the principles of agent-based modelling theory, which is used to tackle the non-linear problem of minimum fleet size. The minimum fleet size problem is tackled by investigating the relationship of system parameters based on queuing theory principles and by deriving and validating a novel model for pickup wait times. Simulating the fleet function in different urban areas shows that ride-sourcing fleets operate queues with zero assignment times above the critical fleet size. The results also highlight that pickup wait times have a pivotal role in estimating the minimum fleet size in ride-sourcing operations, with agent-based modelling being a more reliable estimation method.
The focus is then shifted to empty vehicle redistribution, where the omission of market structure and underlying customer acumen, compromises the effectiveness of existing models. As a solution, the vehicle redistribution problem is formulated as a non-linear convex minimum cost flow problem that accounts for the relationship of supply and demand of rides by assuming a customer discrete choice model and a market structure. An edge splitting algorithm is then introduced to solve a transformed convex minimum cost flow problem for vehicle redistribution. Results of simulated tests show that the redistribution algorithm can significantly decrease wait times and increase profits with a moderate increase in vehicle mileage.
The study is concluded by considering the operational time-horizon decision problems of ride-matching and pricing at periods of peak travel demand. Combinatorial double auctions have been identified as a suitable alternative to surge pricing in research, as they maximise social welfare by relying on stated customer and driver valuations. However, a shortcoming of current models is the exclusion of trip detour effects in pricing estimates. The study formulates a shared-ride assignment and pricing algorithm using combinatorial double auctions to resolve the above problem. The model is reduced to the maximum weighted independent set problem, which is APX-hard. Therefore, a fast local search heuristic is proposed, producing solutions within 10\% of the exact approach for practical implementations.
Version
Open Access
Date Issued
2021-01
Date Awarded
2021-06
Copyright Statement
Creative Commons Attribution-Non Commercial-No Derivatives 4.0 International Licence
Advisor
Angeloudis, Panagiotis
Stettler, Marc
Sponsor
Engineering and Physical Sciences Research Council
Publisher Department
Civil and Environmental Engineering
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)