A column generation approach for locating roadside clinics in Africa based on effectiveness and equity

• Health facilities along African truck routes aim to combat HIV among truck drivers.
• Facility location criteria typically advantage frequently used truck routes.
• More equitable location decisions only marginally reduce effectiveness.
• A column generation approach quickly yields near-optimal solutions.
• We present a real life case study based on the North South Corridor network.

Long distance truck drivers in Sub-Saharan Africa are extremely vulnerable to HIV and other infectious diseases. The NGO North Star Alliance aims to alleviate this situation by placing the so-called Roadside Wellness Centers (RWCs) at busy truck stops along major truck routes. Currently, locations for new RWCs are chosen so as to maximize the expected patient volume and to ensure continuity of access along the routes. As North Star’s network grows larger, the objective to provide equal access to healthcare along the different truck routes gains importance. This paper considers the problem to locate a fixed number of RWCs based on these effectiveness and equity objectives. We come up with a novel, set-partitioning type of formulation for the problem and propose a column generation algorithm to solve it. Additionally, we propose and analyze several state-of-the-art acceleration techniques, including dual stabilization, column pool management, and accelerated pricing, which solves the pricing problem as a sequence of shortest path problems. Though the facility location problem is strongly NPNP-hard, our algorithm yields near-optimal solutions to large randomly generated problem instances within an acceptable amount of time. We use a real life case study on the North South Corridor Network to analyze the impact of including the equity criterion into the location problem. The results show that significant improvements in terms of equity can be achieved at marginal loss in terms of North Star’s current objectives.