Skip to main navigation Skip to search Skip to main content

A spatial branch-and-price-and-cut algorithm for finding globally optimal solutions to the continuous network design problem

Research output: Contribution to journal › Article › peer-review

Abstract

Transportation network design, or the problem of optimizing infrastructure for a societal goal, subject to individual travelers optimizing their behavior for their own preferences, arises frequently in many contexts. However, it is an NP-hard problem due to the leader-follower or bi-level structure involving a follower objective that is different from yet significantly affects the leader objective. Creating globally optimal solution algorithms has been particularly difficult for the continuous network design problem (CNDP), in which leader variables are continuous, because of the many nonlinearities arising therein. We present a globally optimal algorithm for the CNDP based on using the high-point relaxation, i.e., the system optimal CNDP, and value function cuts to find lower bounds and solving the traffic assignment follower problem to find upper bounds. We introduce a convex relaxation and a spatial branching scheme to handle the non-convexity of value function cuts. This leads to a spatial branch-and-cut algorithm that gradually cuts out bi-level infeasible points from the feasible region of the CNDP. To enhance computational performance, we outer-approximate nonlinear convex functions and use column generation to obtain a sequence of linear programs that can be solved relatively quickly. We show that, for a predefined ϵ, our spatial branch-and-price-and-cut algorithm converges to ϵ-optimality. Compared to prior work on globally optimal solution algorithms for CNDP, we can find ϵ-optimal solutions for the same small test networks in much less time, or solve CNDP on problem instances based on networks that are two orders of magnitude larger than those used in the literature.

Original languageEnglish (US)
Article number104870
JournalTransportation Research Part E: Logistics and Transportation Review
Volume211
DOIs
StatePublished - Jul 2026

Bibliographical note

Publisher Copyright:
© 2026 Elsevier Ltd.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

  1. SDG 11 - Sustainable Cities and Communities
    SDG 11 Sustainable Cities and Communities

Keywords

  • Continuous network design problem
  • Outer approximation
  • Traffic assignment
  • User equilibrium,
  • Value function cuts

Fingerprint

Dive into the research topics of 'A spatial branch-and-price-and-cut algorithm for finding globally optimal solutions to the continuous network design problem'. Together they form a unique fingerprint.

Cite this