Home and community-based care in South Africa

Assignment, routing and scheduling of care workers aims to ease HIV/AIDS-induced orphaned and vulnerable child crisis

International Operations Research

By Wilna du Plessis, Wilna Bean, Chanel Schoeman and Jozine Botha

South Africa’s HIV/AIDS pandemic is considered to be the largest in the world, with more than 5 million South Africans living with the disease [1]. This unprecedented scale of HIV occurrence, as well as the effects of related diseases – such as tuberculosis –places a heavy burden on the country’s already limited health care resources. The disease’s impact is not only reflected in national health statistics, but also by the almost 3.8 million children in South Africa left orphaned and vulnerable due to losing one or both parents to HIV/AIDS. This number is expected to increase drastically over the next few years [2].

As a result of the pandemic, home and community-based care (HBC) services are becoming increasingly prevalent in South Africa. These services do not only relieve the burden on the hospitals and community clinics, but also serve as affordable alternatives to institutional care. A HBC service is also a less uprooting way of addressing the HIV/AIDS-induced orphaned and vulnerable child (OVC) crisis, by keeping these children in familiar surroundings and assigning care responsibilities to community care workers.

To justify HBC as an affordable and effective alternative to institutional care, good service delivery is imperative. To achieve this various restrictions need to be addressed, including:

  • matching the OVC or beneficiary need with the skills of a care worker;
  • limiting the variety of care workers assigned to an OVC (to enable relationship and trust development); and
  • minimizing the travel time of care workers.

Through the analyses of these restrictions, two distinct sub-problems emerged:

  • the assignment of beneficiaries to suitable care workers, identified as the nurse rostering problem (NRP) [3]; and
  • the optimal scheduling and routing of care workers, identified as an extension of the vehicle routing problem (VRP) [4].

The similarities between the NRP and HBC problem are clear from the description of the NRP: “The assignment of duties to a set of people with different qualifications, work regulations and preferences” [3]. Solving this problem will therefore ensure that the skills of care workers and the requirements of beneficiaries are matched. Consequently an algorithm was developed and applied to Heartbeat – an organization providing HBC to children left orphaned and vulnerable as a result of HIV/AIDS.

Heartbeat Case Study

Heartbeat is a non-profit and public benefit organization – founded in response to the orphan challenges in South Africa – that endeavors to empower OVC to reach their full potential. Heartbeat’s caring programs – in impoverished communities across South Africa – provide basic services, such as food parcels, psychosocial support and educational assistance, to address the needs of OVCs.

Of the vast amount of orphaned children, few are fortunate enough to be cared for by a grandparent or other relative. Numerous children are, however, forced to take on the role of caregiver and provide for themselves. These children – who live without adequate care and protection – are more susceptible to neglect and exploitation.

Through regular home visits to OVC families, Heartbeat attempts to provide stability, protection and care by assuming the role of caregiver or parent. Trained home care workers assess the needs of the children, address problems within the household and provide counseling, mediation of disputes and assistance with homework and chores.

The frequency of visits between care workers and OVCs vary depending on the target group. Heartbeat’s ideal frequency of home visits are: three times a week for child-headed and potential child-headed households (children living with terminally ill parents); once a week at relative-headed households that do not receive government grants; and once a month at relative-headed households receiving government grants.

The purpose of the high frequency contact between care workers and child-headed- or potential child-headed households, is to address their more severe shortfall of adult-care and stability.

Heartbeat Specific Problem

To provide quality care to the children, Heartbeat aims to maintain a ratio of one care worker for every 10 households. However, due to the enormous amount of OVC in South Africa and Heartbeat’s limited staff capacity, this ratio is exceeded by far. The limited number of care workers also restricts the amount of contact between care worker and OVC. Both of these problems drastically impair the quality of service provided to the OVC.

The variation of care workers that currently assume parental responsibilities toward an OVC is also proving problematic to Heartbeat. To provide stability and build a trusting relationship with the OVC through home visits, the same care worker should ideally visit the family every time.

At present, there is no structured approach for assigning visits to Heartbeat’s care workers. Therefore most visits are performed on an ad hoc basis, where no prior arrangements are made. This often results in OVCs not being at home when a care worker conducts a visit. These visits are seldom followed up, due to a lack of time and poor reporting and monitoring of performed visits, leading to an unfulfilled visit demand. The geographical dispersal of the households also contributes to this problem. The households located on the outskirts of the settlement, furthest from the care workers, are often neglected because of the extra effort required to perform visits there.

Solution Approach

As stated before, the HBC problem encapsulates two well-known sub-problems: the NRP and the VRP, both of which are classified as being non-deterministic polynomial-time hard. Due to the complexity associated with these problems, and the vast computational time required to solve them optimally, the project team decided to develop a solution algorithm that uses metaheuristic approaches.

The main objective of this algorithm is to reduce the travel time of care workers, while balancing the workload between available care workers and satisfying beneficiary requirements. A hybrid approach combining variable neighborhood search – a metaheuristic that exploits the idea of a systematic neighborhood change within a search algorithm [5] – and Tabu Search – a metaheuristic with a memory-based property that prevents future mistakes based on mistakes made in the past [6] – is deemed suitable to solve the HBC problem.

The steps of this algorithm include the pre-processing of data, development of an initial solution, the improvement of care activity assignment and the sequencing of the individual rosters.

Solution Algorithm Application

The developed solution algorithm was evaluated by applying it to Heartbeat’s Nellmapius project site – a semi-urban settlement east of Pretoria, South Africa, with an estimated population of 65,000. Despite the availability of basic amenities, government services such as health care are limited. Unemployment, crime and drug abuse are prevalent in this area. Health statistics also indicate a high HIV prevalence that is reflected in the large number of OVCs in Nellmapius. Nellmapius is a typical example of a community with a great need for HBC but with very few resources.

Heartbeat’s Nellmapius project currently serves 132 OVC households through only five home care workers. It is clear that Heartbeat’s ideal ratio of one care worker for every 10 households is exceeded by far (1:26), and this is severely impairing the quality of the care.

Data Gathering and Preparation

Raw data regarding care worker and home visit locations had to be transformed into “processable” input data for the solution algorithm.

The project team compiled a list of Heartbeat-served households in Nellmapius that contained details of the address, number of beneficiaries, type of household and the corresponding frequency of visits required. The household and care worker addresses were then mapped using a Geographical Information System (GIS) (see Figure 1).

International Operations Research

Figure 1: Geographical presentation of the locations of care workers and Heartbeat households in Nellmapius, South Africa.

The GIS program, MapInfo, was used to determine the road distances between the households and care workers, and an internodal distance matrix was constructed.

Of the 132 households served by Heartbeat in Nellmapius, 17 are child-headed- or potential child-headed households, 64 are relative-headed households not receiving grants, and 51 are relative-headed households receiving government grants. Therefore, to meet the frequencies of visits Heartbeat prescribes, a total of 511 visits need to be conducted during a four-week period, to serve the 132 households.

Pre-Processing of Data

All the care workers employed by Heartbeat are community members who received the same informal training from Heartbeat. Since no skill variation exists between the care workers, it was decided to permanently assign all critical visits (the child-headed- and the potential child-headed households) to a specific care worker. These assignments were then made to a care worker who is situated within a close proximity of the household. Not only will this lessen travel time and ensure that a trusted adult is nearby in case of an emergency, but it will also prevent care worker variation and contribute to providing a sense of stability.

Initial Solution

Variable neighborhood search and Tabu search are metaheuristics that find good solutions through the iterative improvement of initial feasible solutions. As such, a construction heuristic was used to develop an initial solution for the metaheuristics.

The remaining visits, not assigned during the pre-processing phase, were ordered in a descending order from the most critical (households not receiving grants) to the least critical (households receiving grants). These visits were then assigned to the care worker who will incur the smallest penalty for conducting the visit. The penalty is calculated based on the distance between the care worker and the household, as well as the number of visits already performed by the care worker per day. The assigned visits were then ordered into a schedule, to serve as an initial solution.

Improved Solution

The developed solution algorithm was then applied to the initial solution with the intent of improving it over two neighborhoods.

The first neighborhood search attempts improvement over the extended neighborhood of the schedules of all care workers comprising the first neighborhood. This search induces a single swap of a care-activity between a pair of care-workers. The quality of the proposed swap is then evaluated by calculating the total schedule time of the new proposed roster with the Tabu Search algorithm. If the best solution – the roster with the shortest schedule time – obtained in the current iteration is not an improvement of the solution in the previous iteration, the algorithm extends its search to search for another move that will result in an improvement. Otherwise, the solution is updated as the incumbent solution and the algorithm returns to the first neighborhood of the new solution. When there are no more improving moves left within the first neighborhood, or the stopping criteria are met, the search extends to the second neighborhood.

The second neighborhood search considers the entire monthly schedule of each particular care worker. This search, which is individually conducted for each care worker, performs an exchange between care activities in a specific care worker’s schedule. As with the first neighborhood, the quality of the swap is evaluated with a Tabu Search. If the proposed move results in an improved solution, the incumbent solution is updated to the current solution. This process is repeated until the stopping criteria are met.


The new care worker visit schedules, developed through this approach, addresses Heartbeat’s home-based care problems in the following ways:

Fair work distribution: The number of visits assigned to each care worker varies between four and six per day. Taking into consideration both the travelling duration of the care worker and the number of visits performed, the total schedule duration of each care worker compares favorably to that of other care workers.

Effective routing and scheduling: The improved routing and scheduling of the initial solution resulted in care worker schedules not exceeding three and a half hours in any day. This allows care workers to perform the visits in the afternoon, after school, between 2 p.m. and 6 p.m.

Limited care worker variation: Permanently allocating a specific care worker to each child-headed household eliminates variation of care workers for these critical visits, enabling the children to develop a trusting relationship with the specific care worker. Assigning these visits to the care worker living closest to the family also adds to the security of child-headed households by ensuring that a familiar and trusted adult is close by in case of an emergency.

Visit planning: A major advantage of using the assignment, scheduling and routing algorithm to swiftly pre-determine the entire monthly schedule, is that it enables care workers to make appointments with the children in advance, so that children can plan to be at home when visits are conducted.


As a result of the HIV/AIDS pandemic, the need for alternative health care solutions is increasing. The novelty of home-based care and inadequate service delivery by care workers has caused reluctance to recognize home-based care as an equal alternative of institutional care.

The aim of this project was to improve the assignment, routing and scheduling of care workers, in order to advance service delivery in the home-based care of orphaned and vulnerable children. This problem presented itself as a classical optimization problem, where the travel duration needed to be minimized, while adhering to certain constraints [3].

To ensure that the developed solution brings about the required improvements of HBC activities at Heartbeat, its implementation should address the following aspects found to be key to the successful rollout of programs for OVCs [7]:

  • close monitoring and evaluation enables early intervention and correction;
  • beneficiary involvement enables buy-in and highlights possible pitfalls;
  • involvement and training of care workers;
  • model flexibility enables adaptability to varying community needs; and
  • continuous improvement of applied models ensures model relevance.

Proposed further development of the project entails creating a user-friendly interface to facilitate staff use of the algorithm, as well as communication channels between a central facility – where the algorithm will be executed – and the respective care workers, enabling the communication of schedules.

Wilna du Plessis is a junior lecturer and Jozine Botha is a lecturer in the Department of Industrial Engineering at the University of Pretoria, South Africa. Wilna Bean and Chanel Schoeman (cmschoeman@csir.co.za) are industrial engineers with the Council for Scientific and Industrial Research (CSIR), South Africa.


  1. Joint United Nations Programme on HIV/AIDS (UNAIDS), 2010, Global Report: UNAIDS Report on the Global AIDS Epidemic 2010. Available at: www.unaids.org/en/media/unaids/contentassets/documents/unaidspublication/2010/20101123_globalreport_en.pdf. ISBN 978-92-9173-871-7.
  2. Pendelbury, S, Lake, L and Smith, C., 2009, “South African child gauge 2008/2009,” University of Cape Town, Children’s Institute.
  3. Burke, E., De Causmaecker, P. and Van den Berghe, G., 1999, “A hybrid tabu search algorithm for the nurse rostering problem,” lecture notes in “Computer Science,” pp. 187-194.
  4. Joubert, J., 2006, “An integrated and intelligent metaheuristic for constrained vehicle routing,” Ph.D. thesis: University of Pretoria.
  5. Hansen, P. and Mlandenoviyc, N., 2001, “Variable neighbourhood search: Principles and applications,” European Journal of Operations Research, Vol. 130, pp. 449-467.
  6. Dreo, J., Petrowski, A., Siarry, P., and Taillard, E., 2003, “Metaheuristics for Hard Optimization: Methods and Case Studies,” Springer.
  7. Strebel, A., 2004, “The development, implementation and evaluation of interventions for the care of orphans and vulnerable children in Botswana, South Africa and Zimbabwe,” Human Sciences Research Council.