Mathematics AI SL
Sample Internal Assessment
6/7
2,348 Words
English
Free

Using the travelling salesman problem’s “nearest Neighbour ” Method to find the most ef icient (fastest and Least expensive) combination of travel to six destinations By rail in ireland

Introduction

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.

Figure 1 - Sample Journey On “Journey Planner” Section Of Irish Rail Website

Raw Data

Figure 2 - Table On Locations And Their Associated Journey Times (In Minutes)
figure 3 - Table On Locations And Their Associated Journey Prices (In Euros)

Application

Nearest neighbour method

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).

Top IB Math Tutor: 45/45 IBDP, 7/7 Further Math, 7 Yrs Exp, Medicine Student

Video Course

• Figure 4 - Table On
Figure 5 - Table On As Seen Below, The Next Nearest Neighbour Appears To Be Limerick (98 Minutes)
Figure 6 - Table On Limerick’s Nearest Available Neighbour Is Galway (113 Mins).
Figure 7 - Table On Out Of The Two Remaining Options, Waterford Is Galway’s Nearest Neighbour (145 Mins).
Figure 8 - Table On The Only Option To Proceed Is Dublin (245 Mins).
Figure 9 - Table On In Order To Return Back To Cork, Tt Takes 147 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.

Journey prices (in euros)

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.

Figure 10 - Table On
Figure 11 - Tablr On The Next Nearest Neighbour Is Limerick (4.25 Euros).
Figure 12 - Table On Limerick's Next Nearest Neighbour Is Killarney (9.20 Euros).
Figure 13 - Table On From Killarney, The Next Nearest Neighbour Is Galway (8.99 Euros).
Figure 14 - Table On After Galway, The Nearest Neighbour Is Dublin (8.00 Euros).
Figure 15 - Table On Lastly, The Remaining Option Is To Return To Cork From Dublin (14.39 Euros).

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.

Top IB Math Tutor: 45/45 IBDP, 7/7 Further Math, 7 Yrs Exp, Medicine Student

Video Course

• Figure 16 - Table On The Cost Of Cork To Limerick Is 7.25 Euros.
Figure 17 - Table On Limerick’s Nearest Neighbour Is Waterford (4.25 Euros)
Figure 18 - Table On From Waterford, The Next Nearest Neighbour Is Killarney (8.40 Euros)
Figure 19 - Table On Afterwards, Killarney’s Nearest Neighbour Is Galway (8.99 Euros).
Figure 20 - Table On From Galway, The Remaining Option Is Dublin (8.00 Euros).
Figure 21 - Table On To Return To Cork, It Costs 14.39 Euros.

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.

Verification

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.

Figure 22 - Optimal Journey Time As Calculated On TSP Calculator Website

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 -

Figure 23 - Optimal Journey Price As Calculated On TSP Calculator Website

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.

Top IB Math Tutor: 45/45 IBDP, 7/7 Further Math, 7 Yrs Exp, Medicine Student

• Conclusion and Evaluation

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.

Bibliography

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).