Abstract Evacuation planning and scheduling is a critical aspect of disaster management and national security applications. This paper proposes a conflict-based path-generation approach for evacuation planning. Its key idea is to decompose the evacuation planning problem into a master and a subproblem. The subproblem generates new evacuation paths for each evacuated area, while the master problem optimizes the flow of evacuees and produce an evacuation plan. Each new path is generated to remedy conflicts in the evacuation flows and adds new columns and a new row in the master problem. The algorithm is applied to a set of large-scale evacuation scenarios ranging from the Hawkesbury-Nepean flood plain (West Sydney, Australia) which require evacuating in the order of 70,000 persons, to the New Orleans metropolitan area and its 1,000,000 residents. Experiments illustrate the scalability of the approach which is able to produce evacuation for scenarios with more than 1200 nodes, while a direct Mixed Integer Programming formulation becomes intractable for instances with more than 5 nodes. With this approach, realistic evacuations scenarios can be solved near-optimally in reasonable time, supporting both evacuation planning in strategic, tactical, and operational environments.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A conflict-based path-generation heuristic for evacuation planning


    Contributors:


    Publication date :

    2015-09-14


    Size :

    15 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    A conflict-based path-generation heuristic for evacuation planning

    Van Hentenryck, Pascal | Online Contents | 2016


    Pedestrian evacuation planning: Unveiling evacuation routes via column generation

    Nicolás Cabrera / Jorge A. Huertas / Andrés L. Medaglia | DOAJ | 2022

    Free access

    Exploration Priority Based Heuristic Approach to UAV path planning

    Redwan Newaz, Abdullah Al / Pratama, Ferdian Adi / Chong, Nak Young | IEEE | 2013


    Potential functions based sampling heuristic for optimal path planning

    Qureshi, A. H. | British Library Online Contents | 2016


    Heuristic Framework for Optimizing Hurricane Evacuation Operations

    Afshar, Abbas Mohasel | Online Contents | 2008