Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems

Cheng Li; David Parker; Qi Hao

doi:10.1109/ICRA48506.2021.9561281

Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems

Cheng Li
, David Parker
, Qi Hao

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

511 Downloads (Pure)

Abstract

Shared autonomous mobility-on-demand systems hold great promise for improving the efficiency of urban transportation, but are challenging to implement due to the huge scheduling search space and highly dynamic nature of requests. This paper presents a novel optimal schedule pool (OSP) assignment approach to optimally dispatch high-capacity ride-sharing vehicles in real time, including: (1) an incremental search algorithm that can efficiently compute the exact lowest-cost schedule of a ride-sharing trip with a reduced search space; (2) an iterative online re-optimization strategy to dynamically alter the assignment policy for new incoming requests, in order to maximize the service rate. Experimental results based on New York City taxi data show that our proposed approach outperforms the state-of-the-art in terms of service rate and system scalability.

Original language	English
Title of host publication	2021 IEEE International Conference on Robotics and Automation (ICRA)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Number of pages	7
ISBN (Electronic)	9781728190778
ISBN (Print)	9781728190785 (PoD)
DOIs	https://doi.org/10.1109/ICRA48506.2021.9561281
Publication status	Published - 18 Oct 2021
Event	2021 IEEE International Conference on Robotics and Automation - International Convention and Exhibition Center, Xi’an , China Duration: 30 May 2021 → 5 Jun 2021

Publication series

Name	IEEE International Conference on Robotics and Automation
Publisher	IEEE
ISSN (Print)	1050-4729
ISSN (Electronic)	2577-087X

Conference

Conference	2021 IEEE International Conference on Robotics and Automation
Abbreviated title	ICRA 2021
Country/Territory	China
City	Xi’an
Period	30/05/21 → 5/06/21

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 11 Sustainable Cities and Communities

Keywords

space vehicles
shedules
scalability
urban areas
optimal scheduling
dynamic scheduling
real time systems

Access to Document

10.1109/ICRA48506.2021.9561281Licence: None: All rights reserved

LiC2021Optimal
This is the Author Accepted Manuscript of the following proceeding Cheng Li; David Parker; Qi Hao, Optimal Online Dispatch for High-Capacity Shared Autonomous Mobility-on-Demand Systems 202110.1109/ICRA48506.2021.9561281 © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 1.36 MBLicence: Other (please specify with Rights Statement)

Cite this

Li, C., Parker, D., & Hao, Q. (2021). Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems. In 2021 IEEE International Conference on Robotics and Automation (ICRA) Article 9561281 (IEEE International Conference on Robotics and Automation). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ICRA48506.2021.9561281

@inproceedings{788aee8738bb45e6b4c0391a7d1e4bf1,

title = "Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems",

abstract = "Shared autonomous mobility-on-demand systems hold great promise for improving the efficiency of urban transportation, but are challenging to implement due to the huge scheduling search space and highly dynamic nature of requests. This paper presents a novel optimal schedule pool (OSP) assignment approach to optimally dispatch high-capacity ride-sharing vehicles in real time, including: (1) an incremental search algorithm that can efficiently compute the exact lowest-cost schedule of a ride-sharing trip with a reduced search space; (2) an iterative online re-optimization strategy to dynamically alter the assignment policy for new incoming requests, in order to maximize the service rate. Experimental results based on New York City taxi data show that our proposed approach outperforms the state-of-the-art in terms of service rate and system scalability.",

keywords = "space vehicles, shedules, scalability, urban areas, optimal scheduling, dynamic scheduling, real time systems",

author = "Cheng Li and David Parker and Qi Hao",

year = "2021",

month = oct,

day = "18",

doi = "10.1109/ICRA48506.2021.9561281",

language = "English",

isbn = "9781728190785 (PoD)",

series = "IEEE International Conference on Robotics and Automation",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

booktitle = "2021 IEEE International Conference on Robotics and Automation (ICRA)",

note = "2021 IEEE International Conference on Robotics and Automation, ICRA 2021 ; Conference date: 30-05-2021 Through 05-06-2021",

}

Li, C, Parker, D & Hao, Q 2021, Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems. in 2021 IEEE International Conference on Robotics and Automation (ICRA)., 9561281, IEEE International Conference on Robotics and Automation, Institute of Electrical and Electronics Engineers (IEEE), 2021 IEEE International Conference on Robotics and Automation, Xi’an , China, 30/05/21. https://doi.org/10.1109/ICRA48506.2021.9561281

Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems. / Li, Cheng; Parker, David; Hao, Qi.
2021 IEEE International Conference on Robotics and Automation (ICRA). Institute of Electrical and Electronics Engineers (IEEE), 2021. 9561281 (IEEE International Conference on Robotics and Automation).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems

AU - Li, Cheng

AU - Parker, David

AU - Hao, Qi

PY - 2021/10/18

Y1 - 2021/10/18

N2 - Shared autonomous mobility-on-demand systems hold great promise for improving the efficiency of urban transportation, but are challenging to implement due to the huge scheduling search space and highly dynamic nature of requests. This paper presents a novel optimal schedule pool (OSP) assignment approach to optimally dispatch high-capacity ride-sharing vehicles in real time, including: (1) an incremental search algorithm that can efficiently compute the exact lowest-cost schedule of a ride-sharing trip with a reduced search space; (2) an iterative online re-optimization strategy to dynamically alter the assignment policy for new incoming requests, in order to maximize the service rate. Experimental results based on New York City taxi data show that our proposed approach outperforms the state-of-the-art in terms of service rate and system scalability.

AB - Shared autonomous mobility-on-demand systems hold great promise for improving the efficiency of urban transportation, but are challenging to implement due to the huge scheduling search space and highly dynamic nature of requests. This paper presents a novel optimal schedule pool (OSP) assignment approach to optimally dispatch high-capacity ride-sharing vehicles in real time, including: (1) an incremental search algorithm that can efficiently compute the exact lowest-cost schedule of a ride-sharing trip with a reduced search space; (2) an iterative online re-optimization strategy to dynamically alter the assignment policy for new incoming requests, in order to maximize the service rate. Experimental results based on New York City taxi data show that our proposed approach outperforms the state-of-the-art in terms of service rate and system scalability.

KW - space vehicles

KW - shedules

KW - scalability

KW - urban areas

KW - optimal scheduling

KW - dynamic scheduling

KW - real time systems

U2 - 10.1109/ICRA48506.2021.9561281

DO - 10.1109/ICRA48506.2021.9561281

M3 - Conference contribution

SN - 9781728190785 (PoD)

T3 - IEEE International Conference on Robotics and Automation

BT - 2021 IEEE International Conference on Robotics and Automation (ICRA)

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 2021 IEEE International Conference on Robotics and Automation

Y2 - 30 May 2021 through 5 June 2021

ER -

Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Fingerprint

Cite this