More Web Proxy on the site http://driver.im/

research-article

Optimal Trip-Vehicle Dispatch with Multi-Type Requests

Authors:

Fei FangAuthors Info & Claims

AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

Pages 2024 - 2026

Published: 08 May 2019 Publication History

Abstract

In recent years, traditional transportation platforms which mainly provide real-time ride-hailing services have started to accept rides scheduled in advance. The presence of both ride requests posted in real time and scheduled rides leads to new challenges to the service providers in deciding which requests to accept and how to dispatch the vehicles in a dynamic and optimal way, which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we provide the following contributions: (i) a novel two-stage decision-making model where in the first stage, the system decides whether to accept requests scheduled in advance in an online fashion, and in the second stage, dispatches vehicles to on-demand ride requests in real time given the accepted scheduled requests as constraints; (ii) novel algorithms for both stages that take an estimated distribution of on-demand ride requests into account to handle both on-demand and scheduled requests.

References

[1]

Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. 2017. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences, Vol. 114, 3 (2017), 462--467.

[2]

Javier Alonso-Mora, Alex Wallar, and Daniela Rus. 2017. Predictive routing for autonomous mobility-on-demand systems with ride-sharing. In Intelligent Robots and Systems (IROS), 2017 IEEE/RSJ International Conference on. IEEE, 3583--3590.

[3]

Apple Inc. 2018. App Store Preview, Supershuttle. https://itunes.apple.com/us/app/supershuttle/id376771013?mt=8. (2018).

[4]

Ana LC Bazzan and Camelia Chira. 2015. A Hybrid Evolutionary and Multiagent Reinforcement Learning Approach to Accelerate the Computation of Traffic Assignment. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1723--1724.

Digital Library

[5]

Dimitris Bertsimas, Patrick Jaillet, and Sébastien Martin. 2018. Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications. (2018).

[6]

Shih-Fen Cheng, Duc Thien Nguyen, and Hoong Chuin Lau. 2014. Mechanisms for arranging ride sharing and fare splitting for last-mile travel demands. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems. International Foundation for Autonomous Agents and Multiagent Systems, 1505--1506.

Digital Library

[7]

Brian J Coltin and Manuela Veloso. 2013. Towards ridesharing with passenger transfers. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. International Foundation for Autonomous Agents and Multiagent Systems, 1299--1300.

Digital Library

[8]

Der-Horng Lee, Hao Wang, Ruey Cheu, and Siew Teo. 2004. Taxi dispatch system based on current demands and real-time traffic conditions. Transportation Research Record: Journal of the Transportation Research Board 1882 (2004), 193--200.

[9]

Meghna Lowalekar, Pradeep Varakantham, and Patrick Jaillet. 2018. Online spatio-temporal matching in stochastic and dynamic domains. Artificial Intelligence, Vol. 261 (2018), 71--112.

[10]

Hongyao Ma, Fei Fang, and David C Parkes. 2018. Spatio-Temporal Pricing for Ridesharing Platforms. arXiv preprint arXiv:1801.04015 (2018).

[11]

Shuo Ma, Yu Zheng, and Ouri Wolfson. 2013. T-share: A large-scale dynamic taxi ridesharing service. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on. IEEE, 410--421.

Digital Library

[12]

Luis Moreira-Matias, Joao Gama, Michel Ferreira, Joao Mendes-Moreira, and Luis Damas. 2013. Predicting taxi--passenger demand using streaming data. IEEE Transactions on Intelligent Transportation Systems, Vol. 14, 3 (2013), 1393--1402.

Digital Library

[13]

Deepika Pathania and Kamalakar Karlapalem. 2015. Social network driven traffic decongestion using near time forecasting. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems . International Foundation for Autonomous Agents and Multiagent Systems, 1761--1762.

Digital Library

[14]

Kiam Tian Seow, Nam Hai Dang, and Der-Horng Lee. 2010. A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering, Vol. 7, 3 (2010), 607--616.

[15]

Yongxin Tong, Yuqiang Chen, Zimu Zhou, Lei Chen, Jie Wang, Qiang Yang, Jieping Ye, and Weifeng Lv. 2017. The simpler the better: a unified approach to predicting original taxi demands based on large-scale online platforms. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1653--1662.

Digital Library

[16]

Chao Wang, Somchaya Liemhetcharat, and Kian Hsiang Low. 2016. Multi-agent continuous transportation with online balanced partitioning. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1303--1304.

Digital Library

[17]

Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, Qiang Li, Junxiao Nan, Chunyang Liu, Wei Bian, and Jieping Ye. 2018. Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 905--913.

Digital Library

[18]

Lingyu Zhang, Tao Hu, Yue Min, Guobin Wu, Junying Zhang, Pengcheng Feng, Pinghua Gong, and Jieping Ye. 2017. A taxi order dispatch model based on combinatorial optimization. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2151--2159.

Digital Library

[19]

Rick Zhang and Marco Pavone. 2016. Control of robotic mobility-on-demand systems: a queueing-theoretical perspective. The International Journal of Robotics Research, Vol. 35, 1--3 (2016), 186--203.

Digital Library

Cited By

Wu JLu CWu CQin YLi QMa NFang J(2021)Mobility Data-driven Complete Dispatch Framework for the Ride-hailing PlatformAdjunct Proceedings of the 2021 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2021 ACM International Symposium on Wearable Computers10.1145/3460418.3480407(684-690)Online publication date: 21-Sep-2021
https://dl.acm.org/doi/10.1145/3460418.3480407

Index Terms

Optimal Trip-Vehicle Dispatch with Multi-Type Requests
1. Applied computing
  1. Operations research
    1. Decision analysis
      1. Multi-criterion optimization and decision-making
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

Joserlin: joint request and service scheduling for peer-to-peer non-linear media access
MM '13: Proceedings of the 21st ACM international conference on Multimedia

A peer-to-peer non-linear media streaming system needs to schedule both on-demand and prefetch requests carefully so as to reduce the server load and ensure good user experience. In this work, we propose, Joserlin, a joint request and service scheduling ...
Ride-Hailing Order Matching and Vehicle Repositioning Based on Vehicle Value Function
Knowledge Science, Engineering and Management
Abstract
Online ride-hailing platforms, such as Uber, DiDi and Lyft, have significantly revolutionized the way of travelling and improved traffic efficiency. How to match orders with feasible vehicles and how to dispatch idle vehicles to the area with ...
Utilizing slack time for aperiodic and sporadic requests scheduling in real-time systems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

May 2019

2518 pages

ISBN:9781450363099

General Chairs:
Edith Elkind
University of Oxford, UK
,
Manuela Veloso
CMU (on leave), JPMorgan, USA
,
Program Chairs:
Noa Agmon
Bar-Ilan University, Israel
,
Matthew E. Taylor
Borealis AI, Canada

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 08 May 2019

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS '19

Sponsor:

SIGAI

AAMAS '19: International Conference on Autonomous Agents and Multiagent Systems

May 13 - 17, 2019

Montreal QC, Canada

Acceptance Rates

AAMAS '19 Paper Acceptance Rate 193 of 793 submissions, 24%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
90
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu JLu CWu CQin YLi QMa NFang J(2021)Mobility Data-driven Complete Dispatch Framework for the Ride-hailing PlatformAdjunct Proceedings of the 2021 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2021 ACM International Symposium on Wearable Computers10.1145/3460418.3480407(684-690)Online publication date: 21-Sep-2021
https://dl.acm.org/doi/10.1145/3460418.3480407

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents