R中带目标值与约束的路径规划算法需求及优化问询

• 手头数据集包含79个地点的经纬度、value_generated（对应代码中的social_cost）和processing_time字段
• 核心需求：设计路径算法，选出总value_generated最高的路径，同时满足总旅行时间 + 总处理时间 ≤ 一年的约束
• 旅行时间计算规则：两点间距离除以10mph，无需覆盖所有地点，优先采用真实路网（也可使用直线距离简化）
• 现有实现问题：用贪心算法（以score = individual_social_cost - (individual_processing_time + individual_travel_time)为选择依据）生成的路径存在不合理跳转，比如生成1,7,10,15,30，但7和15相邻，最优路径应为1,7,15,10,30以减少旅行距离

find_optimal_path <- function(deschutes_nf, max_time) {
  num_locations <- nrow(deschutes_nf)
  distances <- matrix(0, nrow = num_locations, ncol = num_locations)
  
  # Calculate distances between locations
  for (i in 1:num_locations) {
    for (j in 1:num_locations) {
      distances[i, j] <- calculate_distance_miles(deschutes_nf[i,], deschutes_nf[j,])
    }
  }
  
  current_location <- 1  # Start from location 1
  visited_locations <- c(current_location)
  remaining_locations <- setdiff(1:num_locations, current_location)
  
  total_social_cost <- 0
  total_processing_time <- 0
  total_distance <- 0
  total_travel_time <- 0
  total_time <- 0 
  
  while (length(remaining_locations) > 0) {
    best_location <- NULL
    best_score <- -Inf
    
    # Step 1: Evaluate feasibility of adding next location to the path
    for (next_location in remaining_locations) {
      path <- c(visited_locations, next_location)
      
      # Calculate total social cost, processing time, distance, and travel time
      total_social_cost_candidate <- sum(deschutes_nf[path, "social_cost"])
      total_processing_time_candidate <- sum(deschutes_nf[path, "processing_time"])
      total_distance_candidate <- sum(distances[path[1:(length(path)-1)], path[2:length(path)]])
      total_travel_time_candidate <- sum(calculate_travel_time(distances[path[1:(length(path)-1)], path[2:length(path)]]))
      
      # Calculate total time including processing and travel time
      total_time_candidate <- total_processing_time_candidate + total_travel_time_candidate
      
      # Check if constraints are satisfied
      if (total_time_candidate <= max_time) {
        # Step 2: Evaluate individual contribution of next location to the path
        individual_social_cost <- deschutes_nf[next_location, "social_cost"]
        individual_processing_time <- deschutes_nf[next_location, "processing_time"]
        individual_distance <- distances[visited_locations[length(visited_locations)], next_location]
        individual_travel_time <- calculate_travel_time(individual_distance)
        
        # Calculate score based on individual contribution and distance penalty
score <- individual_social_cost - (individual_processing_time + individual_travel_time) - (10 * individual_distance)

        
        # Update the best location if the current candidate has a higher score
        if (score > best_score) {
          best_location <- next_location
          best_score <- score
          best_processing_time <- individual_processing_time
          best_distance <- individual_distance
          best_travel_time <- individual_travel_time
          best_social_cost <- individual_social_cost
        }
      }
    }
    
    # If a feasible location is found, move to that location
    if (!is.null(best_location)) {
      current_location <- best_location
      visited_locations <- c(visited_locations, current_location)
      remaining_locations <- remaining_locations[remaining_locations != current_location]
      total_social_cost <- total_social_cost + best_social_cost  
      total_processing_time <- total_processing_time + best_processing_time
      total_distance <- total_distance + best_distance
      total_travel_time <- total_travel_time + best_travel_time
      total_time <- total_processing_time + total_travel_time
    } else {
      # If no feasible location is found, break the loop
      break 
    }
  }
  
  return(list(path = visited_locations, total_social_cost = total_social_cost, 
              total_processing_time = total_processing_time, total_distance = total_distance, 
              total_travel_time = total_travel_time, total_time = total_time))
}

1. 给贪心算法加局部重排优化 #

当前贪心只做“单次向前选择”，忽略已选路径的局部优化。可以在每添加若干节点后，对已选路径做局部调整：

• 每添加2-3个节点，遍历已选路径中的相邻节点对，尝试交换位置
• 计算交换后的总时间和总收益，若总时间不超约束且收益不降低，则更新路径
• 示例代码（插入到visited_locations更新后的位置）：

# 局部重排优化：交换相邻节点尝试优化路径
if (length(visited_locations) >= 3) {
  for (i in 2:(length(visited_locations)-1)) {
    # 交换第i和i+1个节点
    temp_path <- visited_locations
    temp_path[c(i, i+1)] <- temp_path[c(i+1, i)]
    
    # 计算交换后的时间与收益
    temp_processing <- sum(deschutes_nf[temp_path, "processing_time"])
    temp_travel <- sum(calculate_travel_time(distances[temp_path[1:(length(temp_path)-1)], temp_path[2:length(temp_path)]]))
    temp_total_time <- temp_processing + temp_travel
    temp_total_cost <- sum(deschutes_nf[temp_path, "social_cost"])
    
    # 满足约束且收益不降低则更新
    if (temp_total_time <= max_time && temp_total_cost >= total_social_cost) {
      visited_locations <- temp_path
      total_processing_time <- temp_processing
      total_travel_time <- temp_travel
      total_time <- temp_total_time
      total_social_cost <- temp_total_cost
      current_location <- visited_locations[length(visited_locations)]
    }
  }
}

2. 换用更适配的算法（针对79节点规模） #

79个节点的规模，纯暴力枚举不可行，但以下方法更适合：

• 遗传算法/模拟退火：属于启发式算法，通过迭代进化寻找近似最优解，实现难度适中，能处理79节点的规模，且容易调整参数平衡效果与效率
• 分支定界法：如果能设计有效的剪枝规则（比如用当前最优收益作为上界，剪掉不可能更优的分支），可以找到精确最优解，但实现复杂度较高
• 动态规划（近似版）：传统状态压缩DP（状态为节点访问掩码）因2^79的规模不可行，但可以限制路径长度（比如最多访问20个节点），或用贪心+DP结合的方式

3. 距离计算优化（可选） #

• 若要使用真实路网，可部署本地OSRM服务计算道路距离，替代直线距离
• 用R的向量化操作替换双重循环计算距离矩阵，提升效率：

# 用向量化方式计算距离矩阵，替代双重for循环
library(geosphere)
distances <- distm(deschutes_nf[, c("lon", "lat")], deschutes_nf[, c("lon", "lat")], fun = distHaversine)
# 转换为英里（1米=0.000621371英里）
distances <- distances * 0.000621371

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