Real-time adaptive algorithms for dial-a-ride problems

• Main Author: Pandi, Ramesh Ramasamy
• Other Authors: Justin Dauwels
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Electrical and electronic engineering::Computer hardware, software and systems; Business::Operations management::Business planning
• Online Access: https://hdl.handle.net/10356/144558
• Institution: Nanyang Technological University

Autonomous Mobility-on-Demand, a key step towards sustainable future urban mobility, refers to a transformative and rapidly developing mode of transportation wherein self-driving vehicles transport passengers in a given environment. Dial-a-ride problem (DARP) is an underlying optimization problem in the operational planning of mobility-on-demand systems. The primary objective of DARP is to design routes and schedules to perform passenger transportation services with a high-level of user comfort. DARP often arises in dynamic real-world scenarios, where rapid route planning is crucial. Despite the advancements in technologies, autonomous mobility-on-demand systems are still being considered to be in the trial phase, as the commercial deployment is impeded by the following research gaps. First, the traditional CPU-based algorithms are generally too slow to be useful in practice. There is a growing interest in fast methods since the users expect the service providers to provide an answer quickly, particularly in case of dynamic and disruptive scenarios. Second, regardless of the technological advancements, vehicle breakdowns lead to major disruption of transportation services across the globe. In the context of dial-a-ride systems, this results in an inflated operational cost and damaged reputation for the service providers (operators of taxis, private buses, etc.). However, modeling such dynamic events for dial-a-ride systems has not been addressed in the literature. Third, the advent of autonomous electric vehicles (EV) has the potential to revolutionize intelligent transportation systems and especially useful in mobility-on-demand services to combat issues such as global warming, fuel consumption, air pollution, and road safety. Despite the importance of EVs, the existing distribution of static charging stations (SCS) is not abundant and reachable, which causes range anxiety. The latest charging technology, mobile energy disseminator (MED), is energy-efficient and able to recharge EV on the move without causing any detours. Nevertheless, to promote the usage of autonomous EVs and achieve green transportation, it is necessary to integrate them into the daily transit systems. Therefore, this thesis introduces real-time adaptive algorithms for the dial-a-ride system. The following are the major contributions. First, a generic GPU framework has been proposed to accelerate time-critical neighborhood exploration of local search operations under the guidance of meta-heuristics to efficiently solve DARP. Specifically, device-oriented optimization strategies are introduced to enhance the utilization of a current-generation GPU architecture (Tesla P100). Second, models and algorithms for the dial-a-ride problem with the vehicle breakdown. Specifically, we propose a disruption management framework with the combination of online optimization and fleet size minimization. Third, models and algorithms for the electric autonomous dial-a-ride problem with mobile energy disseminators. We investigate the effectiveness of the proposed recharging strategy for electric autonomous DARP in comparison with the conventional SCS. Simulations are conducted on DARP benchmark instances and real-world Uber taxi trips in San Francisco City, USA. The proposed GPU-based solution methodologies perform 10x to 100x faster than their CPU counterpart and achieve better solution quality in a short time when compared to the existing approaches. Furthermore, when compared to the conventional disruption management techniques, the proposed disruption management scheme achieves a significant reduction in fleet idle time under normal operations and a reduction in operational cost under disruption in dial-a-ride operations. In terms of the EV charging methodologies, the latest mobile energy disseminators that act as a moving charging station seems to improve the operational service quality of electric autonomous dial-a-ride systems when compared to conventional recharging methodologies. In summary, we introduce novel formulations and solution frameworks to advance the state-of-the-art in DARP and conduct simulations on both benchmark and real-world test instances to verify the suitability and effectiveness of the proposed frameworks. We report the effect of GPU on accelerating solution algorithms for solving DARP under dynamic real-life settings, the effect of minimizing fleet size on the service provider and customer experience both before and after disruptive events such as vehicle breakdown, the effect of optimizing depot locations on transportation costs, and the effect of the latest recharging infrastructures on reducing the EV range anxiety in dial-a-ride operations. At the end of the thesis, we provide concluding remarks and several interesting future research directions.