Arc- and Path-Based Models and a Heuristic Method for the Building Evacuation Planning Problem

Abstract

One of the essential proceedings to save the lives of the occupants of a multifloor and large building in emergency situations (such as fire and chemical spills) is the proper, timely, and safe evacuation of the building. This paper addresses the building evacuation planning as an important predisaster task and presents two equivalent mixed-integer linear programming (MILP) formulations where the first model is based on arc flows, and the second one is based on path flows. For each model, some valid inequalities are introduced to make the linear programming (LP) relaxation space closer to the convex hull of the original problem and speed up the model resolution via MILP solvers. Further, to solve large instances of the problem, a heuristic algorithm is developed. The performance of the proposed models, the effect of valid inequalities, and the efficiency of the proposed algorithm were evaluated on some instances taken from the literature and some randomly generated instances. The results confirmed the efficiency of the proposed heuristic method in terms of both running time and solution quality.