Solving Multiple Traveling Salesmen Problem Using Prim’s and Dijkstra’s Algorithms: A Case Study on Emergency Medical Supplies

A sequential integration of Prim’s and Dijkstra’s Algorithms is proposed in this work to solve the multiple traveling salesman problem through a case study on optimizing the supply route for emergency services to different places in a metropolis in the COVID situation. The objective is set to optimize the delivery, and return route for nurses and emergency supplies by minimizing travel distance and increasing the number of patients served each trip. Prim’s algorithm is employed to solve the issue of delivering emergency services to as many patients as feasible on a single trip for a single van, while Dijkstra’s algorithm is used to find the least path for the van’s return journey. The integration of Prim’s and Dijkstra’s algorithms has been found to be beneficial for route optimization in multiple traveling salesman problems for designing cost-effective routing systems, assuring improved vehicle utilization, and enhancing overall service delivery.