Rapid transit network design via convex optimization: The role of sparsity and entropy-based regularizers

In real-world transportation networks, optimizing binary and integer variables is manageable when dealing with linear formulations and small dimensions. However, the challenge arises when costs and constraints become non-linear, especially in high-dimensional contemporary transportation systems that consider both infrastructure operators and user behavior. The infeasibility of implementing Mixed-Integer Non-Linear Programming (MINLP) solvers in those scenarios prompts our focus on computationally tractable algorithms designed as solutions to judiciously formulated convex programs. Specifically, we investigate the problem of optimizing the infrastructure of a transportation network (arcs and stations) considering construction costs, demand estimates, and user behavior modeled by a logit model that ponders attributes of the routes users choose. Our innovative approach formulates the problem as a continuous convex constrained optimization, relaxing binary/integral variables and incorporating convex costs and constraints. Notably, our formulation: i) enhances sparsity in the infrastructure through reweighted norm-1 regularizers; and ii) models user behavior by introducing entropy-based regularizers whose KKT conditions lead to logit-based decisions. We test our approach thoroughly in small networks and, then, apply it to the design of the metro system of the city of Seville, Spain. Practically, our convex-based optimization algorithms significantly outpace MINLP commercial solvers in terms of speed, making them applicable to large networks far exceeding the capacity of standard solvers. Methodologically, our adaptable formulation offers a promising solution for various scenarios, presenting a viable approach to addressing large-dimensional problems in transportation systems.