Travelling Salesman Problem: Visit Each City Once In The Shortest
Route and Finish Where You Started.
pacman::p_load(pacman,geosphere, GA)
# Load the cities data
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 <- as.matrix(distm(cities[, c("Longitude", "Latitude")], fun = distHaversine))
# Nearest Neighbour Heuristic Function
nearest_neighbour_tsp <- function(distance_matrix) {
num_cities <- nrow(distance_matrix)
visited <- rep(FALSE, num_cities)
route <- integer(num_cities)
current_city <- 1
route[1] <- current_city
visited[current_city] <- TRUE
for (i in 2:num_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 Nearest Neighbor Heuristic
nn_result <- nearest_neighbour_tsp(distance_matrix)
nn_route <- nn_result$route
nn_distance <- nn_result$total_distance
# Run Ant Colony Optimisation
aco_result <- ant_colony_optimisation(distance_matrix)
aco_route <- aco_result$route
aco_distance <- aco_result$total_distance
# Convert distances to kilometers and miles
nn_distance_km <- nn_distance / 1000
nn_distance_miles <- nn_distance / 1609.34
aco_distance_km <- aco_distance / 1000
aco_distance_miles <- aco_distance / 1609.34
# Print results
print(paste("Nearest Neighbour Route:", paste(cities$City[nn_route], collapse = " -> ")))
## [1] "Nearest Neighbour Route: London -> Woking -> Reading -> Oxford -> Swindon -> Bristol -> Cardiff -> Exeter -> Plymouth -> Southampton -> Portsmouth -> Brighton -> Crawley -> Southend-on-Sea -> Ipswich -> Norwich -> Cambridge -> Peterborough -> Northampton -> Milton Keynes -> Luton -> Coventry -> Birmingham -> Wolverhampton -> Stoke-on-Trent -> Stockport -> Manchester -> Oldham -> Huddersfield -> Bradford -> Leeds -> Barnsley -> Sheffield -> Derby -> Nottingham -> Leicester -> Warrington -> St Helens -> Liverpool -> Southport -> Blackpool -> York -> Hull -> Middlesbrough -> Sunderland -> Newcastle upon Tyne -> Edinburgh -> Glasgow -> Aberdeen -> London"
print(paste("Nearest Neighbour Total Distance (metres):", nn_distance))
## [1] "Nearest Neighbour Total Distance (metres): 3244330.67568849"
print(paste("Nearest Neighbour Total Distance (km):", nn_distance_km))
## [1] "Nearest Neighbour Total Distance (km): 3244.33067568849"
print(paste("Nearest Neighbour Total Distance (miles):", nn_distance_miles))
## [1] "Nearest Neighbour Total Distance (miles): 2015.93863054948"
print(paste("Ant Colony Optimisation Route:", paste(cities$City[aco_route], collapse = " -> ")))
## [1] "Ant Colony Optimisation Route: Cambridge -> Peterborough -> Leicester -> Nottingham -> Derby -> Sheffield -> Barnsley -> Huddersfield -> Bradford -> Leeds -> York -> Hull -> Middlesbrough -> Sunderland -> Newcastle upon Tyne -> Edinburgh -> Glasgow -> Aberdeen -> Southport -> Blackpool -> Liverpool -> St Helens -> Warrington -> Stockport -> Oldham -> Manchester -> Stoke-on-Trent -> 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"
print(paste("Ant Colony Optimisation Total Distance (metres):", aco_distance))
## [1] "Ant Colony Optimisation Total Distance (metres): 2805823.95039051"
print(paste("Ant Colony Optimisation Total Distance (km):", aco_distance_km))
## [1] "Ant Colony Optimisation Total Distance (km): 2805.82395039051"
print(paste("Ant Colony Optimisation Total Distance (miles):", aco_distance_miles))
## [1] "Ant Colony Optimisation Total Distance (miles): 1743.46250661172"