A General Methodology for Reducing Computing Times of Road Network Design Algorithms

Document Type : Research Paper

Authors

1 Department of Roads, Vilnius Gediminas Technical University, Vilnius, Lithuania

2 Department of Civil, Architectural and Environmental Engineering, Federico II University of Naples, Naples, Italy

3 Department of Engineering, University of Sannio, Benevento, Italy

Abstract

In this paper a general methodology is proposed for reducing computing times in procedures for solving RNDPs. 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. 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 assignment approaches.

Keywords

Main Subjects

References

Abdulaal M. and Le Blanc L.J. (1979). Continuous equilibrium network design models. Transportation Research Part B, Vol. 13, pp. 19-32.
Babazadeh A., Poorzahedy H. and Nikoosokhan S. (2011). Application of particle swarm optimization to transportation network design problem. Journal of King Saud University – Science, Vol. 23, pp. 293-300.
Bagloee S.A. and Sarvi M. (2018). An outer approximation method for the road network design problem. PLoS ONE, Vol. 13, art.no. e0192454. pp. 1-28.
Bagloee S.A., Sarvi M., Rajabifard A., Thompson R.S. and Saberi M. (2016). A solution to the road network design problem for multimodal flow. Proceedings of the 19th IEEE International Conference on Intelligent Transportation Systems (IEEE ITSC 2016), pp. 235-240.
Billheimer J.W. and Gray P. (1973). Network design with fixed and variable cost elements. Transportation Science, Vol. 7, pp. 49-74.
Cantarella G.E. (1997). A general fixed-point approach to multimode multi-user equilibrium assignment with elastic demand. Transportation Science, Vol. 31, pp. 107-128.
Cantarella G.E., de Luca S., Di Pace R. and Memoli S. (2015a). Network Signal Setting Design:
Meta-heuristic optimisation methods. Transportation Research Part C, Vol. 55, 24-45.
Cantarella G.E., de Luca S., Di Gangi M. and Di Pace R. (2015b). Approaches for solving the stochastic equilibrium assignment with variable demand: internal vs. external solution algorithms. Optimization Methods & Software, Vol. 30, pp. 338-364.
Cantarella G.E., Pavone G. and Vitetta A. (2006). Heuristics for urban road network design: lane layout and signal settings. European Journal of Operational Research, Vol. 175, pp. 1682-1695.
Cantarella G.E. and Vitetta A. (2006). The multi-criteria road network design problem in an urban area. Transportation, Vol. 33, pp. 567-588.
Cao J.X., Wang Y., Wei Z.M. and Wu J. (2013). Solve the discrete network design problem under construction cost uncertainties with the stochastic programming approach. Procedia - Social and Behavioral Sciences, Vol. 96, pp. 1039-1049.
Cascetta E. (2009). Transportation systems analysis: Models and applications. Springer, New York (NY), USA.
Cascetta E., Gallo M. and Montella B. (2006). Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment. Annals of Operations Research, Vol. 144,
pp. 301-328.
Chen A., Zhou Z., Chootinan P., Ryu S., Yang C. and Wong S.C. (2011). Transport Network Design Problem under Uncertainty: A Review and New Developments. Transport Reviews, Vol. 31, pp. 743-768.
Chiou S.W. (2005). Bilevel programming for the continuous transport network design problem. Transportation Research Part B, Vol. 39, pp. 361-383.
D’Acierno L., Gallo M. and Montella B. (2011). A fixed-point model and solution algorithms for simulating urban freight distribution in a multimodal context. Journal of Applied Sciences, Vol. 11,
pp. 647-654.
D’Acierno L., Gallo M. and Montella B. (2013). Application of metaheuristics to large-scale transportation problems. Lecture Notes in Computer Science, Vol. 8353, pp. 215-222.
D’Acierno L., Montella B. and De Lucia F. (2006). A stochastic traffic assignment algorithm based on Ant Colony Optimisation. Lecture Notes in Computer Science, Vol. 4150, pp. 25-36.
Daganzo C.F. (1983). Stochastic network equilibrium with multiple vehicle types and asymmetric, indefinite link cost Jacobians. Transportation Science, Vol. 17, pp. 282-300.
Di Z., Yang L., Qi J. and Gao Z. (2018). Transportation network design for maximizing flow-based accessibility. Transportation Research Part B, Vol. 110, pp. 209-238.
Dimitriou L., Tsekeris T. and Stathopoulos A. (2008). Genetic computation of road network design and pricing Stackelberg games with multi-class users. In: Giacobini, M. et al. (Eds.), Applications of Evolutionary Computing. Springer, Berlin, Heidelberg, pp. 669-678.
Drezner Z. and Wesolowsky G.O. (2003). Network design: Selection and design of links and facility location. Transportation Research Part A, Vol. 37, pp. 241-256.
Farahani R.Z., Miandoabchi E., Szeto W.Y. and Rashidi H. (2013). A review of urban transportation network design problems. European Journal of Operational Research, Vol. 229, pp. 281-302.
Feremans C., Labbé M. and Laporte G. (2003). Generalized network design problems. European Journal of Operational Research, Vol. 148, pp. 1-13.
Fontaine P. and Minner S. (2018). Benders decomposition for the Hazmat Transport Network Design Problem. European Journal of Operational Research, Vo. 267, pp. 996-1002.
Gallo M., D’Acierno L. and Montella, B. (2010). A meta-heuristic approach for solving the urban network design problem. European Journal of Operational Research, Vol. 201, pp. 144-157.
Gallo M., D’Acierno L. and Montella B. (2012). A meta-heuristic algorithm for solving the road network design problem in regional contexts. Procedia – Social and Behavioral Sciences, Vol. 54, pp. 84-95.
Gao Z., Wu J. and Sun H. (2005). Solution algorithm for the bi-level discrete network design problem. Transportation Research Part B, Vol. 39, pp. 479-495.
Guihaire V. and Hao J. (2008). Transit network design and scheduling: a global review. Transportation Research Part A, Vol. 42, pp. 1251-1273.
Haas I. and Bekhor S. (2017). Network design problem considering system time minimization and road safety maximization: formulation and solution approaches. Transportmetrica A, Vol. 13, pp. 829-851.
Hosseininasab S.-M. and Shetab-Boushehri S.-N. (2015). Integration of selecting and scheduling urban road construction projects as a time-dependent discrete network design problem. European Journal of Operational Research, Vol. 246, pp. 762-771.
Khooban Z., Farahani R.Z., Miandoabchi E. and Szeto W.Y. (2015). Mixed network design using hybrid scatter search. European Journal of Operational Research, Vol. 247, pp. 699-710.
Memoli S., Cantarella G.E., de Luca S. and Di Pace R. (2017). Network signal setting design with stage sequence optimisation. Transportation Research Part B, Vol. 100, pp. 20-42.
Liu H. and Wang D.Z.W. (2015). Global optimization method for network design problem with stochastic user equilibrium. Transportation Research Part B, Vol. 72, pp. 20-39.
Liu H. and Wang D.Z.W. (2016). Modeling and solving discrete network design problem with stochastic user equilibrium. Journal of Advanced Transportation, Vol. 50, pp. 1295-1313.
Lo H.K. and Szeto W.Y. (2009). Time-dependent transport network design under cost-recovery. Transportation Research Part B, Vol. 43, pp. 142–158.
Magnanti T.L. and Wong R.T. (1984). Network design and transportation planning: models and algorithms. Transportation Science, Vol. 18, pp. 1-55.
Poorzahedy H. and Abulghasemi F. (2005). Application of ant system to network design problem. Transportation, Vol. 32, pp. 251-273.
Poorzahedy H. and Rouhani O.M. (2007). Hybrid meta-heuristic algorithms for solving network design problem. European Journal of Operational Research, Vol. 182, pp. 578-596.
Sheffi Y. and Powell W.B. (1981). A comparison of stochastic and deterministic traffic assignment over congested networks. Transportation Research Part B, Vol. 15, pp. 53-64.
Solanki R.S., Gorti J.K. and Southworth F. (1998). Using decomposition in large-scale highway network design with a quasi-optimization heuristic. Transportation Research Part B, Vol. 32, pp. 127-140.
Szeto W.Y., Jiang Y. and Wang D.Z.W. (2015). A sustainable road network design problem with land use transportation interaction over time. Networks and Spatial Economics, Vol. 15, pp. 791-822.
Tan Z., Yang H., Tan W. and Li Z. (2016). Pareto-improving transportation network design and ownership regimes. Transportation Research Part B, Vol. 91, pp. 292-309.
Ukkusuri S.V. and Patil G. (2009). Multi-period transportation network design under demand uncertainty. Transportation Research Part B, Vol. 43, pp. 625-642.
Wang D.Z.W., Liu H. and Szeto W.Y. (2015). A novel discrete network design problem formulation and its global optimization solution algorithm. Transportation Research Part E, Vol. 79, pp. 213-230.
Wang D.Z.W. and Lo H.K. (2010). Global optimum of the linearized network design problem with equilibrium flows. Transportation Research Part B, Vol. 44, pp. 482-492.
Wang S., Meng Q. and Yang H. (2013). Global optimization methods for the discrete network design problem. Transportation Research Part B, Vol. 50, pp. 42-60.
Xu M., Wang G., Grant-Muller S. and Gao Z. (2017). Joint road toll pricing and capacity development in discrete transport network design problem. Transportation, Vol. 44, pp. 731-752.
Xu X., Chen A. and Yang C. (2016). A review of sustainable network design for road networks. KSCE Journal of Civil Engineering, Vol. 20, pp. 1084-1098.
Yang H. (1997). Sensitivity analysis for the elastic-demand network equilibrium problem with applications. Transportation Research Part B, Vol. 31, pp. 55-70.
Yang H. and  Bell M.G.H. (1998). Models and algorithms for road network design: a review and some new developments. Transport Reviews, Vol. 18, pp. 257-278.

Files

Share

How to cite

Statistics