Travelling Salesman Problem: Visit Each City Once In The Shortest
Route and Finish Where You Started.
# Load necessary packages
pacman::p_load(pacman, geosphere, leaflet)
# 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 Function
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))
}
# Ant Colony Optimisation Function
ant_colony_optimisation <- function(distance_matrix, num_ants = 50, num_iterations = 100, alpha = 1, beta = 5, rho = 0.1, Q = 100) {
num_cities <- nrow(distance_matrix)
pheromones <- matrix(1, nrow = num_cities, ncol = num_cities)
best_tour <- NULL
best_length <- Inf
for (iter in 1:num_iterations) {
all_tours <- list()
all_lengths <- numeric(num_ants)
for (ant in 1:num_ants) {
start_city <- sample(1:num_cities, 1)
tour <- integer(num_cities)
visited <- rep(FALSE, num_cities)
current_city <- start_city
tour[1] <- current_city
visited[current_city] <- TRUE
for (i in 2:num_cities) {
probabilities <- numeric(num_cities)
for (j in 1:num_cities) {
if (!visited[j]) {
probabilities[j] <- (pheromones[current_city, j] ^ alpha) * ((1 / distance_matrix[current_city, j]) ^ beta)
}
}
probabilities <- probabilities / sum(probabilities)
next_city <- sample(1:num_cities, 1, prob = probabilities)
tour[i] <- next_city
visited[next_city] <- TRUE
current_city <- next_city
}
tour <- c(tour, start_city) # Return to start city
length <- sum(sapply(1:(length(tour) - 1), function(i) {
distance_matrix[tour[i], tour[i + 1]]
}))
all_tours[[ant]] <- tour
all_lengths[ant] <- length
if (length < best_length) {
best_tour <- tour
best_length <- length
}
}
pheromones <- (1 - rho) * pheromones
for (ant in 1:num_ants) {
for (i in 1:(length(all_tours[[ant]]) - 1)) {
pheromones[all_tours[[ant]][i], all_tours[[ant]][i + 1]] <- pheromones[all_tours[[ant]][i], all_tours[[ant]][i + 1]] + Q / all_lengths[ant]
}
pheromones[all_tours[[ant]][length(all_tours[[ant]])], all_tours[[ant]][1]] <- pheromones[all_tours[[ant]][length(all_tours[[ant]])], all_tours[[ant]][1]] + Q / all_lengths[ant]
}
}
return(list(route = best_tour, total_distance = best_length))
}
# Run NN and ACO from each possible starting point and compare
shortest_nn_route <- NULL
shortest_nn_distance <- Inf
shortest_aco_route <- NULL
shortest_aco_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 Ant Colony Optimisation
aco_result <- ant_colony_optimisation(distance_matrix)
if (aco_result$total_distance < shortest_aco_distance) {
shortest_aco_distance <- aco_result$total_distance
shortest_aco_route <- aco_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_aco_distance_km <- shortest_aco_distance / 1000
shortest_aco_distance_miles <- shortest_aco_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 ACO results
print(paste("Ant Colony Optimisation Shortest Route:", paste(cities$City[shortest_aco_route], collapse = " -> ")))
## [1] "Ant Colony Optimisation Shortest Route: Aberdeen -> Edinburgh -> Glasgow -> Blackpool -> Southport -> Liverpool -> St Helens -> Warrington -> Manchester -> Oldham -> Stockport -> Huddersfield -> Bradford -> Leeds -> Barnsley -> Sheffield -> Nottingham -> Derby -> Stoke-on-Trent -> Wolverhampton -> Birmingham -> Coventry -> Leicester -> Northampton -> Milton Keynes -> Luton -> London -> Woking -> Reading -> Oxford -> Swindon -> Bristol -> Cardiff -> Exeter -> Plymouth -> Southampton -> Portsmouth -> Brighton -> Crawley -> Southend-on-Sea -> Ipswich -> Norwich -> Cambridge -> Peterborough -> Hull -> York -> Middlesbrough -> Sunderland -> Newcastle upon Tyne -> Aberdeen"
print(paste("Ant Colony Optimisation Shortest Total Distance (metres):", shortest_aco_distance))
## [1] "Ant Colony Optimisation Shortest Total Distance (metres): 2719572.78505715"
print(paste("Ant Colony Optimisation Shortest Total Distance (km):", shortest_aco_distance_km))
## [1] "Ant Colony Optimisation Shortest Total Distance (km): 2719.57278505715"
print(paste("Ant Colony Optimisation Shortest Total Distance (miles):", shortest_aco_distance_miles))
## [1] "Ant Colony Optimisation Shortest Total Distance (miles): 1689.8683839693"
# Create a data frame for route data
route_data <- data.frame(
City = cities$City,
NN_Route = FALSE,
ACO_Route = FALSE
)
# Mark cities in the routes
route_data$NN_Route[shortest_nn_route] <- TRUE
route_data$ACO_Route[shortest_aco_route] <- TRUE
# Add route numbers to the cities
route_data$NN_Number <- NA
route_data$NN_Number[shortest_nn_route[-length(shortest_nn_route)]] <- 1:(length(shortest_nn_route) - 1)
route_data$NN_Number[shortest_nn_route[length(shortest_nn_route)]] <- 1
route_data$ACO_Number <- NA
route_data$ACO_Number[shortest_aco_route[-length(shortest_aco_route)]] <- 1:(length(shortest_aco_route) - 1)
route_data$ACO_Number[shortest_aco_route[length(shortest_aco_route)]] <- 1
# Create a map
map <- leaflet() %>%
addTiles() %>%
addMarkers(data = cities, ~Longitude, ~Latitude, popup = ~City) %>%
addPolylines(data = cities[shortest_nn_route,], ~Longitude, ~Latitude, color = "blue", weight = 2, opacity = 0.7, label = paste("NN", route_data$NN_Number, sep = "-")) %>%
addPolylines(data = cities[shortest_aco_route,], ~Longitude, ~Latitude, color = "red", weight = 2, opacity = 0.7, label = paste("ACO", route_data$ACO_Number, sep = "-")) %>%
addLegend("bottomright", colors = c("blue", "red"), labels = c("NN Route", "ACO Route"))
# Display the map
map