Complexity and Approximation of the Continuous Network Design Problem

Gairing, M, Harks, T and Klimm, M (2017) Complexity and Approximation of the Continuous Network Design Problem. SIAM Journal on Optimization, 27 (03). pp. 1554-1582.

Text journal-revision-camera.pdf - Author Accepted Manuscript Download (482kB)

Abstract

We revisit a classical problem in transportation, known as the (bilevel) continuous network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing costs of the induced Wardrop equilibrium and the investment costs for installing the edge's capacities. While this problem is considered to be challenging in the literature, its complexity status was still unknown. We close this gap, showing that CNDP is strongly $\mathsf{NP}$-hard and $\mathsf{APX}$-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions [P. Marcotte, Math. Prog., 34 (1986), pp. 142--162]. We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. Then, we prove that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, for example, this best-of-two approach achieves an approximation factor of $49/41\approx 1.195$, which improves on the factor of $5/4$ that has been shown before by Marcotte.

Item Type:	Article
Uncontrolled Keywords:	bilevel optimization, optimization under equilibrium constraints, network design, Wardrop equilibrium, computational complexity, approximation algorithms
Depositing User:	Symplectic Admin
Date Deposited:	17 Mar 2017 15:00
Last Modified:	19 Jan 2023 07:09
DOI:	10.1137/15M1016461
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3006499