Eid homecoming, also known as "Mudik" in Indonesia, is an annual tradition that involves the mass movement of people from cities to their hometowns to celebrate the Eid al-Fitr holiday. Based on data from the Ministry of Transportation of the Republic of Indonesia, there are five major regions that serve as the primary destinations for homecoming travelers: West Java, Central Java, East Java, DI Yogyakarta, and the Jabodetabek region. The Central Java region is estimated to receive the largest number of homecoming travelers, with an estimated 61.6 million people. Given the potential for human movement of up to 193.6 million people during this period, it poses a significant traffic burden, and an efficient determination of the shortest route is crucial. To address this challenge, the study utilizes the Haversine Formula, which calculates the distance between two geographic points on the earth's surface by considering the curvature of the earth. This approach provides a more accurate distance estimate compared to traditional linear distance calculations. Additionally, the A* algorithm is employed to determine the shortest path from the starting point to the destination. The A* algorithm combines the distance calculation results from the Haversine Formula as a heuristic component in the search process, effectively optimizing the route selection. The results of the A* algorithm search identified the shortest route for homecoming travelers, which starts from the city of Jakarta, passes through West Karawang, Indramayu, Cirebon, Tegal, Pekalongan, Semarang, and Salatiga, before reaching the final destination of Klaten. This optimized route covers a total distance of 599.4 km, providing an efficient and cost-effective option for travelers during the Eid homecoming period