运输优化技术.ppt

现代物流与物流中心规划,第三章 运输优化技术,modern logistics and logistics centers planning,本章要点,运输的主体和客体 运输线路选择与优化 运输流量优化 车辆装载优化,运输的主体（实施运输的组织）： （从事运输的）企业 （从事运输的）部门 （从事运输的）人员 运输的客体（运输的对象）： 为客户运输的产品,运输的主体和客体,运输线路的选择和优化,3.1.1 单一起迄点的运输线路优化问题 3.1.2 运输问题,3.1.1 单一起迄点的运输线路优化问题,在一个交通网络中，寻找由出发点到目的地的最短路线问题。,单行线交通网络，求v1到v8的最短路线,这还用问？,最短路的求解方法？ 当然是：dijkstra算法,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法轻松搞定,dijkstra算法非常适合使用计算机进行求解。,地球人都知道,仅考虑最短距离， 而不考虑运行时间？,晕!,3.1.2 运输问题,平衡运输问题 不平衡运输问题,3.1.2 运输问题平衡运输问题,算例：某玻璃制造厂与三个不同地点的纯碱供应商签订合同，由他们供货给三个分厂，条件是不超过合同所定的数量，但必须满足生产需要。该问题如表3-1所示。问题中所给费率是每个供应商到每个工厂之间最短路径的运输费率。求运输方案,3.1.2 运输问题平衡运输问题,3-1运输问题供需情况,供销平衡,3.1.2 运输问题平衡运输问题,3-1运输问题运输成本,3.1.2 运输问题平衡运输问题,求解算法表上作业法,3.1.2 运输问题平衡运输问题,表上作业法非常适合大脑中有两块 p4-cpu的人: (1):展示自己非凡的计算才能 (2):体验当年的工作艰辛,准备好笔、橡皮和纸吧,准备开始讲求解算法？ 麻 烦！,你确认你的cpu是p4的么？,求解算法数学软件包,工欲善其事，必先利其器,lingo,lingo: linear interactive general optimizer,lingo 给我们带来了什么？,大家下课后认真思考,采用lingo求解运输问题需要准备什么？,构造好明确的数学模型 将数学模型按照指定的语法规范输入软件,供销平衡情况,就是这么简单,3.1.2 运输问题不平衡运输问题,供大于需 需大于供,表上作业法需要设立虚拟库存，将该问题转化成为一个平衡运输问题求解 lingo软件法需要修改供需约束的不等号，再进行求解,3.1.2 运输问题不平衡运输问题,产量为6+4+6=16，销量为2+2+3+5=12。产量比销量多4。从供需平衡看，需要虚拟库存,不平衡运输的例子：,3.1.2 运输问题不平衡运输问题,3.1.2 运输问题不平衡运输问题,表上作业法的思路：转化成为一个平衡问题 例如：,产地1存储1，产地2存储1，产地3存储2，此时平衡,3.1.2 运输问题不平衡运输问题,lingo作业法的思路：修改对应的供需约束条件 例如：,3.1.2 运输问题不平衡运输问题,强！,运输问题搞定,3.1.2 运输问题不平衡运输问题,如果用lingo求解最短路线问题如何？,（该部分仅做了解，不作为考试的考察内容）,当然可以！,如果用lingo求解最短路线问题如何？,单行线交通网络，求v1到v8的最短路线,如果用lingo求解最短路线问题如何？,为了寻找网络的最短路线距离，我们将使用下面的动态规划递归式：,f(i)是从节点i到终点的最短距离，d(i,j)是从节点i到节点j的距离。 具体说：从节点i到终点的最短距离是从节点i到临接点的距离加上邻接点的终点的最小距离之和的最小值,用lingo求解最短路线问题的计算结果,从v1到v8的最短距离f(1)12，对应的路径可以对应找出,lingo求解最短路线问题,很强！,lingo能整的东西还挺多,运输流量优化,3.2.1 最大运输流量问题 3.2.2 最小费用最大流问题,最大运输流量问题,如下图所示，连接煤产地v1（发点）到销地v6（收点）的交通网络，v2、v3、v5表示交通网络的中间节点，每条运输线（弧）上的数字表示这条线的单位时间最大通过能力（称弧的容量），现在要制订一个运输方案，使单位时间从发点v1到点v6煤的运输量最多？,可行流的网络,2：最大流 所谓最大流就是在有容量限制的网络中流量最大的可行流。 最大流问题应用很广泛： 运输系统中的车辆流、物资流； 通讯系统中的信息流； 供水系统中的水流； 供电系统中的电； 金融系统中的资金流； 供销系统中的商品流都有最大流问题的足迹。,涉猎广泛,求最大流的方法,标号法 lingo软件求解法,还用lingo？,标号法思路,第一个初始可行解如何给出？,最简单的办法是每条弧上的流量都为零 优点：简单 缺点：可能会增加调整次数,增广链及流的调整法,前向弧、后向弧以及增广链的概念,用标号法找出网络中的最大流,给出初始可行流：,第一次流量调整就完成了,累！,继续讲,接下来，再在新的可行流基础上，从发点开始重新标号找增广链并对此调整，直至找不到增广链，即找到最大流为止,第二次寻找增广链寻找过程,第二次寻找增广链流量调整,第三次寻找增广链寻找过程,第三次寻找增广链流量调整,第四次寻找增广链寻找过程,终于完成了！,看lingo轻松搞定,lingo的必须构造好明确的数学模型,目标函数：路段上流量最大 约束条件：（可行流的满足条件）,easy！,真能整,多个发点和收点的运输流量问题,问题： 在运输流量问题中，可能同时存在多个发点可以供应某种物资，也可能多个收点需要这种物资。,多个发点和收点的运输流量问题,解决方式： 将问题转化成为只有一个收点和一个发点的网络最大流问题，运用相关方法求解,最小费用最大流问题,问题的提出： 在实际的物流运作过程中，不仅要考虑容量限制下的流量问题，而且还要求考虑费用问题。 例如：某公司欲将产品从工厂运到仓库，虽然可以在许多运输线路中选择，在不同的路线上，运费是不同的，而每条路线只能负担有限的货物运输量。如何找到运费最小的货物运输方式，并尽可能多地运输产品。 这就构成了所谓的：最小费用，最大流问题。,赋权图法对问题进行求解,求解最小费用流的算法很多，其中易于理解的一种流行算法是用最短路算法求最小费用的增广链。 算法思路： （1）从零流开始，在始点到终点的所有可能增加流量的增广链中寻找总费用最小的的链，并对该链增加流量，得到第一次调整后的最小费用流。 （2