BalSAM: Balanced and Staggered Routing for Autonomous Mobility on Demand Systems

点击翻译按钮获取中文摘要

Urban areas all around the world suffer from congestion and noxious emissions, as today’s transportation systems are overloaded such that public transport and current shared-mobility concepts do not offer enough capacities for sustainable passenger transport. To this end, experts value autonomous mobility on demand (AMoD) systems as a promising future technology that allows for sustainable shared but yet individual mobility services. Here, a central operator controls a fleet of self-driving vehicles that is and offers a ride-hailing service to customers.With a transparent centralized control over the fleet, such an AMoD system bears major advantages as it allows for a better matching between demand and supply as well as improved customer pooling, congestion aware routing, and a better accessibility due to continuous rebalancing operations. However, the operation of such a system bears an inherent combinatorial complexity on all levers, and its efficiency depends heavily on appropriate algorithmic solutions, which have not yet been sufficiently explored so far.The scope of this research project is to develop a generic algorithmic framework for large-scale AMoD fleet management, which allows a sustainable operation of AMoD systems in the near future. This algorithmic framework covers three basic components that constitute the central planning tasks of a fleet operator: demand pooling, i.e., matching (if possible) customers with similar transportation requests in order to increase the vehicle utilization; vehicle dispatching, i.e., assigning (pooled) transportation requests to vehicles; and vehicle routing, i.e., deciding on routes for customer carrying vehicles but also on routes for idling vehicles in order to rebalance the fleet. So far, these algorithmic components have been addressed either heuristically or on small scale instances, and mostly separately. Moreover, the framework covers two additional concepts that cannot be utilized in a non-autonomous system but gain importance when aiming at efficient AMoD fleet management from a system perspective. First, balanced routing, i.e., routing flows from a system perspective to reduce capacity bottlenecks, becomes increasingly important to avoid or to reduce congestion. Second, staggered pooling and routing, i.e., delaying or forwarding a customer's departure in time, allows for additional temporal flexibility to avoid bottlenecks and congestion. Both of these concepts have not yet been sufficiently explored for complex, large-scale transportation systems and remain an additional novelty in the developed framework.The applicant and the mercator fellow are considered as leading experts in the research field of autonomous mobility on demand systems. They have a vast expertise in routing algorithms, large-scale optimization, and autonomous systems, which allows to develop a new generic state-of-the-art algorithmic toolbox that can serve as a fundament for further research in this field.