The Roadside Healthcare Facility Location Problem

__Abstract__ Providing African truck drivers with adequate access to healthcare is an effective way to reduce the burden and the spread of HIV and other infectious diseases. Therefore, NGO North Star Alliance builds a network of healthcare facilities along major African trucking routes. Choosing the locations of new facilities presents novel and complex optimization problems. This paper considers a general design problem: the Roadside Health Care Facility location Problem (RHFLP). RFHLP entails to select locations for new facilities and to choose for each of these facilities whether or not to add healthcare services for HIV, STIs, Tuberculosis, and/or Malaria to the standard health service package. The objective combines the maximization of the truck driver patient volume at these facilities and the maximization of the extent to which the truck drivers have continuous access to the needed health service packages. We present three measures for continuous access to health services by mobile patients and integrate these measures in a mixed-integer programming formulation for RHFLP. Moreover, we prove the RHFLP to be strongly NP-hard and derive analytical results for the worst-case effects of impreciseness in the input data. We show how large scale real life problem instances can be solved, presenting numerical experiments for the North-South corridor network (Southern and Eastern Africa) and discuss policy implications.