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

G. C. Crişan, C.-M. Pintea, Vasile Palade

Research output: Contribution to journalArticle

11 Citations (Scopus)
144 Downloads (Pure)

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.

The final publication is available at Springer via http://dx.doi.org/10.1007/s10115-016-0938-8
Original languageEnglish
Pages (from-to)265-285
Number of pages21
JournalKnowledge and Information Systems
Volume50
Issue number1
Early online date8 Apr 2016
DOIs
Publication statusPublished - Jan 2017

Keywords

  • Emergency management
  • Traveling Salesman Problem
  • GIS
  • geographic coordinates

Fingerprint Dive into the research topics of 'Emergency management using geographic information systems: application to the first Romanian traveling salesman problem instance'. Together they form a unique fingerprint.

  • Cite this