Optimizing access to drinking water in remote areas. Application to Nepal

• Published in: Computers & operations research 2022-04, Vol.140, p.105669, Article 105669
• Main Authors: Laporte, Gilbert, Rancourt, Marie-Ève, Rodríguez-Pereira, Jessica, Silvestri, Selene
• Format: Article
• Language: English
• Subjects: Apexes; Constraints; Dolakha district; Drinking water; Graph theory; Gravity-fed system; Heuristic; Humanitarian logistics; Integer programming; Linear programming; Location–allocation; Network design; Operations research; Parameter identification; Remote regions; Satellite imagery; Steiner forest; Very large scale; Water distribution; Water distribution network design; Water engineering
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2021.105669

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. •We design a water distribution network with an application to Nepal following the 2015 earthquakes.•In the network, water taps must be located and connected by means of a Steiner forest.•The problem is modeled and solved hierarchically through a two-phase matheuristic.•The problem is solved for two Nepalese districts, using real data obtained by satellite imagery.•Extensive computational results confirm the efficiency of the proposed methodology.