|
|
摘要:Dijkstra(迪科斯彻)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径,其主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
Dijkstra算法是很有代表性的最短路径算法。文章研究了叉车在仓储作业选择最优路径的问题,主要根据仓储巷道交通网络数据,建立数学模型,确定叉车仓储作业的最优路径,并且对模型的优缺点进行分析,提出改进方法,以更好地研究叉车仓储作业的最优路径选择问题。
本研究选出在仓储巷道作业车辆从起点到终点的最优路径。
结果表明,Dijkstra算法能够计算出车辆作业的最优线路,对现场的司机指导、工作效率提高提供了很好的支持。
引言
Dijkstra算法是典型最短路径算法,用于计算一个结点到其他结点的最短路径:。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)直到扩展到终点为止。本文通过Diikstra算法及优化研究了叉车在仓储作业选择最优路径的问题。
1 叉车仓储作业路径选择
目前,仓储又车在复杂的作业环境下,寻找一条可靠、快速、安全的最优路径,能够有效地提升作业效率。本研究通过对仓储内道路状况的收集及运用相关数据建立相应数学模型进行有效的分析,进而选择最优路径。
本研究采用Diikstra算法。该算法是目前交通网络图在单源最短路径问题上运用最普遍、完善的算法之一,也是公认在非负权值且所有的权大于等于零时,寻求最短路问题最好的算法。
本论文通过查找道路交通数据,运用 Diiksta算法、加权平均法的方法去解决出行路径的选择问题。
2 Diikstra 算法
2.1 算法特点
迪科斯彻算法使用广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到个最短路径树[]。该算法常用于路由算法或者作为其他图算法的一个子模块。
2.2 算法的思路
算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组。
第一组为以求出最短路径的顶点集合(用 S 表示,初始时 S 中只有一个源点,以后每求得一条最短路径,就将其加入集合 S,直到全部顶点都加入 S 中)。
第二组为其余未确定最短路径的顶点集合(用 U表示),按最短路径长度的递增次序依次把第二组顶点加入 S。 在加入的过程中,总保持从源点 v 到 S 中各顶点的最短路径长度不大于从源点 v 到 U 中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S 中的顶点的距离就是从 v 到此顶点的最短路径长度,U 中顶点的距离是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前最短路径长度。
(1) 初始时,S 只包含起点 s;U 包含除 s 外的其他顶点,且 U 中顶点的距离为“起点 s 到该顶点的距离”。 例如:U 中顶点 v 的距离(s,v)的长度,然后 s 和v 不相邻,则 v 的距离为正无穷。
(2) 从 U 中选出“距离最短的顶点 k”,并将顶点 k 加入 S;同时,从 U 中移除顶点 k。
(3) 更新 U 中各个顶点到起点 s 的距离。之所以更新 U 中顶点的距离,是由于上一步中确定了k 是求出最短路径的顶点,从而可以利用 k 来更新其他顶点的距离;例如 s,v) 的距离可能大于( s,k) +(k,v)的距离。
(4) 重复(2)和(3),直到遍历完所有顶点。
3 实现过程在仓库拣选过程中,是穿越巷道还是返回,以及拣选设备所处的位置是前通道、后通道还是中通道,决定了仓库拣选路径。
本文根据仓库巷是根据拣货设备与巷道中最远拣货点之间的距离来判断的,当拣货点与拣货设备之间的距离大于拣货巷道长度的一半时,穿越巷道;否则返回。
仓库布局如图 1 所示。
3. 1 深度优先搜索(DFS)首先实现对 Ai 所在连通子图的深度优先搜索,用递归算法实现以下几步基本过程
(1)深度优先遍历图的方法是,从图中某顶点 A1 出发。
(2) 依次以Ai 的未被访问的邻接点为出发点,对图进行深度优先遍历,直至图中所有与 Ai 有路径相通的顶点都被访问。
(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过。
(4)按深度优先搜索递归访问 A1 的某个未被访问的邻接点 A3、A4 中的某一个。 再访问顶点A3 的另一个邻接点 A5,再访问顶点 A5 的邻接点 A7、A8 中的某一个。 同时,结点 A2、A6 已经在深度优先搜索中直接筛除出列,进行该优化步骤能避免传统的Dijkstra 算法盲目取点搜索的缺陷,最终得到全部解子图。
仓库深度优先搜索如图 2 所示。
3. 2 广度优先搜索(BFS)对进行了深度优先搜索的起点 A1 到终点 A8 连通子图进行广度优先搜索。
广度优先搜索目的在于确定各结点在子图中的层次关系,步骤:
(1) 将起始顶点放入队列中。
(2)从队列首部选出一个顶点,并找出所有与之邻接的顶点,将找到的邻接顶点放入队列尾部,将已访问过顶点涂成黑色,没访问过的顶点是白色。
如果顶点的颜色是灰色,表示已经发现并且放入了队列,如果顶点的颜色是白色,表示还没有发现。
(3)按照同样的方法处理队列中的下一个顶点。对各结点做合理的分层安排,求解的所有结点分布在离起点最近的一层。
把所有可能的路径都搜索完后,输出记录的最优路径。
仓库广度优先搜索如图 3所示。
广度优先搜索先用最优分层排序法,确定各结点所在的层次,再确定各层结点间是否存在关联。
使用Dijkstra 算法求解最短路径时,根据各结点间的权值来判定最终选哪个结点作为下一个层次节点,而将各结点放置在离起点最近的层次。
该点若是在最终的最短路径线路上,那么很快会被找到,比它权值大的结点均可直接筛除出列。
3. 3 数据对象封装采用 Python 语言的面向对象的思想,创建结点、结点的相邻边、结点的相邻结点、起点到该结点的最短路径长度等多种信息。
用递归方法设计好,它可以使得程序结构更简捷易懂。
实现深度优先搜索法占内存少但速度较慢,搜索时则会遍历所有的结点,因为每次遍历时间复杂度都是以指数的形式增长的,易超时。
结合广度优先搜索算法占内存多但速度较快,在距离和深度成正比的情况下能较快地求出最优解。
相邻节点处理逻辑如图 4 所示。
…………
以上贴子只是内容提要，完整祥细的内容在下面附件中，请下载后阅读：
|
|
发表于 2024-8-21 17:25:00
