http://iet.metastore.ingenta.com
1887

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

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

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Intelligent Transport Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • 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.
    2. 2)
      • 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.
    3. 3)
      • 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.
    4. 4)
      • 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.
    5. 5)
      • 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.
    6. 6)
      • 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.
    7. 7)
      • 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.
    8. 8)
      • 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.
    9. 9)
      • 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.
    10. 10)
      • 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.
    11. 11)
      • 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.
    12. 12)
      • 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.
    13. 13)
      • 13. Gibbons, R.: ‘Game theory for applied economists’ (Princeton University Press, Princeton, 1992).
    14. 14)
      • 14. Patriksson, M.: ‘The traffic assignment problem: models and methods’, Ann. Phys., 1994, 54, (2), p. xii, 223pp..
    15. 15)
      • 15. Rodríguez, H., Quarantelli, E.L., Dynes, R.R., et al: ‘Handbook of disaster research’, vol. 643(Springer, 2007).
    16. 16)
      • 16. Bash, E.: ‘Methodologies to estimate the economic impacts of disruptions to the goods movement system’, 2012, vol. 1.
    17. 17)
      • 17. Bye, P.: ‘A pre-event recovery planning guide for transportation’, vol. 753 (Transportation Research Board, Washington, D.C., 2013).
    18. 18)
      • 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.
    19. 19)
      • 19. Patil, G., Ukkusuri, S.: ‘System-optimal stochastic transportation network design’, Transp. Res. Rec., J. Transp. Res. Board, 2007, 2029, pp. 8086.
    20. 20)
      • 20. Cormican, K.J., Morton, D.P., Wood, R.K.: ‘Stochastic network interdiction’, Oper. Res., 1998, 46, (2), pp. 184197.
    21. 21)
      • 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.
    22. 22)
      • 22. Israeli, E., Wood, R.K.: ‘Shortest-path network interdiction’, Networks, 2002, 40, (2), pp. 97111.
    23. 23)
      • 23. Lim, C., Smith, J.C.: ‘Algorithms for discrete and continuous multicommodity flow network interdiction problems’, IIE Trans., 2007, 39, (1), pp. 1526.
    24. 24)
      • 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.
    25. 25)
      • 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.
    26. 26)
      • 26. Mohammed, M., Khan, M.B., Bashier, E.B.M.: ‘Machine learning: algorithms and applications’ (CRC Press, Boca Raton, Florida, 2016).
    27. 27)
      • 27. Cassioli, A., Di Lorenzo, D., Locatelli, M., et al: ‘Machine learning for global optimization’, Comput. Optim. Appl., 2012, 51, (1), pp. 279303.
    28. 28)
      • 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.
    29. 29)
      • 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.
    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)
      • 31. Cox, D.R.: ‘The regression analysis of binary sequences’, J. R. Stat. Soc. B, Methodol., 1958, 20, (2), pp. 215242.
    32. 32)
      • 32. Freund, Y., Mason, L.: ‘The alternating decision tree learning algorithm’. Int. Conf. on Machine Learning (ICML), Bled, Slovenia, 1999, vol. 99, pp. 124133.
    33. 33)
      • 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.
    34. 34)
      • 34. Cortes, C., Vapnik, V.: ‘Support-vector networks’, Mach. Learn., 1995, 20, (3), pp. 273297.
    35. 35)
      • 35. LeCun, Y., Bengio, Y., Hinton, G.: ‘Deep learning’, Nature, 2015, 521, (7553), pp. 436444.
    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)
      • 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.
    38. 38)
      • 38. Chen, L., Miller-Hooks, E.: ‘Resilience: an indicator of recovery capability in intermodal freight transport’, Transp. Sci., 2012, 46, (1), pp. 109123.
    39. 39)
      • 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.
    40. 40)
      • 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.
    41. 41)
      • 41. Jenks, G.F.: ‘The data model concept in statistical mapping’, Int. Yearb. Cartography, 1967, 7, (1), pp. 186190.
    42. 42)
      • 42. Powers, D.M.: ‘Evaluation: from precision, recall and f-measure to ROC, informedness, markedness and correlation’, 2011.
    43. 43)
      • 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.
    44. 44)
      • 44. Kingma, D.P., Ba, J.: ‘Adam: a method for stochastic optimization’, arXiv preprint arXiv:1412.6980, 2014.
    45. 45)
      • 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.
    46. 46)
      • 46. Cappanera, P., Scaparra, M.P.: ‘Optimal allocation of protective resources in shortest-path networks’, Transp. Sci., 2011, 45, (1), pp. 6480.
    47. 47)
      • 47. Korf, R.E.: ‘Depth-first iterative-deepening: an optimal admissible tree search’, Artif. Intell., 1985, 27, (1), pp. 97109.
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
This is a required field
Please enter a valid email address