物流运输管理

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第七章,物流运输优化与决策,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 20250,4,三、承运人的选择与评价,（一）影响承运人选择的主要因素,1,运输成本,2,运输时间和运输时间的可靠性,3,可到达性,4,服务能力,5,安全性,5,（二）承运人的评价方法,综合因素加权求和法,表,7-3,承运商评估报告示例,承运人：,_,时期,:_,6,第二节 货物运输调配决策,一、多起迄点间的直达运输,二、存在中间转运的物资调配,7,一、多起迄点间的直达运输,（一）产销平衡的运输问题,1,产销平衡运输问题数学模型,2,求解方法,单纯形法、表上作业法,图,7-1,多点之间的物资运输调拨问题示意图,8,（二）产销不平衡的运输问题,1,总产量大于总销量：,则增加一个假想的销地,B,n+1,，其销量为：,2,总销量大于总产量：,则增加一个假想的产地,A,m+1,，其产量为：,9,二、存在中间转运的物资调配,（一）问题描述,图,7-2,有中间转运的物资运输调拨问题,10,（二）数学模型,目标函数为：,约束条件为：,（,1,）配送量,生产能力的限制：,k=1,，,2,，,，,f,；,（,2,）流通中心发送能力的限制：,i,1,，,2,，,，,m,；,（,3,）满足零售店需求量：,j=1,，,2,，,，,n,；,（,4,）变量非负：,11,（三）求解方法,运输问题表上作业法：,例,7-2,表,7-4,各点间运输单位费用,12,表,7-5,需求和供应量确定准则,转运问题中点的性质,在运输表中的供应值,在运输表中的需求值,供应点,起始供应,+,总供应,总供应,转运点,总供应,总供应,需求点,总供应,起始需求,+,总供应,空 点,0,起始供应起始需求,表,7-6,最终运输表,13,第三节 物流运输线路的优化,一、起迄点不同的单一路线优化,二、起迄点重合的单一路线优化,14,一、起迄点不同的单一路线优化,归结为运筹学中的最短路径问题,图,7-3,从起点到终点的运输网络图,15,动态规划方法,B,1,A,C,3,F,2,F,1,E,3,E,2,E,1,D,3,D,2,D,1,C,4,C,2,C,1,B,2,G,第一阶段,第二阶段,第三阶段,第四阶段,第五阶段,第六阶段,5,3,1,3,6,8,7,6,6,8,3,5,3,4,2,1,3,8,2,2,3,3,3,5,5,2,6,6,4,3,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,该点到,G,点的最短距离,16,（一）动态规划法,图,7-4,多阶段划分,5,2,8,7,12,20,14,19,19,17,（二）,Dijkstra,方法,例,7-3,图,7-5,运输网络图,18,E.W.Dijkstra,算法（标号算法）,算法基本思路分析：（逐步向外搜索）,5,2,1,6,5,8,2,8,9,9,7,2,2,1,2,1,0,2,5,2,7,5,11,12,12,10,5,7,5,6,6,7,9,9,10,10,6,3,3,x,y,起点到,该点的,最短距,离,起点到,该点的,最短距,离的,上,界,19,（二）,Dijkstra,方法,例,7-3,图,7-5,运输网络图,0,0,2,5,4,2,9,4,4,4,8,7,7,14,8,13,20,表,7-8 Dijkstra,算法步骤表,步骤,P,标号点,与,P,点直接相连的,T,标号点,相应的总距离,第,n,个,最近点,最小总距离,最新连接,1,O,A,2,A,2,OA,2,O,A,C,B,4,2+2=4,C,B,4,4,OC,AB,3,A,B,C,D,E,E,2+7=9,4+3=7,4+4=8,E,7,BE,4,A,B,E,D,D,D,2+7=9,4+4=8,7+1=8,D,D,8,8,BD,ED,5,D,E,T,T,8+5=13,7+7=14,T,13,DT,21,A,起点,90,B,138,348,66,C,90,84,E,96,D,156,48,75,F,120,50,132,I,H,48,G,150,126,126,J,终点,22,二、物流运输的优化模型,按货物的自然流向组织货物合理的物流运输是市场经济规律的客观要求，它直接决定着物流的效率与效果。为了制定在产销平衡条件下的运量规划方案，必须建立数学模型，运用数学方法来解决。,23,三、单纯形法,对于运输问题，一般采用单纯形法求解，具体方法和步骤已在前面介绍过，这里不再列述。经验表明，当起运站和目的地都多于,5,个时，用其它方法求解比较困难或繁琐，最好用单纯形法求解。,24,四、图表分析法,图表分析法是在分区产销平衡所确定的供销区域内，按照生产地与消费地的地理分布，根据有利于生产、有利于市场供给、近产近销的原则，应用交通路线示意图和商品产销平衡表找出产销之间经济合理的商品运输路线。,25,五、图上作业法,26,1,运输线路不成圈的图上作业法,27,28,29,30,2,运输线路成圈的图上作业法,运输线路成圈，就是形成闭合回路的“环”形路线，包括一个圈（有三角形、四边形、多边形）和多个圈。成圈的线路流向图要同时达到既无对流现象、又无迂回现象的要求才是最优流向图。,对于成圈运输线路的图上作业法，可按下述三个步骤寻求最优方案，,如表,9-22,所示,。,31,表,9-22,成圈运输线路的图上作业法的步骤,步骤,详 述,去段破圈确定初始运输方案,就是在成圈的线路中，先假设某两点间的线路“不通”，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；按照运输线路不成圈的图上作业法，即可得到初始运输方案。,检查有无迂回现象,因为流向箭头都统一画在线路右边，所以圈内圈外都画有一些流向。分别检查每个小圈，如果圈内和圈外流向的总长度都不超过全圈总长度的,1/2,，那么，全圈就没有迂回现象了，这个线路流向图就是最优的，对应的就是最优运输方案。否则转向第三步。,重新去段破圈，调整流向,在超过全圈总长,1/2,的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的各段上，加上减去的最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直到得到最优线路流向图为止。,如果全圈存在两个及两个以上的圈，则需分别对各圈进行是否存在迂回线路的检查，如果各圈的里、外圈都不超过全圈总线长的,1/2,，则不存在迂回现象，此方案为最优运输方案。,32,(13),(18),33,34,35,最小树问题,与网络设计,树（,Tree,）和最小树,树是图论中一类重要的图，实际中很多系统的结构都是树。,树,连通且不含圈的图，简记为,T,。,树的性质：,（,1,）在树中，任意两个顶点间必有且仅有一条链；,（,2,）在树中，在不相邻的顶点中添加一条树枝，则恰好得到一个圈；,（,3,）在树中，任意去掉一条树枝，就变成分离图；,（,4,）设,T,是棵有,n,个顶点的树，则,T,的树枝数为,n-1,；,（,5,）一棵树至少有两个悬挂点；,（,6,）树是连通且边数最少的图。,36,最小树问题,树（,Tree,）和最小树,树的权,若,T,k,是加权图,G,的一棵树，则树,T,的全部边的权之和称为树,T,k,的权，记为 （,T,k,）,= ,（,e,）； ,e T,k,最小树,T,*,是加权图,G,的一棵,最小,树，即（,T,*,）,=min (T,k,) ,37,最小树问题,树（,Tree,）和最小树,破圈法，避圈法求最小,支撑树：,图,G,1,5,4,2,4,5,3,1,3,4,4,2,1,5,1,2,最小支撑树,T,最小支撑树,T,1,2,1,2,1,1,2,1,2,3,1,2,1,1,2,3,38,案例：,几家石油公司准备联合建设一个输油管道来连接西南地区、东南地区和中西部地区的城市，网络图如下图所示，其中各个城市之间的英里数显示在各个分支上。确定用最少距离的管道连接,10,个城市的管道系统并计算出需要使用多少英里的管道。,39,2,9,10,8,7,4,5,6,3,1,丹佛,奥马哈,得梅因,印第安纳,波利斯,阿尔伯克基,俄克拉何马城,小石城,纳什维尔,圣路易斯,堪萨斯城,400,490,520,450,750,240,310,580,210,120,250,250,235,340,260,270,320,260,340,40,练习：,我校拟设立一个网络将主要的校园建筑与计算机中心连接起来提高网络服务。一些电缆需要埋到地下，主要利用现有的电缆通道来架设。如下网络显示了节点,1,计算机中心与不同建筑物之间连接的各个分支及其距离，试确定网络中可以连接所有建筑物的最小树及需要的总的电缆长度。,41,2,9,10,8,7,4,5,6,3,1,12,14,11,13,86,98,48,82,114,52,35,39,127,56,48,29,58,102,80,186,311,38,208,92,105,62,71,83,276,93,71,64,57,42,网络流（,Flow,）与最大流问题,最大流问题是一类应用极为广泛的问题，如运输网络中的人流、车流、物流，供水网络中的水流，金融系统中的现金流，通信系统中的信息流，等等。,20,世纪,50,年代,Ford Fulkerson,建立的“ 网络流理论 ”，是网络应用的重要组成部分。,43,一、基本概念,1,容量网络：,（,1,） 容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最大可能负载）称为该,弧的容量,。记为,:,C,（,v,i,，,v,j,）或,C,ij,，也常记为,b,ij,。,（,2,） 容量网络：对所有的弧都给出了容量的有向网络，记为,D=,（,V,，,A,，,C,）或,D=,（,V,，,A,，,B,）。,44,（,1,）,流,：,弧上的流,网络中加在弧上的负载 量。记为,f,ij,或,x,ij,。,图上的流,加在网络中各条弧上,的一组负载量（即定义在弧集上的一个函数）。记为,f=f,（,v,i,，,v,j,）,=f,ij,2,流与可行流,（,2,）,零流,：若网络上所有弧上的流均为,0,，即对所有的,i,和,j,，都有,f,ij,=0,，则称相应的图上的流为零流。,45,（,3,）,可行流,：,在容量网络上，满足容量限制条件和中间点平衡条件（连续性定理）的,图上的流。,即,0f,ij,c,ij,;,其中,f,为网络中从起点,s,到终点,t,的流量。,问： 零流是不是可行流？,46,3,割（割集、截集）：,设,V,为网络中所有顶点的集合，,将,V,剖分为两个子集 和 ，满足,:,称,弧集,为分离起点和终点的的,割集,。组成割集的各条弧容量之和称为,割容量,（截量），所有割集中容量最小的割集称为,最小割,。,47,4,、,弧的分类,（,1,）在可行流,f,=f,ij,中，按流量的特征分有：,饱和弧,f,ij,=c,ij,非饱和弧,f,ij,0,48,（,2,）,在容量网络中从起点,v,s,到收点,v,t,的一条链中，按弧的方向分,前向弧,与链的方向一致的弧。前向弧全体记为,+,；,后向弧,与链的方向相反的弧。后向弧全体记为,-,；,其中,链的方向规定为,:,从起点,v,s,指向终点,v,t,。,49,例：,：,S,，,e,1,，,V,1,，,e,2,，,V,2,，,e,3,，,V,4,，,e,4,，,V,3,，,e,5,，,T,V,2,T,V,1,S,V,3,V,4,e,1,e,2,e,3,e,4,e,5,e,7,e,6,e,8,e,9,+,=,：,e,1,，,e,3,，,e,5,=,：,e,2,，,e,4,50,5.,增广链（流量修正路线）,：,设,f,是一可行流，,是从起点,v,s,到终点,v,t,的一条链，若,满足下面两个条件，则称,为关于可行流,f,的一条,增广链,：,在弧（,v,i,，,v,j,）,+,上，,0f,ij,c,ij,（即前向弧均为非饱和弧）,在弧（,v,i,，,v,j,）,-,上，,0 f,ij,c,ij,（即后向弧均为非零流弧）,51,二、什么是最大流问题？,在满足容量限制条件和中间点平衡条件的要求下，求取流量值达到最大的可行流的一类优化问题。简言之，是求容量网络中具有,最大流量值,的,可行流,问题。,所求出的该可行流称为最大流。,52,三、,Ford-Fulkerson,标记化方法的理论基础,最大流最小割定理（最大流量最小截量定理）,在任一容量网络中，从发点到收点的最大流流量等于该网络最小割的割容量。,53,网络最大流问题的标号算法,1,确定初始可行流。,如果没有给定，也难以观察得出，则将零流作为初始可行流；,2,标号过程（目的是用标号法寻求增广链）,（,1,）标号的意义,符号,v,i,（,v,j,i,）表示,v,i,点的标号是（,v,j,，,i,） ，其中,v,j,表示点,v,i,的标号来自,v,j,，,i,表示流量的修正量。,54,(2),标号过程,给起点标上标号（,0,，,+,）；,考察起点的所有相邻未标号点：,对正向弧,(v,s,v,j,),， 检查其是否饱和？,是，则不加标记；不是，则加标记为,(v,s,j,),， 其中,j,=c,sj,-f,sj,；,对反向弧检查其是否是零流弧？,是，则不加标记；不是，则加标记为,(-v,s,j,),，其中,j,=f,sj,；,55,重复步骤二，但要注意把,v,s,换成已得到标号的点；可能出现两种结局：,a.,标号过程中断，收点得不到标号。说明该网络中不存在增广链，现行的可行流就是最大流；,b.,收点得到标号，反向追踪即可找到一条从起点到收点由标号点及相应的弧连接而成的增广链。,56,3,调整过程,修改流量，其中流量调整量 ，,指增广链上所有弧的流量修正量；,在增广链的正向弧上增加 ；,反向弧上减少 ；,其它弧上流量不变。,调整方法,：,57,v,s,v,1,v,2,v,3,v,4,v,t,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(5,3),(2,1),(v,s,4),(-v,1,1),(v,2,1),(-v,2,1),(v,3,1),(5,2),(1,0),(1,0),(2,2),(v,s,3),例：弧旁的数是（,c,ij,f,ij,),：（容量，流量）,最大流为,5.,58,案例：,联邦航空局（,FAA,）批准给全航空一个新的航空许可，准许它运行从洛杉矶到芝加哥的多条航线。每条航线的航班数显示在下图网络中，确定每天从洛杉矶到芝加哥的最大航班数，并确定每条路线的航班数。,59,1,2,3,5,4,6,7,8,10,5,8,6,7,5,4,4,7,6,5,7,8,洛杉矶,凤凰城,达拉斯,丹佛,圣路易斯,芝加哥,盐湖城,堪萨斯城,60,v,s,v,t,(4,3),(1,1),(7,6),(3,2),(3,2),(4,3),(2,2),(8,2),(4,1),(3,2),(4,3),(5,3),练习：求下图所示网络的最大流。（,c,ij,f,ij,),61,二、起迄点重合的单一路线优化,（一）旅行商问题,TSP,模型,0-1,整数规划模型,图,7-6 TSP,问题示意图,代价矩阵,C,ij,变量矩阵,62,（二）中国邮递员问题,1,确定可行方案,2,判断最优方案,63,第四节 行车路线及时刻表的制定,一、运输路线及时刻表制订的原则,二、行车路线制订的扫描法,三、行车路线制订的节约法,64,合理路线和时刻表的制定原则,（,1,）安排车辆负责相互距离最接近的站点的货物运输。,图,7-11,合理的车辆分派方案,图,7-12,不合理的车辆分派方案,一、运输路线及时刻表制订的原则,65,(2),安排车辆各日途经的站点时，就注意使站点群更加紧凑。,仓库,F,F,F,F,F,T,T,T,T,T,T,F,T,a),不合理的线路划分方式：线路交叉,66,b),较合理的线路划分方式,仓库,F,F,F,F,F,T,T,T,T,T,T,F,T,67,(3),从仓库最远的站点开始设计路线。,要设计出有效的路线，首先要划分出距仓库最远的站点周围的站点群，然后逐步划出仓库附近的站点群。一旦确定了最远的站点就应该选定距该核心站点最近的一些站点形成站点群，分派载货能力能满足该站点群需要地卡车。然后，从还没有分派车辆的其他站点中找出距仓库最远的站点，分派另一车辆。如此往复，直到所有站点都分派有车辆。,68,图（,a,）是不合理的运行路线，图（,b,）是合理的运行路线。,图,7-13,运输路线示意图,（,4,）卡车的行车路线不交叉，且应呈水滴状。,69,（,5,）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的。,（,6,）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。,（,7,）对过于遥远而无法归入群落的站点，可以采用其它配送方式。,70,行车路线和时刻表的制定方法,1,、扫描法,（,1,）在地图或方格图中确定所有站点的位置。,（,2,）自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑：如果在某线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力。如果超过，就剔除最后的那个站点。继续这一过程直到所有站点得到安排。,（,3,）排定各路线上每个站点的顺序使行车距离最短。排序时可使用水滴法。,71,案例：,Smith,卡车运输公司用厢式货车从货主那里取货。货物先运回仓库，集中后以更大的批量进行长途运输。下图列出了一天的取货量，厢式货车的载货量是,1000,件。完成所有取货任务一般需要整整一天的时间。公司想知道需要多少条运输路线（即多少部车），每条路线上应该经过哪些站点，每条路线上的站点应该怎样排序。,72,仓库,2000,2000,2000,2000,3000,1000,4000,2000,3000,3000,2000,1000,地理区域,取货点,73,仓库,2000,2000,2000,2000,3000,1000,4000,2000,3000,3000,2000,1000,路线,1,路线,2,路线,3,74,二、行车路线制订的扫描法,原理,:,先以仓库,(,物流中心,),为原点，将所有需求点的极坐标算出，然后依角度大小以逆时针或顺时针方向扫描，若满足车辆装载量即划分为一群，将所有点扫描完毕后在每个群内用最短路径法求出车辆最佳行驶路径。,例,7-4,表,7-10,客户数据信息,客户,1,2,3,4,5,6,7,8,9,10,11,12,13,D,i,(,吨,),1.9,2.8,3.15,2.4,2,3,2.25,2.5,1.8,2.15,1.6,2.6,1.5,X,i,20.0,18.8,18.3,19.1,18.8,18.6,19.5,19.93,20.0,19.5,18.7,19.5,20.3,Y,i,4.80,5.17,5.00,4.78,6.42,5.88,5.98,5.93,5.55,4.55,4.55,5.19,5.20,75,第一步：求出各客户点的极坐标。,第二步：扫描划分客户群。,第三步：确定每辆车的最佳路径。,图,7-14,客户位置及扫描法求出的结果,76,三、行车路线制订的节约法,基本思想：如果将运输问题中的两个回路合并成一个回路，就可缩短线路总里程（即节约了距离），并减少了一辆卡车。,图,7-15,节约法的图形描述,77,例,7-5,表,7-11,客户坐标及订单规模,站点,X,坐标,Y,坐标,订单规模（件）,配送中心,顾客,1,顾客,2,顾客,3,顾客,4,顾客,5,顾客,6,顾客,7,顾客,8,顾客,9,顾客,10,顾客,11,顾客,12,顾客,13,0,0,6,7,9,15,20,17,7,1,15,20,7,2,0,12,5,15,12,3,0,-2,-4,-6,-6,-7,-9,-15,48,36,43,92,57,16,56,30,57,47,91,55,38,78,1,确定距离方阵,表,7-12,客户及配送中心之间的距离,79,2,计算节约矩阵,表,7-13,第一次计算的节约矩阵,80,3,将客户划归到不同的运输路线,表,7-14,第一次改进后的节约矩阵,81,表,7-15,第二次改进后的节约矩阵,82,表,7-16,第三次改进后的节约矩阵,83,图,7-16,配送中心送货线路规划方案,84,第五节 运输工具与货载的最优分配,一、航线配船优化问题,二、多车多品种货载配车优化,85,一、航线配船优化问题,（一）问题概述,（二）数学模型的建立,1,参数说明,2,目标函数,min K=,3,约束条件,86,（三）航线配船优化举例,表,7-17,某船公司船型及航线与航次,表,7-18,不同航线和船型的营运成本,航线,船型,季节最大航次数,航线,船型,单船单航次成本,（万,USD,）,87,表,7-19,不同航线的运量和机会成本,解：（,1,）目标函数（,2,）约束条件（,3,）求解结果,求解得出的航线最优配备船舶计划如下：,航线,1,2,3,4,5,6,机会成本（万,USD/TEU,）,0.15,0.125,0.1,0.1,0.15,0.125,运量（,TEU,）,6000,8000,5000,4500,3000,7000,航线,船型,航次数,88,二、多车多品种货载配车优化,（一）问题描述,（二）模型建立,1,变量及参数说明,2,目标函数,3,约束条件,（,1,）每辆车的载重能力限制：,（,2,）每辆车的容积限制：,（,3,）每一批货物最多只能装入一辆车：,（,4,）变量约束：,89,（三）启发式方法求解算例,表,7-20,货物信息表,1,启发式算法简介,2,求解步骤,第一阶段：货物聚类,（,1,）将每批货物看成是一类,记做,G,1,G,2,G,n,。计算其对应货物的容重比 。,90,（,2,）确定每批货物之间的距离,d,ij,， 。计算出,n,种货物间容重比距离,d,ij,(i,j=1, 2, , n),，得到货物距离关系表记作,D(0),，见表,7-21,。,表,7-21,货物距离关系表,D(0),91,（,3,）比较,D(0),中的每个非零元素,d,ij,，如果任意,d,ij,小于临界值,C,则停止。如果存在某个,d,ij,大于,C,则继续下一步。,（,4,）把距离最大的两批货物合并成一个新类，记做,G,n+1,，取消原来的两个类，若存在多个这样的类，则同时合并。,（,5,）重新计算各类之间的距离，得到降一阶的新距离矩阵,D(1),，见表,7-22,。,表,7-22,货物距离关系表,D(1),92,（,6,）对,D(1),重复步骤（,4,）,（,5,），直到所有,d,ij,小于临界值,C,为止。得表,7-23,所示的货物距离关系表。,表,7-23,货物距离关系表,D,（,1,）,货物编号,聚类名称,货物品种,v,i,(m,3,),g,i,(t),c,i,i,1,19,3,4,5,8.9,5.1,1.75,i,2,17,1,2,6,4,1.5,i,3,20,10,12,7.6,3,2.53,i,4,18,6,13,5.3,3,1.77,i,5,16,8,14,2.9,1.6,1.81,i,6,11,11,2.4,1.5,1.6,i,7,9,9,2,0.8,2.5,i,8,7,7,1.4,0.5,2.8,（,7,）对货物进行聚类分组得到新的待装货物，见表,7-24,。,表,7-24,新待装货物信息表,93,第二阶段：货物配装,对聚类后的新货物进行装载，得到最终装载方案，如表,7-25,。,表,7-25,配装方案表,车辆编号,货物编号,聚类名称,货物品种,重量（,t,）,体积（,m,3,）,1,i,1,19,3,4,5,8.9,5.1,2,i,2, i,7, i,8,17,7,9,1,2,7,9,9.4,5.3,3,i,3, i,6,11,20,10,11,12,10,4.5,4,i,4, i,5,16,18,6,13,8,14,8.2,4.6,94,