Mathematics AI SL's Sample Internal Assessment

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

6/7

12 mins read

Candidate Name: N/A

Candidate Number: N/A

Session: N/A

Word count: 2,348

Table of content

Introduction

Raw Data

Application

Verification

Conclusion and Evaluation

Bibliography

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

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

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