Optimal Location and Allocation in Shared Mobility Services via Semi-discrete Optimal Transport and Simulated Annealing

Shared mobility services, including car-sharing, bike-sharing, and microtransit, are reshaping urban transportation by improving accessibility and addressing the first/last mile gap. We study the design of a hub-to-spoke service model, where users access designated locations rather than point-to-point rides, offering a more cost-effective alternative with competitive performance. The operator must decide both the placement of service hubs and the allocation of users, a problem that is NP-hard under dense demand. To address this, we approximate the dense demand as a continuous density function and study the continuous variant of the problem. We introduce a framework combining Optimal Transport theory with Simulated Annealing to solve this location–allocation problem efficiently. Using 2.2 million trips from the New York City taxicab dataset, we demonstrate that our algorithms can scale to city-level demand and provide robust solutions for shared mobility services.