Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests

Taoan Huang, Bohui Fang, Xiaohui Bei, Fei Fang
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:250-260, 2020.

Abstract

Transportation service providers that dispatch drivers and vehicles to riders start to support both on-demand ride requests posted in real time and rides scheduled in advance, leading to new challenges which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we design novel trip-vehicle dispatch algorithms to handle both types of requests while taking into account an estimated request distribution of on-demand requests. At the core of the algorithms is the newly proposed Constrained Spatio-Temporal value function (CST-function), which is polynomial-time computable and represents the expected value a vehicle could gain with the constraint that it needs to arrive at a specific location at a given time. Built upon CST-function, we design a randomized best-fit algorithm for scheduled requests and an online planning algorithm for on-demand requests given the scheduled requests as constraints. We evaluate the algorithms through extensive experiments on a real-world dataset of an online ride-hailing platform.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-huang20a, title = {Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests}, author = {Huang, Taoan and Fang, Bohui and Bei, Xiaohui and Fang, Fei}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {250--260}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/huang20a/huang20a.pdf}, url = {https://proceedings.mlr.press/v115/huang20a.html}, abstract = {Transportation service providers that dispatch drivers and vehicles to riders start to support both on-demand ride requests posted in real time and rides scheduled in advance, leading to new challenges which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we design novel trip-vehicle dispatch algorithms to handle both types of requests while taking into account an estimated request distribution of on-demand requests. At the core of the algorithms is the newly proposed Constrained Spatio-Temporal value function (CST-function), which is polynomial-time computable and represents the expected value a vehicle could gain with the constraint that it needs to arrive at a specific location at a given time. Built upon CST-function, we design a randomized best-fit algorithm for scheduled requests and an online planning algorithm for on-demand requests given the scheduled requests as constraints. We evaluate the algorithms through extensive experiments on a real-world dataset of an online ride-hailing platform.} }
Endnote
%0 Conference Paper %T Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests %A Taoan Huang %A Bohui Fang %A Xiaohui Bei %A Fei Fang %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-huang20a %I PMLR %P 250--260 %U https://proceedings.mlr.press/v115/huang20a.html %V 115 %X Transportation service providers that dispatch drivers and vehicles to riders start to support both on-demand ride requests posted in real time and rides scheduled in advance, leading to new challenges which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we design novel trip-vehicle dispatch algorithms to handle both types of requests while taking into account an estimated request distribution of on-demand requests. At the core of the algorithms is the newly proposed Constrained Spatio-Temporal value function (CST-function), which is polynomial-time computable and represents the expected value a vehicle could gain with the constraint that it needs to arrive at a specific location at a given time. Built upon CST-function, we design a randomized best-fit algorithm for scheduled requests and an online planning algorithm for on-demand requests given the scheduled requests as constraints. We evaluate the algorithms through extensive experiments on a real-world dataset of an online ride-hailing platform.
APA
Huang, T., Fang, B., Bei, X. & Fang, F.. (2020). Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:250-260 Available from https://proceedings.mlr.press/v115/huang20a.html.

Related Material