时间戳

首页 > 解决方案 > 从R中的GPS坐标列表创建最短路径

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

问题描述

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

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

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

出于我的目的，如果列表是基于 2D 空间中的点距离排序的，那么如果这样可以简化算法，那很好。

我查看了 igraph 包以了解可能使用的功能，但无法对其进行正面或反面。我愿意接受最容易完成工作的任何事情。我是R菜鸟。谢谢。

标签： rgraphroutescoordinatesdistance

解决方案

学习如何制作可重现的示例：如何制作出色的 R 可重现示例

对于您的问题：

> #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

推荐阅读