CH运输决策PPT课件

1、物流决策的三角形 客户服务目标 产品 物流服务 信息系统运输战略：运输基础知识运输决策库存战略：预测仓储基础知识库存决策采购和供应决策仓储决策选址战略：选址决策网络规划流程第1页/共50页路线规划的三个基本类型P170 起止点不同的单一路径规划ROUTE 多个起止点的运输量规划TRANLP 起点和终点相同的路径规划ROUTESEQ 规划目的：既定客户服务水平下，运输成本最小化。要素：距离；时间 第2页/共50页起讫点不同的单一问题 P171 解决方法：最短路径法（Shortest Route Method） 最短路径法描述：已知一个由链和节点组成的网络，其中节点代表由链（运输路径）连接的点，链

2、代表节点之间的成本（距离、时间或距离和时间的加权平均）。 最初，所有的节点都没有经过求解：也就是说，没有通过各个节点的明确的路线，开始时只有起点是已解的节点。 如下图所示：第3页/共50页起点：阿马里洛起点：阿马里洛终点：沃恩堡终点：沃恩堡俄克拉荷马城俄克拉荷马城9034813815390668484120601261261324813215048ABCDEFGHIJ图图 阿马里洛和沃思堡之间高速公路网示意图，附行车时间阿马里洛和沃思堡之间高速公路网示意图，附行车时间 最短路径法示意图第4页/共50页5解答迭代法（1）目的：通过n次迭代，逐渐获得距离起点累加的最短距离；（2）步骤：1.在所有未

3、解节点中，找出距起点最近的节点，和起点一起作为已解节点；2.将那些连接已解节点的最近的未知节点，作为候选节点3.统计各候选节点到起点的距离之和，最短总距离的候选节点为新的已解节点；4.重复迭代，直到所有节点都解开到达终点，即可获得最短路径第5页/共50页 例：找到得州的阿马里洛与沃思堡之间行车时间最短的路线。节点之间的每条链上都标有相应的行车时间，节点代表公路的连接处。（时间：分钟）起点：阿马里洛起点：阿马里洛终点：沃恩堡终点：沃恩堡俄克拉荷马城俄克拉荷马城9034813815390668484120601261261324813215048ABCDEFGHIJ图图 阿马里洛和沃思堡之间高速公

4、路网示意图，附行车时间阿马里洛和沃思堡之间高速公路网示意图，附行车时间第6页/共50页71AB90B90AB2ABCC13890+66=156C138AC3ABCDEF34890+84=174138+90=228E174BE4ACEDFI348138+90=228174+84=258F228CF5ACEFDDIH348138+153=291174+84=258228+60=288I258EI表 最短路径法的计算步骤表步骤直接连接到未解节点的已解节点与其直接连接的最近未解结点候选节点相关总成本第n个最近已解节点最小总成本最新连接第7页/共50页86ACFIDDHJ348138+153=29122

5、8+60=288258+126=384H288FH7ACFHIDDGGJ348138+153=291228+132=360288+48=336258+126=384D291CD8DFHIGGGJ291+48=339228+132=360288+48=336258+126=384G336HG9IHGJJJ258+126=384288+126=414336+150=486J384IJ步骤直接连接到未解节点的已解节点与其直接连接的未解结点相关总成本第n个最近解点最小成本最新连接第8页/共50页起点：阿马里洛起点：阿马里洛终点：沃恩堡终点：沃恩堡俄克拉荷马城俄克拉荷马城9034813815390668

6、484120601261261324813215048ABCDEFGHIJ第9页/共50页ROUTE模组 目的：最小化运输成本（时间、距离） There may be up to 500 nodes in the network If you need a graph of the result, coordinate points for the nodes may be added. To determine these coordinate points, place a linear grid over a map of the network and read the X,Y coo

7、rdinates for each node. The 0,0 coordinates must begin in the southwest corner of the grid. Cost may also be expressed as a weighted index of both time and distance 第10页/共50页第11页/共50页最短距离未必最优没有考虑每条路线的运行质量过路费道路施工情况罚款现实世界的路线-昆虫智慧：蚂蚁行动留下信息素跟踪别人的路线因此，路线规划的作用最大是体现在路线运行的初期，后期需要结合实际运行的信息就行调整和修改第12页/共50页多起止

8、点运输决策的补充内容线性规划第13页/共50页基本概念目标函数决策变量约束条件线性非负性可行域第14页/共50页Stratton 公司第15页/共50页型号1型号2第16页/共50页x1 = 型号1塑料管的生产、销售数量（单位：100英尺）x2 = 型号2塑料管的生产、销售数量（单位：100英尺） 线性规划模型的构建第17页/共50页线性规划模型的构建第18页/共50页线性规划模型的构建第19页/共50页第20页/共50页线性规划模型的构建第21页/共50页线性规划模型的构建第22页/共50页线性规划模型的构建第23页/共50页线性规划模型求解18 16 14 12 10 8 6 4 2 0

9、x1x24x1 + 6x2 48 (挤压工时限制)(12, 0)(0, 8)|24681012141618第24页/共50页线性规划模型求解18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 48 (挤压工时限制)(9, 0)(0, 9)2x1 + 2x2 18 (装箱工时限制)第25页/共50页线性规划模型求解18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 48 (挤压工时限制)(8, 0)(0, 16)2x1 + 2x2 18 (装箱工时限制)2x1 + x2 16 (原材料

10、添加剂)第26页/共50页线性规划模型求解18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 48 (挤压工时限制)2x1 + 2x2 18 (装箱工时限制)2x1 + x2 16 (原材料添加剂)可行域ABCDE第27页/共50页线性规划模型求解18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 48 (挤压工时限制)2x1 + 2x2 18 (装箱工时限制)2x1 + x2 16 (原材料添加剂)ABCDE (8,0)(0,6.8)第28页/共50页线性规划模型求解18 16 1

11、4 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 48 (挤压工时限制)2x1 + 2x2 18 (装箱工时限制)2x1 + x2 16 (原材料添加剂)ABCDE (8,0)(0,6.8)第29页/共50页线性规划模型求解18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 48 (挤压工时限制)2x1 + 2x2 18 (装箱工时限制)2x1 + x2 16 (原材料添加剂)ABCDE (8,0)(0,6.8)第30页/共50页线性规划模型求解18 16 14 12 10 8 6 4 2 0

12、|24681012141618x1x24x1 + 6x2 48 (挤压工时限制)2x1 + 2x2 18 (装箱工时限制)2x1 + x2 16 (原材料添加剂)ABCDE (8,0)(0,6.8)第31页/共50页线性规划模型求解|24681012141618x14x1 + 6x2 48 (挤压工时限制)2x1 + 2x2 18 (装箱工时限制)2x1 + x2 16 (原材料添加剂)DE (8,0)18 16 14 12 10 8 6 4 2 0 x2ABC(0,6.8)最优角点最优角点4x1+ 6x2= 482x1+ 2x2= 18第32页/共50页例 某制造商与不同三个地点的供应商签订

13、合同，由它供货给三个工厂，约束条件是不超过合同所定的数量，但必须满足生产要求。供应商A400供应商C500供应商B700工厂1需求=600工厂3需求=300工厂2需求=500476555598数字为：运输路线上每吨货物的费率多起止点问题多起止点问题运量规划问题运量规划问题P175是单一路径确定后的运量分配后续问题是单一路径确定后的运量分配后续问题第33页/共50页 多个货源地可以服务多个目的地。 问题： 在单一路径规划基础上，为每条路径运输数量进行决策。 产量、供给的约束 解决方法： 线性规划图解法回顾 复杂的线性规划第34页/共50页运输模型 销地销地产地产地1 2 3 N供应供应/产产量量

14、123：:MX11 X12 X13 . . X1n. . . .Xm1 Xm2 Xm3 . . Xmn a1a2a3am需求需求/销量销量b1 b2 b3 bn 第35页/共50页 目标函数： Min zijminjijxc1111Cmnijijijx，单位运输成本；运输量1 1 +2 1 +3 16 0 01 2 +2 2 +3 25 0 01 3 +2 3 +3 33 0 01 1 +1 2 +1 34 0 02 1 +2 2 +2 37 0 03 1 +3 2 +3 35 0 01 1 ,2 1 ,3 1 ,1 2 ,2 2 ,3 2 ,1 3 ,2 3 ,3 3XXXXXXXXXXXX

15、XXXXXXXXXXXXXXX约 束 函 数 ：皆 为 正 整 数第36页/共50页Logware TranlpTranlp00.dat It will handle a problem of up to 30 rows and 30 columns supply and demand are not required to be equal. Supply and requirements values should be entered as whole (integer) numbers. 输入的成本可以是小数，但应避免极大或者极小值输入，转换单位让其“正常”第37页/共50页更一般的线

16、性规划问题 TRANLAP模组局限：形式固定 约束函数无法添加系数 供应约束 函数只能为最小化形式 需求约束函数只能固定为=形式前面的例子如何解决？前面的例子如何解决？第38页/共50页LOGWARELNPROG 最多能解决50个约束、100个变量的线性规划问题 软件中右侧的(RHS) values必须0 To reconfigure the matrix for a problem size different than appears on the screen, first click on the Resize button and then change the number of

17、constraints and number of variables. 该模组默认解决最小化问题（Obj.Coef为正数），如果是最大化问题，则通过加上“-”号，转化为最小化问题 符号类型 即为第39页/共50页起止点重合的问题运量与运输路径的特殊规划销售员问题：假设有一个推销员要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使

18、所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）特征：在既定运量情况下，用合并运输减少成本的路径规划 需要在路径若干站点停留 最终回到原起点第40页/共50页合理路线制定原则P179 安排车辆负责相互距离最近的站点运输，以使站点之间的行车时间最短第41页/共50页 安排车辆途径的站点时，应注意使站点群更加紧凑； 从距离仓库最远点开始划分站点群 站点群内的路线设计，应当不存在路线交叉 尽可能使用最大运货量的汽车，满足站点群的需要。 取货、送货应该混合安排，不应该在完成全部送货任务之后再取货； 对过于遥远而无法归入群落的站点，可以采用其它配

19、送方式，如小卡或外包；第42页/共50页实践中合理路线制定方法（1） 扫描法根据运量划分站点群 每个站点群的运量用一辆卡车就能解决 站点群之间和站点群内部，行车路线不应当存在交叉a)不合理的不合理的线路交叉划分方式线路交叉划分方式b)合理的合理的线路划分方式线路划分方式TDFFFFFFTTTTTT站点站点仓库仓库TDFFFFFFTTTTTT仓库仓库第43页/共50页一、扫描法(感知法)P183 在地图或方格图中确定所有站点（含仓库）的位置； 自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线到与某站点相交。 继续旋转，直到最大容量第44页/共50页45例 某公司用厢式货车从货主处

20、取货，图(a) 是一天的取货量，单位是件。厢式货车的载货量是10000件。完成所有取货任务需一天时间。公司需要多少条运输路线（即多少部车），每条路线上应该经过哪些站点，每条路线上的站点怎样排序。 首先，向北画一条直线，进行逆时针方向“扫描”。这些都是随机决定的。逆时针旋转该直线，直到装载的货物能装上一辆载重10000件的卡车，同时又不超载。一旦所有的站点都分派有车辆，就可以利用“水滴”法安排经过各站点的顺序，图 (b)是所列出的最终的路线设计。200020002000200020002000200020001000100020002000300030001000100040004000200020003000300030003000线路3线路38000件8000件线路1线路110000件10000件线路2线路29000件9000件(a)(b)优点：迅速得出结果；缺点：10%的平均误差第45页/共50页二、站点群内路线设计 节约法（Clarke-Wright）站点群内路径距离优化方法 P184 目标：是使所有车辆行驶的总里程最短，并进而为所有的站点提供服务的卡车数量最少。