Implementation of Christofides Algorithm to Determine the Shortest Tour of Some Hospitals in Palembang City

Determining the shortest route to connect hospitals is a very important aspect of improving the efficiency of medical service distribution in a big city like Palembang. The shortest tour will result in a shorter time required. This study aims to minimize the time needed for a team of technicians who want to distribute medical equipment and provide simple usage examples to some hospitals in Palembang city. There are 20 hospitals under consideration, and the data on time needed from one hospital to another were obtained from Google Maps. The distance between locations was calculated based on travel time using a four-wheeled vehicle. The Christofides Algorithm will be used in this problem to determine the shortest tour. The results show that the travel time needed is 171 minutes (only for traveling from one hospital to another and back to the origin, not including the time needed for giving the simple usage of medical equipment). This study provides practical solutions to improve time efficiency, such as delivering medical supplies or emergency response.