Flexsim实现Dijkstra最短路径算法

第一次接触最短路径算法是2012年去沈阳做项目,当时使用网络节点模拟AGV地图。学习最短路径算法,可以帮助建模工程师全部掌握中间经过的所有节点信息,这是实现复杂任务逻辑或交通管制逻辑的基础。

感谢【火星十一郎】博客上的一篇关于最短路径算法的介绍,科普和入门的大家可以前往查阅。受他恩惠,现在我重新写一篇使用flexsim的实现方法。

 使用UserCommands 工具自定义一个 cmd_dijkstra 方法,这个方法用来计算 AGV模块地图中任意一个控制点begin到另一控制点end的最短路径。参数1、2传入控制点对象的引用即可,方法代码如下:

var begin = param(1);
var end = param(2);
#define UNREACHABLE 1000000
if (!objectexists(begin) || !objectexists(end))
 return "unreachable";
if (!isclasstype(begin, "AGV::ControlPoint") || !isclasstype(end, "AGV::ControlPoint"))
 return "unreachable";
pt("初始化图:");pr();
Variant pathList = "";
Variant distList = 0;
Variant vList = begin;
Variant T = begin;
forobjecttreeunder(model()) {
 if(isclasstype(a, "AGV::ControlPoint") && vList.indexOf(a)<0) {
  double dist = cmd_cpdistance(begin,a);
  distList.push(dist);
  pathList.push(getname(begin)+"-->"+getname(a));//path
  vList.push(a);
 if(dist >= UNREACHABLE)
 { pt(pathList[pathList.length]+" =unreachable");pr();}
 else
 { pt(pathList[pathList.length]+" ="+numtostring(dist,0,2));pr();}
 }
}
pr();pt("松弛:");pr();

while(true) {
 int indexMin = 0;
 double distMin = UNREACHABLE;
 for(int i=1;i<=distList.length;i++) {
  if(T.indexOf(vList[i])<0 && distList[i]<distMin) {
   distMin = distList[i];
   indexMin = i;
  }
}
if(indexMin<=0) break; //If none element has been find then break
T.push(vList[indexMin]);
for(int i=1;i<=distList.length;i++) {
 double dist = cmd_cpdistance(vList[indexMin],vList[i]);
 if(T.indexOf(vList[i])<0 && distList[indexMin] + dist < distList[i]) {
  distList[i] = distList[indexMin] + dist;
  pt(pathList[i]+" 变更为 ");
  pathList[i] = pathList[indexMin] + "-->" + getname(vList[i]);
  pt(pathList[i]);pr(); 
  }
 }
}

return T.indexOf(end)<0?"unreachable":pathList[vList.indexOf(end)];

现在,从模型库中随便拉一些path路径对象,并随机建摆上一些控制点,得到如下一个AGV地图:

使用上面封装的函数cmd_dijkstra(cp_start,cp_end),再使用model().find 函数随机选择起点和终点控制点,运行:

return cmd_dijkstra(model().find("ControlPoint24"),model().find("ControlPoint18"));

在控制台中获得结果如下:

初始化图: ControlPoint24-->ControlPoint3 =2.70 
ControlPoint24-->ControlPoint4 =unreachable 
ControlPoint24-->ControlPoint5 =unreachable 
ControlPoint24-->ControlPoint6 =unreachable 
ControlPoint24-->ControlPoint7 =unreachable 
ControlPoint24-->ControlPoint8 =unreachable ... 松弛: 
ControlPoint24-->ControlPoint25 变更为 
ControlPoint24-->ControlPoint3-->ControlPoint25 
ControlPoint24-->ControlPoint4 变更为 
ControlPoint24-->ControlPoint3-->ControlPoint25-->ControlPoint4 
ControlPoint24-->ControlPoint13 变更为 
ControlPoint24-->ControlPoint3-->ControlPoint25-->ControlPoint13 ...

最终的输出内容是:
“ControlPoint24-->ControlPoint3-->ControlPoint25-->ControlPoint4-->ControlPoint5-->ControlPoint11-->ControlPoint18”

总结设计思路:
①初始化队列 distList; 用来存储begin到其它各顶点的直接距离。
②初始化队列 pathList; 用来存储begin到其他各顶点的路径信息。
③初始化队列 vList; 用来存放所有未遍历过的顶点对象。
④初始化队列 T; 用来存放已经遍历过的顶点对象。
⑤初始化图,遍历模型中的所有顶点并初始化distList、pathList和vList。
⑥完成初始化后,遍历vList队列,对begin至各顶点之间的距离进行“松弛”,然后放入T队列(避免重复计算)。
⑦完成松弛后,begin对所有顶点的距离结果存储在distList中,路径信息存储在pathList中。
⑧查询end对象,如果不存在于T队列中,则无法到达。若存在,则查询pathList、distList就可以获得他们的路径和距离。
Dijkstra算法最核心的思路是对图G进行“松弛”。
如果有需要模型的请私信我。


2020-3-26 更新:

关于代码中 cmd_cpdistance()方法的介绍,我们先看上面代码第15行

  double dist = cmd_cpdistance(begin,a);

这里在构图的时候,把从begin开始能够到达的控制点加入List,若不能直接到达的控制点则不能放入。所以这方法兼具两条目的:①求出两个控制点的距离,②判断两个控制点是否是直接到达关系,看看实现方法:

var cp1 = param(1);
var cp2 = param(2);
 
#define GLOBAL_UNREACHABLE 100000000000
 
double cmd_cpdistance(var cp1, var cp2) {
 
if (!objectexists(cp1) || !objectexists(cp2))
 return GLOBAL_UNREACHABLE;
if (!isclasstype(cp1, "AGV::ControlPoint") || !isclasstype(cp2, "AGV::ControlPoint"))
 return GLOBAL_UNREACHABLE;
  
//原理: 假设cp1与cp2的最短距离 dist0
//假设cp1与cp2之间存在任意一个cpi, 其中 cp1-cpi -> dist1,  cpi-cp2 -> dist2
//如果dist0 是 dist1 和 dist2 的总和,则cpi是cp1与cp2路径中的点
//即:证明cp1与cp2最短距离中存在cpi,也就是说cp1与cp2非相邻关系,返回GLOBAL_UNREACHABLE
 
double dist0 = cpdistance(cp1,cp2);
forobjecttreeunder(model()) {
 if(isclasstype(a, "AGV::ControlPoint") && a!= cp1 && a!=cp2) {
  double dist1 = cpdistance(cp1,a);
  double dist2 = cpdistance(a,cp2);
  if(fabs(dist1 + dist2 - dist0) <0.000001)
  {
   return GLOBAL_UNREACHABLE;
  }
 }
}
return dist0;
}

如果不加这个方法的限制,直接用cpdistance方法构图,则运行结果会是如下(另一个地图):

初始化图:
ControlPoint18-->ControlPoint3 =19.75
ControlPoint18-->ControlPoint4 =7.69
ControlPoint18-->ControlPoint5 =12.67
ControlPoint18-->ControlPoint6 =15.49
ControlPoint18-->ControlPoint7 =16.93
ControlPoint18-->ControlPoint8 =13.99
ControlPoint18-->ControlPoint9 =7.83
ControlPoint18-->ControlPoint10 =9.46
ControlPoint18-->ControlPoint11 =13.84
ControlPoint18-->ControlPoint12 =16.08
ControlPoint18-->ControlPoint13 =18.51
ControlPoint18-->ControlPoint15 =19.23
ControlPoint18-->ControlPoint16 =19.42
ControlPoint18-->ControlPoint17 =17.92
ControlPoint18-->ControlPoint19 =22.56

松弛:

可以看到 模型中CP18一开始加入list的元素基本上是全部节点,这样就不能满足算法的需求了。

另外再补充一点:本文演示了用flexsim实现dijkstra算法,构图的选择上使用了比较容易的AGV地图,所以在判断节点与节点关系时不得不采用遍历的方式约束,这会导致效率降低,如果仍然使用这种方法,建议给控制点加入连线,通过连线判断是否直连,而不是遍历。

One thought on “Flexsim实现Dijkstra最短路径算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

4 × 5 =