Solving the Bi-level Linear Programming Network Design Problem (BLPNDP), which is typically regarded as a strongly NP-complete problem, with traditional mathematical programming algorithms is computationally intractable. A majority of the research efforts have been focused on tackling this problem using meta-heuristics. However, the evaluation functions in most meta-heuristic approaches involve dynamic traffic simulation when evaluating feasible capacity expansion policies. This commonly used evaluation function becomes a major bottleneck constraining the applicability of meta-heuristics as it is computationally expensive and analytically complicated. To address this issue, we present a modified Genetic Algorithm (GA) to solve the BLPNDP with a novel evaluation function which reduces the number of dynamic traffic simulations needed. The heuristic exploits the underlying linear programming structure of the BLPNDP and employs dual variable approximation techniques to estimate the evaluation function instead of dynamic traffic simulation. Empirical analyses are conducted on three networks of varying sizes to examine the performance of the GA based heuristic. From the experiments conducted, the proposed GA based heuristic outperforms the traditional GA. Also the proposed method of estimating the evaluation function is flexible and can be used within the framework of many meta-heuristic approaches.
A genetic algorithm for bi-level linear programming dynamic network design problem
Transportation Letters ; 1 , 4 ; 281-294
2009-10-01
14 pages
Article (Journal)
Electronic Resource
English
Dynamic Continuous Network Design Problem: Linear Bilevel Programming and Metaheuristic Approaches
Transportation Research Record | 2006
|Dynamic Continuous Network Design Problem: Linear Bilevel Programming and Metaheuristic Approaches
British Library Conference Proceedings | 2006
|Dynamic Continuous Network Design Problem: Linear Bilevel Programming and Metaheuristic Approaches
Online Contents | 2006
|Bi-Level Programming Model in Road Network Programming and Its Genetic Algorithm
British Library Conference Proceedings | 2007
|