A Column Generation Approach for Locating Roadside Clinics in Africa based on 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 (North Star) aims to alleviate this situation by placing so-called Roadside Wellness Centers (RWCs) at busy truck stops along major 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 the truck drivers use. As North Star's network grows larger, the objective to provide equal access to healthcare along the different truck routes gains importance. To solve the problem to locate a fixed number of RWCs based on these effectiveness and equity objectives, new models and solution methods are needed.

Our contributions are fourfold. First, we introduce and motivate the equity criterion. Second, we propose and analyze a novel set partitioning formulation for the location problem. Third we propose and analyze a column generation approach to solve it and show how the pricing problem can be heuristically solved by using a sequence of shortest path problems. Moreover, we investigate several acceleration techniques, including dual stabilization, column pool management and a two-stage algorithm. Last, we numerically assess the trade-off between the equity criterion and North Star's current criteria based on randomly generated instances. Our results show that the column generation approach efficiently solves large problem instances to near-optimality and that solutions that are close to optimal with respect to each of the effectiveness and equity objectives are likely to be attainable.

• Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars