Waffle House: TSP map

wh_tsp

#Code adapted from https://github.com/datawookie/travelling-salesman-map/blob/master/travelling-salesman-demo.R

library(tidyverse)
library(purrr)
library(ggmap)
library(gmapsdistance)
library(TSP)
library(sf)

# Due to changes in the Google Maps Terms of Service, this code will not work without first registering an API key.
#
register_google(key = YOUR KEY HERE)

atl<-st_read("data/atlanta_msa_counties.gpkg") #County boundaries

wh<-read_csv("wafflehouse/wh_locations_coords.csv") %>% #Previously downloaded location data
  st_as_sf(coords=c("Longitude","Latitude"),crs=4326,remove=FALSE) %>%
  mutate(Longitude=as.numeric(Longitude),
         Latitude=as.numeric(Latitude)) %>%
  st_join(atl,join=st_within) %>%
  filter(is.na(GEOID)==FALSE) %>%
  mutate(latlon = sprintf("%f+%f", Latitude, Longitude)) %>%
  mutate(st_num=paste("WH",row_number(),sep=""))

write_csv(wh,"wafflehouse/wh_atl.csv")

# DISTANCES -----------------------------------------------------------------------------------------------------------
#Create a Euclidean distance matrix because it would be too costly on Google Maps PAI
distance<-st_distance(wh,wh)

# Scale to km.
#
distance <- as.matrix(distance) / 1000
#
colnames(distance) <- wh$st_num
rownames(distance) <- wh$st_num

# Convert to distance matrix.
#
distance <- as.dist(distance)

# TRAVELLING SALESMAN -------------------------------------------------------------------------------------------------

tsp <- TSP(distance)

methods <- c(
  "nearest_insertion",
  "farthest_insertion",
  "cheapest_insertion",
  "arbitrary_insertion",
  "nn",
  "repetitive_nn",
  "two_opt"
)

tours <- methods %>% map(function(method) {
  solve_TSP(tsp, method)
})

tour <- solve_TSP(tsp)
#
# Order of locations in tour.
#
tour_order <- as.integer(tour)
#
# Sort addresses.
#
addresses <- wh[tour_order,]

# BUILD ROUTE ---------------------------------------------------------------------------------------------------------

route <- lapply(seq(nrow(addresses) - 1), function(n) {
  print(n)
  route(addresses$latlon[n], addresses$latlon[n+1], structure = "route") %>%
    mutate(section = n)
})

route1 <- route %>% 
  bind_rows() %>%
  mutate(step=row_number())

write_csv(route1,"wafflehouse/wh_routes.csv")

#These are vertices. Actual route lines are created on QGIS.

#Route length in miles
routes_line<-st_read("wafflehouse/wh_routes.gpkg") %>%
  summarise()
as.numeric(st_length(routes_line))/1609.344