Despite recent progress, Malawi continues to perform poorly on key health indicators such as child mortality and life expectancy. These problems are exacerbated by a severe lack of access to health care. Health Surveillance Assistants (HSAs) help bridge this gap by providing community-level access to basic health care services. However, the success of these HSAs is limited by a lack of supplies and long distances between HSAs and patients. To address this issue, we used large-scale p-median and capacitated facility location problems to create a scalable, three-tiered plan for optimal allocation of HSAs, HSA designated medical backpacks, and backpack resupply centers. Our analysis uses real data on the location and characteristics of hospitals, health centers, and the general population. In addition to offering specific recommendations for HSA, backpack, and resupply center locations, it provides general insights into the scope of the proposed HSA backpack program scale-up. In particular, it demonstrates the importance of local health centers to the resupply network. The proposed assignments are robust to changes in the underlying population structure, and could significantly improve access to medical supplies for both HSAs and patients.