Travelling Salesman with ggmap

May 10, 2018
By

(This article was first published on R on datawookie, and kindly contributed to R-bloggers)

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.

To leave a comment for the author, please follow the link and comment on their blog: R on datawookie.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)