TSP: UK, 49 Most Populated Cities vs Nearest Neighbour Heuristic and Genetic Algorithm - Enhanced.

Travelling Salesman Problem: Visit Each City Once In The Shortest Route and Finish Where You Started.

pacman::p_load(pacman,geosphere,GA)

# Read the CSV file correctly
cities <- read.csv("UK_Cities.csv", header = TRUE, sep = ",")

# Split the City, Latitude, Longitude, and Population into separate columns
cities_split <- do.call(rbind, strsplit(as.character(cities$City.Latitude.Longitude.Population), ","))
cities <- data.frame(
  City = cities_split[, 1],
  Latitude = as.numeric(cities_split[, 2]),
  Longitude = as.numeric(cities_split[, 3]),
  Population = as.numeric(cities_split[, 4])
)

# Calculate the distance matrix
distance_matrix <- distm(cities[, c("Longitude", "Latitude")])

# Nearest Neighbour Heuristic
nearest_neighbour_tsp <- function(distance_matrix, start_city) {
  visited <- rep(FALSE, nrow(cities))
  route <- integer(nrow(cities))
  current_city <- start_city
  route[1] <- current_city
  visited[current_city] <- TRUE
  
  for (i in 2:nrow(cities)) {
    distances <- distance_matrix[current_city, ]
    distances[visited] <- Inf
    next_city <- which.min(distances)
    route[i] <- next_city
    visited[next_city] <- TRUE
    current_city <- next_city
  }
  
  # Return to start
  route <- c(route, route[1])
  total_distance <- sum(sapply(1:(length(route) - 1), function(i) {
    distance_matrix[route[i], route[i + 1]]
  }))
  
  return(list(route = route, total_distance = total_distance))
}

# Genetic Algorithm with a specified starting point
genetic_algorithm_tsp <- function(distance_matrix, start_city) {
  tsp_fitness <- function(route) {
    total_distance <- sum(sapply(1:(length(route) - 1), function(i) {
      distance_matrix[route[i], route[i + 1]]
    })) + distance_matrix[route[length(route)], route[1]] # return to start
    return(-total_distance)
  }
  
  cities_indices <- setdiff(1:nrow(cities), start_city)
  ga_tsp <- ga(
    type = "permutation",
    fitness = function(route) tsp_fitness(c(start_city, cities_indices[route])),
    lower = 1,
    upper = nrow(cities) - 1,
    popSize = 50,
    maxiter = 500,
    run = 100
  )
  
  best_route <- c(start_city, cities_indices[ga_tsp@solution[1, ]], start_city)
  best_distance <- -ga_tsp@fitnessValue
  
  return(list(route = best_route, total_distance = best_distance))
}

# Run NN and GA from each possible starting point and compare
shortest_nn_route <- NULL
shortest_nn_distance <- Inf

shortest_ga_route <- NULL
shortest_ga_distance <- Inf

for (i in 1:nrow(cities)) {
  # Run Nearest Neighbour
  nn_result <- nearest_neighbour_tsp(distance_matrix, i)
  if (nn_result$total_distance < shortest_nn_distance) {
    shortest_nn_distance <- nn_result$total_distance
    shortest_nn_route <- nn_result$route
  }
  
  # Run Genetic Algorithm
  ga_result <- genetic_algorithm_tsp(distance_matrix, i)
  if (ga_result$total_distance < shortest_ga_distance) {
    shortest_ga_distance <- ga_result$total_distance
    shortest_ga_route <- ga_result$route
  }
}

# Convert distances to kilometres and miles
shortest_nn_distance_km <- shortest_nn_distance / 1000
shortest_nn_distance_miles <- shortest_nn_distance / 1609.34

shortest_ga_distance_km <- shortest_ga_distance / 1000
shortest_ga_distance_miles <- shortest_ga_distance / 1609.34

# Print NN results
print(paste("Nearest Neighbour Shortest Route:", paste(cities$City[shortest_nn_route], collapse = " -> ")))

## [1] "Nearest Neighbour Shortest Route: Leicester -> Nottingham -> Derby -> Stoke-on-Trent -> Stockport -> Manchester -> Oldham -> Huddersfield -> Bradford -> Leeds -> Barnsley -> Sheffield -> York -> Hull -> Middlesbrough -> Sunderland -> Newcastle upon Tyne -> Edinburgh -> Glasgow -> Aberdeen -> Blackpool -> Southport -> Liverpool -> St Helens -> Warrington -> Wolverhampton -> Birmingham -> Coventry -> Northampton -> Milton Keynes -> Luton -> London -> Woking -> Reading -> Oxford -> Swindon -> Bristol -> Cardiff -> Exeter -> Plymouth -> Southampton -> Portsmouth -> Brighton -> Crawley -> Southend-on-Sea -> Ipswich -> Norwich -> Cambridge -> Peterborough -> Leicester"

print(paste("Nearest Neighbour Shortest Total Distance (metres):", shortest_nn_distance))

## [1] "Nearest Neighbour Shortest Total Distance (metres): 2838406.37621598"

print(paste("Nearest Neighbour Shortest Total Distance (km):", shortest_nn_distance_km))

## [1] "Nearest Neighbour Shortest Total Distance (km): 2838.40637621598"

print(paste("Nearest Neighbour Shortest Total Distance (miles):", shortest_nn_distance_miles))

## [1] "Nearest Neighbour Shortest Total Distance (miles): 1763.70833771359"

# Print GA results
print(paste("Genetic Algorithm Shortest Route:", paste(cities$City[shortest_ga_route], collapse = " -> ")))

## [1] "Genetic Algorithm Shortest Route: York -> Warrington -> St Helens -> Leicester -> Reading -> Exeter -> Plymouth -> Crawley -> Luton -> London -> Woking -> Swindon -> Bristol -> Cardiff -> Birmingham -> Oxford -> Milton Keynes -> Brighton -> Ipswich -> Southend-on-Sea -> Norwich -> Cambridge -> Peterborough -> Nottingham -> Derby -> Northampton -> Southampton -> Portsmouth -> Coventry -> Manchester -> Stockport -> Leeds -> Aberdeen -> Edinburgh -> Newcastle upon Tyne -> Bradford -> Glasgow -> Blackpool -> Oldham -> Southport -> Liverpool -> Wolverhampton -> Stoke-on-Trent -> Hull -> Huddersfield -> Sheffield -> Barnsley -> Middlesbrough -> Sunderland -> York"

print(paste("Genetic Algorithm Shortest Total Distance (metres):", shortest_ga_distance))

## [1] "Genetic Algorithm Shortest Total Distance (metres): 5159987.52252063"

print(paste("Genetic Algorithm Shortest Total Distance (km):", shortest_ga_distance_km))

## [1] "Genetic Algorithm Shortest Total Distance (km): 5159.98752252063"

print(paste("Genetic Algorithm Shortest Total Distance (miles):", shortest_ga_distance_miles))

## [1] "Genetic Algorithm Shortest Total Distance (miles): 3206.2755679475"

Code Explaination

knitr::opts_chunk$set(echo = TRUE): This configuration is identical to the previous version, ensuring that R code chunks are displayed in the rendered document.

pacman::p_load(…): This line loads the pacman, geosphere (for distance calculations), and GA (for the genetic algorithm) packages.

Reading the CSV data, splitting the combined column into separate ones, and calculating the distance matrix.

Enhanced Nearest Neighbour Algorithm.

This function is enhanced to take a start_city argument. It works similarly to the original version, but it begins the route from the specified start_city instead of always starting from the first city in the list.

Enhanced Genetic Algorithm.

This function also takes a start_city argument. The genetic algorithm now includes this specified starting city in every route it considers. The cities_indices line creates a vector of city indices excluding the start_city, which is used for generating permutations in the GA. The best route is then constructed by adding the start_city at the beginning and end.

Finding the Shortest Routes.

This section iterates over all cities (1:nrow(cities)). For each city, it:

Runs the Nearest Neighbour algorithm starting from that city.

If the resulting route is shorter than the previously found shortest NN route, it updates shortest_nn_route and shortest_nn_distance.

Does the same for the Genetic Algorithm.

By trying all possible starting points, it increases the chances of finding a better solution.

The final section converts the shortest distances found by NN and GA to kilometres and miles.

It then prints the shortest routes found by both algorithms, along with their distances in different units.