物流系统工程第七章

1、2内容提要内容提要第一篇第一篇 物流系统物流系统篇篇第二篇第二篇 物流工程物流工程篇篇第三篇第三篇 软件应用软件应用篇篇3物流工程篇物流工程篇n物流库存问题物流库存问题n物流运输问题物流运输问题n物流配送问题物流配送问题n物流节点选址与网络布局物流节点选址与网络布局n物流系统设施布局物流系统设施布局4物流运输问题物流运输问题7.2运输方式选择问题运输方式选择问题7.3车辆配载问题车辆配载问题7.1物资调运问题物资调运问题7.4 车辆路径问题车辆路径问题7.5 车辆调度问题车辆调度问题7.6 案例：天通磁心公案例：天通磁心公司运输部的完美转身司运输部的完美转身57.1.1 运输问题的模型和特征运

2、输问题的模型和特征n数学模型数学模型 ：11MinmnijijijZc xjixnjbxmiaxS.T.ijmijijnjiij, 0, 2 , 1, 2 , 1,11对所有的67.1.1 运输问题的模型和特征运输问题的模型和特征n运输问题的特征：运输问题的特征： 在产销平衡时，运输问题一定有可行解，且有最优解。在产销平衡时，运输问题一定有可行解，且有最优解。当产量与销量均为整数时，必存在决策变量为整数的最优解。当产量与销量均为整数时，必存在决策变量为整数的最优解。决策变量的系数只有决策变量的系数只有0和和1，系数矩阵，系数矩阵A有有m+n行、行、m*n列，列，秩为秩为m+n-1，从而有，从而

3、有m+n-1个基变量。个基变量。运输问题的运输问题的m+n-1个基变量不构成闭回路；个基变量不构成闭回路；运输问题可以采用运筹学的线性规划求解，一般可以采用表上运输问题可以采用运筹学的线性规划求解，一般可以采用表上作业法。作业法。77.1.2 用表上作业法求解运输问题用表上作业法求解运输问题n基本步骤基本步骤 :(1)编制初始调运方案编制初始调运方案(即确定初始基本可行解，西北角法即确定初始基本可行解，西北角法/最小元素法最小元素法)(2)最优性检验最优性检验(即求出相应的检验数，闭回路法即求出相应的检验数，闭回路法/位势法位势法)(3)解的改进根据检验数确定方案是否最优，是则终止，否则采用闭

4、回路法调解的改进根据检验数确定方案是否最优，是则终止，否则采用闭回路法调整，再返回到第整，再返回到第2步，直至最优。步，直至最优。87.1.2 用表上作业法求解运输问题用表上作业法求解运输问题n例例7-1，现由，现由A1、A2、A3三个供应地向三个供应地向B1、B2、B3、B4四个需求地供应商品，各供应点四个需求地供应商品，各供应点的供应量、需求点的需求量、以及从供应点到需求点的单位的供应量、需求点的需求量、以及从供应点到需求点的单位(包括设备交通包括设备交通)费用如表费用如表7-2所所示，问如何安排可使总费用最小？示，问如何安排可使总费用最小？97.1.2 用表上作业法求解运输问题用表上作业

5、法求解运输问题n解：解：1)西北角法，如表西北角法，如表7-32)最小费用法，如表最小费用法，如表7-4(1)编制初始调运方案编制初始调运方案3)以上两种方法在求初始基可行解时，均会遇到一些特殊情况，一般称为以上两种方法在求初始基可行解时，均会遇到一些特殊情况，一般称为“退化退化”。 107.1.2 用表上作业法求解运输问题用表上作业法求解运输问题n解：解：(2)最优性检验最优性检验1)闭回路法闭回路法2)位势法位势法117.1.2 用表上作业法求解运输问题用表上作业法求解运输问题n解：解：(3)用闭回路法调整运输方案用闭回路法调整运输方案改进基可行解改进基可行解127.1.3 其它运输问题的

6、处理其它运输问题的处理n具体参考例具体参考例9-4 13物流运输问题物流运输问题7.2运输方式选择问题运输方式选择问题7.3车辆配载问题车辆配载问题7.1物资调运问题物资调运问题7.4 车辆路径问题车辆路径问题7.5 车辆调度问题车辆调度问题7.6 案例：天通磁心公案例：天通磁心公司运输部的完美转身司运输部的完美转身147.2.1 因素分析法因素分析法n步骤：步骤：n(1)因素分析法首先对所要进行选择的运输方式，按重要性因素或其它尺因素分析法首先对所要进行选择的运输方式，按重要性因素或其它尺度进行标定度进行标定n(2)按各种不同标准，分别给各种运输工具打分按各种不同标准，分别给各种运输工具打分

7、n(3)对每种运输工具计算其总分对每种运输工具计算其总分n(4)选择出总分最高的运输方式选择出总分最高的运输方式nijiSjV1),()(模型：模型：157.2.2 加权因素分析法加权因素分析法n加权因素分析法是因素分析法的一种改进，主要改进的地方是对不同的准则按其重加权因素分析法是因素分析法的一种改进，主要改进的地方是对不同的准则按其重要性分别给予不同的权重。基本步骤同因素分析法。要性分别给予不同的权重。基本步骤同因素分析法。模型：模型： nijiSiWjV1),()()(167.2.3 层次分析法层次分析法n20世纪世纪70年代，著名运筹学家萨迪年代，著名运筹学家萨迪(T.L.Saaty)

8、提出提出n适用于那些难于完全用定量进行分析的复杂问题适用于那些难于完全用定量进行分析的复杂问题 步骤：步骤： 1)系统层次结构的建立系统层次结构的建立2)构造两两比较判断矩阵构造两两比较判断矩阵3)单一准则下元素相对权重计算单一准则下元素相对权重计算4)单一准则下的一致性检验单一准则下的一致性检验5)层次总排序与总一致性检验层次总排序与总一致性检验17物流运输问题物流运输问题7.2运输方式选择问题运输方式选择问题7.3车辆配载问题车辆配载问题7.1物资调运问题物资调运问题7.4 车辆路径问题车辆路径问题7.5 车辆调度问题车辆调度问题7.6 案例：天通磁心公案例：天通磁心公司运输部的完美转身司

9、运输部的完美转身187.3.1 建立货车匹配层次结构图建立货车匹配层次结构图197.3.3 一致性检验一致性检验207.3.4 层次总排序层次总排序n子准则层各因索子准则层各因索C对总目标对总目标A的权值计算：的权值计算：W=(0.24，0.26，0.05，0.32，0.13)T217.3.4 层次总排序层次总排序n(1)所有制及车辆投保计分所有制及车辆投保计分C1n采用百分制：国营采用百分制：国营60；集体；集体40；个体；个体20；车保；车保40。n(2)出发日期计分出发日期计分C2n采用百分制：出发日期与发货日期同天采用百分制：出发日期与发货日期同天100；出发日期与发货日期第二天；出发

10、日期与发货日期第二天60；出发日期与发货日期第三天；出发日期与发货日期第三天20；再以；再以后不予考虑。后不予考虑。n(3)吨百公里油耗计分吨百公里油耗计分C3n设吨百公里油耗为设吨百公里油耗为X升，升，C3=100-(X-2)10n(4)行程利用率计分行程利用率计分C4nC4=行程利用率行程利用率100 n(5)实载率计分实载率计分C5n货物重量货物重量载重吨位时：载重吨位时：C5=实载率实载率100；货物重量；货物重量载重吨位时：载重吨位时：C5=100/实载率实载率-20n(6)总分总分CnC=0.24C1+0.26C2+0.05C3+0.32C4+0.13C5总分总分C最大的即为最佳匹

11、配最大的即为最佳匹配 22物流运输问题物流运输问题7.2运输方式选择问题运输方式选择问题7.3车辆配载问题车辆配载问题7.1物资调运问题物资调运问题7.4 车辆路径问题车辆路径问题7.5 车辆调度问题车辆调度问题7.6 案例：天通磁心公案例：天通磁心公司运输部的完美转身司运输部的完美转身237.4.1 最短路算法模型最短路算法模型n1. Dijkstra标号法标号法例例7-3，某公司要在起点，某公司要在起点A和终点和终点J之间寻找一条运输时间最短的路线。从之间寻找一条运输时间最短的路线。从A到到J有多有多条路线条路线(如图如图7-6所示所示)，图，图7-6中凡是连接的地方均是可以通达的路线，其

12、中每两个中凡是连接的地方均是可以通达的路线，其中每两个结点之间的运输时间为图中数字所示结点之间的运输时间为图中数字所示(单位：单位：Km)。247.4.1 最短路算法模型最短路算法模型解：解： 结论：最短路为结论：最短路为A-B-E-I-J，最短距离为，最短距离为384Km 257.4.2 小规模路网最短路的小规模路网最短路的Excel求解求解图图7-7 物流运输网络图物流运输网络图(有向图有向图)如图如图7-7所示路线，车辆从所示路线，车辆从V1点出发，到达终点点出发，到达终点V8，如何选择行车路径，使总的行车路径最短。，如何选择行车路径，使总的行车路径最短。 假设为：假设为：(1)在网络中

13、选择一条路，始于某源点终于目的地；在网络中选择一条路，始于某源点终于目的地；(2)连接两个节点的连线叫做边连接两个节点的连线叫做边(允许向任一方向进行，或者叫双向通行允许向任一方向进行，或者叫双向通行)或弧或弧(只允许沿一个方向进只允许沿一个方向进行，或者叫单向通行行，或者叫单向通行)，每条边，每条边(弧弧)相关的一个非负数，叫做该边的长度；相关的一个非负数，叫做该边的长度；(3)目标是为了寻找从源点到目的地的最短路目标是为了寻找从源点到目的地的最短路(总长度最小的路总长度最小的路)。267.4.3 全国公路骨干网最短路的全国公路骨干网最短路的Premium Solver求解求解n截至截至20

14、05年底，全国公路总里程达到年底，全国公路总里程达到193.05万公里，路网结构进一步完万公里，路网结构进一步完善。全国公路总里程中，国道善。全国公路总里程中，国道132674公里、省道公里、省道233783公里、县道公里、县道494276公里、乡道公里、乡道981430公里、专用公路公里、专用公路88380公里。特别是公里。特别是“十五十五”和和“十一五十一五”的建设，总规模约的建设，总规模约3.5万公里的万公里的 “五纵七横五纵七横”国道主干线已国道主干线已基本贯通。这基本贯通。这12条主干线全部是二级以上的高等级公路，其中高速公路约条主干线全部是二级以上的高等级公路，其中高速公路约占总里

15、程的占总里程的76%，一级公路约占总里程的，一级公路约占总里程的4.5%，二级公路占总里程，二级公路占总里程19.5%。它们连接了首都、各省省会、直辖市、经济特区、主要交通枢。它们连接了首都、各省省会、直辖市、经济特区、主要交通枢纽和重要对外开放口岸，覆盖了全国所有人口在纽和重要对外开放口岸，覆盖了全国所有人口在100万以上的特大城市和万以上的特大城市和93%的人口在的人口在50万以上的大城市，是具有全国性政治、经济、国防意义万以上的大城市，是具有全国性政治、经济、国防意义的重要干线公路。的重要干线公路。为了方便在为了方便在Excel中建模，我们将骨干网分为中建模，我们将骨干网分为672段，共

16、段，共449个节点。个节点。求解求解出任何两个点之间的最短路出任何两个点之间的最短路 。277.4.3 全国公路骨干网最短路的全国公路骨干网最短路的Premium Solver求解求解图图7-23 我国公路骨干网我国公路骨干网28物流运输问题物流运输问题7.2运输方式选择问题运输方式选择问题7.3车辆配载问题车辆配载问题7.1物资调运问题物资调运问题7.4 车辆路径问题车辆路径问题7.5 车辆调度问题车辆调度问题7.6 案例：天通磁心公案例：天通磁心公司运输部的完美转身司运输部的完美转身297.5.1 车辆调度问题的一般模型车辆调度问题的一般模型n假设：假设：n(1)人的数量和工作的数量相等；

17、人的数量和工作的数量相等；n(2)每个人只能完成一项工作；每个人只能完成一项工作；n(3)每项工作只能由一个人来完成；每项工作只能由一个人来完成；n(4)每个人和每项工作的组合都会有一个相关的成本；每个人和每项工作的组合都会有一个相关的成本；n(5)目标是要确定如何指派才能使总成本最小。目标是要确定如何指派才能使总成本最小。数学模型：数学模型： 1111min.1(1,2,., ).1(1,2,., )1( ,1,2,., )nnij ijijnijjnijiijzc xxinistxjnjxi jn第 人只能做一项工作第 项工作只能由一人做非负307.5.2 车辆调度规划的车辆调度规划的Ex

18、cel求解求解n某物流公司是浙江著名的第三方非资产型物流公司，该物流公司在浙江省某物流公司是浙江著名的第三方非资产型物流公司，该物流公司在浙江省可以调度的车辆超过可以调度的车辆超过3，000辆，协议仓库超过辆，协议仓库超过20处处(30万平方米万平方米)。该公。该公司作为资源整合型第三方物流企业，将车辆的合理优化调度作为其核心竞司作为资源整合型第三方物流企业，将车辆的合理优化调度作为其核心竞争力。现有一具体情况，公司接到争力。现有一具体情况，公司接到4家客户的订单要求家客户的订单要求(客户所在地为金华、客户所在地为金华、绍兴、丽水和温州绍兴、丽水和温州)，将货物在，将货物在4小时内分别运往诸暨

19、、嘉兴、温岭和东阳。小时内分别运往诸暨、嘉兴、温岭和东阳。该公司在接到订单后，进行了车货匹配，发现可以从杭州、宁波、衢州和该公司在接到订单后，进行了车货匹配，发现可以从杭州、宁波、衢州和台州调车。虽然浙江的交通网络相当发达，基本实现了省内主干道运输不台州调车。虽然浙江的交通网络相当发达，基本实现了省内主干道运输不超过超过4小时，但想在客户要求的时间由一辆车来完成两个客户是不现实的，小时，但想在客户要求的时间由一辆车来完成两个客户是不现实的，也就是说，现在只能让每辆车负责一家客户。具体的车辆分布情况、客户也就是说，现在只能让每辆车负责一家客户。具体的车辆分布情况、客户分布情况和各地之间的路程分布

20、情况和各地之间的路程(单位为公里单位为公里)都已在表中列出都已在表中列出(见表见表7-24和表和表7-25)，该公司的物流经理小王现在在考虑，怎样调度这些车辆，方案最，该公司的物流经理小王现在在考虑，怎样调度这些车辆，方案最佳。佳。 317.5.2 车辆调度规划的车辆调度规划的Excel求解求解327.5.3全国全国43城市的车辆优化调度城市的车辆优化调度(Premium Solver求解求解)nExcel自带的自带的Solver工具可以求解工具可以求解200个变量的规划求解问题，对于指派问题，理论个变量的规划求解问题，对于指派问题，理论上可以求解上可以求解1414的指派问题。但对实际的指派问

21、题，可能会复杂很多，可能会有的指派问题。但对实际的指派问题，可能会复杂很多，可能会有很大失误。很大失误。Premium Solver Platform可以求解多达可以求解多达2，000个变量的规划求解问题，事实上个变量的规划求解问题，事实上可以求解多达可以求解多达4444的指派问题，我们以全国主要的的指派问题，我们以全国主要的43城市为例城市为例(4343)，分别，分别为北京、天津、锦州、沈阳、长春、哈尔滨、齐齐哈尔、牡丹江、吉林、丹东、大为北京、天津、锦州、沈阳、长春、哈尔滨、齐齐哈尔、牡丹江、吉林、丹东、大连、济南、青岛、徐州、合肥、南京、上海、杭州、南昌、福州、石家庄、郑州、连、济南、青

22、岛、徐州、合肥、南京、上海、杭州、南昌、福州、石家庄、郑州、武汉、长沙、株洲、广州、深圳、柳州、南宁、桂林、西安、兰州、西宁、乌鲁木武汉、长沙、株洲、广州、深圳、柳州、南宁、桂林、西安、兰州、西宁、乌鲁木齐、拉萨、成都、重庆、贵阳、昆明、太原、呼和浩特、银川和二连浩特齐、拉萨、成都、重庆、贵阳、昆明、太原、呼和浩特、银川和二连浩特(地理位地理位置如图置如图7-48所示所示)。 我们需要通过这我们需要通过这43个城市之间的里程表来完成车辆调度。个城市之间的里程表来完成车辆调度。337.5.3全国全国43城市的车辆优化调度城市的车辆优化调度(Premium Solver求解求解)图图7-48 全国全国4