A hybrid bacterial foraging – simulated annealing framework for improving road networks

Abstract

Effective techniques for reducing traffic congestion include adding new edges to the road network or increasing the capacity of existing edges. To determine the optimal set of improvements that can be made to an existing road network, it is standard practise to solve a Discrete Network Design Problem. Due to the bi-level nature of its formulation, it is one of the most difficult problems to solve to optimality. The Bacterial Foraging Optimization technique has been investigated in a previous work to gauge its effectiveness in determining the n-optimal solution to the Discrete Network Design Problem. This concept is further developed in this paper by hybridizing the Bacterial Foraging Optimization algorithm with Simulated Annealing. In the elimination step, the metropolis criterion from Simulated Annealing ensures a more diverse search of the solution space. We also employ a modified candidate set of improvements that incorporates both edge and capacity additions. The effectiveness of the hybrid bacterial foraging optimization algorithm in determining n-optimal solutions to the Discrete Network Design Problem has been demonstrated by testing it on the 24-node, 76-arc Sioux Falls network.

Keywords

• Road network
• Bacterial foraging optimization
• Simulated annealing
• Network design