Using the travelling salesman problem’s “nearest Neighbour” Method to find the most efficient (fastest and least expensive) combination of travel to six destinations by rail in Ireland

As someone who is enthralled by adventure and exploration, I have always been interested in planning holidays. I sometimes wonder: is there a way to plan a successful trip in a methodical, mathematical way? After graduation, I would love to invite my friends to my small country, Ireland, and provide them with an efficient yet budget-friendly trip: using trains to visit locations.

 

“The Travelling Salesman Problem” (TSP), first studied in the 1930s by applied mathematicians, is one of the most studied problems in operations research (Daniells, 2020). I will use this problem to uncover the least expensive and quickest way to travel to six locations in Ireland.

 

I decided that the journey would begin and end in Cork (my home town) in order to apply the theory of a Hamiltonian cycle: “a graph cycle (i.e. a closed loop) that visits each node exactly once” (Wolfram MathWorld, 2022). The journey will also include Killarney, Dublin, Limerick, Galway, Waterford and Dublin.

 

I will use the “Nearest Neighbour” method in this investigation. It can be calculated as: “given a set of n points and a query point,” the nearest neighbour approach focuses on “finding the point closest to the query point” (O'Neil, 2008).

 

In order to maintain control variables, this data was collected on the 10th of June, 2022. The date of the tickets is the 15th of July, 2022, and the ticket type is a “young adult flexible ticket”. I chose the earliest possible train. I acquired the data from the Irish Rail website: https://journeyplanner.irishrail.ie/webapp.

Journey Time (in minutes)

 

Since the journey would start in Cork, I highlighted the possible next steps in pink. The nearest neighbour appears to be Killarey (87 minutes).

Thus: CK (87) + KL (98) + LG (113) + GW (145) + WD (245) + DC (147) = 835 By using the Nearest Neighbour method, I calculated that the shortest travel time is 835 minutes in total.

The next possible destinations from Cork are highlighted in pink. The nearest neighbours are equally Waterford and Limerick (7.25 euros). For this calculation, Waterford will be utilised.

Therefore - CW (7.25) + WL (4.25) + LK (9.20) + KG (8.99) + GD (8.00) + CD (14.39) = 52.08. The total for this Nearest Neighbour application is 52.08 euros.

 

I must check, however, if the different path in step 2 could have resulted in different result: Limerick and Waterford were both equal in price. I will re-apply the Nearest Neighbour method below using Limerick as the second destination, rather than Waterford.

Thus, CL (7.25) + LW (4.25) + WK (8.40) + KG (8.99) + GD (8.00) + DC (14.39) = 51.28 euros. This is the cheaper cost compared to that previously calculated.

I was able to verify my answers through the use of an online TSP calculator (https://www.easycalculation.com/operations-research/traveling-salesman-problem.php). The calculator can be utilised by selecting a matrix size (in this case, 6) and entering the numbers from the table. This website claims to be able to calculate the shortest path possible; therefore it can be used to evaluate the accuracy of my calculations.

This result (688) can be adapted in order to calculate the length of a Hamiltonian cycle (starting and ending in Cork) by adding the distance from Dublin (2) to Cork (1), which is 147 minutes. 688 + 147 = 835 minutes. This equates to the result I found from my calculation.

 

Similarly, the journey prices can be verified through the calculator -

To bring the journey to an end in Cork, one must add the length from Dublin (2) to Cork (1) 37.69 + 14.3 = 52.08. This figure is the same as the one I calculated.

Through my research and calculations, I sought to find the shortest distance and cheapest way to navigate Ireland through 6 cities, starting and beginning in Cork. I applied the Travelling Salesman Problem, with a Hamiltonian cycle, and used the Nearest Neighbour Method. My results were verified by an online calculator.

 

Methods like the Nearest Neighbour method are considered “greedy algorithms” because they “make the best optimal choice at each small stage”. A greedy algorithm “picks the best immediate output, but does not consider the big picture” (Techopedia, 2020). Some studies have argued against the Nearest Neighbour method, stating that the “travelling salesman should not be greedy” (Gutin et al., 2002). On the other hand, the Nearest Neighbour method is highly accessible and possible to do manually, without the use of complex computing programs.

 

This investigation has led me to consider possible other areas of development. The travelling salesman problem is “an NP-hard problem”, meaning that “there is no polynomial-time algorithm that is known to efficiently solve every travelling salesman problem” (Daniells, 2020). Although the online calculator verified that I had found the “optimal” solution, better combinations may be possible, derived from the plethora of other methods. Additionally, with the addition of more locations, there is infinite potential for further exploration.

Gutin, G., Yeo, A. and Zverovich, A. (2002) “Traveling salesman should not be greedy - Domination analysis of greedy-type heuristics for the TSP,” Discrete Applied Mathematics, 117(1-3), pp. 81–86. Available at - https://doi.org/10.1016/s0166-218x(01)00195-0.

 

Hamiltonian cycle (2022) Wolfram MathWorld. Available at: https - //mathworld.wolfram.com/HamiltonianCycle.html (Accessed: October 20, 2022).

 

Kuo , M. (2020) Solving the travelling salesman problem for deliveries, Routific. Available at: https://blog.routific.com/blog/travelling-salesman-problem (Accessed: October 4, 2022).

 

Libby Daniells (2020) The travelling salesman problem, Libby Daniells. Available at https - //www.lancaster.ac.uk/stor-i-student-sites/libby-daniells/2020/04/21/the-travelling-s alesman-problem/ (Accessed: October 20, 2022).

 

O'Neil, D.J. (2008) “Nearest neighbors problem,” Encyclopedia of GIS, pp. 783–787. Available at: https://doi.org/10.1007/978-0-387-35973-1_869.

 

Techopedia (2020 What is a greedy algorithm? - definition from Techopedia (2020) Techopedia.com. Available at - https -//www.techopedia.com/definition/16931/greedy-algorithm%20(Accessed:%20October%2012,%202022).