  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.
