Network Design with Endogenous Demand: Adaptive Discretization for Non-Convex MIPs

Network design is a well-studied mixed-integer programming (MIP) problem. It involves constructing nodes and arcs of a network to minimize the total construction plus operating cost under fixed exogenous demand. However, in practice, demand is often dependent on network attributes through non-convex functions. We propose exact methods and efficient heuristics to find provably near-optimal solutions to large-scale network design problems. Our algorithms are applied to several real-world case studies in urban transportation, including transit, micro-mobility (e.g., bike-sharing) and urban air mobility (UAM) networks. Our algorithms consistently outperform benchmarks in terms of solution quality, runtimes and solution guarantee. Computational results indicate the importance of modeling endogenous demand, and provide structural insights into the optimal network designs.