A Column Generation Approach for Locating Roadside Clinics in Africa based upon Effectiveness and Equity

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 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 NP-hard, our algorithm yields near-optimal solutions to large randomly generated problem instances within an acceptable amount of time. Our analysis of the trade-off between the equity criterion and North Star's current criteria shows that solutions that are close to optimal with respect to each of the effectiveness and equity objectives are likely to be attainable.