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

In this paper a general methodology is proposed for reducing computing times in procedures for solving road network design problems. Extensively studied in the literature, such problems 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 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 hence 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 of up to 80% compared to traditional approaches.