Spurred by the growth of transportation network companies and increasing data capabilities, vehicle routing and ride-matching algorithms can improve the efficiency of private transportation services. However, existing routing solutions do not address where drivers should travel after dropping off a passenger and before receiving the next passenger ride request, i.e., during the between-ride period. We address this problem by developing an efficient algorithm to find the optimal policy for drivers between rides in order to maximize driver profits. We model the road network as a graph, and we show that the between-ride routing problem is equivalent to a stochastic shortest path problem, an infinite dynamic program with no discounting. We prove under reasonable assumptions that an optimal routing policy exists that avoids cycles; policies of this type can be efficiently found. We present an iterative approach to find an optimal routing policy. Our approach can account for various factors, including the frequency of passenger ride requests at different locations, traffic conditions, and surge pricing. We demonstrate the effectiveness of the approach by implementing it on road network data from Boston and New York City.


    Access

    Download


    Export, share and cite



    Title :

    Between-Ride Routing for Private Transportation Services


    Contributors:

    Publication date :

    2018


    Remarks:

    8 pages


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




    Transportation Ride Quality

    I. D. Jacobson / R. W. Barber / A. J. Healy et al. | NTIS | 1977


    Transportation ride quality

    National Research Council, Transportation Research Board, USA | TIBKAT | 1977


    Container truck transportation routing as a Mixed Fleet Heterogeneous Dial-a-Ride Problem

    Amine Masmoudi Mohamed / Kuzmicz Katarzyna Anna / Pesch Erwin et al. | DOAJ | 2020

    Free access


    Private Location Sharing for Decentralized Routing Services

    Tsao, Matthew / Yang, Kaidi / Gopalakrishnan, Karthik et al. | IEEE | 2022