New optimisation method makes huge-scale water-well planning solvable

A research project that began through the Analytics for a Better World Fellowship, in response to a challenge from the Red Cross in West Darfur, Sudan, has been accepted for publication in OMEGA.

OMEGA – The International Journal of Management Science is a leading peer-reviewed journal in management science and operations research. It publishes research on areas including optimisation, analytics, decision-making and their practical applications, with a long-standing focus on work that connects methodological advances with real-world problems.

The project, A geospatial decomposition method for huge-scale maximum covering facility location problems, has been led by ABW PhD Candidate, Britt van Veggel, who worked with fellow researchers from KU Leuven, Tilburg University, and the 510 Red Cross team. This research addresses a simple but computationally difficult question: where should water wells be placed so that as many people as possible live within 500 metres of one?

The challenge: planning at huge scale

The West Darfur case involved around 90,000 demand points representing locations where people need access to water. With a large number of possible sites for new wells, identifying the best combination quickly becomes too computationally demanding for standard optimisation methods.

This is known as a maximum covering facility location problem: deciding where to place a limited number of facilities so they can serve as much demand as possible within a given distance.

The solution: using geography to break the problem apart

The researchers used a simple geographic insight. If two demand points are more than 1,000 metres apart, they cannot both be reached by the same well when the service radius is 500 metres.

That makes it possible to divide the full problem into smaller geographic clusters that can be solved independently and then combined.

The result is a method that can find exact solutions at scales that had not previously been tackled. In optimisation, an exact solution means the model can identify the best possible solution within its assumptions, rather than settling for a good solution that can be calculated quickly.

The potential: better support for large-scale infrastructure decisions

For West Darfur, this could mean making limited investment in new wells go further by directing it to locations where it can improve water access for the greatest number of people.

The method was motivated by water-well planning, but the underlying problem appears in many other settings where facilities need to be placed close to the people who use them.

By making very large location problems computationally manageable, the approach could support future decisions about where limited infrastructure should be placed to reach as many people as possible.

The paper grew out of the ABW Fellowship and shows how a practical planning challenge can lead to a new optimisation method with applications beyond the original case.