基于R计算带顶点停留时间惩罚的最优出行路线技术咨询

要解决在最小化总出行时间的基础上避免中转过多的问题，核心思路是给每个中转节点添加惩罚成本，并将其整合到路径权重中，让算法自动权衡「时间成本」和「中转次数」。下面用igraph（图分析常用工具）提供具体实现方案，同时补充替代思路。

步骤1：准备数据与构建图 #

先把出行时间表转换成有向图结构（路线是有向的，比如A→B和B→A的时间可能存在差异）：

library(igraph)

# 导入出行数据
travel_df <- data.frame(
  from = c("A", "A", "A", "A", "B", "B", "C", "D", "D", "E"),
  to = c("B", "C", "D", "E", "A", "D", "A", "A", "B", "A"),
  time = c(10, 20, 10, 30, 10, 5, 20, 10, 5, 30)
)

# 构建有向图
travel_graph <- graph_from_data_frame(travel_df, directed = TRUE)

步骤2：整合中转惩罚到权重中 #

中转惩罚的本质是：每经过一个非起点/终点的节点，就增加额外成本。我们可以把这个惩罚转化为边权重的增量——每走一条边对应到达一个新节点（除了起点），因此将每条边的权重设为出行时间 + 中转惩罚值，这样路径总权重等价于总出行时间 + 中转惩罚×(中转次数+1)，减去固定惩罚值后，就等于我们需要的总出行时间 + 中转惩罚×中转次数（固定惩罚不影响路径选择）。

# 定义每个中转节点的惩罚值（可根据需求调整）
transfer_penalty <- 15

# 调整边权重：出行时间 + 中转惩罚
E(travel_graph)$adjusted_weight <- travel_df$time + transfer_penalty

步骤3：计算兼顾惩罚的最优路径 #

用igraph的最短路径函数，基于调整后的权重计算最优路线：

# 示例：计算从A到B的最优路径
target_from <- "A"
target_to <- "B"

# 获取最短路径（基于调整后权重）
path_result <- get.shortest.paths(
  travel_graph,
  from = target_from,
  to = target_to,
  mode = "out",
  weights = E(travel_graph)$adjusted_weight
)$vpath[[1]]

# 提取路径节点
path_nodes <- V(travel_graph)$name[path_result]

# 计算各项指标
total_time <- sum(E(travel_graph, path = path_result)$time)
transfer_count <- length(path_nodes) - 2  # 减去起点和终点
total_cost <- total_time + transfer_penalty * transfer_count

# 输出结果
cat("最优路径：", paste(path_nodes, collapse = " -> "), "\n")
cat("总出行时间：", total_time, "\n")
cat("中转次数：", transfer_count, "\n")
cat("总成本（含惩罚）：", total_cost, "\n")

效果验证 #

以从E到B的场景为例：

• 纯时间最优路径是E→A→D→B，总时间45，中转2次，总成本=45+15×2=75
• 兼顾惩罚的最优路径是E→A→B，总时间40，中转1次，总成本=40+15×1=55
  算法会自动选择总成本更低的后者，避免了过多中转。

替代方案（不用igraph） #

如果不想用igraph，可以用lpSolve做线性规划建模：定义变量表示是否经过某条边，添加约束保证路径连通，目标函数设为总出行时间 + 中转惩罚×中转次数。不过这种方法实现复杂度更高，仅适合小规模图。

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