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