A Convex Design for Transportation Networks Based on Sparsity and the Legendre Transform

This work addresses the challenge of designing capacitated transportation networks in scenarios where nonlinear costs, constraints, and a large number of variables render standard Mixed-Integer Programming (MIP) infeasible. To that end, we propose a computationally efficient method that reformulates the problem of selecting the stations, links, capacities, and routes of the transportation network as a continuous convex optimization by: i) relaxing binary and integer variables; ii) using entropy-based regularizers to model user behavior through logit-based decisions; and iii) using norm-1 regularizers to promote sparsity in infrastructure design. The design accounts for both operator and passenger preferences. Preliminary tests on small networks showcase that our method performs much faster than MIP algorithms with a small optimality loss.