TY - JOUR
T1 - A column generation approach for locating roadside clinics in Africa based upon effectiveness and equity
AU - Nunez Ares, J (Jose)
AU - de Vries, Harwin
AU - Huisman, Dennis
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
U2 - 10.1016/j.ejor.2016.04.031
DO - 10.1016/j.ejor.2016.04.031
M3 - Article
VL - 254
SP - 1002
EP - 1016
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
ER -