物流设计大赛稿件(智联队).docx

《物流设计大赛稿件(智联队).docx》由会员分享，可在线阅读，更多相关《物流设计大赛稿件(智联队).docx（34页珍藏版）》请在三一办公上搜索。

1、黑体初号，居中中文题目黑体二号，居中第三届物流设计大赛案例英文题目Arial二号，大写，居中队伍名称智联队学生姓名黑体三，居中 学生姓名 学生姓名 学生姓名 学生姓名 2012年10月25日目 录前言 -41公司概况 -41.1 安吉汽车物流公司简介-41.2 SWOT环境分析-51.3 本章小结-52.汽车物流运输方式及线路的优化-52.1基于运用AHP分析方法的物流运输方式选择-52.1.1AHP分析方法概述-62.2问题的模型建立-62.2.1层次分析法-62.2.1.1层次分析法的基本原理与步骤-72.2.1.2 递阶层次结构的建立与特点-72.2.3 构造判断矩阵-72.2.1.4

2、层次单排序及一致性检验-82.2.1.5 层次总排序及一致性检验-82.1.6相对重要程度的计算-82.3汽车物流运输方式及线路的优化-82.3.1问题的背景分析-92.3.2DHGF综合算法的原理-102.3.3问题的求解-112.3.3.1 Floyd算法的基本原理-122.3.3.2 Floyd算法构造距离矩阵的原理-132.3.3.3 Floyd算法步骤-132.3.3.4回溯法求最短路径-142.3.3.5 改进Floyd算法原理-142.3.3.6 改进Floyd算法的计算步骤-152.4总结-153 案例12循环取货的优化- 163.1物流的概述- - -163.1.1 物流行业

3、概况- - -163.1.2 五力竞争分析- -163.1.3 竞争者分析- - -163 .1.4 合理规划运输路线- -163.1.4 本章小结- -17 3.2物流概念-173.2.1 循环取货Milk-run - -173.2.2 JIT 模式 - -183.2.3 精益物流 - -183.2.4 供应商管理的库存- - 183.2.5 第三方物流TPL - -193.2.6 本章小结- -203.3传统的入厂物流模式与循环取货- -20 3.3.1 传统模式分析- - 22 3.3.2 循环取货的优缺点- -22 3.3.3 循环取货的可行性- -24 3.3.4 本章小结- -24

4、3.4 方案优化- 25 3.4.1 如何选择路径- 26 3.4.2 突发状况的解决方案- - - 27 3.4.3 装载优化- -29 3.4.4 制度优化- -313.4.5 本章小结- -34信息来源- -34前言中国经济的持续发展和人民生活水平的日益提高，中国市场的汽车消费迅速膨胀，为中国汽车物流企业提供了广阔的市场需求空间，促进了中国汽车物流企业的发展壮大。汽车物流是汽车供应链上原材料、零部件、整车以及售后配件在各个环节之间的实体流动过程。广义的汽车物流还包括为废旧汽车回收提供的物流服务。汽车物流在汽车产业链中起到桥梁和纽带的作用，是实现汽车产业价值流顺畅流动的根本保障，也是物流领

5、域的重要组成部分，具有与其他物流种类所不同的特点。汽车物流业是一个蓬勃发展的行业，巨大的国内外市场潜力给汽车物流业带来了机遇和挑战，中国汽车物流企业已经到了大变革的关键时刻。那么，应如何改善物流业所面临的外部环境，促进汽车物流企业的可持续发展？作为行业领先者的安吉物流，又该如何应对上述种种挑战，在当前环境下从自身运作着眼寻求新的突破和持续发展？ 本案为安吉物流的整车运输方式选择和线路优化以及零部件配送进行了分析和提出改进方案。1 安得汽车物流公司简介安吉汽车物流有限公司成立于 2000 年 8 月，是上汽集团旗下的全资子公司。安吉物流是全球业务规模最大的汽车物流服务供应商，共有员工17,000

6、人，拥有船务、铁路、公路等10家专业化的轿车运输公司以及50家仓库配送中心，仓库总面积超过440万平方米，年运输和吞吐量超过570万辆商品车，并且全部实现联网运营。公司以“服务产品技术化”的理念，从事汽车整车物流、零部件物流、口岸物流以及相关物流策划、物流技术咨询、规划、管理培训等服务。提供一体化、技术化、网络化、透明化、可靠的独特解决方案的物流供应链服务。 在此众所周知主要了解零部件物流的概况，零部件物流板块以安吉物流下属上海安吉汽车零部件物流有限公司（以下简称“安吉零部件”）为主体。安吉零部件是国内汽车物流业首家经国家交通部、外经贸部正式批准、注册资本最大的汽车物流中外合资企业。公司注册资

7、本为3000万美元，中外双方各占50%股份。公司主要从事与汽车零部件相关的物流和与汽车相关的国内货运代理服务、整车仓储、物流技术咨询、规划、管理、培训等服务以及国际货运代理、汽车零部件批发、进出口及相关配套服务，是一家专业化运作，能为客户提供一体化、技术化、网络化、可靠的、独特解决方案的第三方物流供应商。安吉零部件目前拥有整车物流仓库24个，总面积超过440万平方米；入厂零部件物流仓库10个，面积总计52万平方米，以及420辆运输车辆；售后零部件物流仓库14个，面积总计15万平方米。拥有移动装卸设备近400辆。安吉零部件在全国各地分布着6家合资公司和18家分公司，核心业务是入厂物流、售后物流、

8、网络运输、整车仓储、进出口物流。目前服务的客户主要有上海大众、上海通用、上海汽车、上汽通用五菱、上汽大通、上汽依维柯红岩、上汽汇众、一汽丰田、华晨宝马、长城汽车、河南宇通、伊顿、TRW、法雷奥、菲亚特、华域汽车等。“海纳百川，有容乃大。”公司矢至于创建多客户、多业务的统一平台，通过自身的不断完善以及与业界同行的战略合作，构筑了遍布全国并延伸至海外的物流服务网络；基于以人为本的理念，公司始终贯彻“投资于人”的经营方针，将努力培养一支“国际化、专业化”的优秀团队视为公司的核心竞争力。 “海阔凭鱼跃，天高任鸟飞。”中国汽车工业的蓬勃发展为众所周知描绘了广阔的未来，相信通过全体“安吉人”的共同创造，必

9、将实现公司“成为国内领先，国际一流的专业汽车供应链管理和服务供应商”的远大目标，为中国现代汽车物流业的发展作出众所周知积极的贡献！ 物流行业现状/特点、发展趋势1运输作为物流的基本功能之一，在整个物流环节中占有十分重要的地位。根据相关统计，物流运输成本占物流总成本的50以上，对许多商品来说，运输成本要占商品价格的4一10，也就是说运输成本占物流总成本的比重比其他物流活动大。目前，我国的交通运输业主要由公路、铁路、水路、航空等多种运输方式组成。在市场经济体制下，各种运输方式之间也不可避免地存在着激烈的竞争。各种运输方式均拥有自己固有的技术经济特征(见表1)。如何针对各种运输方式的特点，选择合适的

10、运输方式，使货物能够安全、快速、经济、便利的到达目的地，也就成为企业决策者必须面对的问题。运用AHP分析方法就物流运输方式选择问题进行一些探讨，为企业决策者提供一些决策依据。2.汽车物流运输方式及线路的优化2综合评价指标体系的建立影响运输方式选择的因素很多，本文主要从经济性、高效性、可靠性、可达性、安全性等方面衡量。21 经济性经济性表现为运输成本。一般来说，短途运输，公路的成本较低，中长途运输，铁路成本较大，长途运输并对时间有较高要求的运输，宜选择民航运输。22 高效性高效性体现为运输速度与准时率。不同的运输方式，运输速度各不相同。运输载体的最高技术速度一般受到运输载体运动的阻力、载体的推动

11、技术、载体材料对速度的承受能力以及与环境有关的可操纵性等因素的制约。目前，我国各种运输方式的技术速度分别是：铁路80kmh一160kmh，水路10kmh一30kmh，公路80kmh一120 kmh，航空900kmh一1000 kmh。23 可达性一般指运输J两路的密度和覆盖面，也就是选择某种特定的运输方式的方便程度。一般情况下，铁路和公路的可达性比较强，空运的可达性受到航线的影响，而水运受自然条件的限制，仅限于一定范围内，可达性相比起来就比较弱一些了。可达性一般很难定量表示，本文近似的利用发货人所在地至装车地之间的距离来表示，其距离越近，便利性越好。24 安全性安全性包括货物运输的安全和人员的

12、安全以及公共安全。从整个运输过程来说，与其他运输方式相比，载货卡车能够更好地保护货物的安全，因为只有卡车才能够实现“门到门”的运输，而不需要中途装卸和搬运。2.3问题的模型建立2.3.1层次分析法层次分析法（Analytic Hierarchy Process，简称AHP）是对一些较为复杂、较为模糊的问题作出决策的简易方法，它特别适用于那些难于完全定量分析的问题。它是美国运筹学家T. L. Saaty 教授于70年代初期提出的一种简便、灵活而又实用的多准则决策方法。2.3.1.1层次分析法的基本原理与步骤人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互

13、制约的众多因素构成的复杂而往往缺少定量数据的系统。层次分析法为这类问题的决策和排序提供了一种新的、简洁而实用的建模方法。运用层次分析法建模，大体上可按下面四个步骤进行：（i）建立递阶层次结构模型；（ii）构造出各层次中的所有判断矩阵；（iii）层次单排序及一致性检验；（iv）层次总排序及一致性检验。下面分别说明这四个步骤的实现过程。2.3.1.2 递阶层次结构的建立与特点应用AHP分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型。在这个模型下，复杂问题被分解为元素的组成部分。这些元素又按其属性及关系形成若干层次。上一层次的元素作为准则对下一层次有关元素起支配作用。这些层次

14、可以分为三类：（i）最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层。（ii）中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层。（iii）最底层：这一层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层或方案层。.2.3.1.3 构造判断矩阵层次结构反映了因素之间的关系，但准则层中的各准则在目标衡量中所占的比重并不一定相同，在决策者的心目中，它们各占有一定的比例。在确定影响某因素的诸因子在该因素中所占的比重时，遇到的主要困难是这些比重常常不易定量化。此外，当影响某因素的

15、因子较多时，直接考虑各因子对该因素有多大程度的影响时，常常会因考虑不周全、顾此失彼而使决策者提出与他实际认为的重要性程度不相一致的数据，甚至有可能提出一组隐含矛盾的数据。为看清这一点，可作如下假设：将一块重为1千克的石块砸成小块，你可以精确称出它们的重量，设为，现在，请人估计这小块的重量占总重量的比例（不能让他知道各小石块的重量），此人不仅很难给出精确的比值，而且完全可能因顾此失彼而提供彼此矛盾的数据。设现在要比较个因子对某因素的影响大小，怎样比较才能提供可信的数据呢？Saaty等人建议可以采取对因子进行两两比较建立成对比较矩阵的办法。即每次取两个因子和，以表示和对的影响大小之比，全部比较结果

16、用矩阵表示，称为之间的成对比较判断矩阵（简称判断矩阵）。容易看出，若与对的影响之比为，则与对的影响之比应为。定义1 若矩阵满足（i），（ii）（）则称之为正互反矩阵(易见，)。关于如何确定的值，Saaty等建议引用数字19及其倒数作为标度。下表列出了19标度的含义：标度含 义13572，4，6，8倒数表示两个因素相比，具有相同重要性表示两个因素相比，前者比后者稍重要表示两个因素相比，前者比后者明显重要表示两个因素相比，前者比后者强烈重要表示上述相邻判断的中间值若因素与因素的重要性之比为，那么因素与因素重要性之比为。2.3.1.4 层次单排序及一致性检验判断矩阵对应于最大特征值的特征向量，经归一

17、化后即为同一层次相应因素对于上一层次某因素相对重要性的排序权值，这一过程称为层次单排序。上述构造成对比较判断矩阵的办法虽能减少其它因素的干扰，较客观地反映出一对因子影响力的差别。但综合全部比较结果时，其中难免包含一定程度的非一致性。如果比较结果是前后完全一致的，则矩阵的元素还应当满足：， 定义2 满足关系式（1）的正互反矩阵称为一致矩阵。需要检验构造出来的（正互反）判断矩阵是否严重地非一致，以便确定是否接受。定理1 正互反矩阵的最大特征根必为正实数，其对应特征向量的所有分量均为正实数。的其余特征值的模均严格小于。定理2 若为一致矩阵，则（i）必为正互反矩阵。（ii）的转置矩阵也是一致矩阵。（i

18、ii）的任意两行成比例，比例因子大于零，从而（同样，的任意两列也成比例）。（iv）的最大特征值，其中为矩阵的阶。的其余特征根均为零。（v）若的最大特征值对应的特征向量为，则，即定理3 阶正互反矩阵为一致矩阵当且仅当其最大特征根，且当正互反矩阵非一致时，必有。根据定理3，众所周知可以由是否等于来检验判断矩阵是否为一致矩阵。由于特征根连续地依赖于，故比大得越多，的非一致性程度也就越严重，对应的标准化特征向量也就越不能真实地反映出 在对因素的影响中所占的比重。因此，对决策者提供的判断矩阵有必要作一次一致性检验，以决定是否能接受它。对判断矩阵的一致性检验的步骤如下：（i）计算一致性指标 （ii）查找相

19、应的平均随机一致性指标。对，Saaty给出了的值，如下表所示：1 2 3 4 5 6 7 8 9 0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 的值是这样得到的，用随机方法构造500个样本矩阵：随机地从19及其倒数中抽取数字构造正互反矩阵，求得最大特征根的平均值，并定义。（）计算一致性比例 当时，认为判断矩阵的一致性是可以接受的，否则应对判断矩阵作适当修正。2.3.1.5 层次总排序及一致性检验上面众所周知得到的是一组元素对其上一层中某元素的权重向量。众所周知最终要得到各元素，特别是最低层中各方案对于目标的排序权重，从而进行方案选择。总排序权重要自上而下地将单准

20、则下的权重进行合成。设上一层次（层）包含共个因素，它们的层次总排序权重分别为。又设其后的下一层次（层）包含个因素，它们关于的层次单排序权重分别为（当与无关联时，）。现求层中各因素关于总目标的权重，即求层各因素的层次总排序权重，计算按下表所示方式进行，即，。对层次总排序也需作一致性检验，检验仍象层次总排序那样由高层到低层逐层进行。这是因为虽然各层次均已经过层次单排序的一致性检验，各成对比较判断矩阵都已具有较为满意的一致性。但当综合考察时，各层次的非一致性仍有可能积累起来，引起最终分析结果较严重的非一致性。设层中与相关的因素的成对比较判断矩阵在单排序中经一致性检验，求得单排序一致性指标为，（），相

21、应的平均随机一致性指标为（已在层次单排序时求得），则层总排序随机一致性比例为当时，认为层次总排序结果具有较满意的一致性并接受该分析结果。26 相对重要程度的计算理论上讲，对以某个上级要素为准则所评价的同级要素之相对重要程度可以由计算判断矩阵A的特征值获得。但因其计算方法较为复杂，而且实际上只能获得对A粗略的估计，因粗计算其精确特征值是没有必要的。本文采用求根法计算特征值的近似值。(1)将矩阵按 (2)归一化 一致性检验在实际评价中评价者只能对判断矩阵A进行粗略判断，甚至有时会犯不一致的错误。为了检验判断矩阵的一致性，根据AHP原理，可以利用 与n之差检验一致性。定义计算一致性指标：显然，随着n

22、的增加判断误差就会增加，因此判断一致性时应当考虑到n的影响，使用随机性一为平均随机一致性。由此，根据层次分析法，打出影响运输方式的最主要因素有运费和时间。二、汽车物流运输方式及线路的优化2.1问题的背景分析上汽集团是国内领先的汽车制造企业、最大的乘用车制造商和销量最高的汽车生产商。上海汽车作为上汽集团的下属自主品牌。目前拥有两大生产基地，分别是上海南汇临港基地和南京浦口基地。上海工厂生产出来的汽车存储在临港库，库容为12000台。南京工厂生产出来的汽车存储在南京库，库容为6000台。作为上汽集团全资子公司，安吉物流承担着上海汽车两大基地商品车的运输业务，负责为客户提供点对点的运输服务。目前安吉

23、物流配送城市覆盖全国大部分地区。安吉物流针对不同运输线路，采取了不同的运输方式。例如：对于广州、天津等沿海地区的整车运输，安吉物流倾向于考虑海运；对于武汉、重庆等沿江地区的整车运输，安吉物流倾向于考虑江运；对于其他城市，安吉物流倾向于采用公路运输。在一些特殊情况下，如加急订单等，一些原定于水路运输将调整为公路运输。安吉物流虽然在配送方面取得了成功，但是还是需要改进的地方，在线路优化方面安吉大多采用单一的运输方式，这样的形式不仅运输风险大，而且成本较高；在客户满意度方面，安吉的运输在途时间还有优化的空间，在交货时，商品的完成率也做得不够，客户往往希望商品车的行驶里程不超过50公里。对于以上问题的

24、分析，众所周知发现如果公司能适当增加多式联运的比例，节约成本和提升客户满意度方面的问题都能够有效的改善。多式联运是由两种以上的运输工具互相衔接，转运而共同完成的运输过程。由于多式联运采用一次托运、一次付费、单到底统一理赔、全程负责的运输的业务方法，这可以大大减少中间环节，简化运输与结算手续，提高服务质量。再者，由于多式联运对运输线路的合理选择和运输方式的合理使用，全程运输成本减低，利润可以大大提高。公路、水路和航空运输这几种常用的运输方式在运输的成本平均运输时间、可靠性以及安全性等各个方面有着各自的特点 而且难以用统一的标准来衡量 这样 就产生了一个如何对不同的运输方式进行选择的问题1。本文旨

25、在利用DHGF综合算法对这一问题进行探讨。二、DHGF综合算法的原理DHGF综合算法是将改进的德尔菲法、层次分析法、灰色关联、模糊评价的成功之处集合而成的一种综合评价方法，是结合众家之长而形成的算法 是一种从定性到定量的数学方法，它体现了这四种算法各自的优点3。三，DHGF综合算法的方法步骤及其在在多种物流方式选择中的具体应用分析1运用Delphi法收集、分析、讨论及统计以确定综合评价指标体系集G=(g 、g。、g 、g 5、g6、g 、g。、g 9)假设聘请5人的专家团对物流运输方式选择影响因素进行咨询、分析和统计 确定影响物流运输方式选择的评价指标，得出下列指标集G，并分成三类：区间型指标

26、G1：环保要求g1、受气候影响情况g2；效益型指标G2：物流运输方式的便捷程度g3、物流公司信誉度g4、服务水平g5、货物完好率g6；成本型指标：物流成本g7 支付要求g8，违约成本g9。2 确定加权子集运用层次分析法，综合专家对各项评价指标相对重要性的判断，构造比较判断权重矩阵。根据seaty原则，5位专家对评价指标之间比较 得出判断矩阵及其权重G 2G =4 G G =6，G G =2， W ：(0082 0 326，0 592)。得出判断矩阵之后要对其进行一致性检验， 经过计算= 3 095 相容性指标Cl=O 04750 1，因此特征向量是可以接受的。同理 众所周知可以得到第三级之间的

27、判断矩阵及其权重分别等于2 00240333 013 相容性指标Cl均小于0 1 因而判断矩阵是相容的。根据上述计算 众所周知可以求得最终各个评价指标的组合权重W= (0 027、0 055、0 029、0 1 28、0 116、0 053、0 415、02 最短路程目前，解决最短线路优化问题的方法有很多，如位势法，“帚”型法，动法等 为便于计算运输线路中的最大流量和最短路径的可靠性问题，针对网络的特点，众所周知引人最小路集法现介绍如下21 最小路集所谓路集是指运输线路网络中弧的集合，当这些弧正常时，能使网络系统正常，即能使输入节点和输出节点沟通，则称这些弧的集合为路集，如图11中 ，8，G)

28、， 8，E，H)等都是路集在任一路集的基础上再添加当然仍是路集但如果某个路集，任意地减掉一条弧就不再是路集时，这样的路集就是最小路集最小路集所会的弧数称为路长在最小路集中，其所形成的通路也没有重复的节点，因此，一个节点的网络系统，路长最大的最小路集最多只能包含 个点也就是说，最小路集的最大路长是 一1，路长大于等于 的最小路集是不存在的22 求最小路集利用联络矩阵法求最小路集（1）联络矩阵给定一个任意类型线路网络，它有 个节点，设矩阵c一c ， i， 一1，2， ， (I-1)式中C。，为矩阵元素，定义为：f-z节点i到节点 间有弧-z直接相连节点 到节点 间无弧直接相连称矩阵c为该网络的联络

29、矩阵联络矩阵为c一0 A C D 0 00 0 1 0 B 00 0 O F E 00 0 F 0 0 H0 0 E 0 0 G0 0 O O O O（2）联络矩阵的乘方规则式中 为节点数c 的含意：它表示从节点 到所有可能的节点走，再从走到节点 的最小路集即从节点 到节点 的路长为2的所有最小路集因此，按式(13)得到的路长小于2的要除去推广为普遍形式：式中 为节点数，c 的含意：它表示从节点 到 之间路长为r的所有最小路集因此按式(14)得到的路长小于r的要除去设 为输入节点，L为输出节点，从定义可知，对于任意的c ，和c一样，第L行及第列的所有元素都为0有了联络矩阵c，只要做多次矩阵连乘

30、，相继求出c ，c。， ，c一 即可得到任意二节点 ，J间所有的最小路集由于众所周知研究的是运输线路的起点(输入节点 )到终点(输出节点L)之间的最小短路问题，因此对于其他节点之间的最小路集可不考虑从式(14)可看出，在这种情况下只需求中的第L列即：c2只需求出第行元素即可，而不用求整列的元素3 最大流量最大流量按下列两条原则进行计算：1)确定连接输出节点上的线路个数m，如图21，有两条输出线路G和H，所以m一2；2)根据最小路集分别计算m中每条线路的流量，直到m 条线路中各线路的流量之差0在两条输出线路G和H 中分别有路长：A，B，G)、C，E，G)、A，I，E，G)、D，F，E，G)和C，

31、F，H )、A，I，F，H )、A，B，E，F，H )、D，H )分别确定输出线路G和H 中各路长的最小流量在输出线路G中，线路G一2为最小流量在输出线路H 中，线路F一3为最小流量，则剩余流量：Q 。，且F一0对于路径A，I，F，H)，A，B，E，F，H)，因元素F一0，所以不再计算对于路径D，H)，在Q 。中减去最小流而元素D 已为零计算毕总流量为：QG+F+D一2+3+38(千辆小时)4 系统可靠度某些条件下，运输线路的运行情况无法用准确的数值表达，如线路质量等级，可能发生的塞车故障等，这时可用概率来描述R为可靠度，即线路正常运行的概率已知最小路集：由于最小路之间是相交的，所以必须用相容

32、事件的概率公式来计算系统可靠度尺运输线路网络系统中正常运行的可靠程度为：0835（1）在运输线路优化问题的计算中，最小路集法既便于运输网络定性分析，又便于运输线路定量计算，特别是在计算最大流量时更具有独特的优势（2）最小路集法除在最短路程和最大流量的计算、分析中有显著的特点外，在对网络系统的可靠性分析中也具有重要作用从述可靠度计算可看出，它清晰地描述了运输线路正常运行的可靠程度，便于管理者对线路的优化和决策2.4问题的求解最优线路问题成为研究交通问题中的一个重要问题，在解决公交最佳出行线路、城市援救最佳线路、物流配送、高速公路联网收费等与人们日常生活密切相关问题中发挥着重要的作用。这些年来，城

33、市的交通系统有了很大发展，为公众的出行以及进行各项日常活动带来了很大的便利，但同时也面临着多条线路的选择问题。所以建立交通中最优线路问题的数学模型，为人们进行日常活动提供参考有很大的价值，是一个值得研 究的课题。建立交通中最优线路问题数学模型的目的就是寻找最优路径，为公众做出出行决策提供参考。目前关于最佳出行线路问题的研究主要是一些传统算法和根据问题的特点对传统算法进行改造。合运输网络中求解起点到终点的最短可行路径；Paola Modesti等 针对最小出行时间研究了求解综合运输网络最短路径问题，使用多标记图构建运输网络和对应的数据，并提出了求解算法。但这些已有的算法都不能解决出行线路双向选择

34、、环形出行线路和多权问题，因此需要一种新的算法来建立交通中最优线路问题的数学模型。3 Floyd算法Floyd(弗洛伊德)算法 剐是一种矩阵(表格)迭代方法，对于求任意两点间的最短路、混合图的最短路、有负权图的最短路等一般网络问题来说均比较有效。Floyd算法通过对表示有向图的邻接矩阵作叠代计算来解决有向图任意一对顶点之间的最短路径间题。Floyd算法不仅是建立在简单的数据结构基础之上，而且就解决问题的彻底性而言也是最完满的。迄今为止，它仅仅是作为解决有向图的最短路径问题的一个重要方法而被提及。实际上，Floyd算法与图的许多重要性质以及与图论中其它一些重要问题的解决有着密切的联系。31 Fl

35、oyd算法的基本原理Floyd算法的主要思想是从代表任意2个顶点到 的距离的带权邻接矩阵开始，每次插入一个顶点 ，然后将 到vi间的已知最短路径与插入顶点 作为中间顶点(一条路径中除始点和终点外的其他顶点)时可能产生的 到 路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出rt个矩阵Du)，D(2， D( ，当所有的顶点均作为任意2个顶点 到 ，中间顶点时得到的最后的带权邻接矩阵D 就反映了所有顶点对之间的最短距离信息，成为有n个顶点的图G的距离矩阵。最后对G中各行元素求和并比较大小，决定最优的路线。32 Floyd算法构造距离矩阵的原理对一个有几个顶点的图G，将顶点用n个

36、整数(从1到7,)进行编号 。把G的带权邻接矩阵作为距离矩阵的初值，即D（0) =W。从图的带权邻接矩阵 开始，递归地进行a次更新，即由矩阵D(0=W，按一个公式构造出矩阵JD(1；又用同样的公式由Dl构造出矩阵D(2 ；最后又用同样的公式由JD 构造出矩阵D。矩阵D的i行_列元素便是i号顶点到号顶点的最短路径长度，称D 为图的距离矩阵，同时还可以引入一个路由矩阵path来记录两点间的最短路径。第一步：构造D(0=W)。第二步：构造D = (d ) ，其中d =mind ，d +d 是从 到 的只允许 。作为中间点的路径中最短路长度。第三步：构造D= ( ) ，其中 =raind ，d +d 是从t， 到t，的只允许t，l，2作为中间点的路径中最短路长度。第n步：构造D =(d