80. Maximum covering network design for improving health care access
Contributed abstract in session SA-1: Location optimization, stream Location optimization.
Saturday, 10:00 - 11:30Room: L226
Authors (first author is the speaker)
| 1. | Felix Rauh
|
| Operations Research and Statistics Research Group (ORSTAT), KU Leuven | |
| 2. | Jannik Matuschke
|
| KU Leuven | |
| 3. | Hande Yaman
|
| ORSTAT, KU Leuven |
Abstract
We tackle a problem that arises when improving health care access in areas that are prone to disruptions that are caused, for example, by recurring floods. A given budget can be used both for building new hospitals as well as improving the network design by making weak links in the network resilient to floods. The objective is to maximize the number of households that can reach a hospital via a flood-resilient access of a maximum distance of, e.g., five kilometers.
First, we show that the problem on trees allows for an optimal solution approach via dynamic programming that is pseudo-polynomial in the given budget. Another class of graphs that are of interest are graphs that have cut vertices (also called articulation points), thus allowing for non-trivial block-cut tree decompositions (where each block is a maximal biconnected component). Motivated by the DP on trees, we introduce an exact approach that uses primal and dual bounds on the blocks to create fast heuristic as well as optimal solutions.
We present the computational benefits of the approach via preliminary results of an extensive computational study that compares it, among others, with a branch and cut approach that uses the idea of length-bounded cuts.
Keywords
- Exact algorithms for combinatorial optimization problems
- Graph theory and networks
- Routing, location and capacity planning
Status: accepted
Back to the list of papers