寻求计算检查员累计出行距离的更高效方法

原代码瓶颈分析 #

你当前的实现依赖嵌套循环（while+双层for），每次迭代都要单独计算最近点，且动态删除ExamAssets行后重复扫描全量数据，再加上使用地理坐标系（EPSG:4326）计算球面距离，对于20000个站点的规模来说，效率极低。以下是针对性的优化方案：

优化方案与代码实现 #

1. 先转换到平面坐标系

地理坐标系的球面距离计算远慢于平面坐标系的欧氏距离，先将数据转换为英国本土平面坐标系（EPSG:27700）：

library(tidyverse)
library(sf)
library(units)
library(spData)
library(nngeo)

# 数据生成与投影转换
UK <- world[world$name_long == "United Kingdom", ] %>% 
  st_transform(crs = 27700) # 转换为英国平面坐标系
Data <- st_sample(UK, size = 20000, type = "random", crs = st_crs(27700)) %>% st_as_sf()
Examiner_Locations_all <- st_sample(UK, size = 25, type = "random", crs = st_crs(27700)) %>% 
  st_as_sf() %>% 
  mutate(examiner_id = row_number()) # 给检查员添加唯一ID

ExamsPerDay <- 4

2. 矢量化批量分配站点

用空间索引一次性完成所有站点到最近检查员的分配，避免循环：

# 批量匹配每个站点到最近的检查员
site_assignments <- st_join(Data, Examiner_Locations_all, join = st_nearest_feature) %>% 
  rename(examiner_id = examiner_id.y) %>% 
  select(-examiner_id.x)

# 将每个检查员的站点按距离分组（每组ExamsPerDay个）
site_groups <- site_assignments %>% 
  group_by(examiner_id) %>% 
  mutate(
    dist_to_examiner = st_distance(geometry, Examiner_Locations_all[examiner_id, ]$geometry, by_element = TRUE) %>% as.numeric(),
    group_id = ceiling(row_number() / ExamsPerDay) # 按顺序分组
  ) %>% 
  arrange(dist_to_examiner) %>% 
  ungroup()

3. 批量计算路径总距离

采用贪心算法（快速）或TSP算法（路径更优）计算每组站点的往返路径，避免逐点循环：

贪心算法（适合大数据量，速度快）

# 计算单组站点的往返路径距离
calculate_greedy_distance <- function(site_group, examiner_loc) {
  # 按距离检查员由近到远排序站点
  sorted_sites <- site_group %>% 
    mutate(dist = st_distance(geometry, examiner_loc$geometry) %>% as.numeric()) %>% 
    arrange(dist)
  # 构建路径：检查员 -> 站点1 -> ... -> 站点n -> 检查员
  path_points <- c(st_geometry(examiner_loc), st_geometry(sorted_sites), st_geometry(examiner_loc))
  # 累加连续点之间的距离
  total_dist <- sum(st_distance(path_points[-length(path_points)], path_points[-1], by_element = TRUE) %>% as.numeric())
  return(total_dist)
}

# 汇总每个检查员的总行驶距离
examiner_total_dist <- site_groups %>% 
  group_by(examiner_id, group_id) %>% 
  group_modify(~{
    examiner_loc <- Examiner_Locations_all[.$examiner_id[1], ]
    dist <- calculate_greedy_distance(.x, examiner_loc)
    tibble(group_distance = dist)
  }) %>% 
  group_by(examiner_id) %>% 
  summarise(total_distance = sum(group_distance) %>% set_units("m")) %>% 
  left_join(Examiner_Locations_all, by = "examiner_id")

TSP算法（路径更优，适合对路径长度要求高的场景）

如果需要更优的路径，可以使用TSP包求解旅行商问题：

library(TSP)

calculate_tsp_distance <- function(site_group, examiner_loc) {
  # 组合检查员位置与站点位置
  all_points <- c(st_geometry(examiner_loc), st_geometry(site_group))
  # 生成距离矩阵
  dist_matrix <- st_distance(all_points) %>% as.matrix() %>% as.numeric() %>% matrix(nrow = length(all_points))
  # 构建闭合TSP问题（起点/终点为检查员位置）
  tsp <- TSP(dist_matrix) %>% insert_dummy(label = "end")
  tour <- solve_TSP(tsp, method = "nearest_insertion")
  # 计算总路径长度
  total_dist <- tour_length(tour)
  return(total_dist)
}

# 替换上述group_modify中的函数即可使用TSP算法

优化核心优势 #

• 矢量化操作：用st_join+空间索引一次性完成所有站点分配，避免循环遍历
• 平面坐标系：欧氏距离计算速度远快于球面距离
• 批量路径计算：贪心/TSP算法批量处理路径，替代逐点找最近点的低效逻辑
• 无动态数据修改：避免原代码中反复删除数据导致的全量扫描

内容的提问来源于stack exchange，提问作者DX101