Abstract
This study is motivated by the need to restore part of the Nepal water distribution network that was destroyed by the Gorkha and Dolakha earthquakes in April and May 2015. The problem consists of two hierarchical subproblems: locating water taps to ensure a good coverage of the population, and connecting these water taps to water sources by means of a pipe distribution network. Both subproblems are subject to a variety of accessibility and technical constraints that make the problem unique and highly complex. Namely, because Nepal is highly mountainous, elevations must be taken into account in the distance calculations, and the distribution network is gravity-fed, meaning that pumps are not used. The problem is solved by means of a two-phase matheuristic: the first subproblem is a constrained location–allocation problem which is solved exactly by integer linear programming, while the second subproblem is tackled by means of a cluster-first, tree-second heuristic. Several variants of the heuristic are developed and compared. The network design problem is of very large scale, being solved on a graph with as many as 29,900 vertices and 75,200 arcs. Tests are performed on real-world data, obtained by satellite imagery, from the Suspa Kshemawati and Lapilang communities in the Dolakha district. Extensive computational results confirm the effectiveness of the proposed methodology and enable an identification of the best parameter settings and algorithmic tactical choices.
Original language | English |
---|---|
Article number | 105669 |
Journal | Computers and Operations Research |
Volume | 140 |
Early online date | 23 Dec 2021 |
DOIs | |
Publication status | Published - 30 Apr 2022 |
Bibliographical note
Funding Information:The authors are grateful to Magdalena Bauerl and Bassam Qashqo from the Austrian Red Cross, and to Lorentz Wendt from the Department of Geoinformatics Z-GIS of the University of Salzburg for several helpful discussions at the beginning of this project. Gilbert Laporte and Marie-Ève Rancourt were funded by the Canadian Natural Sciences and Engineering Research Council under grants 2015-06189 and 2014-03945 . Selene Silvestri received a postdoctoral fellowship from the Institute for Data Valorisation (IVADO) . Jessica Rodríguez-Pereira was funded through a postdoctoral fellowship from grants provided by IVADO and the Canada Research Chair in Distribution Management. This support is gratefully acknowledged. Thanks are also due to Joel Grau Bellet for his professional help with the geographical maps, and to the referees for their valuable comments.
Funding Information:
The authors are grateful to Magdalena Bauerl and Bassam Qashqo from the Austrian Red Cross, and to Lorentz Wendt from the Department of Geoinformatics Z-GIS of the University of Salzburg for several helpful discussions at the beginning of this project. Gilbert Laporte and Marie-?ve Rancourt were funded by the Canadian Natural Sciences and Engineering Research Council under grants 2015-06189 and 2014-03945. Selene Silvestri received a postdoctoral fellowship from the Institute for Data Valorisation (IVADO). Jessica Rodr?guez-Pereira was funded through a postdoctoral fellowship from grants provided by IVADO and the Canada Research Chair in Distribution Management. This support is gratefully acknowledged. Thanks are also due to Joel Grau Bellet for his professional help with the geographical maps, and to the referees for their valuable comments.
Keywords
- Dolakha district
- Gravity-fed system
- Humanitarian logistics
- Location–allocation
- Steiner forest
- Water distribution network design
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research