access icon free Hybrid machine learning and optimisation method to solve a tri-level road network protection problem

In this study, the authors employ machine learning to develop a new solution method for solving a tri-level network protection problem. In the upper-level, the planner aims to minimise the impact of the interdictor's attempt to disrupt a road network through protection activities. At the middle-level, however, the interdictor seeks to maximise the network's cost function, that is total travel time while the user equilibrium assignment models the road users behaviour at the lower-level. The proposed solution algorithm combines implicit enumeration with machine learning for faster performance. In so doing, four machine learning methods are evaluated among which the artificial neural network model shows the best performance and thereby to be exploited. Principal component analysis is also employed as part of the data pre-processing to perform dimensionality reduction. The proposed solution algorithm exhibits a reasonable level of tractability when employed to solve large problems in which a real-world network is under investigation. Although it cannot guarantee global optimality, it is argued that this is an essential compromise for the application of the network optimisation problems on extensive real-world networks and the large solution space that they generate.

Inspec keywords: roads; learning (artificial intelligence); principal component analysis; behavioural sciences computing; neural nets; optimisation; traffic engineering computing

Other keywords: protection activities; optimisation method; road users behaviour; user equilibrium assignment; hybrid machine learning; artificial neural network model; tri-level road network protection problem; network cost function maximisation; data preprocessing; principal component analysis; dimensionality reduction; network optimisation problems

Subjects: Social and behavioural sciences computing; Traffic engineering computing; Neural computing techniques; Other topics in statistics; Knowledge engineering techniques; Optimisation techniques

References

    1. 1)
      • 10. Faturechi, R., Miller-Hooks, E.: ‘Measuring the performance of transportation infrastructure systems in disasters: a comprehensive review’, ASCE J. Infrastruct. Syst., 2014, 21, (1), pp. 115.
    2. 2)
      • 21. Scaparra, M.P., Church, R.L.: ‘Protecting supply systems to mitigate potential disaster: a model to fortify capacitated facilities’, Int. Reg. Sci. Rev., 2010, 35, (2), p. 22.
    3. 3)
      • 37. Wu, J.H., Florian, M., He, S.: ‘An algorithm for multi-class network equilibrium problem in PCE of trucks: application to the SCAG travel demand model’, Transportmetrica, 2006, 2, (1), pp. 19. Available at http://www.tandfonline.com/doi/abs/10.1080/18128600608685656.
    4. 4)
      • 40. Chen, A., Yang, H., Lo, H.K., et al: ‘Capacity reliability of a road network: an assessment methodology and numerical results’, Trans. Res. B, Methodol., 2002, 36, (3), pp. 225252.
    5. 5)
      • 16. Bash, E.: ‘Methodologies to estimate the economic impacts of disruptions to the goods movement system’, 2012, vol. 1.
    6. 6)
      • 7. Faturechi, R., Miller-Hooks, E.: ‘Travel time resilience of roadway networks under disaster’, Transp. Res. B, Methodol., 2014, 70, pp. 4764. Available at http://dx.doi.org/10.1016/j.trb.2014.08.007.
    7. 7)
      • 11. Gao, Z., Wu, J., Sun, H.: ‘Solution algorithm for the bi-level discrete network design problem’, Transp. Res. B, Methodol., 2005, 39, (6), pp. 479495.
    8. 8)
      • 41. Jenks, G.F.: ‘The data model concept in statistical mapping’, Int. Yearb. Cartography, 1967, 7, (1), pp. 186190.
    9. 9)
      • 33. Ho, T.K.: ‘Random decision forests’. 1995 Proc. of the Third Int. Conf. on Document Analysis and Recognition, Montreal, Quebec, Canada, 1995, vol. 1, pp. 278282.
    10. 10)
      • 46. Cappanera, P., Scaparra, M.P.: ‘Optimal allocation of protective resources in shortest-path networks’, Transp. Sci., 2011, 45, (1), pp. 6480.
    11. 11)
      • 26. Mohammed, M., Khan, M.B., Bashier, E.B.M.: ‘Machine learning: algorithms and applications’ (CRC Press, Boca Raton, Florida, 2016).
    12. 12)
      • 35. LeCun, Y., Bengio, Y., Hinton, G.: ‘Deep learning’, Nature, 2015, 521, (7553), pp. 436444.
    13. 13)
      • 15. Rodríguez, H., Quarantelli, E.L., Dynes, R.R., et al: ‘Handbook of disaster research’, vol. 643(Springer, 2007).
    14. 14)
      • 43. Rodrigues, M., de la Riva, J.: ‘An insight into machine-learning algorithms to model human-caused wildfire occurrence’, Environ. Model. Softw., 2014, 57, pp. 192201.
    15. 15)
      • 22. Israeli, E., Wood, R.K.: ‘Shortest-path network interdiction’, Networks, 2002, 40, (2), pp. 97111.
    16. 16)
      • 3. Kaviani, A., Thompson, R.G., Rajabifard, A., et al: ‘A model for multi-class road network recovery scheduling of regional road networks’, Transportation, 2018, pp. 135.
    17. 17)
      • 24. Araghi, S., Khosravi, A., Creighton, D.: ‘A review on computational intelligence methods for controlling traffic signal timing’, Expert Syst. Appl., 2015, 42, (3), pp. 15381550.
    18. 18)
      • 31. Cox, D.R.: ‘The regression analysis of binary sequences’, J. R. Stat. Soc. B, Methodol., 1958, 20, (2), pp. 215242.
    19. 19)
      • 47. Korf, R.E.: ‘Depth-first iterative-deepening: an optimal admissible tree search’, Artif. Intell., 1985, 27, (1), pp. 97109.
    20. 20)
      • 28. Liu, R., Agrawal, A., Liao, W.-K., et al: ‘Pruned search: a machine learning based meta-heuristic approach for constrained continuous optimization’. 2015 Eighth Int. Conf. on Contemporary Computing (IC3), Noida, India, 2015, pp. 1318.
    21. 21)
      • 9. Zhang, X., Miller-Hooks, E.: ‘Scheduling short-term recovery activities to maximize transportation network resilience’, J. Comput. Civ. Eng., 2015, 29, (6), p. 04014087.
    22. 22)
      • 12. Farvaresh, H., Sepehri, M.M.: ‘A branch and bound algorithm for bi-level discrete network design problem’, Netw. Spat. Econ., 2013, 13, (1), pp. 67106.
    23. 23)
      • 27. Cassioli, A., Di Lorenzo, D., Locatelli, M., et al: ‘Machine learning for global optimization’, Comput. Optim. Appl., 2012, 51, (1), pp. 279303.
    24. 24)
      • 29. Guo, P., Cheng, W., Wang, Y.: ‘Hybrid evolutionary algorithm with extreme machine learning fitness function evaluation for two-stage capacitated facility location problems’, Expert Syst. Appl., 2017, 71, pp. 5768.
    25. 25)
      • 18. Yang, H., Bell, M.G.H.: ‘Models and algorithms for road network design: a review and some new developments’, Transp. Rev., 1998, 18, (3), pp. 257278.
    26. 26)
      • 2. Miller-Hooks, E., Zhang, X., Faturechi, R.: ‘Measuring and maximizing resilience of freight transportation networks’, Comput. Oper. Res., 2012, 39, (7), pp. 16331643. Available at http://dx.doi.org/10.1016/j.cor.2011.09.017.
    27. 27)
      • 20. Cormican, K.J., Morton, D.P., Wood, R.K.: ‘Stochastic network interdiction’, Oper. Res., 1998, 46, (2), pp. 184197.
    28. 28)
      • 5. Zhang, X., Miller-Hooks, E., Denny, K.: ‘Assessing the role of network topology in transportation network resilience’, J. Transp. Geogr., 2015, 46, pp. 3545. Available at http://dx.doi.org/10.1016/j.jtrangeo.2015.05.006.
    29. 29)
      • 1. Kaviani, A., Thompson, R.G., Rajabifard, A., et al: ‘A decision support system for improving the management of traffic networks during disasters’. 37th, 2015 Australasian Transport Research Forum (ATRF), Sydney, New South Wales, Australia, 2015.
    30. 30)
      • 30. Bagloee, S.A., Asadi, M., Sarvi, M., et al: ‘A hybrid machine learning and optimization method to solve bi-level problems’, Expert Syst. Appl., 2017, 95, pp. 142152.
    31. 31)
      • 38. Chen, L., Miller-Hooks, E.: ‘Resilience: an indicator of recovery capability in intermodal freight transport’, Transp. Sci., 2012, 46, (1), pp. 109123.
    32. 32)
      • 25. Jimbo, T., Fujinami, K.: ‘Detecting mischoice of public transportation route based on smartphone and GIS’. Adjunct Proc. of the 2015 ACM Int. Joint Conf. on Pervasive and Ubiquitous Computing and Proc. of the 2015 ACM Int. Symp. on Wearable Computers, Osaka, Japan, 2015, pp. 165168.
    33. 33)
      • 6. Kaviani, A., Thompson, R.G., Rajabifard, A.: ‘Improving regional road network resilience by optimised traffic guidance’, Transportmetrica A, Transp. Sci., 2017, 13, (9), pp. 133.
    34. 34)
      • 14. Patriksson, M.: ‘The traffic assignment problem: models and methods’, Ann. Phys., 1994, 54, (2), p. xii, 223pp..
    35. 35)
      • 42. Powers, D.M.: ‘Evaluation: from precision, recall and f-measure to ROC, informedness, markedness and correlation’, 2011.
    36. 36)
      • 36. Wardrop, J.G.: ‘Some theoretical aspects of road traffic research’. Proc. Institution Civil Engineers, London, UK, 1952, vol. 1, VN - re.
    37. 37)
      • 39. Chang, C.H., Tung, Y.K., Yang, J.C.: ‘Monte Carlo simulation for correlated variables with marginal distributions’, J. Hydraul. Eng., 1994, 120, (3), pp. 313331.
    38. 38)
      • 23. Lim, C., Smith, J.C.: ‘Algorithms for discrete and continuous multicommodity flow network interdiction problems’, IIE Trans., 2007, 39, (1), pp. 1526.
    39. 39)
      • 13. Gibbons, R.: ‘Game theory for applied economists’ (Princeton University Press, Princeton, 1992).
    40. 40)
      • 17. Bye, P.: ‘A pre-event recovery planning guide for transportation’, vol. 753 (Transportation Research Board, Washington, D.C., 2013).
    41. 41)
      • 34. Cortes, C., Vapnik, V.: ‘Support-vector networks’, Mach. Learn., 1995, 20, (3), pp. 273297.
    42. 42)
      • 45. Scaparra, M.P., Church, R.L.: ‘A bilevel mixed-integer program for critical infrastructure protection planning’, Comput. Oper. Res., 2008, 35, (6), pp. 19051923.
    43. 43)
      • 19. Patil, G., Ukkusuri, S.: ‘System-optimal stochastic transportation network design’, Transp. Res. Rec., J. Transp. Res. Board, 2007, 2029, pp. 8086.
    44. 44)
      • 4. Faturechi, R., Miller-Hooks, E.: ‘A mathematical framework for quantifying and optimizing protective actions for civil infrastructure systems’, Comput.-Aided Civ. Infrastruct. Eng., 2014, 29, (8), pp. 572589.
    45. 45)
      • 32. Freund, Y., Mason, L.: ‘The alternating decision tree learning algorithm’. Int. Conf. on Machine Learning (ICML), Bled, Slovenia, 1999, vol. 99, pp. 124133.
    46. 46)
      • 8. Fan, Y., Liu, C.: ‘Solving stochastic transportation network protection problems using the progressive hedging-based method’, Netw. Spat. Econ., 2010, 10, (2), pp. 193208.
    47. 47)
      • 44. Kingma, D.P., Ba, J.: ‘Adam: a method for stochastic optimization’, arXiv preprint arXiv:1412.6980, 2014.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-its.2018.5168
Loading

Related content

content/journals/10.1049/iet-its.2018.5168
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading