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

BalSAM：用于自主移动按需系统的平衡和交错路由

• 批准号: 449261765
• 负责人: Professor Dr. Maximilian Schiffer
• 金额: --
• 依托单位: Professur für Operations and Supply Chain Management
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2020
• 资助国家: 德国
• 起止时间: 2019-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/449261765?language=en
• 关键词: BalSAM; Balanced; Staggered; Routing; Autonomous

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.

世界各地的城市地区都遭受着拥堵和有毒排放的困扰，因为当今的交通系统超载，公共交通和目前的共享流动概念无法为可持续的客运提供足够的能力。为此，专家们将自主移动按需（阿莫德）系统视为一种有前途的未来技术，可以实现可持续的共享但又个性化的移动服务。在这里，一个中央运营商控制着一个自动驾驶车队，并为客户提供叫车服务。通过对车队的透明集中控制，这样的阿莫德系统具有重大优势，因为它可以更好地匹配需求和供应，改善客户池，拥塞感知路由，以及由于持续的再平衡操作而更好的可达性。然而，这样一个系统的运作承担了固有的组合复杂性的所有杠杆，其效率在很大程度上取决于适当的算法解决方案，这还没有得到充分的探索至今，本研究项目的范围是开发一个通用的算法框架，大规模的阿莫德车队管理，这使得可持续经营的阿莫德系统在不久的将来。该算法框架涵盖构成车队运营商的中央规划任务的三个基本组成部分：需求池，即，匹配（如果可能的话）具有类似运输请求的客户，以便增加车辆利用率;车辆调度，即，将（汇集的）运输请求分配给车辆;以及车辆路由，即，决定客户运载车辆的路线，也决定空转车辆的路线，以便重新平衡车队。到目前为止，这些算法组件已经被解决了，或者是在小规模的情况下，大部分是单独的。此外，该框架还涵盖了两个额外的概念，这些概念不能在非自主系统中使用，但从系统的角度来看，当目标是高效的阿莫德车队管理时，它们会变得重要。第一，均衡路由，即，从系统的角度来减少容量瓶颈的路由流对于避免或减少拥塞变得越来越重要。第二，交错汇集和路由，即，延迟或提前客户的出发时间，允许额外的时间灵活性，以避免瓶颈和拥堵。这两个概念还没有被充分探索复杂的，大规模的交通系统，并保持在发达的框架中的额外的新奇。申请人和墨卡托研究员被认为是在自主移动按需系统的研究领域的领先专家。他们在路由算法，大规模优化和自治系统方面拥有丰富的专业知识，可以开发一个新的通用最先进的算法工具箱，可以作为该领域进一步研究的基础。