Emergency humanitarian logistics: models and algorithms for evacuation planning

This thesis deals with an emergency humanitarian problem aiming to plan and control the evacuation time of a building. The main tools used for handling the problem are linear programming models. Our implementation is based on models originally engineered for many problems like routing design and strategical positioning of hospitals, shipping centers, hubs, warehouses and in logistics. In the different proposed configurations, our mathematical model is able to optimize the evacuation time from the building, deciding the routing path for all the evacuees and their assigned emergency exits, with different variants on the evacuation path modelling. But, it is also able, in a planning phase, to choose which subset of candidate positions for emergency exits is preferable in terms of expected evacuation time. The real case exploited to test this work is the emptying of Palazzo Camponeschi in L'Aquila during an earthquake. Several solution algorithms have been implemented and tested: both exact (the models themselves and their solution though the constraints generation techniques, often able to solve more efficiently models with a huge number of constraints), and heuristic (a variant of the constraint generation algorithm, designed for solving larger problem instances). The computer that runs the solver, indispensable for solving the mathematical programming models is an Asus core i5, 8th Gen, 1.8 GHZ with 8 Gb of RAM memory under Windows 10 Home 64-bits, and the solver is Xpress IVE with the Mosel language. Computational tests have proven that there is not an obvious best algorithm choice, since the outcomes depend by the intrinsic characteristics of the problem in question e this leads to a competitiveness of the tools adopted. Although the framework lacks of a predominant procedure, there are two discriminating factors. The first one is the phase in which the analysis shall be applied for a matter of available time: in a planning phase, in general this time is large and hence it is possible and favorable to exploit an exact algorithm; in case of short of time, it is more likely to consider using an heuristic approach. The second factor is the real case itself: in case of a large enough available time, it is undoubtedly preferable an exact algorithm since with a heuristic algorithm people could get hurt because of potential sub-optimal results. The first chapter introduces the main components used in the following. Chapter 2 addresses the problem itself in detail, introducing the linear programming models and the setting of parameters. Chapter 3 describes in practice the algorithms in support of the model resolution and finally, chapter 4, outlines the results.