An e-scooter service region and fleet allocation design problem with elastic demand

Despite the rapid growth of micromobility, and e-scooters in particular, there is no systematic approach for designing a contiguous service region with fleet allocation and responsive demand. We propose a non-rooted maximum weighted connected subgraph model with demand response to deal with this need, the first such model that does not require enumerating cycles or node pairs. The nonlinear demand response function is piecewise-linearized to obtain a mixed integer linear program and solved using an open-source solver, which is computationally efficient even for a Manhattan-sized study area with run times on the order of minutes for 318 zones. Two sets of experiments are conducted, the first on a 4-by-4 grid region to verify the model, and a second on the Manhattan region using realistic data. The results show that (1) there can exist thresholds where a strategy may switch from zone expansion to fleet expansion; and (2) reveals areas in Manhattan that should be avoided.