返回

物流路径规划机理模型

模型

发布时间:2019/08/28 20:07

标签:

摘要:物流路径规划是制造企业规划中的一个重要单元,主要可分为区域物流路径规划和工厂内物流路径规划。

物流路径规划机理模型

物流路径规划是制造企业规划中的一个重要单元,主要可分为区域物流路径规划和工厂内物流路径规划。

针对地区间物流规划,常用的规划方法原理及建模方法有:1、物流需求预测法:将物流相关货运流量预测融合进传统交通需求预测过程;2、物流需求增长因子法:主要根据历史物流情况或经济活动的变化预测物流的需求变化;3、物流设施地点选择法:假定建立物流设施,分析其对周围甚至整个区域经济、交通的影响,以及设施本身从周围经济、交通环境受益情况。

针对工厂内物流路径规划,可采用petri 网模型,研究物流系统通畅性,通过结合排队理论和遗传算法等各类算法,分别计算出工序物流和工艺物流的最小物流量,得出局部或整体优化方案。经典物流路径规划方法最短路径法旨在寻找图(由结点和路径组成的)中两结点之间的最短路径,解决最短路的问题有以下算法,Dijkstra 算法,Bellman-Ford 算法,Floyd 算法和SPFA算法等。同时,通过引入物流需求预测,可更大程度优化物流路径的规划。如装配型企业生产过程中,为使物流总成本最小,引入后道工序拉动前道工序生产的拉式生产思想,这种需求拉动式生产模式可改善企业加工浪费和库存浪费,使企业的生产模式由粗放式生产向精益生产转变。

Dijkstra算法是1959年提出的一个适合于所有边的权限均为非负值的最短路径算法,也是众多可以求解最短路径问题的经典算法之一。Dijkstra算法适用于单源最短路径规划问题,即从一个点开始到所有其他点的路径。Dijkstra算法的基本原理:每次扩展一个新点(该新点到起始点距离为最短),然后计算该新点到其相邻各点的距离。

当所有的边权值都为正时,因为图中不会存在一个未经扩展的到起始点距离更短的点,所以这个点到起始点的距离将被固定,因而确保了算法的正确性。据此原理,用Dijkstra 算法求最短路径的图中不允许存在负权值的边, 若图中存在负权值的边, 则当算法扩展到负权边的时候会产生更短的到起始点的距离, 已经更新的点到起始点的距离被固定的性质就会遭到破坏。其适用条件包括有向图和无向图,无向图的每条边可以看成相反的两条边。

Bellman—Ford算法,是一种用来解决带权图中单源最短路径问题的简洁算法。与Dijkstra算法相比,这种算法的复杂度较大。然而,在精确信息未知情况下,需要进行实时动态的路径规划时,Bellman—Ford算法又呈现出其它算法所不具有的优点,迭代次数少,迭代过程灵活,可以进行异步、实时、分布式的规划,当威胁概率发生变化时,不需要终止和重启算法,只需更新带权图G一(V,E)的各边的权即可。在利用Bellman—Ford算法进行路径规划时,做出以下两点假设:①规划目标点为结点1;②从给定结点i到目标点1的最短路径至多包含h条边,且只经过目标点1一次。


Floyd算法是典型的多源最短路径算法,又称为插点法,是一种用于寻找给定的加权图中多源点之间最短路径的算法。主要特点是需要用邻接矩阵来储存边,并通过考虑最佳子路径来得到最佳路径。Floyd算法是一个基于动态规划的算法,动态规划是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。经分解得到子问题往往不是互相独立的,而是相互影响的。

Floyd的算法逻辑为动态规划算法,动态规划不仅可以得到原问题的最优解,还可以得到各个子问题的解,它存在回溯的过程,因此它可用来计算负权图,但不能计算负权回路。Floyd算法是一种动态算法,这就使得它的学习难度比较大,并且它所能解决的问题规模都比较大,如应用到某个城市的规划建设中等大问题。

SPFA算法采用动态逼近法,通过控制顶点的松弛顺序来优化Bellman-Ford 算法.在Bellman-Ford 算法中,松弛过的顶点顺序会影响之后顶点的松弛顺序, 只有那些在上一次松弛中改变了最短路径估计值的顶点, 才可能引起与该顶点相邻的顶点最短路径估计值发生改变.因此,用一个先进先出的队列来保存被松弛过的顶点, 之后只处理队列中的顶点,以此来降低算法的时间复杂度。

SPFA 算法的具体步骤如下:

(1)初始化,将源点加入队列;

(2)进行迭代,每次取得队列的队首节点,将所有与队首节点相邻的顶点进行松弛操作,若松弛成功,则查看进行松弛操作的顶点是否在队列中,若不在将该顶点加入队列中;

(3)反复从队列里取出点来对当前最短路径进行优化,直至队列为空不需要再优化为止。