Implementation of the Cheapest Insertion Heuristic Algorithm for Optimizing the Shortest Route of the Semarang City Health Office to Inpatient Health Centers

Abstract

The supervision activities conducted by the Semarang City Health Office to Inpatient Community Health Centers play a strategic role in ensuring the quality of healthcare services. However, limited time and resources often hinder the effectiveness of these supervisory visits. This study aims to improve the efficiency of supervision travel routes by minimizing the total travel distance using the Cheapest Insertion Heuristic (CIH) algorithm. The data used consists of asymmetric distances between the Health Office and 10 Inpatient Community Health Centers. The process was carried out manually by forming an initial subtour, followed by inserting nodes based on the smallest additional distance. The manually constructed route was then validated using a Python simulation to ensure accuracy. In addition, the resulting route was compared with the actual supervision route as a form of efficiency evaluation. The findings show that the application of the CIH algorithm can produce routes with shorter total travel distances compared to the actual route, thus providing a useful basis for more efficient supervision planning.