EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

573. A method for huge scale maximum covering facility location problems with an application to water well placement in West Darfur

Invited abstract in session WC-18: Facilities Routing and Planning in Developing Countries, stream OR for Development and Developing Countries.

Wednesday, 12:30-14:00
Room: 42 (building: 116)

Authors (first author is the speaker)

1. Britt van Veggel
Business Analytics, University of Amsterdam

Abstract

In the analytical context of addressing humanitarian issues, huge-scale facility location problems play an important role. Whether it comes to finding locations for schools, hospitals, or water wells, these problems often involve many demand locations and many potential facility locations. Solving such problems using traditional methods quickly becomes intractable, or even impossible due to large memory requirements.
We propose a decomposition approach to efficiently solve huge-scale problems in an exact way by clustering the demand points, solving subproblems for each cluster independently, and combining solutions of subproblems by solving a integer programming problem. Clustering takes advantage of the spatial separation of demand locations to address subproblems independently, guaranteeing optimality. Optionally, heuristic subclustering can be used to further divide clusters. When subclustering is used, bounds on optimality gaps are provided, offering quality guarantees about obtained solutions.
We demonstrate the effectiveness of the proposed approach with a case study, which is done in collaboration with the 510 team of The Dutch Red Cross, involving the placement of water wells in West Darfur (Sudan). Solutions for capacitated and uncapacitated problems are obtained within reasonable computation times while providing optimality guarantees where appropriate.

Keywords

Status: accepted

Back to the list of papers