物流运输线路规划

（优质）物流运输线路规划PPT课件目前一页\总数二十四页\编于十三点案例1伊万斯维尔地方学区为小学生提供校车服务。如图所示，现有一辆校车被分派到该地区。已知每年学生的新名册，接送学生的停车点位置在地图上标出。对各站点进行排序以确定校车每次行驶所需的时间和距离。利用你最佳的感知技巧设计满足下列条件的最短路径：经过所有停车点。孩子们可以在街道的任何一边上下车。住在临近街区的孩子可以在拐弯处上下车。不允许转U形弯。校车有足够空间，可以接送路上所有的学生。借助尺子计算校车行驶的总距离。目前二页\总数二十四页\编于十三点校车路线制定练习123456789101112141315161718192021目前三页\总数二十四页\编于十三点习题4答案目前四页\总数二十四页\编于十三点1.将相互接近的停留点的货物装在一辆车上运送2.将集聚在一起的停留点安排同一天送货3.运行路线从离仓库最远的停留点开始。4.一辆运货车顺次途经各停留点的路线要成泪滴状。5.尽可能使用最大的车辆进行运送。6.取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。7.对偏离集聚停留点路线远的单独的停留点可应用另一个送货方案。8.应当避免停留点工作时间太短的约束。一.合理的运行路线和时间安排原则目前五页\总数二十四页\编于十三点1.将相互接近的停留点的货物装在一辆车上运送

仓库差的串联仓库更好的串联车辆将停留点串起来的示意图

DD仓库停留点仓库目前六页\总数二十四页\编于十三点2.将集聚在一起的停留点安排同一天送货

不合理的—路线交叉划分方式较合理的—线路划分方式一周各天停留点群的划分FFFFFFFTTTTTTTD仓库FFFFFTTTFTFTTTD仓库(a)(b)停留点目前七页\总数二十四页\编于十三点3.运行路线从离仓库最远的停留点开始。首先应划分出离仓库最远的停留点集聚区。选定距该核心停留点最近的一些停留点形成停留点集聚区，分派载货能力能满足该停留点集聚区需要的卡车。从还没有分派车辆的其他停留点中找出距仓库最远的站点，分派另一车辆。目前八页\总数二十四页\编于十三点4.一辆运货车顺次途经各停留点的路线要成泪滴状。根据经验，当运行路线不发生交叉时，经过各停留点的次序是合理的，同时，应尽量使运行路线形成泪滴状。目前九页\总数二十四页\编于十三点运输路线示意图

不好的线路规划—线路交叉

好的线路规划—线路不交叉

仓库

仓库

目前十页\总数二十四页\编于十三点［例］安休瑟—布喜公司(Anheuser—BuschCompany)利用售货员通过流动卡车销售啤酒和其它饮料，卡车由当地经销人员所有。公司售货员同当地经销人员一样都是收取佣金，因而都不希望每天向各客户提供服务时花费不必要的时间，行走多余的路程。他们将图钉固定在地图上，以确定某推销员现有客户的位置。图中所举的是一个20个客户的例子，客户点的信息已经被转换到网格地图上，图中的坐标与距离相关。我们要找出的是，卡车从仓库出发，经过所有的客户点，再回到仓库，这个运行过程中距离最短的路径。目前十一页\总数二十四页\编于十三点建议的路径

用软件ROUTE的计算结果。整个行程的总成本为37.59距离单位。

目前十二页\总数二十四页\编于十三点

比例尺：1＝5英里珠宝推销员问题中客户(X)和汽车旅馆(Y)的位置习题丹·帕普(DanPupp)是个珠宝推销员，他需要走访中西部的店铺。图中列出了他负责的某个销售区域。他的工作方式是在走访的前一天晚上来到这个地区，住在当地的汽车旅馆里，花两天时间走访这个地区，随后在第三天早上离开。由于是自己付费，他希望总成本能够最小。第一天要走访第1至第9位客户，第二天走访其余的客户。他有两个方案可供比较。方案1：三晚都住在汽车旅馆M2中，住宿费是每晚49.00美元。方案2：前两晚都住在汽车旅馆M1中，走访客户l至9，住宿费为每晚40.00美元。随后，搬到汽车旅馆M3住一晚，走访客户10至18，住宿费是每晚45.00美元。在走访客户l至9后，推销员回到M1，在此过夜。随后，搬到M3，过夜并于次日早晨离开。M1和M3相距36英里。不管丹在这个地区的什么地方，旅行成本都是0.30美元／英里。哪个方案对丹最好?目前十三页\总数二十四页\编于十三点答案方案1

路线停留点顺序距离

86412357995.4010131417181612151186.46线路总长度（英里）181.86方案1的总成本为：住宿费：49×3＝147美元旅行费用：181.86×0.30＝54.56美元总成本：201.56美元目前十四页\总数二十四页\编于十三点答案方案2

路线停留点顺序距离

23579864195.4018171314101115121680.30M1与M3距离36线路总长度（英里）211.70方案1的总成本为：住宿费：40+40+45＝125美元旅行费用：211.70×0.30＝63.51美元总成本：188.51美元采用第二种方案最好目前十五页\总数二十四页\编于十三点二.点点间运输——最短路径求解方法

（配送货物由一个配送中心直达某客户）最短路问题的含义最短路问题的基本原型求解最短路问题的算法目前十六页\总数二十四页\编于十三点1.最短路问题的含义连通图的最短路问题指求两个顶点间长度最短的路径。

对最短路径问题的描述如下：

假设有一n个节点和m条弧的连通图G(Vn，Em)，并且图中的每条弧（i，j）都有一个长度cij（或者费用cij），则最短路径问题为：在连通图G中找到一条从节点1到节点n距离最短（或费用最低）的路径。

用数学方法表达是：

存在连通图G(Vn，Em)，且长度矩阵C={cij│1≤i≤n，1≤j≤n│}

目标函数：sabcdeft9877456456574目前十七页\总数二十四页\编于十三点2.最短路问题的基本原型对工程实际的研究和抽象，在最短路径问题中有3种基本原型：连通图G(Vn，Em)中，从指定起始点到指定目的点之间的最短路径。连通图G(Vn，Em)中，从指定起始点到其余所有节点之间的最短路径。连通图G(Vn，Em)中，所有任意两点之间的最短路径。sabcdeft9877456456574目前十八页\总数二十四页\编于十三点3.求解最短路问题的算法Dijkstra算法

标号设定法、标号修正法逐次逼近法Floyd算法目前十九页\总数二十四页\编于十三点sabcdeft9877456456574574810916sabcdeft9877456456574目前二十页\总数二十四页\编于十三点指起始点或目的点不唯一的运输调配问题。多点间运输中最常见的问题是产销平衡问题。

设计的总供应能力和总需求是一样，但是由不同的路径进行配送时，会导致最终的总运输成本不一样，此类问题的目标就是寻找最低的总运输成本。三.

多点间运输——运输算法目前二十一页\总数二十四页\编于十三点有m个已知的供应点A={a1，a2，…，am}，有n个已知的需求点B={b1，b2，…，bn}，它们之间有一系列代表距离或成本的权重值cij连接起来。数学模型：条件变量：A：供应点的供应能力矩阵B：需求点的需求矩阵C：运输距离或成本矩阵决策变量：xij=从ai到bj的发送量a1a2amb1bncij供应点需求点……目前二十二页\总数二十四页\编于十三点目标函数满足a