A Real-Time Dispatching Strategy for Shared Automated Electric Vehicles with Performance Guarantees
Preprint
Abstract
Real-time vehicle dispatching operations in traditional car-sharing systems is an already computationally challenging scheduling problem. Electrification only exacerbates the computational difficulties as charge level constraints come into play. To overcome this complexity, we employ an online minimum drift plus penalty (MDPP) approach for SAEV systems that (i) does not require a priori knowledge of customer arrival rates to the different parts of the system (i.e. it is practical from a real-world deployment perspective), (ii) ensures the stability of customer waiting times, (iii) ensures that the deviation of dispatch costs from a desirable dispatch cost can be controlled, and (iv) has a computational time-complexity that allows for real-time implementation. Using an agent-based simulator developed for SAEV systems, we test the MDPP approach under two scenarios with real-world calibrated demand and charger distributions: 1) a low-demand scenario with long trips, and 2) a high-demand scenario with short trips. The comparisons with other algorithms under both scenarios show that the proposed online MDPP outperforms all other algorithms in terms of both reduced customer waiting times and vehicle dispatching costs.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Position weighted backpressure intersection control for urban networksTransportation Research Part B: Methodological, 2019
- An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: Model formulation and Lagrangian relaxation-based solution approachTransportation Research Part B: Methodological, 2018
- Electric vehicle fleet size and trip pricing for one-way carsharing services considering vehicle relocation and personnel assignmentTransportation Research Part B: Methodological, 2018
- Tracking a system of shared autonomous vehicles across the Austin, Texas network using agent-based simulationTransportation, 2017
- Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisionsTransportation Research Part A: Policy and Practice, 2016
- Minimum Cost Matching for Autonomous CarsharingIFAC-PapersOnLine, 2016
- Simulation of City-wide Replacement of Private Cars with Autonomous Taxis in BerlinProcedia Computer Science, 2016
- Exploring the impact of shared autonomous vehicles on urban parking demand: An agent-based simulation approachSustainable Cities and Society, 2015
- Toward a Systematic Approach to the Design and Evaluation of Automated Mobility-on-Demand Systems: A Case Study in Singapore2014
- Integer priority queues with decrease key in constant time and the single source shortest paths problemJournal of Computer and System Sciences, 2004