Create shortest path from list of GPS coordinates in R

Question

I have a list of GPS coordinates as a 2 column (lat and long) dataframe.

I want to find the shortest path that includes all GPS coordinates and re-sort the dataframe with the GPS coordinates in order of the shortest path.

The route will be non-cyclical, so the distance from the last coordinate to the first is irrelevant since it does not need to loop back.

For my purposes here it's fine if the list is sorted based on point distances in 2D space if that simplifies the algorithm.

I had a look at the igraph package for possible functions to use but couldn't make heads or tails of it. I'm open to whatever gets the job done the easiest. I'm an R noob. Thanks.

Answer 1

Learn how to make a reproducible example: How to make a great R reproducible example

For your problem:

> #grab some US city lat and long. I downloaded uscities.csv data from from simplemaps.com .  after downloading to your local folder.
> cities <- read.csv(".../uscities.csv") #where ever the file on your local machine
> #select 8
> cities <- cities[1:8,c("city","lat","lng")]
> cities
          city     lat       lng
1     New York 40.6943  -73.9249
2  Los Angeles 34.1139 -118.4068
3      Chicago 41.8373  -87.6862
4        Miami 25.7839  -80.2102
5       Dallas 32.7936  -96.7662
6 Philadelphia 40.0077  -75.1339
7      Houston 29.7863  -95.3889
8      Atlanta 33.7627  -84.4224
> 
> #create a distance matrix.  I used this answer https://stackoverflow.com/questions/45784094/geosphere-dplyr-create-matrix-of-distance-between-coordinates
> library(geosphere)
> # create a distance matrix
> m <- distm(cities[3:2], cities[3:2], fun = distVincentyEllipsoid)
> 
> # replace the diagonal with 0
> diag(m) <- 0
> 
> # bind the distance matrix to the dataframe
> cities = cbind.data.frame(cities, m)
> 
> #solve for shortest path 
> library(TSP)
> 
> tsp = TSP(m)
> tour = solve_TSP(tsp)
> 
> #tour length 
> tour_length(tour)
[1] 10220935
> 
> #permutation vector for shortest tour
> perm_vec = as.integer(tour)
> 
> #re-arrange cities data frame in order of city tour
> cities <- cities[perm_vec,]
> cities
          city     lat       lng         1       2         3         4         5         6         7         8
4        Miami 25.7839  -80.2102 1753118.6 3777773 1908488.7       0.0 1783521.9 1646629.9 1558870.8  973458.3
8      Atlanta 33.7627  -84.4224 1206599.8 3127449  940984.3  973458.3 1154246.7 1078687.4 1127668.8       0.0
7      Houston 29.7863  -95.3889 2288557.3 2223344 1505897.4 1558870.8  358282.5 2163138.9       0.0 1127668.8
5       Dallas 32.7936  -96.7662 2211900.8 2013528 1284933.7 1783521.9       0.0 2092251.3  358282.5 1154246.7
2  Los Angeles 34.1139 -118.4068 3962368.2       0 2814608.6 3777772.5 2013528.3 3865420.3 2223343.6 3127449.0
3      Chicago 41.8373  -87.6862 1158846.6 2814609       0.0 1908488.7 1284933.7 1075634.3 1505897.4  940984.3
1     New York 40.6943  -73.9249       0.0 3962368 1158846.6 1753118.6 2211900.8  127912.5 2288557.3 1206599.8
6 Philadelphia 40.0077  -75.1339  127912.5 3865420 1075634.3 1646629.9 2092251.3       0.0 2163138.9 1078687.4

Answer 2

Eric gave a good answer, he only disregarded the querist's statement that The route will be non-cyclical, while solve_TSP() searches for a cyclical tour which returns to the starting city. But this is not a big deal; the TSP documentation shows the way to transform a shortest Hamiltonian path problem (i.e., finding an optimal linear order) into a shortest Hamiltonian cycle problem with the aid of insert_dummy():

tsp = TSP(m)
tsp = insert_dummy(tsp) # add a dummy city to find a short Hamiltonian path
tour = solve_TSP(tsp)
path = cut_tour(tour, "dummy")  # cut the tour to get the path
print(cities[path,1:3]) # view the cities sorted along the path

We can see that therewith tour_length(tour) is smaller than the length of the cyclical tour reduced by its greatest distance (Los Angeles to Chicago in Eric's example).

Also of interest might be TSP – Infrastructure for the Traveling Salesperson Problem.