An Evaluation of Heuristic Methods for Determining Optimal Link Capacity Expansions on Road Network

Abstract

Since the bilevel formulation of the Continuous Network Design Problem (CNDP) has the characteristic of a non- convex optimization problem, heuristic methods are usually the preferred option for solving it. On the other hand, the computation time is crucial importance for solving the CNDP because the algorithms implemented on real sized networks require solving traffic assignment model many times, in which algorithms spend more time in comparison with the other parts of the solution process. Therefore, solving the CNDP with less number of traffic assignments can be assessed as one of the most important topics in the transportation field. Thus, the paper deals with analyzing the performance of recently developed heuristic methods in solving the CNDP. In this study, the capability of Harmony Search (HS), Artificial Bee Colony (ABC) and Differential Evolution (DE) algorithms for solving the CNDP is evaluated, and numerical calculations are performed on example test networks. The results obtained through the HS, ABC and DE algorithms on 18-link network are compared with those generated by two different heuristic methods, which are available in a previous study. Additionally, the performance of the proposed heuristics is compared on Sioux Falls city network with other major algorithms available in the literature. Numerical examples have clearly indicated that the DE shows good performance in comparison with the proposed algorithms in terms of both objective function value and required computational effort.