【独家发布】用igraph包做有时限条件的路径分析

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

这个问题是前几天论坛wushibuzhi同学提出来的（ https://bbs.pinggu.org/thread-10540615-1-1.html ）本来可以直接回复他，后来考虑内容比较多，而且为更方便其他同学利用，因此这里新开一贴。

问题：计算从A到Z之间的最优时效路径

为此做了一个示例数据，如下：

本帖隐藏的内容

netE.rar (190 Bytes) 本附件包括：

• netE.csv

2021-4-9 09:27:35 上传

csv格式示例数据

1. #读入数据
   
2. edges <- read.csv("netE.csv", header=T,stringsAsFactors = FALSE)
   
3. 
   
4. #不考虑时间约束的网络图
   
5. net_g <- graph_from_data_frame(d = edges[,-3], directed = TRUE)
   
6. 
   
7. l1 <- layout_on_grid(net_g)
   
8. plot(net_g,
   
9. vertex.size = 24,
   
10. vertex.label.cex = 1.2,
    
11. vertex.label.dist = 3,
    
12. edge.color = "tomato",
    
13. edge.arrow.size = 0.3,
    
14. layout = l1
    
15. )

复制代码

不考虑时间约束的网络图


使问题复杂化的是，从一个节点到下一个节点的行程时间如果超过下一个节点的出发时间，需要等一天，也就是相应的形成时间增加24小时，导致上面这个网络里的每条边的耗时是不确定的。

思路是这样的，针对有向网络，如果A出发可以去n个节点，比如可以去B，也可以去C，则将A拆成n个，A1去节点B，A2去节点C;其他节点同样处理，比如B1可以去C，B2可以去D。节点拆分后，edge也增加了，比如A1-B1, A1-B2 。这样处理后，我们就可以根据约束条件计算每一条edge的耗时，或者是标准时间，或者是标准时间+24 。然后即可以用igraph生成网络，并计算节点之间的最短路径。

1. #考虑时间约束
   
2. edges <- edges %>% arrange(from,to)
   
3. branches <- table(edges[,1])
   
4. f<-levels(as.factor(edges[,1]))
   
5. 
   
6. #调整from
   
7. nf<-NULL
   
8. for (i in 1:length(f)) {nf<-append(nf,paste(f[i],1:branches[f[i]],sep=""))}
   
9. edges[,1]<-nf
   
10. 
    
11. #调整to
    
12. nedge<- data.frame()
    
13. 
    
14. for (j in 1:dim(edges)[1]) {
    
15.   if (edges[j,2]!="E"){
    
16.   tmp<-NULL
    
17.   k=1
    
18.   repeat {
    
19.     tmp<-rbind(tmp,edges[j,])
    
20.     k=k+1
    
21.     if (k>branches[edges[j,2]]) break
    
22.   }
    
23.   tmp[,2]<-paste(edges[j,2],1:branches[edges[j,2]],sep="")
    
24.   nedge <- rbind(nedge,tmp)
    
25.   }
    
26.   else
    
27.     nedge <- rbind(nedge,edges[j,])
    
28. }
    
29. 
    
30. #调整weight
    
31. 
    
32. nedge[,3]<-parse_date_time(nedge[,3],"%H:%M",exact = TRUE)
    
33. for (i in 1:dim(nedge)[1]) {
    
34.   if (nedge[i, 2] != "E") {
    
35.     if (nedge[i, 3] + 3600 * nedge[i, 4] >= (nedge[which(nedge[, 1] == nedge[i, 2]), ])[1, 3])
    
36.       nedge[i, 4] <- nedge[i, 4] + 24
    
37.   }
    
38. }
    
39. 
    
40. 
    
41. #增加A
    
42. nedge<-nedge[,-3]
    
43. nedge<-rbind(nedge,data.frame(from=rep("A",branches["A"]),to=paste("A",1:branches["A"],sep=""),weight=rep(0,4)))
    
44. 
    
45. 
    
46. #调整后的网络
    
47. net_n <- graph_from_data_frame(d = nedge,directed = TRUE)
    
48. 
    
49. l2 <- layout_on_grid(net_n)
    
50. plot(net_n,
    
51. vertex.size = 24,
    
52. vertex.label.cex = 1.2,
    
53. vertex.label.dist = 3,
    
54. edge.color = "tomato",
    
55. edge.arrow.size = 0.3,
    
56. layout = l2
    
57. )

复制代码

调整后的网络图如下：



经过上述调整，我们可以计算最短路径

1. shortest_paths(net_n,"A","E")[[1]]
   
2. #最优路径的结果如下
   
3. #[1] A  A2 C1 D1 E  
   
4. 
   
5. #解读为ACDE是耗时最短的方案
   
6. 
   
7. shortest.paths(net_n,"A","E") #计算该路径的最短耗时
   
8. 
   
9. #3.5
   
10. 
    
11. shortest.paths(net_n) #生成每个节点之间的最短耗时矩阵

复制代码

提醒：
1、上述网络是有向的；
2、上述代码只计算了从A到E的路径，计算其他区间点，需要对代码略作调整；

3、这种方式的缺点是，如果节点太多，可能会极大地增加计算量。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：GRAPH GRAP 路径分析 APH RAP 网络路径优化

上述代码使用的包
library(dplyr)
library(lubridate)
library(igraph)

支持一下，周末可以学习。

owenqi 发表于 2021-4-9 13:06
支持一下，周末可以学习。

特殊问题，不具普遍性