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 journalArticlepeer-review

    15 Citations (Scopus)
    408 Downloads (Pure)


    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
    Issue number1
    Early online date8 Apr 2016
    Publication statusPublished - Jan 2017


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


    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