物流运输线路规划PPT课件

1、运输与配送的线路规划,合理的运行路线和时间安排原则 点点间运输最短路径求解方法 多点间运输运输算法,.,2,案例1,伊万斯维尔地方学区为小学生提供校车服务。如图所示，现有一辆校车被分派到该地区。已知每年学生的新名册，接送学生的停车点位置在地图上标出。对各站点进行排序以确定校车每次行驶所需的时间和距离。利用你最佳的感知技巧设计满足下列条件的最短路径： 经过所有停车点。 孩子们可以在街道的任何一边上下车。 住在临近街区的孩子可以在拐弯处上下车。 不允许转U形弯。 校车有足够空间，可以接送路上所有的学生。 借助尺子计算校车行驶的总距离。,.,3,校车路线制定练习,.,4,习题4答案,.,5,1.将相

2、互接近的停留点的货物装在一辆车上运送 2.将集聚在一起的停留点安排同一天送货 3.运行路线从离仓库最远的停留点开始。 4.一辆运货车顺次途经各停留点的路线要成泪滴状。 5. 尽可能使用最大的车辆进行运送。 6. 取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。 7.对偏离集聚停留点路线远的单独的停留点可应用另一个送货方案。 8.应当避免停留点工作时间太短的约束。,一. 合理的运行路线和时间安排原则,.,6,1.将相互接近的停留点的货物装在一辆车上运送,仓库差的串联 仓库更好的串联,车辆将停留点串起来的示意图,.,7,2.将集聚在一起的停留点安排同一天送货,不合理的路线交叉划分方式

3、较合理的线路划分方式 一周各天停留点群的划分,.,8,3.运行路线从离仓库最远的停留点开始。,首先应划分出离仓库最远的停留点集聚区。 选定距该核心停留点最近的一些停留点形成停留点集聚区，分派载货能力能满足该停留点集聚区需要的卡车。 从还没有分派车辆的其他停留点中找出距仓库最远的站点，分派另一车辆。,.,9,4.一辆运货车顺次途经各停留点的路线要成泪滴状。,根据经验，当运行路线不发生交叉时，经过各停留点的次序是合理的，同时，应尽量使运行路线形成泪滴状。,.,10,运输路线示意图,不好的线路规划线路交叉 好的线路规划线路不交叉,.,11,例安休瑟布喜公司(AnheuserBusch Company

4、)利用售货员通过流动卡车销售啤酒和其它饮料，卡车由当地经销人员所有。公司售货员同当地经销人员一样都是收取佣金，因而都不希望每天向各客户提供服务时花费不必要的时间，行走多余的路程。他们将图钉固定在地图上，以确定某推销员现有客户的位置。图中所举的是一个20个客户的例子，客户点的信息已经被转换到网格地图上，图中的坐标与距离相关。我们要找出的是，卡车从仓库出发，经过所有的客户点，再回到仓库，这个运行过程中距离最短的路径。,.,12,建议的路径,用软件ROUTE的计算结果。整个行程的总成本为37.59距离单位。,.,13,比例尺：15英里 珠宝推销员问题中客户(X)和汽车旅馆(Y)的位置,习题,丹帕普(

5、Dan Pupp)是个珠宝推销员，他需要走访中西部的店铺。图中列出了他负责的某个销售区域。他的工作方式是在走访的前一天晚上来到这个地区，住在当地的汽车旅馆里，花两天时间走访这个地区，随后在第三天早上离开。由于是自己付费，他希望总成本能够最小。第一天要走访第1至第9位客户，第二天走访其余的客户。他有两个方案可供比较。 方案1：三晚都住在汽车旅馆M2中，住宿费是每晚49.00美元。 方案2：前两晚都住在汽车旅馆M1中，走访客户l至9，住宿费为每晚40.00美元。随后，搬到汽车旅馆M3住一晚，走访客户10至18，住宿费是每晚45.00美元。在走访客户l至9后，推销员回到M1，在此过夜。随后，搬到M3

6、，过夜并于次日早晨离开。M1和M3相距36英里。不管丹在这个地区的什么地方，旅行成本都是0.30美元英里。 哪个方案对丹最好?,.,14,答案 方案1,路线停留点顺序 距离 8 6 4 1 2 3 5 7 9 95.40 10 13 14 17 18 16 12 15 11 86.46 线路总长度（英里） 181.86,方案1的总成本为： 住宿费： 493 147 美元 旅行费用：181.860.30 54.56美元 总成本： 201.56美元,.,15,答案 方案2,路线停留点顺序 距离 2 3 5 7 9 8 6 4 1 95.40 18 17 13 14 10 11 15 12 16 8

7、0.30 M1与M3距离 36 线路总长度（英里） 211.70,方案1的总成本为： 住宿费： 40 + 40 + 45 125 美元 旅行费用：211.700.30 63.51美元 总成本： 188.51美元,采用第二种方案最好,.,16,二. 点点间运输最短路径求解方法 （配送货物由一个配送中心直达某客户）,最短路问题的含义 最短路问题的基本原型 求解最短路问题的算法,.,17,1.最短路问题的含义,连通图的最短路问题指求两个顶点间长度最短的路径。,对最短路径问题的描述如下： 假设有一n个节点和m条弧的连通图G(Vn，Em)，并且图中的每条弧（i，j）都有一个长度cij（或者费用cij），

8、则最短路径问题为：在连通图G中找到一条从节点1到节点n距离最短（或费用最低）的路径。,用数学方法表达是： 存在连通图G(Vn，Em)，且长度矩阵C= cij1in，1jn,目标函数：,.,18,2. 最短路问题的基本原型,对工程实际的研究和抽象，在最短路径问题中有3种基本原型： 连通图G(Vn，Em)中，从指定起始点到指定目的点之间的最短路径。 连通图G(Vn，Em)中，从指定起始点到其余所有节点之间的最短路径。 连通图G(Vn，Em)中，所有任意两点之间的最短路径。,.,19,3. 求解最短路问题的算法,Dijkstra算法 标号设定法、标号修正法 逐次逼近法 Floyd算法,.,20,5,

9、7,4,8,10,9,16,.,21,指起始点或目的点不唯一的运输调配问题。 多点间运输中最常见的问题是产销平衡问题。 设计的总供应能力和总需求是一样，但是由不同的路径进行配送时，会导致最终的总运输成本不一样，此类问题的目标就是寻找最低的总运输成本。,三. 多点间运输运输算法,.,22,有m个已知的供应点A=a1，a2，am，有n个已知的需求点B=b1，b2，bn，它们之间有一系列代表距离或成本的权重值cij连接起来。,数学模型： 条件变量： A：供应点的供应能力矩阵 B：需求点的需求矩阵 C：运输距离或成本矩阵 决策变量： xij=从ai到bj的发送量,.,23,目标函数,满足,.,24,多点间运输调配问题的求解方法,单纯形法 表上作业法（运输算法） 运用相关软件TRANLP(LOGWARE)求法,相对精确，但计算冗长，一般需借助计算机进行计算。,将运输问题用表格的形式来描述，求解过程方便直观，计算量不大，可用手工直接完成，适合于简单问题的求解。,.,25,例一制造商有三个工厂分别是1、2、3，且同时有三家供应商A、B、C。工厂1、2、3的需