物流运输管理-第七章课件

第一节 物流运输服务选择决策v一、物流运输方式选择的原则v二、基于物流总成本比较的运输方式选择v三、承运人的选择与评价1 1整体概述概述二点击此处输入相关文本内容概述一点击此处输入相关文本内容概述三点击此处输入相关文本内容2 2一、物流运输方式选择的原则（一）安全性原则（二）及时性原则（三）准确性原则（四）经济性原则3 3二、基于物流总成本比较的运输方式选择vv基于运输成本与库存成本的总成本分析方法：基于运输成本与库存成本的总成本分析方法：表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 20250成本类型计算公式铁路运输驮背运输公路运输航空运输运输成本RD70000105000140000980000在途库存ICDT/3653624662416448630134521工厂存货ICQ/2900000418500378000182250仓库存货I(C+R)Q/2903000420593380520190755总成本223546611857379848214 4三、承运人的选择与评价（一）影响承运人选择的主要因素1运输成本2运输时间和运输时间的可靠性3可到达性4服务能力5安全性5 5（二）承运人的评价方法vv综合因素加权求和法综合因素加权求和法表7-3 承运商评估报告示例承运人：_时期:_最高分评价标准承运人分数备注13满足接货时间表1313满足搬运109运输时间910运输时间一致性77费率53附加费1高的住宅搬运5运营比率396.5增长4收益性33索赔频率33索赔解决310账单错误79跟踪能力711设备可用性l无平台装货卡车100总分726 6第二节 货物运输调配决策v一、多起迄点间的直达运输v二、存在中间转运的物资调配7 7一、多起迄点间的直达运输（一）产销平衡的运输问题1产销平衡运输问题数学模型2求解方法 单纯形法、表上作业法图7-1 多点之间的物资运输调拨问题示意图8 8（二）产销不平衡的运输问题1总产量大于总销量：v则增加一个假想的销地Bn+1，其销量为：2总销量大于总产量：v则增加一个假想的产地Am+1，其产量为：9 9二、存在中间转运的物资调配（一）问题描述图7-2 有中间转运的物资运输调拨问题1010（二）数学模型目标函数为：约束条件为：（1）配送量 生产能力的限制：k=1，2，f；（2）流通中心发送能力的限制：i1，2，m；（3）满足零售店需求量：j=1，2，n；（4）变量非负：1111（三）求解方法vv运输问题表上作业法：运输问题表上作业法：v例7-2表7-4 各点间运输单位费用ABEFCDA013461214B130761312E470388F663078C121387017D1412881701212表7-5 需求和供应量确定准则转运问题中点的性质在运输表中的供应值在运输表中的需求值供应点起始供应+总供应总供应转运点总供应总供应需求点总供应起始需求+总供应空点0起始供应起始需求表7-6 最终运输表ABEFCD空列供应A0134612140500B1307613120550E4703880350F6630780350C1213870170350D1412881700350需求350350350350480480901313第三节 物流运输线路的优化v一、起迄点不同的单一路线优化v二、起迄点重合的单一路线优化1414一、起迄点不同的单一路线优化vv归结为运筹学中的最短路径问题归结为运筹学中的最短路径问题 图7-3 从起点到终点的运输网络图1515动态规划方法 B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段531368766835342138223335526643437597681310912131618该点到G点的最短距离1616（一）动态规划法图7-4 多阶段划分528712201419191717（二）Dijkstra方法v例7-3图7-5 运输网络图1818E.W.Dijkstra 算法（标号算法）算法基本思路分析：（逐步向外搜索）521658289972212102527 5111212105756 679 910106 3 3xy起点到该点的最短距离起点到该点的最短距离的上界1919（二）Dijkstra方法v例7-3图7-5 运输网络图0025429444877148132020表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=14T13DT2121A起点90B13834866C9084E96D1564875F12050132IH48G150126126J终点2222 二、物流运输的优化模型v 按货物的自然流向组织货物合理的物流运输是市场经济规律的客观要求，它直接决定着物流的效率与效果。为了制定在产销平衡条件下的运量规划方案，必须建立数学模型，运用数学方法来解决。2323 三、单纯形法v 对于运输问题，一般采用单纯形法求解，具体方法和步骤已在前面介绍过，这里不再列述。经验表明，当起运站和目的地都多于5个时，用其它方法求解比较困难或繁琐，最好用单纯形法求解。2424 四、图表分析法v 图表分析法是在分区产销平衡所确定的供销区域内，按照生产地与消费地的地理分布，根据有利于生产、有利于市场供给、近产近销的原则，应用交通路线示意图和商品产销平衡表找出产销之间经济合理的商品运输路线。2525 五、图上作业法2626 1运输线路不成圈的图上作业法2727282829293030 2运输线路成圈的图上作业法v 运输线路成圈，就是形成闭合回路的“环”形路线，包括一个圈（有三角形、四边形、多边形）和多个圈。成圈的线路流向图要同时达到既无对流现象、又无迂回现象的要求才是最优流向图。v 对于成圈运输线路的图上作业法，可按下述三个步骤寻求最优方案，如表9-22所示。3131表9-22成圈运输线路的图上作业法的步骤步骤详 述去段破圈确定初始运输方案 就是在成圈的线路中，先假设某两点间的线路“不通”，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；按照运输线路不成圈的图上作业法，即可得到初始运输方案。检查有无迂回现象 因为流向箭头都统一画在线路右边，所以圈内圈外都画有一些流向。分别检查每个小圈，如果圈内和圈外流向的总长度都不超过全圈总长度的1/2，那么，全圈就没有迂回现象了，这个线路流向图就是最优的，对应的就是最优运输方案。否则转向第三步。重新去段破圈，调整流向 在超过全圈总长1/2 的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的各段上，加上减去的最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直到得到最优线路流向图为止。如果全圈存在两个及两个以上的圈，则需分别对各圈进行是否存在迂回线路的检查，如果各圈的里、外圈都不超过全圈总线长的1/2，则不存在迂回现象，此方案为最优运输方案。3232(13)(13)(18)(18)333334343535v最小树问题与网络设计v树（Tree）和最小树v树是图论中一类重要的图，实际中很多系统的结构都是树。v树连通且不含圈的图，简记为 T。v 树的性质：（1）在树中，任意两个顶点间必有且仅有一条链；（2）在树中，在不相邻的顶点中添加一条树枝，则恰好得到一个圈；（3）在树中，任意去掉一条树枝，就变成分离图；（4）设T是棵有n个顶点的树，则T的树枝数为n-1；（5）一棵树至少有两个悬挂点；（6）树是连通且边数最少的图。3636v最小树问题v树（Tree）和最小树v树的权 若Tk是加权图G的一棵树，则树T的全部边的权之和称为树Tk的权，记为 （Tk）=（e）；e Tkv最小树 T*是加权图G的一棵最小树，即（T*）=min(Tk)3737v最小树问题v树（Tree）和最小树v破圈法，避圈法求最小支撑树：图G1542453134421512最小支撑树T最小支撑树T12121121231211233838v案例：v几家石油公司准备联合建设一个输油管道来连接西南地区、东南地区和中西部地区的城市，网络图如下图所示，其中各个城市之间的英里数显示在各个分支上。确定用最少距离的管道连接1010个城市的管道系统并计算出需要使用多少英里的管道。39392 29 910108 87 74 45 56 63 31 1丹佛奥马哈得梅因印第安纳波利斯阿尔伯克基 俄克拉何马城小石城纳什维尔圣路易斯堪萨斯城4004004904905205204504507507502402403103105805802102101201202502502502502352353403402602602702703203202602603403404040v练习：v我校拟设立一个网络将主要的校园建筑与计算机中心连接起来提高网络服务。一些电缆需要埋到地下，主要利用现有的电缆通道来架设。如下网络显示了节点1 1计算机中心与不同建筑物之间连接的各个分支及其距离，试确定网络中可以连接所有建筑物的最小树及需要的总的电缆长度。414129108745631121411138698488211452353912756482958102801863113820892105627183276937164574242网络流（Flow）与最大流问题 最大流问题是一类应用极为广泛的问题，如运输网络中的人流、车流、物流，供水网络中的水流，金融系统中的现金流，通信系统中的信息流，等等。20 世纪 50 年代 Ford Fulkerson 建立的“网络流理论”，是网络应用的重要组成部分。4343一、基本概念1 1容量网络：容量网络：n（1）容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最大可能负载）称为该弧的容量弧的容量。记为:C（vi，vj）或Cij，也常记为bij。n（2）容量网络：对所有的弧都给出了容量的有向网络，记为D=（V，A，C）或D=（V，A，B）。4444（1）流流：弧上的流弧上的流网络中加在弧上的负载 量。记为fij或xij。图上的流图上的流加在网络中各条弧上的一组负载量（即定义在弧集上的一个函数）。记为 f=f（vi，vj）=fij2流与可行流（2）零流零流：若网络上所有弧上的流均为0，即对所有的i和j，都有fij=0，则称相应的图上的流为零流。4545 （3）可行流可行流：在容量网络上，满足容量限制条件和中间点平衡条件（连续性定理）的图上的流。图上的流。即 0fijcij;其中f为网络中从起点s到终点t的流量。问：问：零流是不是可行流？零流是不是可行流？4646 3 3 割（割集、截集）：割（割集、截集）：设V为网络中所有顶点的集合，将V剖分为两个子集 和 ，满足:称弧集 为分离起点和终点的的割集。组成割集的各条弧容量之和称为割容量（截量），所有割集中容量最小的割集称为最小割。4747 4、弧的分类（1 1）在可行流）在可行流f f=f=fij ij 中，按流量的特征分有：中，按流量的特征分有：饱和弧fij=cij 非饱和弧fij0 4848（2 2）在容量网络中从起点在容量网络中从起点v vs s到收点到收点v vt t的一条的一条链中，按弧的方向分链中，按弧的方向分 前向弧前向弧与链的方向一致的弧。前向弧全体记为+；后向弧后向弧与链的方向相反的弧。后向弧全体记为-；其中,链的方向规定为:从起点vs指向终点vt。4949例：S S，e1，V V1 1，e2，V V2 2，e3，V V4 4，e4，V V3 3，e5，TTV2TV1SV3V4e1e2e3e4e5e7e6e8e9 +=：e1，e3，e5 =：e2，e4 50505.5.增广链（流量修正路线）增广链（流量修正路线）：设f是一可行流，是从起点vs到终点vt的一条链，若满足下面两个条件，则称 为关于可为关于可行流行流f f的一条的一条增广链增广链：在弧（vi，vj）+上，0fijcij（即前向弧均为非饱和弧）在弧（vi，vj）-上，0 fijcij（即后向弧均为非零流弧）5151二、什么是最大流问题？在满足容量限制条件和中间点平衡条件的要求下，求取流量值达到最大的可行流的一类优化问题。简言之，是求容量网络中具有最大流量值的可行流问题。所求出的该可行流称为最大流。5252三、三、Ford-FulkersonFord-Fulkerson标记化方法的理论基础标记化方法的理论基础 最大流最小割定理（最大流量最小截量定理）最大流最小割定理（最大流量最小截量定理）在任一容量网络中，从发点到收点的最大流流量等于该网络最小割的割容量。5353网络最大流问题的标号算法v1确定初始可行流。v 如果没有给定，也难以观察得出，则将零流作为初始可行流；v2标号过程（目的是用标号法寻求增广链）v （1）标号的意义符号vi（vj,i）表示vi点的标号是（vj，i），其中vj表示点vi的标号来自vj，i 表示流量的修正量。5454(2)标号过程给起点标上标号（0，+）；考察起点的所有相邻未标号点：对正向弧(vs,vj )，检查其是否饱和？是，则不加标记；不是，则加标记为(vs,j)，其中 j=csj-fsj；对反向弧检查其是否是零流弧？是，则不加标记；不是，则加标记为(-vs,j)，其中 j=fsj；5555 重复步骤二，但要注意把v vs s换成已得到标号的点；可能出现两种结局：a.a.标号过程中断，收点得不到标号。说明该网络中不存在增广链，现行的可行流就是最大流；b.b.收点得到标号，反向追踪即可找到一条从起点到收点由标号点及相应的弧连接而成的增广链。56563 3调整过程修改流量，其中流量调整量 ，指增广链上所有弧的流量修正量；在增广链的正向弧上增加 ；反向弧上减少 ；其它弧上流量不变。调整方法：5757vsv1v2v3v4vt(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)例：弧旁的数是（c cijij,f,fijij)：（容量，流量）最大流为最大流为5.5.5.5.5858v案例：联邦航空局（FAA）批准给全航空一个新的航空许可，准许它运行从洛杉矶到芝加哥的多条航线。每条航线的航班数显示在下图网络中，确定每天从洛杉矶到芝加哥的最大航班数，并确定每条路线的航班数。59591235467810586754476578洛杉矶凤凰城达拉斯丹佛圣路易斯芝加哥盐湖城堪萨斯城6060vsvt(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)6161二、起迄点重合的单一路线优化（一）旅行商问题TSP模型v0-1整数规划模型图7-6 TSP问题示意图代价矩阵Cij变量矩阵6262（二）中国邮递员问题1确定可行方案2判断最优方案6363第四节 行车路线及时刻表的制定v一、运输路线及时刻表制订的原则v二、行车路线制订的扫描法v三、行车路线制订的节约法6464v合理路线和时刻表的制定原则v（1）安排车辆负责相互距离最接近的站点的货物运输。图7-11 合理的车辆分派方案图7-12 不合理的车辆分派方案一、运输路线及时刻表制订的原则6565v(2)安排车辆各日途经的站点时，就注意使站点群更加紧凑。仓库FFFFFTTTTTTFTa)不合理的线路划分方式：线路交叉6666vb)较合理的线路划分方式仓库FFFFFTTTTTTFT6767v(3)从仓库最远的站点开始设计路线。v要设计出有效的路线，首先要划分出距仓库最远的站点周围的站点群，然后逐步划出仓库附近的站点群。一旦确定了最远的站点就应该选定距该核心站点最近的一些站点形成站点群，分派载货能力能满足该站点群需要地卡车。然后，从还没有分派车辆的其他站点中找出距仓库最远的站点，分派另一车辆。如此往复，直到所有站点都分派有车辆。6868v图（a）是不合理的运行路线，图（b）是合理的运行路线。图7-13运输路线示意图v（4）卡车的行车路线不交叉，且应呈水滴状。6969v（5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的。v（6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。v（7）对过于遥远而无法归入群落的站点，可以采用其它配送方式。7070v行车路线和时刻表的制定方法v1、扫描法v（1）在地图或方格图中确定所有站点的位置。v（2）自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑：如果在某线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力。如果超过，就剔除最后的那个站点。继续这一过程直到所有站点得到安排。v（3）排定各路线上每个站点的顺序使行车距离最短。排序时可使用水滴法。7171v案例：vSmith卡车运输公司用厢式货车从货主那里取货。货物先运回仓库，集中后以更大的批量进行长途运输。下图列出了一天的取货量，厢式货车的载货量是1000件。完成所有取货任务一般需要整整一天的时间。公司想知道需要多少条运输路线（即多少部车），每条路线上应该经过哪些站点，每条路线上的站点应该怎样排序。7272仓库200020002000200030001000400020003000300020001000地理区域取货点7373仓库200020002000200030001000400020003000300020001000路线1路线2路线37474二、行车路线制订的扫描法v原理:先以仓库(物流中心)为原点，将所有需求点的极坐标算出，然后依角度大小以逆时针或顺时针方向扫描，若满足车辆装载量即划分为一群，将所有点扫描完毕后在每个群内用最短路径法求出车辆最佳行驶路径。v例7-4表7-10 客户数据信息客户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.207575第一步：求出各客户点的极坐标。第二步：扫描划分客户群。第三步：确定每辆车的最佳路径。图7-14 客户位置及扫描法求出的结果7676三、行车路线制订的节约法v基本思想：如果将运输问题中的两个回路合并成一个回路，就可缩短线路总里程（即节约了距离），并减少了一辆卡车。图7-15 节约法的图形描述7777v例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-154836439257165630574791553878781确定距离方阵 表7-12 客户及配送中心之间的距离配送中心客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13128171515201786162111150989172322171823282227010891513912141814200414202019222226243001116161620192221280651117911142204142087162301016461220068135120141979059160132008079792计算节约矩阵表7-13 第一次计算的节约矩阵客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13011211810973055100151514131272101153028181714611112420191916711214520292712422251280331462834151201572932161208161614110881012032181501916018080803将客户划归到不同的运输路线表7-14 第一次改进后的节约矩阵线路客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13123456789106 612130112118109730551001515141312721011530281817146111124201919167112145202927124222512803314628343415120157293216120816161411088101203218150191601808181表7-15第二次改进后的节约矩阵线路客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户131234566 689106 61213011211810973055100151514131272101153028181714611112420191916711214520292712422251280333314628343415120157293216120816161411088101203218150191601808282表7-16 第三次改进后的节约矩阵线路客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户13客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12客户131233 3566 689106 6121301121181097305510015151413127210115302828181714611112420191916711214520292712422251280333314628343415120157293216120816161411088101203218150191601808383图7-16 配送中心送货线路规划方案8484第五节 运输工具与货载的最优分配v一、航线配船优化问题v二、多车多品种货载配车优化8585一、航线配船优化问题（一）问题概述（二）数学模型的建立1 1参数说明2 2目标函数 min K=min K=3 3约束条件8686（三）航线配船优化举例表7-17 某船公司船型及航线与航次表7-18 不同航线和船型的营运成本123456型船（1500TEU），8艘232312型船（850TEU），12艘343423型船（500TEU），10艘444521航线船型季节最大航次数123456型船（1500TEU），8艘302528253532型船（850TEU），12艘242425243028型船（500TEU），10艘182020.518.52332航线船型单船单航次成本（万USD）8787表7-19不同航线的运量和机会成本解：（1 1）目标函数（2 2）约束条件（3 3）求解结果求解得出的航线最优配备船舶计划如下：航线123456机会成本（万USD/TEU）0.150.1250.10.10.150.125运量（TEU）600080005000450030007000123456型船（1500TEU），8艘003224型船（850TEU），12艘700001型船（500TEU），10艘011400航线船型航次数8888二、多车多品种货载配车优化（一）问题描述（二）模型建立1 1变量及参数说明2 2目标函数3 3约束条件（1 1）每辆车的载重能力限制：（2 2）每辆车的容积限制：（3 3）每一批货物最多只能装入一辆车：（4 4）变量约束：8989（三）启发式方法求解算例表7-20 货物信息表1 1启发式算法简介2 2求解步骤第一阶段：货物聚类（1 1）将每批货物看成是一类,记做G G1 1,G,G2 2,G,Gn n。计算其对应货物的容重比 。1234567891011121314vi(m3)2.43.60.535.43.51.42.426.42.41.21.80.5gi(t)312.50.6210.50.60.821.51219090（2 2）确定每批货物之间的距离d dijij，。计算出n n种货物间容重比距离d dijij(i,j=1,2,n)(i,j=1,2,n)，得到货物距离关系表记作 D(0)D(0)，见表7-217-21。表7-21 货物距离关系表D(0)cidijcjG1G2G3G4G5G6G7G8G9G10G11G12G13G140.83.60.252.73.52.842.53.21.61.20.90.5G10.80G23.62.80G30.20.63.40G454.21.44.80G52.71.90.92.52.30G63.52.70.13.31.50.80G72.820.82.62.20.10.70G843.20.43.811.30.51.20G92.51.71.12.32.50.210.31.50G103.22.40.431.80.50.30.40.8 0.70G111.60.821.43.41.11.91.2 2.40.91.60 G121.20.42.413.81.52.31.6 2.81.320.40 G130.90.12.70.74.11.82.61.9 3.11.62.30.70.30 G140.50.33.10.34.52.232.3 3.522.71.10.70.409191Q&A问答环节敏而好学，不耻下问。学问学问，边学边问。Heisquickandeagertolearn.Learningislearningandasking.9292感谢参与本课程，也感激大家对我们工作的支持与积极的参与。课程后会发放课程满意度评估表，如果对我们课程或者工作有什么建议和意见，也请写在上边结束语9393感谢您的观看与聆听本课件下载后可根据实际情况进行调整9494