Solving discrete network design problem using disjunctive constraints

Abstract

This paper introduces a deterministic algorithm to solve the discrete network design problem (DNDP) efficiently. This non-convex bilevel optimization problem is well-known as an non deterministic polynomial (NP)-hard problem in strategic transportation planning. The proposed algorithm optimizes budget allocation for large-scale network improvements deterministically and with computational efficiency. It integrates disjunctive programming with an improved partial linearized subgradient method to enhance performance without significantly affecting solution quality. We evaluated our algorithm on the mid-scale Sioux Falls and large-scale Chicago networks. We assess the proposed algorithm's accuracy by examining the objective function's value, specifically the total travel time within the network. When tested on the mid-scale Sioux Falls network, the algorithm achieved an average 46% improvement in computational efficiency, compared to the best-performing method discussed in this paper, albeit with a 4.17% higher total travel time than the most accurate one, as the value of the objective function. In the application to the large-scale Chicago network, the efficiency improved by an average of 99.48% while the total travel time experienced a 4.34% increase. These findings indicate that the deterministic algorithm proposed in this research improves the computational speed while presenting a limited trade-off with solution precision. This deterministic approach offers a structured, predictable, and repeatable method for solving DNDP, which can advance transportation planning, particularly for large-scale network applications where computational efficiency is paramount. Show more