I’ve been testing out some ideas around the Travelling Salesman Problem using TSP and ggmap.
For illustration I’ll find the optimal route between the following addresses:
ADDRESSES = c(
"115 St Andrew's Drive, Durban North, KwaZulu-Natal, South Africa",
"1 Evans Road, Glenwood, Berea, KwaZulu-Natal, South Africa",
"7 Radar Drive, Durban North, KwaZulu-Natal, South Africa",
"25 Gainsborough Drive, Durban North, KwaZulu-Natal, South Africa",
"77 Armstrong Avenue, Umhlanga, KwaZulu-Natal, South Africa",
"255 Musgrave Road, Berea, KwaZulu-Natal, South Africa",
"11 Cassia Road, Reservoir Hills, Durban, KwaZulu-Natal, South Africa",
"98 Shepstone Road, Berkshire Downs, New Germany, KwaZulu-Natal, South Africa",
"12 Finchley Road, Berea West, Westville, KwaZulu-Natal, South Africa"
)
Load up some packages.
library(dplyr)
library(ggmap)
library(gmapsdistance)
library(TSP)
Geocoding
I added the latitude and longitude for each address using the handy ggmap::mutate_geocode(). I also added in a latlon column which is in the correct format for gmapsdistance.
addresses
# A tibble: 9 x 5
label address lon lat latlon
<chr> <chr> <dbl> <dbl> <chr>
1 A 115 St Andrews Dr, Durban North, 4051, South Africa 31.0 -29.8 -29.778758+31.043515
2 B 1 Evans Rd, Glenwood, Berea, 4001, South Africa 31.0 -29.9 -29.865966+30.992366
3 C 7 Radar Dr, Athlone, Durban North, 4051, South Africa 31.0 -29.8 -29.798012+31.033163
4 D 25 Gainsborough Dr, Athlone, Durban North, 4051, South Africa 31.0 -29.8 -29.795748+31.029069
5 E 77 Armstrong Ave, Umhlanga, 4051, South Africa 31.1 -29.7 -29.746962+31.067561
6 F 255 Musgrave Rd, Musgrave, Berea, 4001, South Africa 31.0 -29.8 -29.844441+31.001648
7 G 11 Cassia Rd, Reservoir Hills, Durban, 4090, South Africa 30.9 -29.8 -29.794960+30.940820
8 H 98 Shepstone Rd, Berkshire Downs, New Germany, 3610, South Africa 30.9 -29.8 -29.797855+30.879264
9 I 12 Finchley Rd, Berea West, Westville, 3629, South Africa 30.9 -29.8 -29.838373+30.925782
Calculate Distance Matrix
Next I used gmapsdistance::gmapsdistance() to calculate the distances between all pairs of locations and converted the result into a distance matrix.
distances
A B C D E F G H
B 14.507
C 2.855 11.369
D 2.931 11.884 1.311
E 5.032 18.065 7.785 8.329
F 11.039 2.921 7.248 7.739 15.051
G 16.663 16.103 13.740 13.370 22.195 12.763
H 22.166 19.120 19.243 18.873 27.698 18.916 7.480
I 20.321 10.232 16.443 16.074 24.938 10.028 8.794 11.407
Solve the Travelling Salesman Problem
The TSP package provides a range of solution techniques for the Travelling Salesman Problem. I got decent results using the default optimisation.
tsp <- TSP(distances)
tour <- solve_TSP(tsp)
tour
object of class ‘TOUR’
result of method ‘arbitrary_insertion+two_opt’ for 9 cities
tour length: 68.406
The length of the optimal tour is 68.4 km.
Build Route and Plot
Finally I used ggmap::route() to build a route between the locations in the order specified by tour and plotted.
The code for this is available here.