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进行“松弛”。
如果有需要模型的请私信我。


发表评论

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

5 × 2 =