Repositioning in shared mobility systems

Abstract

The global market for personal mobility has transformed over the last decade. Traditional taxi services have to compete with the emergence of ride-hailing services such as Uber and Lyft. Rapid developments in available algorithms and real-time inter-connectivity of travellers and vehicles offer mobility-on-demand (MOD) services new possibilities to maximise the efficiency of the ride-hailing process. It is well established that rebalancing can enable the true potential of a ride-hailing fleet. In this context, rebalancing is defined as the redistribution of idle vehicles over the service area of a ride-hailing operator. In the search for the optimal rebalancing strategy, model predictive control (MPC) and approximate dynamic programming (ADP) methodologies are active fields of research. However, the computational burden of MPC limits the length of the predictive horizon in large MOD applications. This thesis proposes a novel algorithm that combines ADP and MPC. More specifically, we integrated a value function into the MPC framework as a terminal cost. We shorten the horizon of MPC and propose to use the value function as a long-term planner. For the terminal cost, we continue research into piece-wise linear value function approximation. We implement a novel multi-period approximation of the value function, where we use the maximum repositioning length as the horizon. In our case study, the value-based repositioning strategy offers comparable service quality to conventional MPC at 5.2% of the computational burden. The hybrid ADP-MPC algorithm offers flexible horizon partitions between the multi-period value function and MPC. It addresses the shortcomings of both ADP and MPC algorithms in repositioning problems. At peak performance, it offers an increase of 4.5% in service rate and a decrease of 5.2% in the average waiting time over conventional MPC, at roughly half the computational burden. Keywords: Ride-hailing, Mobility on demand, Model predictive control, Approximate Dynamic programming