计算具有顶点停靠点成本惩罚的最佳路线

Question

我希望用 R 计算最佳旅行路线。假设我有一个如下所示的旅行时间表。

通过 igraph 和 distance_table，我和我的同事已经弄清楚如何计算旅行路线，从而最小化旅行时间总和，或者最小化路线中的边数（我通过将所有旅行时间设置为 1 来实现）。

我还没有弄清楚该怎么做，是计算最小旅行时间，但为每个停止点添加时间旅行惩罚。这样，我就可以避免获得经过太多中途停留的最佳路线。做这个的最好方式是什么？我想用 R 来做这件事，但我愿意使用 igraph 以外的库（我不太熟悉）。

起源	目的地	旅行时间
A	B	10
A	C	20
A	D	10
A	E	30
B	A	10
B	D	5
C	A	20
D	A	10
D	B	5
E	A	30

Answer 1

您当然可以在这里使用

igraph

来让您的工作更轻松。

首先，将数据框转换为图形对象，这很简单：

library(igraph)

g <- graph_from_data_frame(df)

我们可以通过做来看看它是什么样子

plot(g)

如果我们想要节点之间的最短距离，考虑到旅行时间，我们可以简单地使用函数

distances

，使用旅行时间作为权重：

times <- distances(g, weights = edge_attr(g, 'Travel Time'))

times
#>    A  B  C  D  E
#> A  0 10 20 10 30
#> B 10  0 30  5 40
#> C 20 30  0 30 50
#> D 10  5 30  0 40
#> E 30 40 50 40  0

如果我们想添加中途停留惩罚，那么我们需要知道我们正在穿越多少条边。显然，对于距离矩阵的对角线来说，没有经过任何边，但如果只经过一条边，我们也不需要中途停留惩罚，因为没有中途停留。本质上，我们希望对所遍历的 n - 1 条边中的每条边进行中途停留惩罚。我们可以通过将未加权图表乘以中途停留时间并将其添加回我们的加权距离矩阵来获得总旅行时间：

stopover_time <- 5

n_nodes <- distances(g)
result <- replace(n_nodes - 1, n_nodes - 1 < 0, 0) * stopover_time + times

result
#>    A  B  C  D  E
#> A  0 10 20 10 30
#> B 10  0 35  5 45
#> C 20 35  0 35 55
#> D 10  5 35  0 45
#> E 30 45 55 45  0

^{创建于 2023-10-03，使用 reprex v2.0.2}

---

可重现格式的问题数据框

df <- structure(list(Origin = c("A", "A", "A", "A", "B", "B", "C", 
"D", "D", "E"), Destination = c("B", "C", "D", "E", "A", "D", 
"A", "A", "B", "A"), `Travel Time` = c(10L, 20L, 10L, 30L, 10L, 
5L, 20L, 10L, 5L, 30L)), class = "data.frame", row.names = c("1", 
"2", "3", "4", "5", "6", "7", "8", "9", "10"))