Abstract

Fleet sizing is one of the most important tactical planning problems facing transportation service providers; it directly and significantly impacts costs and customer service quality. This paper proposes a network flow-based formulation to model the robo-taxi, or automated mobility-on-demand (AMOD), service fleet sizing problem. The formulation is similar to the minimum cost flow problem formulation in a time-expanded network, except it includes a set of external flows as variables to model the fleet size decision, alongside empty repositioning vehicle movements. The study compares the network flow-based approach to the state-of-the-art deterministic AMOD fleet sizing modeling approach, which formulates the problem as a path covering problem that relies on constructing shareability graphs. Both approaches make several simplifying assumptions but they both admit exact solutions to large-scale problem instances. Using New York City taxi data, this paper compares the two approaches in terms of minimum fleet size (lower bound) estimates, empty vehicle miles traveled estimates, and computational complexity and performance. We conclude that the TDTP formulation has several advantages over the path cover approach including scalability, computational efficiency, conservation of vehicles during the analysis period, and empty vehicle miles/kilometers traveled forecasts.