Vehicle dispatch in high-capacity shared autonomous mobility-on-demand systems

Ride-sharing is a promising solution for transportation issues such as traffic congestion and parking land use, which are brought about by the extensive usage of private vehicles. In the near future, large-scale Shared Autonomous Mobility-on-Demand (SAMoD) systems are expected to be deployed with the realization of self-driving vehicles. It has the potential to encourage a car-free lifestyle and create a new urban mobility mode where ride-sharing is widely adopted among people. This thesis addresses the problem of improving the efficiency and quality of vehicle dispatch in high-capacity SAMoD systems. The first part of the thesis develops a dispatcher which can efficiently explore the complete candidate match space and produce the optimal assignment policy when only deterministic information is concerned. It uses an incremental search method that can quickly prune out infeasible candidates to reduce the search space. It also has an iterative re-optimization strategy to dynamically alter the assignment policy to take into account both previous and newly revealed requests. Case studies of New York City using real-world data shows that it outperforms the state-of-the-art in terms of service rate and system scalability. The dispatcher developed in this part can serve as a foundation for the next two parts, which consider two kinds of uncertain information, stochastic travel times and the dynamic distribution of requests in the long-term future, respectively. The second part of the thesis describes a framework which makes use of stochastic travel time models to optimize the reliability of vehicle dispatch. It employs a candidate match search method to generate a candidate pool, uses a set of preprocessed shortest path tables to score the candidates and provides an assignment policy that maximizes the overall score. Two different dispatch objectives are discussed: the on-time arrival probabilities of requests and the profit of the platform. Experimental studies show that higher service rates, reliability and profits can be achieved by considering travel time uncertainty. The third part of the thesis presents a deep reinforcement learning based approach to optimize assignment polices in a more far-sighted way. It models the vehicle dispatch problem as a Markov Decision Process (MDP) and uses a policy evaluation method to learn a value function from the historic movements of drivers. The learned value function is employed to score candidate matches to guide a dispatcher optimizing long-term objective, and will be continually updated online to capture the real-time dynamics of the system. It is shown by experiments that the value function helps the dispatcher to yield higher service rates.