An Improved Relax-and-Fix Algorithm for the Fixed Charge Network Design Problem with User-optimal Flow

摘要

Due to the constant development of society, increasing quantities of commodities have to be transported in large urban centers. Therefore, network planning problems arise as tools to support decision-making, aiming to meet the need of finding efficient ways to perform such transportations. This paper review a bi-level formulation, an one level formulation obtained by applying the complementary slackness theorem, Bellman's optimality conditions and presents an improved Relax-and-Fix heuristic, through combining a randomized constructive algorithm with a Relax-and-Fix heuristic, so high quality solutions could be found. Besides that, our computational results are compared with the results found by an one-level formulation and other heuristics found in the literature, showing the efficiency of the proposed method.