A parsimonious heuristic for the discrete network design problem

Abstract

The problem of selecting the optimal set of transportation projects out of a given set of projects, known as the network design problem (NDP), has been researched for many years. Typical transportation projects are interdependent in their nature, which turns the problem into a very complex one. When a certain objective is sought, an exact solution of the problem can be derived only by enumerating each possible project combination. Therefore, when a large set of possible combinations is involved an alternative approach must be taken. Meta-heuristic methods usually used for this purpose do not make use of the special properties of the given problem. This paper proposes an alternative heuristic that simplifies significantly the solution process. The benefit of a certain combination of projects is inferred based on a subset (pairs or triplets) of projects. The proposed heuristic is tested on simple networks and applied for a real-size network. The paper also discusses the trade-offs between solution accuracy and computation time.

Keywords:

• network design problem
• project selection
• project interdependencies
• traffic assignment

ORCID

Inbal Haas http://orcid.org/0000-0002-2003-3788

Shlomo Bekhor http://orcid.org/0000-0002-9152-6336

Acknowledgement

The authors gratefully acknowledge the insightful comments of the four anonymous reviewers, and their contribution to the current version of the paper.

Additional information

Funding

This work was supported in part by the Israel Science Foundation administered by the Israel Academy of Sciences [grant number 1479/13].