Computational complexity and linear formulations for optimizing the location of shared mobility stations

Abstract

Properly planned shared mobility services can be attractive even for who owns and drives a private vehicle, but would consider not owning it anymore if a cheaper, more sustainable, and accessible transport service is available. However, planning such services may become computationally intractable as demand and coverage widen, requiring different methods for optimizing them. This work contextualizes the computational challenges in defining station locations for shared mobility services; proves the NP‐hardness of optimizing the exact locations for shared mobility stations; proves the NP‐hardness of selecting street segments to have shared mobility stations; proposes mixed‐integer linear programming formulations for both problems; proposes and compares the performance of these formulations to two heuristics; and applies these formulations to the road network of the metropolitan region of São Paulo in Brazil. Results show the trade‐off between computational efforts and the precision of optimal solutions by choosing which problem to solve.