物流运输管理

1、第七章物流运输优化与决策1第一节 物流运输服务选择决策一、物流运输方式选择的原则二、基于物流总成本比较的运输方式选择三、承运人的选择与评价2一、物流运输方式选择的原则（一）安全性原则（二）及时性原则（三）准确性原则（四）经济性原则3二、基于物流总成本比较的运输方式选择基于运输成本与库存成本的总成本分析方法：表7-1 各种运输方式的基本参数表7-2 各种运输方式成本计算结果运输方式费率R(元/件) 时间T(天) 年运送批次 平均存货量Q/2铁路0.1 21 10 100000驮背0.15 14 20 46500公路0.2 5 20 42000航空1.4 2 40 202504三、承运人的选择与评

2、价（一）影响承运人选择的主要因素1运输成本2运输时间和运输时间的可靠性3可到达性4服务能力5安全性5（二）承运人的评价方法综合因素加权求和法表7-3 承运商评估报告示例承运人：_时期:_6第二节 货物运输调配决策一、多起迄点间的直达运输二、存在中间转运的物资调配7一、多起迄点间的直达运输（一）产销平衡的运输问题1产销平衡运输问题数学模型2求解方法 单纯形法、表上作业法图7-1 多点之间的物资运输调拨问题示意图8（二）产销不平衡的运输问题1总产量大于总销量：则增加一个假想的销地Bn+1，其销量为：2总销量大于总产量：则增加一个假想的产地Am+1，其产量为：9二、存在中间转运的物资调配（一）问题描

3、述图7-2 有中间转运的物资运输调拨问题10（二）数学模型目标函数为：约束条件为：（1）配送量生产能力的限制： k=1，2，f； （2）流通中心发送能力的限制： i1，2，m；（3）满足零售店需求量： j=1，2，n；（4）变量非负：11（三）求解方法运输问题表上作业法：例7-2表7-4 各点间运输单位费用12表7-5 需求和供应量确定准则转运问题中点的性质在运输表中的供应值在运输表中的需求值供应点起始供应+总供应总供应转运点总供应总供应需求点总供应起始需求+总供应空 点0起始供应起始需求表7-6 最终运输表13第三节 物流运输线路的优化一、起迄点不同的单一路线优化二、起迄点重合的单一路线优化

4、14一、起迄点不同的单一路线优化归结为运筹学中的最短路径问题 图7-3 从起点到终点的运输网络图15动态规划方法 B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段531368766835342138223335526643437597681310912131618该点到G点的最短距离16（一）动态规划法图7-4 多阶段划分5287122014191917（二）Dijkstra方法例7-3图7-5 运输网络图18E.W.Dijkstra 算法（标号算法）算法基本思路分析：（逐步向外搜索）5216582899722121025275111

5、21210575667991010633xy起点到该点的最短距离起点到该点的最短距离的上界19（二）Dijkstra方法例7-3图7-5 运输网络图00254294448771481320表7-8 Dijkstra算法步骤表步骤P标号点与P点直接相连的T标号点相应的总距离第n个最近点最小总距离最新连接1OA2A2OA2OACB42+2=4CB44OCAB3ABCDEE2+7=94+3=74+4=8E7BE4ABEDDD2+7=94+4=87+1=8DD88BDED5DETT8+5=137+7=14T13DT21A起点90B13834866C9084E96D1564875F12050132IH4

6、8G150126126J终点22 二、物流运输的优化模型 按货物的自然流向组织货物合理的物流运输是市场经济规律的客观要求，它直接决定着物流的效率与效果。为了制定在产销平衡条件下的运量规划方案，必须建立数学模型，运用数学方法来解决。23 三、单纯形法 对于运输问题，一般采用单纯形法求解，具体方法和步骤已在前面介绍过，这里不再列述。经验表明，当起运站和目的地都多于5个时，用其它方法求解比较困难或繁琐，最好用单纯形法求解。24 四、图表分析法 图表分析法是在分区产销平衡所确定的供销区域内，按照生产地与消费地的地理分布，根据有利于生产、有利于市场供给、近产近销的原则，应用交通路线示意图和商品产销平衡表

7、找出产销之间经济合理的商品运输路线。25 五、图上作业法26 1运输线路不成圈的图上作业法27282930 2运输线路成圈的图上作业法 运输线路成圈，就是形成闭合回路的“环”形路线，包括一个圈（有三角形、四边形、多边形）和多个圈。成圈的线路流向图要同时达到既无对流现象、又无迂回现象的要求才是最优流向图。 对于成圈运输线路的图上作业法，可按下述三个步骤寻求最优方案，如表9-22所示。31表9-22 成圈运输线路的图上作业法的步骤 步骤详 述去段破圈确定初始运输方案 就是在成圈的线路中，先假设某两点间的线路“不通”，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；按照运输线路不成圈的图上作业法

8、，即可得到初始运输方案。检查有无迂回现象 因为流向箭头都统一画在线路右边，所以圈内圈外都画有一些流向。分别检查每个小圈，如果圈内和圈外流向的总长度都不超过全圈总长度的1/2 ，那么，全圈就没有迂回现象了，这个线路流向图就是最优的，对应的就是最优运输方案。否则转向第三步。重新去段破圈，调整流向 在超过全圈总长1/2 的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的各段上，加上减去的最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直到得到最优线路流向图为止。 如果全圈存在两个及两个以上的圈，则需分别对各圈进行是否存在迂回

9、线路的检查，如果各圈的里、外圈都不超过全圈总线长的1/2 ，则不存在迂回现象，此方案为最优运输方案。32(13)(18)333435最小树问题与网络设计树（Tree）和最小树树是图论中一类重要的图，实际中很多系统的结构都是树。树连通且不含圈的图，简记为 T 。 树的性质：（1）在树中，任意两个顶点间必有且仅有一条链；（2）在树中，在不相邻的顶点中添加一条树枝，则恰好得到一个圈；（3）在树中，任意去掉一条树枝，就变成分离图；（4）设T是棵有n个顶点的树，则T的树枝数为n-1；（5）一棵树至少有两个悬挂点；（6）树是连通且边数最少的图。36最小树问题树（Tree）和最小树树的权 若Tk是加权图G的

10、一棵树，则树T的全部边的权之和称为树Tk的权，记为 （ Tk ）= （e）； e Tk最小树 T*是加权图G的一棵最小树，即（ T* ）=min (Tk) 37最小树问题树（Tree）和最小树破圈法，避圈法求最小支撑树：图G1542453134421512最小支撑树T最小支撑树T121211212312112338案例：几家石油公司准备联合建设一个输油管道来连接西南地区、东南地区和中西部地区的城市，网络图如下图所示，其中各个城市之间的英里数显示在各个分支上。确定用最少距离的管道连接10个城市的管道系统并计算出需要使用多少英里的管道。3929108745631丹佛奥马哈得梅因印第安纳波利斯阿尔伯

11、克基 俄克拉何马城小石城纳什维尔圣路易斯堪萨斯城40049052045075024031058021012025025023534026027032026034040练习：我校拟设立一个网络将主要的校园建筑与计算机中心连接起来提高网络服务。一些电缆需要埋到地下，主要利用现有的电缆通道来架设。如下网络显示了节点1计算机中心与不同建筑物之间连接的各个分支及其距离，试确定网络中可以连接所有建筑物的最小树及需要的总的电缆长度。41291087456311214111386984882114523539127564829581028018631138208921056271832769371645742

12、网络流（Flow）与最大流问题 最大流问题是一类应用极为广泛的问题，如运输网络中的人流、车流、物流，供水网络中的水流，金融系统中的现金流，通信系统中的信息流，等等。20 世纪 50 年代 Ford Fulkerson 建立的“ 网络流理论 ”，是网络应用的重要组成部分。43一、基本概念1容量网络：（1） 容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最大可能负载）称为该弧的容量。记为: C（vi，vj）或Cij，也常记为bij。（2） 容量网络：对所有的弧都给出了容量的有向网络，记为D=（V，A，C）或D=（V，A，B）。44 （1）流：弧上的流网络中加在弧上的负载 量。记为fi

13、j或xij。 图上的流加在网络中各条弧上的一组负载量（即定义在弧集上的一个函数）。记为 f=f（vi，vj）=fij2流与可行流（2）零流：若网络上所有弧上的流均为0，即对所有的i和j，都有fij=0，则称相应的图上的流为零流。45 （3）可行流：在容量网络上，满足容量限制条件和中间点平衡条件（连续性定理）的图上的流。 即 0fijcij; 其中f为网络中从起点s到终点t的流量。问： 零流是不是可行流？46 3 割（割集、截集）： 设V为网络中所有顶点的集合，将V剖分为两个子集 和 ，满足:称弧集 为分离起点和终点的的割集。组成割集的各条弧容量之和称为割容量（截量），所有割集中容量最小的割集称

14、为最小割。47 4、弧的分类（1）在可行流f=fij中，按流量的特征分有： 饱和弧fij=cij 非饱和弧fij0 48（2）在容量网络中从起点vs到收点vt的一条链中，按弧的方向分 前向弧与链的方向一致的弧。前向弧全体记为+； 后向弧与链的方向相反的弧。后向弧全体记为- ； 其中,链的方向规定为: 从起点vs指向终点vt。49例： ：S，e1，V1，e2，V2，e3，V4，e4，V3，e5，TV2TV1SV3V4e1e2e3e4e5e7e6e8e9+ =：e1，e3，e5 =：e2，e4505.增广链（流量修正路线）： 设f是一可行流，是从起点vs到终点vt的一条链，若满足下面两个条件，则称

15、为关于可行流f的一条增广链： 在弧（vi，vj）+上， 0fijcij（即前向弧均为非饱和弧） 在弧（vi，vj）-上， 0 fijcij（即后向弧均为非零流弧） 51二、什么是最大流问题？ 在满足容量限制条件和中间点平衡条件的要求下，求取流量值达到最大的可行流的一类优化问题。简言之，是求容量网络中具有最大流量值的可行流问题。 所求出的该可行流称为最大流。52三、Ford-Fulkerson标记化方法的理论基础 最大流最小割定理（最大流量最小截量定理） 在任一容量网络中，从发点到收点的最大流流量等于该网络最小割的割容量。 53网络最大流问题的标号算法1确定初始可行流。 如果没有给定，也难以观察

16、得出，则将零流作为初始可行流；2标号过程（目的是用标号法寻求增广链） （1）标号的意义符号vi（vj , i）表示vi点的标号是（vj，i） ，其中vj表示点vi的标号来自vj ， i 表示流量的修正量。54(2)标号过程给起点标上标号（0，+）；考察起点的所有相邻未标号点：对正向弧(vs,vj ) ， 检查其是否饱和？是，则不加标记；不是，则加标记为(vs, j)， 其中 j =csj-fsj；对反向弧检查其是否是零流弧？是，则不加标记；不是，则加标记为(-vs, j)，其中 j =fsj；55重复步骤二，但要注意把vs换成已得到标号的点；可能出现两种结局： a.标号过程中断，收点得不到标号

17、。说明该网络中不存在增广链，现行的可行流就是最大流； b.收点得到标号，反向追踪即可找到一条从起点到收点由标号点及相应的弧连接而成的增广链。563调整过程修改流量，其中流量调整量 ， 指增广链上所有弧的流量修正量； 在增广链的正向弧上增加 ； 反向弧上减少 ； 其它弧上流量不变。 调整方法：57vsv1v2v3v4vt(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(-v1,1)(v2,1)(-v2,1)(v3,1)(5,2)(1,0)(1,0)(2,2)(vs,3)例：弧旁的数是（cij,fij)：（容量，流量）最大流为5.58案例：联邦

18、航空局（FAA）批准给全航空一个新的航空许可，准许它运行从洛杉矶到芝加哥的多条航线。每条航线的航班数显示在下图网络中，确定每天从洛杉矶到芝加哥的最大航班数，并确定每条路线的航班数。591235467810586754476578洛杉矶凤凰城达拉斯丹佛圣路易斯芝加哥盐湖城堪萨斯城60vsvt(4,3)(1,1)(7,6)(3,2)(3,2)(4,3)(2,2)(8,2)(4,1)(3,2)(4,3)(5,3)练习：求下图所示网络的最大流。（cij,fij)61二、起迄点重合的单一路线优化（一）旅行商问题TSP模型0-1整数规划模型图7-6 TSP问题示意图代价矩阵Cij变量矩阵62（二）中国邮递

19、员问题1确定可行方案2判断最优方案63第四节 行车路线及时刻表的制定一、运输路线及时刻表制订的原则二、行车路线制订的扫描法三、行车路线制订的节约法64合理路线和时刻表的制定原则（1）安排车辆负责相互距离最接近的站点的货物运输。图7-11 合理的车辆分派方案图7-12 不合理的车辆分派方案一、运输路线及时刻表制订的原则65(2)安排车辆各日途经的站点时，就注意使站点群更加紧凑。仓库FFFFFTTTTTTFTa)不合理的线路划分方式：线路交叉66b)较合理的线路划分方式仓库FFFFFTTTTTTFT67(3)从仓库最远的站点开始设计路线。要设计出有效的路线，首先要划分出距仓库最远的站点周围的站点群

20、，然后逐步划出仓库附近的站点群。一旦确定了最远的站点就应该选定距该核心站点最近的一些站点形成站点群，分派载货能力能满足该站点群需要地卡车。然后，从还没有分派车辆的其他站点中找出距仓库最远的站点，分派另一车辆。如此往复，直到所有站点都分派有车辆。68图（a）是不合理的运行路线，图（b）是合理的运行路线。 图7-13 运输路线示意图 （4）卡车的行车路线不交叉，且应呈水滴状。69（5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的。（6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。（7）对过于遥远而无法归入群落的站点，可以采用其它配送方式。70行车路线和时刻表的制定方法1

21、、扫描法（1）在地图或方格图中确定所有站点的位置。（2）自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑：如果在某线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力。如果超过，就剔除最后的那个站点。继续这一过程直到所有站点得到安排。（3）排定各路线上每个站点的顺序使行车距离最短。排序时可使用水滴法。71案例：Smith卡车运输公司用厢式货车从货主那里取货。货物先运回仓库，集中后以更大的批量进行长途运输。下图列出了一天的取货量，厢式货车的载货量是1000件。完成所有取货任务一般需

22、要整整一天的时间。公司想知道需要多少条运输路线（即多少部车），每条路线上应该经过哪些站点，每条路线上的站点应该怎样排序。72仓库200020002000200030001000400020003000300020001000地理区域取货点73仓库200020002000200030001000400020003000300020001000路线1路线2路线374二、行车路线制订的扫描法原理:先以仓库(物流中心)为原点，将所有需求点的极坐标算出，然后依角度大小以逆时针或顺时针方向扫描，若满足车辆装载量即划分为一群，将所有点扫描完毕后在每个群内用最短路径法求出车辆最佳行驶路径。例7-4表7-10

23、客户数据信息客户12345678910111213Di(吨)1.92.83.152.4232.252.51.82.151.62.61.5Xi20.018.818.319.118.818.619.519.9320.019.518.719.520.3Yi4.805.175.004.786.425.885.985.935.554.554.555.195.2075第一步：求出各客户点的极坐标。第二步：扫描划分客户群。第三步：确定每辆车的最佳路径。图7-14 客户位置及扫描法求出的结果76三、行车路线制订的节约法基本思想：如果将运输问题中的两个回路合并成一个回路，就可缩短线路总里程（即节约了距离），并减

24、少了一辆卡车。图7-15 节约法的图形描述77例7-5表7-11 客户坐标及订单规模站点X坐标Y坐标订单规模（件）配送中心顾客1顾客2顾客3顾客4顾客5顾客6顾客7顾客8顾客9顾客10顾客11顾客12顾客1300679152017711520720125151230-2-4-6-6-7-9-1548364392571656305747915538781确定距离方阵 表7-12 客户及配送中心之间的距离792计算节约矩阵表7-13 第一次计算的节约矩阵803将客户划归到不同的运输路线表7-14 第一次改进后的节约矩阵81表7-15第二次改进后的节约矩阵82表7-16 第三次改进后的节约矩阵83图

25、7-16 配送中心送货线路规划方案84第五节 运输工具与货载的最优分配一、航线配船优化问题二、多车多品种货载配车优化85一、航线配船优化问题（一）问题概述（二）数学模型的建立1参数说明2目标函数 min K=3约束条件86（三）航线配船优化举例表7-17 某船公司船型及航线与航次表7-18 不同航线和船型的营运成本航线船型季节最大航次数航线船型单船单航次成本（万USD）87表7-19不同航线的运量和机会成本解：（1）目标函数（2）约束条件（3）求解结果求解得出的航线最优配备船舶计划如下：航线123456机会成本（万USD/TEU）0.150.1250.10.10.150.125运量（TEU）600080005000450030007000航线船型航次数88二、多车多品种货载配车优化（一）问题描述（二）模型建立1变量及参数说明2目标函数