基于floyd算法的供应链网络路径研究.docx

基于Floyd算法的供应链网络路径研究邬跃，楼振凯（北京物资学院研究生部，北京市，101149）摘要：21世纪的竞争不是企业与企业之间的竞争，而是供应链之间的竞争。运输系统是供应链中一个重要的子系统，运输路径的选择是否合理直接影响供应链的运作成本、速度和效益。本文考虑在拉动式生产的背景下，当销售商提出需求订单的时候，最快的选择相应的制造商和配送中心，使得供应链的总运输成本最小化的问题，利用floyd算法研究三级供应链的运作模式，理论证明其可行性，并通过算例分析验证了此优化算法使得供应链运输成本最小化。关键词：拉动式生产；运输成本；floyd算法；三级供应链中图分类号：F253 文献标志码：A0 引言随着供应链的一体化发展，如今的供应链网络结构已经不是单一、平行的结构，而是多制造商、多配送中心和多销售商的复杂交错的结构。由于运输费用占企业物流总费用的近一半，所以如何选择从制造商到销售商的运输路径直接影响供应链的物流成本。本文研究三级供应链的最小运输费用的路径选择问题，在拉动式生产的前提下，某一销售商获取用户需求信息后，基于运输总成本最小化的目的，即时选择合适的制造商和配送中心。目前研究网络路径优化模型的文献中，张旭凤等【1】将正向物流配送和逆向物流配送路线与运输能力进行整合，运用动态规划算法研究闭环配送网络中的最优路线问题。池洁等【2】将配送区域的划分转化成最小支撑树问题，并根据动态规划原理，对配送过程中路线的选择给出动态规划解法，从而制定合理的配送路线方案。郭晓娟【5】对四级供应链进行了研究，通过建立模型对备选的供应商、制造商和配送中心进行选择，同时给供应商、制造商、配送中心和客户四个节点分配流量，从而达到节省成本的目的。上述文献中，对供应链运输策略的研究涉及较少，而且动态规划算法不能同时给出多源头多末端网络的最优策略。为了给出任一销售商订货的最小运输成本策略，本文将此供应链网络求解模型转化成所有点之间的最短路问题，通过floyd算法进行求解。1 三级供应链网络模型本文三级供应链网络模型中包括制造商、配送中心和销售商，不妨设第一级为制造商，第二级为配送中心，第三级为销售商，其中制造商有k个，配送中心有m个，销售商有n个。供应链的各级传递关系如图1所示：12.........m图1 供应链传递关系图本文对于供应链网络路径的选择是基于运输成本最小化的目的，而对于网络中任何两个相邻节点来说，其距离固定不变，所以运输费用可以看成与距离成正比，故运输费用可以作为每条边的权。不难看出，对于任意一个销售商来说，其订货路径的选择有km种，如果运用动态规划算法进行顺序或逆序求最优路径，则需要k次计算方能比较得出最佳策略。对于n个销售商，从供应链的角度则需要进行kn次运算。运用floyd算法的优势在于，通过一次矩阵运算，即能得出n个销售商需求的最佳路线选择。2 建立数学模型本文的假设如下：（1）运输费用与订单大小无关；（2）各制造商供应能力相等且无限制；（3）配送中心容量无限制；（4）不考虑生产、配货的时间因素；（5）同级节点间不连通。按照floyd算法规则分别对网络中各节点编号，k个制造商分别对应1到k，m个配送中心编为k+1到k+m，n个销售商对应k+m+1到k+m+n，确定初始矩阵D0，如果其中两点i和j横向相邻，则矩阵中（i,j）元素的值为dij=w（i,j），否则令dij=+∞，且令dii=0。由假设（5）可知dij=+∞，分别当i,j取[1,k],[k+1,k+m]和[k+m+1,k+m+n]区间内的整数对时。对于N=1,2,…,k+m+n,依次由DN-1的元素确定DN，并利用递归公式：要确定运输费用最小的路径，也就是选择合适的制造商和配送中心。用上述方法每确定一个元素时，就记下它走过的轨迹，当算法终止时，矩阵Dk+m+n的元素（i,j）就表示从点i到点j的最短路径的长度。初始矩阵表示如下：1 2 ... k k+1 ... k+m k+m+1...k+m+n 12...k+m+n 对矩阵中的取值做一定说明。由算法规则可知，对角线上k+m+n个元素为0。显然，横坐标和纵坐标分别在[1,k]和[k+m+1,k+m+n]区间的元素值取+∞。又因三级供应链的方向性，故横坐标大于纵坐标的元素取+∞。3 算例分析 为了验证上述算法的可行性，本文引入具体数值进行计算。设制造商的数量为3个，分别用I，II和III表示。配送中心对商品有流通加工和分货配货的职能，设配送中心的数量为2个，用A、B来表示。销售商往往比配送中心数量多，设销售商的数量为3个，用甲、乙、丙来表示。网络关系图如下所示，运输费用即每条边的正向权，单位万元。3 32255 22443 5图2 供应链赋权网络图上文已经对每个节点进行编号，赋权之后接下来就是算法进行矩阵计算