  In this paper we study rebalancing strategies for a mobility-on-demand urban
transportation system blending customer-driven vehicles with a taxi service. In
our system, a customer arrives at one of many designated stations and is
transported to any other designated station, either by driving themselves, or
by being driven by an employed driver. The system allows for one-way trips, so
that customers do not have to return to their origin. When some origins and
destinations are more popular than others, vehicles will become unbalanced,
accumulating at some stations and becoming depleted at others. This problem is
addressed by employing rebalancing drivers to drive vehicles from the popular
destinations to the unpopular destinations. However, with this approach the
rebalancing drivers themselves become unbalanced, and we need to "rebalance the
rebalancers" by letting them travel back to the popular destinations with a
customer. Accordingly, in this paper we study how to optimally route the
rebalancing vehicles and drivers so that stability (in terms of boundedness of
the number of waiting customers) is ensured while minimizing the number of
rebalancing vehicles traveling in the network and the number of rebalancing
drivers needed; surprisingly, these two objectives are aligned, and one can
find the optimal rebalancing strategy by solving two decoupled linear programs.
Leveraging our analysis, we determine the minimum number of drivers and minimum
number of vehicles needed to ensure stability in the system. Interestingly, our
simulations suggest that, in Euclidean network topologies, one would need
between 1/3 and 1/4 as many drivers as vehicles.
