A general methodology for reducing computing times of road network design algorithms

Abstract

In this paper, a general methodology for reducing computing times in procedures for solving road network design problems is proposed. Such problems which are studied extensively in the related literature concern the design of road networks, in terms of flow directions, capacity expansion and signal settings in urban contexts, and in terms of link addition and capacity expansion in rural contexts. The solution to them is almost always formulated as a bi-level model, where the upper level operates on the network design decision variables while the lower level estimates the equilibrium traffic flows, which must be known in order to determine objective function values. Computing times required for calculating equilibrium traffic flows at each iteration of the network design procedure significantly affect the total solution time. Hence, any reduction in computing times of the lower level, which has to be implemented numerous times at any step of the upper-level algorithm, allows the global computing time to be considerably reduced. In this context, the methodology proposed herein seeks to reduce computing times of the traffic assignment problem and in turn of the whole network design procedure, acting on the traffic flows adopted in the initialisation phase of the assignment algorithm. Obviously, this approach is feasible only if the topology of the network configuration remains unchanged and therefore only if the network design decision variables are limited to capacity expansion in rural contexts, or signal settings and capacity expansion in urban contexts. The proposed approach is tested on a real-scale case study: the rural road network of Vilnius County (Lithuania). Preliminary results underline the feasibility of the proposal and a significant reduction in computing times -- up to 80% -- compared to traditional approaches.