Help to create routes in R

General
1

HI everyone,

I would like to know if you could help me to solve a problem in R. I am trying to create a R program to solve a routing problem. I have several cities where I need to deliver a product, and I would like to make the less quantity of transports. I am using the TSP package but I am only getting the optimal route between two point. Anyone knows how can improve the program and include for example the cities than are close to this optimal route, for example at less than 50 km. I am using latitude and longitude to establish the point and calculate the distance in between each one. I have tried it creating clusters with the ClusterR package but it didn't help.

I have copied part of the program here:

coord=read.csv2("CoordinatesUK.txt")
coords.df=data.frame(long=coord$Longitude,lat=coord$Latitude)
coords.mx=as.matrix(coords.df)
dist.mx=dist(coords.df)
tsp.ins <-tsp_instance(coords.mx,dist.mx)
tour=run_solver(tsp.ins,method="2-opt")
autoplot(tsp.ins,tour)

This part is using all the point and calculating the optimal route to go through all of them but it is not the solution that I am looking for.

Thank you very much for your help.

1 Like
2

Hi,

Could you give us a minimal reproducible example and some visuals so we can see what exactly it is you need...

Also, in case you were not aware of it, the traveling salesman problem is NP hard and thus an optimal solution can not be guaranteed when you have many points. There are approximation algorithms like in the package, but they are not perfect (though can be very helpful)

Grtz,
PJ

3

Thank you for your reply. I include here more info about my problem. A minimal Reproducible example.

**library**(ggplot2)
**library**(tspmeta)

coord=read.csv2("CoordinatesUKExample.txt")
coords.df=data.frame(long=coord$Longitude,lat=coord$Latitude)
coords.mx=as.matrix(coords.df)
dist.mx=dist(coords.df)
tsp.ins <-tsp_instance(coords.mx,dist.mx)
tour=run_solver(tsp.ins,method="2-opt")
autoplot(tsp.ins,tour)
head(coord)
#> Postcode         	 City			 Latitude 	 Longitude
#> 1 AB53 8BJ 	     	Aberdeenshire   57.52995 	-2.4509960
#> 2 NE46 4SA         	Acomb 			54.99080 	-2.1184036
#> 3 NE66 2HT       	Alnwick 		55.39723 	-1.6900000
#> 4 CA16 6QR       	Appleby 		54.57808 	-2.4929927
#> 5 CA16 6JP       	Appleby 		54.60883 	-2.5188636
#> 6  CO7 7LG       	Ardeigh 		51.92808     0.9833302

In that case this is the optimal path to include all the points. But What I am looking for is to calculate the points that are near to a main route between two cities (points).
I have made also this to map the points in the UK and make it easier to understand. I have calculated all the geodistances between the points and create clusters regarding that distances just to show points in the map (now there are only 10 cities but in the real case I have around 80):

**library**(gmp)
**library**(cluster)
**library**(raster)

#Geo distance function
geo.dist = function(df) {
  require(geosphere)
  d <- function(i,z){         # z[1:2] contain long, lat
    dist <- rep(0,nrow(z))
    dist[i:nrow(z)] <- distHaversine(z[i:nrow(z),1:2],z[i,1:2])
    return(dist)
  }
  dm <- do.call(cbind,lapply(1:nrow(df),d,df))
  return(as.dist(dm))
}
df     <- data.frame(long=coord$Longitude, lat=coord$Latitude, city=coord$City)
d      <- geo.dist(df)   # distance matrix
hc     <- hclust(d)      # hierarchical clustering
df$clust <- cutree(hc,k=10)

UK <- getData("GADM", country = "GBR", level = 1)
map.df <- fortify(UK)

ggplot(map.df)+
  geom_path(aes(x=long, y=lat, group=group))+
  geom_point(data=df, aes(x=long, y=lat, color=factor(clust)), size=4)+
  scale_color_discrete("Cluster")+
  coord_fixed()

So I got the following UK map (without the red line):

image

My objective is to be able to say that if I go from the point 1 to the point 7, my optimal route (red path) is close to the points 9, 3 and 5.

Maybe there is a package to make it easier or something like that. I have seen something about google maps but I couldn’t create a good code to implement it.

If anyone can help me I will be very grateful.

1 Like
4

Hi,

The implementation depends on how accurate to real life you want this to be. At this point, you are calculating distance as a simple linear distance between points, so not taking any real roads or travel time into account. (In your case, the line from 1 - 7 would pass through the sea).

If you want to be more accurate, you will indeed need google maps API to calculate the distance and time between points, and then use this info for further calculations. Getting this API requires setting up a billing account with google, and I'm not sure if there is an easy R implementation yet.

PJ

5

This topic was automatically closed 21 days after the last reply. New replies are no longer allowed.