A metaheuristic approach to the discrete network design problem based on the demand uncertainty

摘要

The discrete network design problem (DNDP) aims to construct new routes or improve existing routes in order to enhance the performance of a traffic network system under the condition of limited budgets and network constraints. It is a complex multi-constrained and NP-Hard problem can prove both time consuming and challenging. Due to these difficulties, metaheuristic approaches are highly suitable for solving the DNDP. Usually the fixed demand is used in the model of the DNDP. However, our paper introduces a framework for solving a bi-level model of DNDP based on the uncertain demand, and also presents some key procedures of metaheuristic approaches improved on the previous published [1], such as the representation, initialization and neighborhood. At the same time, our approach is validated using a simple simulated annealing algorithm. In addition, our method solves the Nguyen-Dupuis benchmark problem.