[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Emergency management using geographic information systems: application to the first Romanian traveling salesman problem instance

  • Regular Paper
  • Published:
Knowledge and Information Systems Aims and scope Submit manuscript

Abstract

The strategic design of logistic networks, such as roads, railways or mobile phone networks, is essential for efficiently managing emergency situations. The geographic coordinate systems could be used to produce new traveling salesman problem (TSP) instances with geographic information systems (GIS) features. The current paper introduces a recurrent framework designed for building a sequence of instances in a systematic way. The framework intends to model real-life random adverse events manifested on large areas, as massive rainfalls or the arrival of a polar front, or targeted relief supply in early stages of the response. As a proof of concept for this framework, we use the first Romanian TSP instance with the main human settlements, in order to derive several sequences of instances. Nowadays state-of-the-art algorithms for TSP are used to solve these instances. A branch-and-cut algorithm delivers the integer exact solutions, using substantial computing resources. An implementation of the Lin–Kernighan heuristic is used to rapidly find very good near-optimal integer solutions to the same instances. The Lin–Kernighan heuristic shows stability on the tested instances. Further work could be done to better exploit GIS features in order to efficiently tackle operations on large areas and to test the solutions delivered by other algorithms on new instances, derived using the introduced framework.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Notes

  1. The instances are available by request to the authors.

References

  1. Adulyasak Y, Cordeau J-F, Jans R (2014) Formulations and Branch-and-Cut algorithms for multivehicle production and inventory routing problems. INFORMS J Comput 26(1):103–120

    Article  MathSciNet  Google Scholar 

  2. Ahammed F, Moscato P (2011) Evolving L-systems as an intelligent design approach to find classes of difficult-to-solve traveling salesman problem instances. Lecture notes in computer science, vol 6624, pp 1–11

  3. Apiletti D, Baralis E, Cerquitelli T (2011) Energy-saving models for wireless sensor networks. Knowl Inf Syst 28(3):615–644

    Article  Google Scholar 

  4. Applegate DL, Bixby RE, Chvátal V, Cook WJ (2006) The traveling salesman problem: a computational study. Princeton University Press, Princeton

    MATH  Google Scholar 

  5. ArcGIS online help (2014) http://resources.arcgis.com/

  6. Asakura K, Fukaya K, Watanabe T (2013) A map construction system for disaster areas based on ant colony systems. Procedia Comput Sci 22:494–501

    Article  Google Scholar 

  7. Ausiello G et al (2001) Algorithms for the on-line travelling salesman. Algorithmica 29(4):560–581

    Article  MathSciNet  MATH  Google Scholar 

  8. Church R, ReVelle C (1974) The maximal covering location problem. Pap Reg Sci 32(1):101–118

    Article  Google Scholar 

  9. Cohoon J et al (1998) Perturbation method for probabilistic search for the traveling salesperson problem. In: Bosacchi B et al (eds) Applications and science of neural networks, fuzzy systems, and evolutionary computation. SPIE Press, vol 3455, p 118

  10. Concorde solver (2011) http://www.math.uwaterloo.ca/tsp/concorde.html

  11. Cook WJ (2011) In pursuit of the travelling salesman: mathematics at the limits of computation. Princeton University Press, Princeton

    Google Scholar 

  12. Cook WJ (2005) The traveling salesman problem web server http://www.math.uwaterloo.ca/tsp/

  13. Crainic TG, Crisan GC, Gendreau M, Lahrichi N, Rei W (2009) Multi-thread cooperative optimization for rich combinatorial problems. In: IEEE international parallel & distributed processing symposium, Rome, Italy, pp 2284–2291

  14. Crisan GC, Nechita E (2008) Solving fuzzy TSP with ant algorithms. Int J Comput Commun Control 3S(3):228–231

    Google Scholar 

  15. Crăciunescu V (2007) Romania: general vector datasets. http://earth.unibuc.ro/download/romania-seturi-vectoriale

  16. Crnkovic I, Larsson M (2002) Building reliable component-based software systems. Artech House Publisher, Norwood

    MATH  Google Scholar 

  17. Crucitti P, Latora V, Marchiori M, Rapisarda A (2004) Error and attack tolerance of complex networks. Phys A 340:388–394

    Article  MathSciNet  MATH  Google Scholar 

  18. Curtin KM, Voicu G, Matthew TR, Stefanidis A (2014) A comparative analysis of traveling salesman solutions from geographic information systems. Trans GIS 18(2):286–301

    Article  Google Scholar 

  19. Czyzyk J, Mesnier MP, Morao JJ (1998) The NEOS server. IEEE J Comput Sci Eng 5(3):68–75

    Article  Google Scholar 

  20. Dolan E (2001) The NEOS server 4.0 administrative guide. In: Technical memorandum ANL/MCS-TM-250 Mathematics and Computer Science Division Argonne National Laboratory

  21. Dorigo M, Gambardella LM (1997) Ant colonies for traveling salesman problem. BioSystems 43:73–81

    Article  Google Scholar 

  22. Eldrandaly KA, Abdallah AF (2012) A novel GIS-based decision-making framework for the school bus routing problem. Geo-spat Inf Sci 15(1):51–59

    Article  Google Scholar 

  23. European Commission (2013) Guidance on integrating climate change and biodiversity into strategic environmental assessment. http://ec.europa.eu/environment/eia/pdf/SEA%20Guidance

  24. Fanea A, Motogna S, Diosan L (2006) Automata-based component composition analysis. Studia Universitas Babes-Bolyai Seria Informatica 50(1):13–20

    MathSciNet  MATH  Google Scholar 

  25. Fiechter C-N (1994) A parallel tabu search algorithm for large traveling salesman problems. Discrete Appl Math 51(3):243–267

    Article  MathSciNet  MATH  Google Scholar 

  26. Fiedrich F, Gehbauer F, Rickers U (2000) Optimized resource allocation for emergency response after earthquake disasters. Saf Sci 35(1–3):41–57

    Article  Google Scholar 

  27. Fischer T, Stützle T, Hoos H, Merz P (2005) An analysis of the hardness of TSP instances for two high-performance algorithms. In: Doerner KF et al (ed) Proceedings of the 6th metaheuristics international conference 2005, pp 361–367

  28. Geosphere R package. https://cran.r-project.org/web/packages/geosphere/

  29. Goldwasser M, Johnson DS, McGeoch CC (eds) (2002) In: Proceedings of the fifth and sixth DIMACS implementation challenges, American Mathematical Society

  30. Gomory RE (1960) An algorithm for the mixed integer problem. Technical Report RM 2597, RAND Corporation

  31. Google Maps Android and JavaScript APIs (2015) https://developers.google.com/maps/

  32. GPS Visualizer (2013) http://www.gpsvisualizer.com

  33. Gropp W, Moré JJ (1997) Optimization environments and the NEOS server. Approximation theory and optimization. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  34. Guntsch M, Middendorf M (2001) Pheromone Modification strategies for ant algorithms applied to dynamic TSP. Lecture notes in computer science, vol 2037, pp 213–220

  35. Gutin G, Punnen AP (eds) (2002) The traveling salesman problem and its variations. Combinatorial optimization, vol 12. Springer, New York

    MATH  Google Scholar 

  36. Hoos H, Stützle T (2014) On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem. Eur J Oper Res 238(1):87–94

    Article  MathSciNet  MATH  Google Scholar 

  37. IBM ILOG (2012) User’s manual for CPLEX. ftp://public.dhe.ibm.com/software/websphere/ilog/docs/optimization/cplex/ps_usrmancplex

  38. Investigation Committee on the Accident at the Fukushima Nuclear Power Stations of Tokyo Electric Power Company (2011) Final report. http://www.cas.go.jp/jp/seisaku/icanps/eng/final-report.html

  39. Jaillet P (1985) Probabilistic travelling salesman problems. Ph.D. thesis, MIT

  40. Kang L, Zhou A, McKay B, Li Y, Kang Z (2004) Benchmarking algorithms for dynamic travelling salesman problems. Congr Evol Comput 2:1286–1292

    Google Scholar 

  41. Kemball-Cook D, Stephenson R (1984) Lessons in logistics from Somalia. Disasters 8:57–66

    Article  Google Scholar 

  42. Kirac E et al (2015) The traveling salesman problem with imperfect information with application in disaster relief tour planning. IIE Trans 47(8):783–799

    Article  Google Scholar 

  43. Konecny M, Zlatanova S, Bandrova TL (eds) (2010) Geographic information and cartography for risk and crisis management. Lecture notes in geoinformation and cartography, Springer

  44. Kovács I, Barabási AL (2015) Destruction perfected. Nature 524:38–39

    Article  Google Scholar 

  45. Land AH, Doig AG (1960) An automatic method of solving discrete programming problems. Econometrica 28(3):497–520

    Article  MathSciNet  MATH  Google Scholar 

  46. Lawler EL et al (1985) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, New York

    MATH  Google Scholar 

  47. Lawler EL, Wood DE (1966) Branch-and-bound methods: a survey. Oper Res 14:699–719

    Article  MathSciNet  MATH  Google Scholar 

  48. Li C, Yang M, Kang L (2006) A new approach to solving dynamic traveling salesman problems. Lecture notes in computer science, vol 4247, pp 236–243

  49. Li X, Zhao Z, Zhu X, Wyatt T (2011) Covering models and optimization techniques for emergency response facility location and planning: a review. Math Methods Oper Res 74(3):1–30

    Article  MathSciNet  MATH  Google Scholar 

  50. Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper Res 21(2):498–516

    Article  MathSciNet  MATH  Google Scholar 

  51. Little JDC et al (1963) An algorithm for the traveling salesman problem. Oper Res 11(6):972–989

    Article  MATH  Google Scholar 

  52. Malandraki C, Dial RB (1996) A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. Eur J Oper Res 90(1):45–55

    Article  MATH  Google Scholar 

  53. Mathew N, Smith SL, Waslander SL (2013) A graph-based approach to multi-robot rendezvous for recharging in persistent tasks. In: IEEE conference on robotics and automation

  54. Mitchell JE (2002) Branch-and-Cut algorithms for combinatorial optimization problems. Handbook of applied optimization. Oxford University Press, Oxford GB, pp 65–77

    Google Scholar 

  55. Montemanni R, Barta J, Mastrolilli M, Gambardella LM (2007) The robust traveling salesman problem with interval data. Transp Sci 41(3):366–381

    Article  Google Scholar 

  56. Motogna S, Ciuciu I, Serban C, Vescan A (2015) Improving software quality using an ontology-based approach. Lecture notes in computer science, vol 9416, pp 456–465

  57. National Atlas of the United States. http://www.lib.ncsu.edu/gis/natatlas.html

  58. Nechita E, Talmaciu M, Muraru C (2012) A Bayesian approach for the assessment of risk probability. Case study for digital risk probability. Environ Eng Manag J 11(12):2249–2256

    Google Scholar 

  59. Padberg M, Rinaldi G (1991) A Branch-and-Cut algorithm for the resolution of large-scale symmetric traveling salesman problems. Siam Rev 33:60–100

  60. Padberg M, Rinaldi G (1987) Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut. Oper Res Lett 6:1–7

    Article  MathSciNet  MATH  Google Scholar 

  61. Pintea C-M (2015) A unifying survey of agent-based approaches for equality-generalized traveling salesman problem. Informatica 26(3):509–522

    Article  MathSciNet  Google Scholar 

  62. Pop P, Matei O (2014) An efficient metaheuristic approach for solving a class of matrix optimization problems. In: Toklu YC, Bekdas G (eds) Proceedings EU/ME workshop, pp 17–25

  63. Potvin J-Y (1996) Genetic algorithms for the traveling salesman problem. Ann Oper Res 63(3):337–370

    Article  MATH  Google Scholar 

  64. Purta R, Dobski M, Jaworski A, Madey G (2013) A testbed for investigating the UAV swarm command and control problem using DDDAS. Procedia Comput Sci 18:2018–2027

    Article  Google Scholar 

  65. Reinelt G (1994) The traveling salesman: computational solutions for TSP applications. Springer, New York

    MATH  Google Scholar 

  66. Ridge E, Kudenko D (2008) Determining whether a problem characteristic affects heuristic performance. Stud Comput Intell 153:21–35

    MATH  Google Scholar 

  67. Rodríguez A, Ruiz R (2012) The effect of the asymmetry of road transportation networks on the traveling salesman problem. Comput Oper Res 39:1566–1576

    Article  MathSciNet  MATH  Google Scholar 

  68. Romanian Parliament Law 351 (2001) http://www.cdep.ro/pls/legis/legis_pck.htp_act_text?idt=28862

  69. Romania2950.tsp dataset (2014) doi:10.13140/2.1.4706.8165, http://cadredidactice.ub.ro/ceraselacrisan/cercetare/

  70. Rossant C (2014) IPython interactive computing and visualization cookbook. Packt Publishing, Birmingham

    Google Scholar 

  71. Showalter PS, Lu Y (eds) (2010) Geospatial techniques in urban hazard and disaster analysis. Geotechnologies and the environment, vol 2. Springer, New York

    Google Scholar 

  72. Spielman D, Teng S-H (2001) Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. In: STOC ’01: proceedings of ACM, pp 296–305

  73. Stoean C, Stoean R (2014) Support vector machines and evolutionary algorithms for classification. Springer, New York

    Book  MATH  Google Scholar 

  74. Su S, Yu S, Ma Y, Yang Y, Xu H (2011) Routing on a spherical surface using hybrid PSO. Commun Comput Inf Sci 237:43–51

    Google Scholar 

  75. TerraLib. http://www.terralib.org/

  76. Toregas C, Swain R, ReVelle C, Bergman L (1971) The location of emergency service facilities. Oper Res 19(6):1363–1373

    Article  MATH  Google Scholar 

  77. TSP data test (2009) http://www.math.uwaterloo.ca/tsp/data/index.html

  78. Traveling Salesman Problem, TSP Website, Last Updated by William Cook: November 2014. http://www.math.uwaterloo.ca/tsp/

  79. TSPLIB (2013) http://www.iwr.uni-heidelberg.de/groups/comopt/software

  80. Urquhart N, Scott C, Hart E (2013) Using graphical information systems to improve vehicle routing problem instances. In: GECCO’13 companion, ACM, NY, pp 1097–1102

  81. van Hemert JI (2005) Property analysis of symmetric travelling salesman problem instances acquired through evolution. Lecture notes in computer science, vol 3448, pp 122–131

  82. Wex F et al (2014) Emergency response in natural disaster management: allocation and scheduling of rescue units. Eur J Oper Res 235(3):697–708

    Article  MathSciNet  MATH  Google Scholar 

  83. Wise S (2013) GIS fundamentals, 2nd edn. CRC Press

  84. Zacarias F, Cuapa R, De Ita G, Torres D (2015) Smart tourism in 1-click. Procedia Comput Sci 56:447–452

    Article  Google Scholar 

Download references

Acknowledgments

The authors would like to thank Professor William Cook and Dr. Vasile Crăciunescu for their support. The authors would also like to thank the reviewers for their suggestions and insightful comments to improve this work.

Author information

Authors and Affiliations

  1. Faculty of Sciences, Vasile Alecsandri University of Bacău, Bacău, Romania

    Gloria Cerasela Crişan

  2. Faculty of Sciences, Technical University of Cluj-Napoca, Cluj-Napoca, Romania

    Camelia-M. Pintea

  3. Faculty of Engineering and Computing, Coventry University, Coventry, UK

    Vasile Palade

Authors
  1. Gloria Cerasela Crişan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Camelia-M. Pintea
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vasile Palade
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vasile Palade.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Crişan, G.C., Pintea, CM. & Palade, V. Emergency management using geographic information systems: application to the first Romanian traveling salesman problem instance. Knowl Inf Syst 50, 265–285 (2017). https://doi.org/10.1007/s10115-016-0938-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10115-016-0938-8

Keywords

Search

Navigation