r - 如何根据 R 中的时间矩阵对点进行排序？

Question

我在 R 中有一个时间矩阵，我在 osrm 包的帮助下计算了它。我想根据相邻点对点进行排序。示例数据:

name <- LETTERS[1:10]
lat  <- c(22.57, 22.69, 22.72, 22.50, 22.66, 22.19, 22.60, 22.27, 22.31, 22.15)
lon  <- c(88.69, 88.84, 88.77, 88.85, 88.63, 88.91, 88.54, 88.62, 88.78, 88.66)
demand <- c(30, 70, 75, 100, 45, 60, 135, 65, 55, 50)

df<-data.frame(name, lon, lat, demand)

计算时间矩阵

library(osrm)


time<- osrmTable(df[,c('name', 'lon', 'lat')])
time_matrix<- time$durations

现在，我想要一个类似这样的数据框，基于上面的时间矩阵。

From To Time Demand
A    G  30.1 135
G    E  33.9 45
E    C  30.3 75

我可以找到最近的点，但我需要检查最近的点是否包含在 From 列中。如果已经存在，则将使用第二个最近的点，依此类推。就像这里 G 的最近点是 A，但因为它已经包含在内，所以它将是 E(第二个最近点)。类似地，它会继续下去，直到所有的点都被包含在表中。

我该怎么做？

Answer 1

解决方案取决于起点(我们可以假定为数据中的第一个点)以及如何选择下一个点。

连续路径

下面的点是最近邻:

diag(time_matrix) <- NA

nearestpoints <- data.frame(matrix(ncol = 4, nrow = 0))
colnames(nearestpoints) <- c("From", "To", "Time", "Demand")

inputrowindex=1
outputrowindex=1
visitedpoints <- c(rownames(time_matrix)[1]) #The visited points are the 'To' points

while(length(setdiff(rownames(time_matrix), visitedpoints)) > 0){
  nearest <- which.min(time_matrix[inputrowindex,])
  if(length(nearest)==0) break
  
  nearestpoints[outputrowindex, 1] <- rownames(time_matrix)[inputrowindex]
  nearestpoints[outputrowindex, 2] <- names(nearest)
  nearestpoints[outputrowindex, 3] <- time_matrix[inputrowindex, nearest]
  nearestpoints[outputrowindex, 4] <- df[nearest, 4]
  
  time_matrix[inputrowindex,] <- NA
  time_matrix[,inputrowindex] <- NA
  
  visitedpoints <- c(visitedpoints, names(nearest))
  
  inputrowindex = as.numeric(nearest) #Next point is the nearest
  outputrowindex = outputrowindex + 1
}

给出:

head(nearestpoints)
#  From To Time Demand
#1    A  G 30.1    135
#2    G  E 33.7     45
#3    E  C 30.3     75
#4    C  B 11.4     70
#5    B  D 35.2    100
#6    D  I 56.5     55

数据有序路径

下面的点是数据中的下一个:

diag(time_matrix) <- NA

nearestpoints <- data.frame(matrix(ncol = 4, nrow = 0))
colnames(nearestpoints) <- c("From", "To", "Time", "Demand")

inputrowindex=1
outputrowindex=1

visitedpoints <- c() #The visited points are the 'From' points

while(length(setdiff(rownames(time_matrix), visitedpoints)) > 0){
  nearest <- which.min(time_matrix[inputrowindex,])
  if(length(nearest)==0) break
  
  nearestpoints[outputrowindex, 1] <- rownames(time_matrix)[inputrowindex]
  nearestpoints[outputrowindex, 2] <- names(nearest)
  nearestpoints[outputrowindex, 3] <- time_matrix[inputrowindex, nearest]
  nearestpoints[outputrowindex, 4] <- df[nearest, 4]
  
  time_matrix[inputrowindex,] <- NA
  time_matrix[,inputrowindex] <- NA
  
  visitedpoints <- c(visitedpoints,  rownames(time_matrix)[inputrowindex])
  
  inputrowindex = inputrowindex + 1 #Next point in the data
  outputrowindex = outputrowindex + 1
}

给出:

head(nearestpoints)
#  From To  Time Demand
#1    A  G  30.1    135
#2    B  C  11.4     75
#3    C  E  30.3     45
#4    D  I  56.5     55
#5    E  G  33.9    135
#6    F  H 118.1     65

---

原始数据:

name <- LETTERS[1:10]
lat  <- c(22.57, 22.69, 22.72, 22.50, 22.66, 22.19, 22.60, 22.27, 22.31, 22.15)
lon  <- c(88.69, 88.84, 88.77, 88.85, 88.63, 88.91, 88.54, 88.62, 88.78, 88.66)
demand <- c(30, 70, 75, 100, 45, 60, 135, 65, 55, 50)
df <- data.frame(name, lat, lon, demand)

library(osrm)
time <- osrmTable(df[,c('name', 'lon', 'lat')])
time_matrix <- time$durations