第5章-运输配送系统模型与仿真

第五章运输配送系统模型与仿真第一节运输系统与配送系统概述第二节运输配送模型第三节单一车辆配送路线的优化第四节多车辆配送路线的优化第一节运输系统与配送系统概述一、运输与运输系统1、运输的定义运输是用设备和工具、将物品从一个地点向另一个地点运送的物流活动，其中包括集货、分配、搬运、中转、装入、卸下、分散等一系列操作。运输的功能运输可以创造出商品的空间效应和时间效应运输可以扩大商品的市场范围运输可以保证商品价格的稳定性运输能够促进社会分工的发展二、现代物流运输方式1、铁路运输2、公路运输3、水路运输4、航空运输5、管道运输三、运输系统1、商品运输系统的构成2、商品运输系统的设计与评价四、运输技术运输技术一般包括运输货物装载技术、运输线路的规划技术和网络分析技术等。1、运输货物装载技术轻重配载技术解体运输技术堆码技术2、运输线路的规划技术3、网络分析技术（1）设计运输网络图（2）计算每道运输工序所需时间（3）找出关键线路（4）计算各道运输工序最早和最迟的开工时间（5）计算各道运输工序的机动时间五、配送与配送系统1、配送的定义配送即是在经济合理区域范围内，根据客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。配送活动的包含内容（1）首先明确指出按用户订货的要求；（2）配送实质是送货，但与一般送货有区别；（3）配送是从物流节点至用户的一种特殊送货形式，（4）与送有机地结合；（5）合理的方式送交用户（6）对资源的配置作用配送的特点配送是一项经济性的活动配送是一项有计划有组织的活动配送是一种用户驱动性的活动配送是“配”和“送”的有机结合六、配送的基本活动1、集货2、储存3、分拣和理货4、配货5、配装6、配送运输7、送达服务8、配送加工七、配送的种类1、按配送商品种类及数量划分多品种、少批量配送少品种、大批量配送成套配送2、按配送时间及数量划分定时配送定量配送定时定量配送定时定量定点配送即时配送3、按配送地点划分配送中心配送配送点配送仓库配送商店配送生产企业配送八、配送作业方法1、配货作业方法（1）分货方式分货方式是将需配送的同一种货物，从配送中心集中搬运到发货场地，然后根据各用户对该种货物的需求量进行二次分配。（2）拣选方式拣选方式是用分拣车在配送中心分别为每个用户拣选其所需货物。2、配送区域划分3、车载货物的配装4、配送路线的确定（1）确定目标（2）确定配送路线的约束条件九、运输配送的合理化1、运输合理化（1）运输网络的合理配置（2）选择最佳的运输方式（3）提高运输效率（4）推动共同运输十、不合理运输的主要表现形式1、迂回运输2、过远运输3、对流运输4、倒流运输5、亏吨运输6、重复运输7、无效运输8、运力选择不当（1）弃水走陆（2）铁路、大型船舶的过近运输（3）运输工具承载能力选择不当9、托运方式选择不当第二节运输配送模型一、物资调运模型1、运输问题的模型和特征已知有m个生产地点Ai，i=1，2，……，m，可供应某种物资，其供应量分别为ai，i=1，2，……，m，有n个销地（需求地）Bj，j=1，2，……，n，其需求量分别为bj，j=1，2，……，n，从Ai到Bj运输单位物资的运价为Cij。运输问题的数学模型用表上作业法求解运输问题编制初始调运方案（西北角法和最小元素法）最优性检验确定最优方案详见书本例题产销不平衡的运输问题1、总产量大于总销量2、总销量大于总产量二、运输方式选择模型1、因素分析法模型（1）对要选择的运输方式，按重要性因素或其他尺度进行标定；（2）按各种不同标准，分别给各种运输工具打分；（3）对每种运输工具计算总分；（4）选择总分最高的运输方式。数学模型2、权重因素分析法模型三、层次分析法模型层次分析法（AHP）是美国运筹学家匹茨堡大学教授萨蒂(T.L.Saaty)于上世纪70年代初，为美国国防部研究“根据各个工业部门对国家福利的贡献大小而进行电力分配”课题时，应用网络系统理论和多目标综合评价方法，提出的一种层次权重决策分析方法。是对难以完全定量的复杂系统作出决策的模型和方法。决策是指在面临多种方案时需要依据一定的标准选择某一种方案。日常生活中有许多决策问题。举例：

1.在海尔、新飞、容声和雪花四个牌号的电冰箱中选购一种。要考虑品牌的信誉、冰箱的功能、价格和耗电量。

2.在泰山、杭州和承德三处选择一个旅游点。要考虑景点的景色、居住的环境、饮食的特色、交通便利和旅游的费用。

3.在基础研究、应用研究和数学教育中选择一个领域申报科研课题。要考虑成果的贡献（实用价值、科学意义），可行性（难度、周期和经费）和人才培养。1、层次分析法的基本原理

层次分析法根据问题的性质和要达到的总目标，将问题分解为不同的组成因素，并按照因素间的相互关联影响以及隶属关系将因素按不同层次聚集组合，形成一个多层次的分析结构模型，从而最终使问题归结为最低层(供决策的方案、措施等)相对于最高层(总目标)的相对重要权值的确定或相对优劣次序的排定。2、层次分析法的步骤和方法

运用层次分析法构造系统模型时，大体可以分为以下四个步骤：（1）建立层次结构模型（2）构造判断(成对比较)矩阵（3）层次单排序及其一致性检验（4）层次总排序及其一致性检验（1）建立层次结构模型将决策的目标、考虑的因素（决策准则）和决策对象按它们之间的相互关系分为最高层、中间层和最低层，绘出层次结构图。最高层：决策的目的、要解决的问题。最低层：决策时的备选方案。中间层：考虑的因素、决策的准则。对于相邻的两层，称高层为目标层，低层为方案层。例1大学毕业生就业选择问题获得大学毕业学位的毕业生，在“双向选择”时，用人单位与毕业生都有各自的选择标准和要求。就毕业生来说选择单位的标准和要求是多方面的，例如：①能发挥自己才干作出较好贡献（即工作岗位适合发挥自己的专长）；②工作收入较好（待遇好）；③生活环境好（大城市、气候等工作条件等）；④单位名声好（声誉等）；⑤工作环境好（人际关系和谐等）⑥发展晋升机会多（如新单位或前景好）等。工作选择可供选择的单位P1’P2，Pn

贡献收入发展声誉工作环境生活环境目标层准则层方案层目标层O(选择旅游地)P2黄山P1桂林P3北戴河准则层方案层C3居住C1景色C2费用C4饮食C5旅途例2.选择旅游地如何在3个目的地中按照景色、费用、居住条件等因素选择.将决策问题分为3个或多个层次：最高层：目标层。表示解决问题的目的，即层次分析要达到的总目标。通常只有一个总目标。中间层：准则层、指标层、…。表示采取某种措施、政策、方案等实现预定总目标所涉及的中间环节；一般又分为准则层、指标层、策略层、约束层等。最低层：方案层。表示将选用的解决问题的各种措施、政策、方案等。通常有几个方案可选。每层有若干元素，层间元素的关系用相连直线表示。层次分析法的思维过程的归纳层次分析法所要解决的问题是关于最低层对最高层的相对权重问题，按此相对权重可以对最低层中的各种方案、措施进行排序，从而在不同的方案中作出选择或形成选择方案的原则。（2）构造判断(成对比较)矩阵在确定各层次各因素之间的权重时，如果只是定性的结果，则常常不容易被别人接受，因而Santy等人提出：一致矩阵法，即：1.不把所有因素放在一起比较，而是两两相互比较。2.对此时采用相对尺度，以尽可能减少性质不同的诸因素相互比较的困难，以提高准确度。心理学家认为成对比较的因素不宜超过9个，即每层不要超过9个因素。判断矩阵是表示本层所有因素针对上一层某一个因素的相对重要性的比较。判断矩阵的元素aij用Santy的1—9标度方法给出。判断矩阵元素aij的标度方法标度含义1表示两个因素相比，具有同样重要性3表示两个因素相比，一个因素比另一个因素稍微重要5表示两个因素相比，一个因素比另一个因素明显重要7表示两个因素相比，一个因素比另一个因素强烈重要9表示两个因素相比，一个因素比另一个因素极端重要2，4，6，8上述两相邻判断的中值倒数因素i与j比较的判断aij，则因素j与i比较的判断aji=1/aij

设要比较各准则C1,C2,…,Cn对目标O的重要性A~成对比较阵A是正互反阵要由A确定C1,…,Cn对O的权向量选择旅游地目标层O(选择旅游地)准则层C3居住C1景色C2费用C4饮食C5旅途C1C2C3C4C5C1C2C3C4C5稍加分析就发现上述成对比较矩阵有问题成对比较的不一致情况一致比较不一致允许不一致，但要确定不一致的允许范围考察完全一致的情况可作为一个排序向量成对比较满足的正互反阵A称一致阵。

A的秩为1，A的唯一非零特征根为n

非零特征根n所对应的特征向量归一化后可作为权向量对于不一致(但在允许范围内)的成对比较阵A，Saaty等人建议用对应于最大特征根的特征向量作为权向量w

，即一致阵性质但允许范围是多大？如何界定？（3）层次单排序及其一致性检验对应于判断矩阵最大特征根λmax的特征向量，经归一化(使向量中各元素之和等于1)后记为W。

W的元素为同一层次因素对于上一层次因素某因素相对重要性的排序权值，这一过程称为层次单排序。能否确认层次单排序，需要进行一致性检验，所谓一致性检验是指对A确定不一致的允许范围。

定理：n阶一致阵的唯一非零特征根为n定理：n

阶正互反阵A的最大特征根

n,当且仅当

=n时A为一致阵由于λ

连续的依赖于aij

，则λ

比n

大的越多，A的不一致性越严重。用最大特征值对应的特征向量作为被比较因素对上层某因素影响程度的权向量，其不一致程度越大，引起的判断误差越大。因而可以用λ-n

数值的大小来衡量A的不一致程度。定义一致性指标:CI=0，有完全的一致性CI接近于0，有满意的一致性CI越大，不一致越严重RI000.580.901.121.241.321.411.451.491.51

n1234567891110为衡量CI的大小，引入随机一致性指标RI。方法为Saaty的结果如下随机一致性指标RI则可得一致性指标随机构造500个成对比较矩阵一致性检验：利用一致性指标和一致性比率<0.1及随机一致性指标的数值表，对进行检验的过程。一般，当一致性比率的不一致程度在容许范围之内，有满意的一致性，通过一致性检验。可用其归一化特征向量作为权向量，否则要重新构造成对比较矩阵A，对aij

加以调整。时，认为定义一致性比率：“选择旅游地”中准则层对目标的权向量及一致性检验准则层对目标的成对比较阵最大特征根=5.073权向量(特征向量)w=(0.263,0.475,0.055,0.090,0.110)T一致性指标随机一致性指标RI=1.12(查表)一致性比率CR=0.018/1.12=0.016<0.1通过一致性检验正互反阵最大特征根和特征向量的简化计算

精确计算的复杂和不必要

简化计算的思路——一致阵的任一列向量都是特征向量，一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。和法——取列向量的算术平均列向量归一化求

行

和

归

一

化精确结果:w=(0.588,0.322,0.090)T,=3.010（4）层次总排序及其一致性检验

计算某一层次所有因素对于最高层(总目标)相对重要性的权值，称为层次总排序。这一过程是从最高层次到最低层次依次进行的。对总目标Z的排序为的层次单排序为即B

层第i

个因素对总目标的权值为：（影响加和）层的层次总排序为：B层的层次总排序AB层次总排序的一致性检验设层对上层(层)中因素的层次单排序一致性指标为，随机一致性指为，则层次总排序的一致性比率为：当时，认为层次总排序通过一致性检验。层次总排序具有满意的一致性，否则需要重新调整那些一致性比率高的判断矩阵的元素取值。

到此，根据最下层（决策层）的层次总排序做出最后决策。记第2层（准则）对第1层（目标）的权向量为同样求第3层(方案)对第2层每一元素(准则)的权向量方案层对C1(景色)的成对比较阵方案层对C2(费用)的成对比较阵…Cn…Bn最大特征根1=3.0052=3.002

…

5

=3.0权向量w1(3)w2(3)…

w5(3)

=(0.595，0.277，0.129)=(0.082，0.236，0.682)=(0.166，0.166，0.668)选择旅游地第3层对第2层的计算结果

w(2)

0.2630.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.0820.47530.1420.4290.4290.0553.0090.1750.1930.6330.09030.6680.1660.1660.110组合权向量RI=0.58(n=3),

CIk

均可通过一致性检验方案P1对目标的组合权重为0.5950.263+0.475*0.082…=0.300方案层对目标的组合权向量为(0.300,0.246,0.456)T1.建立层次结构模型该结构图包括目标层，准则层，方案层。层次分析法的基本步骤归纳如下3.计算单排序权向量并做一致性检验2.构造成对比较矩阵从第二层开始用成对比较矩阵和1~9尺度。对每个成对比较矩阵计算最大特征值及其对应的特征向量，利用一致性指标、随机一致性指标和一致性比率做一致性检验。若检验通过，特征向量（归一化后）即为权向量；若不通过，需要重新构造成对比较矩阵。计算最下层对最上层总排序的权向量。4.计算总排序权向量并做一致性检验进行检验。若通过，则可按照总排序权向量表示的结果进行决策，否则需要重新考虑模型或重新构造那些一致性比率较大的成对比较矩阵。利用总排序一致性比率第三节单一车辆配送路线的优化一、起迄点不同的单一路线优化（一）动态规划法首先，根据网络结构特征将整个线路网络划分成相应个数阶段；其次，对每个阶段的决策问题求解。通常采用从终点到起点的逆序法进行决策；对于每一阶段，以初始状态为基础确定下一阶段的可选状态，并计算各状态的代价，然后从中选择代价最小的状态。（二）标号法在一个连通的网络图G(V,E)中，点集V＝｛v1,v2,…,vn｝,边集E｛e1,e2,…,em｝，标号法适合于每条边上权数cij不小于零的情况。该算法也称双标号法，也就是对图中的每个点vj赋予两个标号，即T标号和P标号。凡是已经得到P标号的点，则说明已求出v1点到改点的最短路，凡是没有得到P标号的点，就标上T标号。不断进行搜索、计算，每一步都是将某一点的T标号改变为P标号的过程。标号法的基本原理：若点序列｛vs,v1,v2,…,vn-1,vn｝是从vs到vn的最短路，则：｛vs,v1,v2,…,vn-1｝必定是从到vn-1的最短路。〔例〕书本226页。二、起迄点重合的单一路线优化物流管理人员经常会遇到起讫点相同的路径规划问题。起讫点重合的路径问题一般被称为“流动推销员”问题，人们已提出不少方法来解决这类问题。如果某个问题中包含很多个点，要找到最优路径是不切实际的，因为许多现实问题的规模太大，即使用最快的计算机进行计算，求最优解的时间也非常长。（一）各点空间相连实际生活中，可以利用人类的模式认知能力很好地解决“流动推销员”问题。我们知道，合理的经停路线中各条线路之间是不交叉的，并且只要有可能路径就会呈凸形，或水滴状。（二）旅行商问题模型

TSP模型：在一个由n个顶点构成的网络中，要求找出一个包括所有顶点的具有最小耗费的环路。（三）中国邮递员问题图论的相关概念：“顶点”表示某对象节点；“边”表示对象之间的某种特性；边上的非负数字称为“权”；以V为顶点的边的数目称为顶点V的“次”；次为奇数的点，称为奇点，次为偶数的点，称为偶点；由点、边交替构成的序列称为“链”；起点与终点相同的链就称为“圈”。若一个圈中没有重复的边，这个就是欧拉圈；若一个图中含有欧拉圈，此图就是欧拉图。当且仅当图中每一个顶点都是偶点时，一个图才是欧拉图。中国邮递员问题的解决步骤：每边先过一次；在每边上增加的重复边最多一条；在每个圈上重复的长度小于等于圈总长的一半。第四节多车辆配送路线的优化一、问题描述某物流中心要为q个客户提供服务。已知每个客户点的地理位置及其货运需求量，物流中心需要调用多辆货车来满足这些客户的服务需求，每辆汽车的载重量一定。要求指派多辆货车，为每辆货车分配一定的服务客户，并确定服务的顺序，即行车的路径，目标是使总服务成本最低。二、扫描法(TheSweepMethod)扫描法步骤如下：在地图或方格图中确定所有站点(含仓库)的位置（极坐标）。自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑，如果在某线路上增加该站点，是否会超过车辆的载货能力?如果没有，继续旋转直线，直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力(先使用最大的车辆)。如果超过，就剔除最后的那个站点，并确定路线。随后，从不包含在上一条路线中的站点开始，继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到路线中。排定各路线上每个站点的顺序使行车距离最短。排序时可以使用“水滴”法成求解“流动推销员”问题的任何算法。合理路线确定的基本原则（1）安排车辆负责相互距离最接近的站点的货物运输。

（2）安排车辆各日途经的站点时，应注意使站点群更加紧凑（3）从距仓库最远的站点开始设计路线（4）卡车的行车路线应呈水滴状（5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的（6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货（7）对过于遥远而无法归入群落的站点，可以采用其它配送方式三、节约用法(TheSavingsMethod)节约法是一种颇为出色的方法，它能够灵活处理许多现实中的约束条件，对站点数量不太多的问题能较快算出结果，且结果与最优解很接近。节约法的目标是使所有车辆行驶的总里程最短，并进而为所有站点提供服务的卡车数量最少。该方法首先假设每一个站点都有一辆虚拟的卡车提供服务，随后返回仓库，如图a所示。这时的路线里程是最长的。下一步，将两个站点合并到同一条行车路线上，减少一辆运输车，相应地缩短路线里程。在决定哪些站点要合并到一条路线时，需要计算合并前后节约的运输距离。由与其它任何点不在一条运输路线上的两点(A和B)合并所节约的距离就是图a中路线的里程减去图b中路线的里程，节约值为S＝doa＋dbo－dab。对每对站点都进行这样的计算，并选择节约距离最多的一对站点合并在一起，修订后的路线见图b。节约法强大的处理能力使得它能够包含实际应用中许多重要的约束条件。该方法可以在指定各路线途经站点的同时确定站点的先后顺序。因此，在将站点归入某条路线之前，应该预先考查加入新站点后路线的情况。此外，还要考虑一系列有关路线规划的问题，如行车时间是否超过允许的最长驾驶时间，是否满足司机休息时间的要求，是否有足够载运量的车辆装载所有的货物，各站点时间窗口的要求是否满足等等。不满足这些条件可能导致该站点不能并入这条路线或者说明该站点在新路线中的排列顺序不当。接着就要按照最大节约值原则选取下一个站点，重复考虑上述问题。因为扩展问题的难度较大，节约法不能保证将得到最优解，但能够获得合理解。例：有一配送中心（Q）要向10个用户配送，配送距