Premium
Bicriterion discrete equilibrium network design problem
Author(s) -
Xie Chi
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21546
Subject(s) - mathematical optimization , network planning and design , heuristics , parameterized complexity , computer science , fixed charge , integer programming , set (abstract data type) , benders' decomposition , flow network , solution set , mathematics , algorithm , computer network , chemistry , molecular physics , programming language
The budget network design problem and fixed‐charge network design problem imply different economic pursuits on travel cost and construction cost and structure these two cost components in different ways. A more general version of these two classic formulations is the biobjective network design problem. This article discusses an exact solution strategy for the biobjective discrete network design problem with equilibrium constraints, which eliminates the inexactness and incompleteness deficiencies pertaining to heuristics or metaheuristics presented in previous research. In particular, we adapted and justified a dichotomic solution framework for the biobjective network design problem, in which the complete solution set of the problem can be exhausted by repeatedly solving a parameterized scalar problem and updating the parameter set. A generalized Benders decomposition method, a widely used solution strategy for nonlinear mixed integer programming problems, is further implemented in the solution framework, which offers an efficient algorithmic tool for solution of the scalar problem. Numerical results obtained from the example problems justify the solution optimality, completeness, and efficiency of the presented solution method. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 286–305 2014