从 R 中的 GPS 坐标列表创建最短路径

Question

我有一个 GPS 坐标列表作为 2 列（经纬度）数据框。

我想找到包含所有 GPS 坐标的最短路径，并按照最短路径的顺序使用 GPS 坐标对数据帧进行重新排序。

该路线将是非循环的，因此从最后一个坐标到第一个坐标的距离无关紧要，因为它不需要环回。

为了我的目的，如果列表根据 2D 中的点距离排序 space 如果这样可以简化算法，那很好。

我查看了 igraph 包以了解可能使用的功能，但无法弄清它的正反面。我对任何最容易完成工作的事情持开放态度。我是一个 R 菜鸟。谢谢。

Answer 1

了解如何制作可重现的示例：How to make a great R reproducible example

针对您的问题：

> #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 
> 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 给出了一个很好的答案，他只是无视了查询者的声明这条路线将是非循环的，而solve_TSP()搜索一个循环的游览returns到出发城市。但这没什么大不了的； TSP documentation 展示了如何将最短哈密顿路径问题（即找到最优线性阶数）转换为借助 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

我们可以看到 tour_length(tour) 小于循环游览的长度减去最大距离（在 Eric 的例子中是洛杉矶到芝加哥）。

也可能感兴趣 TSP – 旅行推销员的基础设施问题.

从 R 中的 GPS 坐标列表创建最短路径

Create shortest path from list of GPS coordinates in R

routes

r

graph

distance

coordinates