Locating Roadside Wellness Centers using a Greedy Heuristic

Truck drivers in Africa have a lifestyle which puts them at great risk of catching HIV and various other diseases. This also puts the communities they are in direct contact with at risk. Non-governmental organization North Star Alliance battles this problem by installing Roadside Wellness Centers (RWCs) along various busy truck stops. To evaluate possible locations three objectives are combined. The literature presents a mixed-integer programming formulation to solve the problem. This formulation is not suitable for large instances, because the problem is NP-hard. To solve large instances this research proposes a Greedy Heuristic. This heuristic solves a large instance in 94.6% less time with a optimality gap of 0.00%