合肥好又多公司物流配送线路优化设计和实现 物流管理专业

目录TOC\o"1-3"\h\u中文摘要 1英文摘要 21绪论 31.1研究的作用及意义 31.2国内外研究现状 31.2.1国外研究现状 41.2.2国内研究现状 41.3研究思路 42好又多配送路线现状 42.1好又多概况 42.2好又多配送路线作业现状 42.3好又多配送现有路线问题分析 63好又多物流配送线路优化设计 73.1研究对象目标设定 73.2模型的构建 103.3基于遗传算法的好又多配送路线优化 113.3.1遗传算法介绍 113.3.2算法思想与算法流程 123.3.3优化后的结果 143.4基于节约里程算法的好又多配送路线优化 153.4.1节约算法的基本原理 153.4.2节约里程算法主要步骤 153.4.3基于节约算法的配送路线优化 163.4.4优化后的配送线 293.5两种配送线路优化分案比较分析 30致谢 32 参考文献 33合肥好又多公司物流配送线路优化设计摘要：车辆调配问题实属复杂的优化问题，物流配送路线的优化需要做多个方面的研究了解。采取网上搜寻意见，翻阅书籍，看视频，实地走访等方式去了解物流配送存在的问题，进而明确设计目标，针对性的实施设计合理化的方案，研究内容的多个方面考虑，本文主要是从车辆的调配以及货物运输方面来进行研究讨论的。研究目标需要合理，尽最大努力做到多个方面的综合考虑，几种方法相结合，做到实际问题的具体化。多个因素考虑分别进行规划与体统的处理，制定出一个较为完善的物流配送优化体系。本文通过好又多连锁超市进行研究，对物流配送体系加以一定程度上的完善。关键词：组合优化；车辆配载；约束条件OptimaldesignoftransportationloadingforHebeiExpressAbstract:Thevehicleloadingproblemisacombinatorialoptimizationproblemisquitecomplexconstraints,whichbelongstoNP-hardproblem.Byreviewingtherelevantliteraturetounderstand,mostofthedomesticscholarshavestudiedonthisissue,themaincontentsofthestudyfromtwoaspectsofvehiclesandgoods,settingthegoalismainlyconsideringthevolumeorweight,seldomconsiderhowtodealwiththeloadingbeforeloadingthegoodsarecombinedprocessing.Thecurriculumdesignwillconsiderthecombinationofgoodsprocessingandpreferredcustomersforemergencygoodsdemanddegreetwoareplanning,companiescanchooseaccordingtotheactualsituationofone,hasthereferencevalue.Inthiscase,theproblemofvehicleloadingcanalsomakeasmallcontributiontothefurtherimprovementofthelogisticsmarketsystem.Keywords:Combinatorialoptimization;Vehicleloading;constraintconditionTOC\o"1-3"\h\u1绪论1.1研究的作用及意义物流配送历史悠久，它是一项综合性比较高的物流运动。物流的配送是物流业企业的经济命脉，物流的配送关系到各个行业的快速发展，配送是一个极其重要的环节，是链接发货商与消费者之间的纽带，货物的输送跟他们紧密相连，满足客户的要求，在收货，运货方面全程跟踪，送货，关于客户的要求，颜色搭配，数量，时间等，都需要进行考虑，做到配与送的有机结合。物流配送成本问题，在不断上升，使得运输成本在一定程度出现了很大的提高，车辆的合理利用与分配显得尤为重要。当下，车辆业务运输量增多，城市道路交通堵塞，车辆的等待时间加长，容易造成交通不舒畅，尾气污染，车祸等，都会出现严重的问题，车祸事故以及能源的浪费，都会产生很大的影响，给城市的交通增添了很多的障碍，如果再加上路线选择的不合理，还会使得运输路线拉长，成本无形增加，出现很多多重复的运输，需要去提高配送效率，降低物流成本，尽最大可能限制在大城市停留的时间，舒缓交通的压力。当下好又多超市物流配送存在很大的问题，本篇文章从长远角度来看待问题，致力于长期发展。运用系统的运用与物流配送体系，优化路线，使得配送体系更加完善，建立一个高校快速的快递运输渠道，降低企业成本，增加企业的利益。创造自己的核心竞争力，使得相对应的系统更加完善，合理化，物流配送系统更加的合理化，好又多的物流配送上升一个档次，路线优化问题的解决对于好又多而言，具有非常大的意义。1.2国内外研究现状1.2.1国外研究现状在国外，发达国家来看，物流配送路线的优化已经应用到生活的方方面面，各个领域都有设计到。国外在这些方面的研究颇多，取得了一定的成果，运用网络化来进行车辆调配，合理运输。国外的报纸投递，书信，牛奶，衣服，垃圾车，水运，空运，电力，建筑行业服务，等等都有涉及到，物流业的配送发展越来越迅速，加快了经济的发展，促进了人们生活的提高。不断研究设计出最为合适的优化组合路径的方案问题。1.2.2国内研究现状关于国内在这方面的专业，系统化的研究还不常见。学者在这方面也做过一些课题，关于实现网络信息化的路线问题，运用算法来计算，网络来进行车辆调配，输送运货问题，做了一定的研究，合理的安排配送路线，设计出合理的配套方案，模型系统化管理，还需要进一步进行大量深入的研究。1.3研究思路本文主要研究合肥好又多的物流运输线路图优化设计，做出优化方案。因此本篇论文的写作思路是:首先介绍物流运输线路的优化设计概念，状况，了解配送的概念，作用，路径的优化设计，做出一定的叙述，根据不同的算法设计出最优化路线，最后进行深层次的介绍进行了解运输成本，配送模式的介绍，如何节约里程，遗传，插入计算，以此来对合肥好又多的原来配送方案进行一定程度的调整。2好又多配送路线现状2.1好又多概况好又多量贩由拥有台资背景的宏仁集团联合诚达集团的掌舵人于曰江投资创办，于曰江于1997年在广州天河开出第一家店，在广州已拥有连锁门店20余家，网络遍布国内20多个省、区、直辖市，总营业面积40多万平方米，有员工3万余人。好又多到2005年，共有27家直营店，这些都是早期开的店，规模和资质相对比较好，但是近两年来，好又多疯狂提高开店速度，多数采用加盟形式，股权复杂，店面大小不一，经营质量参差不齐的问题，门店数量虽然最多，但利润却相对较差。2.2好又多配送路线作业现状配送距离分析(1)配送需求点坐标：现在以好又多物流配送中心为原点(0,0),建立直角坐标系,各商店的坐标如下表所示:X(km);Y(km)表2-1分店所在地坐标坐标分店与配送中心间距离坐标分店与配送中心间距离XY1892-453244102053-3066778158-7-691591010121191012-8-13134-5146615-7-8163417-5101829191-152083i=1，2.........20；(2)现有路线是固定不变且为已知,配送中心与商店之间，商店与商店之间的距离分析如下表：表2-2配送中心与分店之间,分店与分店之间的距离(0点表示配送中心)0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.862173.61.427153.6237.113625626.41306.12136101611191614181310137.15.17.2211234.57.86.1018345131314119.2209.24.51519.25196.1422112118050145.4311281038261533171814361753039363450037452641434020253624344139153369.22.8105143708.3189.26.44.224121204.2114.5234.5717616135.4458.30269.23.65.132209.22712148.5311289.22111133126182602725237.11118214161712179177191412419.29.22705.86.132189.528132013289.210163.616118436.43.6255.802.231187.22611158.5289.211131.4149.210404.25.1236.12.2029165248.5147.1267.11215271820382024327.1323129014245.12023249.223136.415139.2262512201118181614011119.11714108.9148.53.6104.5153619.2189.57.2524110193.6125223.615112313153324202722826245.11119016181911191657.17.1117344.2121413118.5209.13.6160105.1195.11711135.19.21841111416201514231712181007.12615189.267.2514394.58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512179.29.27.1238.93.6195.1158.5190车辆数分析所需车辆数分析(好又多配送中心一年(365天)的车辆调度):表2-3车辆调度情况车辆运用数101291110111010891011运用天数2530364246494838241386表2-4车辆运用数所占比率车辆运用数相对比率累计比率120.070.07120.080.15110.100.25100.120.37120.130.50110.130.63130.130.76100.100.86140.070.93150.040.97130.020.99110.011.00则好又多平均每天所用车辆数为12辆。需求量分析表2-5每个分店（一年365天）平均每天的需求量分店12345678910需求量2324123513分店11121314151617181920需求量23421213222.3好又多配送现有路线问题分析好又多超市物流配送系统体制的不完善，导致配送系统运输货物的不及时性，连锁产业是不能轻易改变策略，方案，模式生产与经营的，商业基础不够完善与完整，它是一个庞大的系统与规模在运行。并不是在段时间内就可以完善好的。好又多的配送目前出现了几个方面的不足：第一是送货的及时性，做的不够到位；第二，没有固定的体系与系统管理；第三，货物积压；第四，资金消耗大；第五，物流配送路径的不合理化；第六，车辆实载率控制解决；第七，物流配送的网络信息化不健全；第八，车辆调配问题无法解决；第九，配送过程的一体化，系列化不到位3好又多物流配送线路优化设计3.1研究对象目标设定物流成本包括两个方面，一个是固定成本，一个是运输成本，物流配送需要考虑几个方面的问题，缩短距离，减少成本，在满足客户需求的同时，争取最大化的利益。好又多超市的运输成本表格如下，运输成本是企业成本花费最大的地方，给企业的效益在一定程度上减少了，如何实现物流业的运输成本下降是企业关心的问题。业务运输成本是物流配送运输需要解决的当下问题表3-1公司货运成本比例表固定费用（22%）营业费用（78%）折旧费（租赁费）：装卸工具，车库，办公室，水电，通迅，差旅费，公务车费用业务印刷费人力（司机）：工资,额外福利，装卸费投资利息：车辆，车库,办公室管理成本：职工月工资,额外福利,旅游和娱乐费用,房屋维修费，牌照费，职工培训费，宣传费及业务手续费。车辆运营成本：燃料（燃油，润滑油，过滤器）维修费（人工费+零部件）轮胎费，交通规费，养路费大修理基金提存道路服务：通行费,保险,许可证和登记费高速公路使用费,燃油司机费用占到百分之29.4，维修费和折扣费占到百分之19.5，燃料费占到百分之18.5，其他的为百分之32.6。根据表格可以看出，车辆的运输费用是最高的，这是物流企业当中的一项尤为重要的变化，现在各个乡镇变化也在不断提升，道路变化情况复杂，车辆的运输成本加大，车辆的里程，燃油量，维修费用都是非常大的一笔资金消耗，而物流行业，车辆运输是最为普通常见的一种运输，海运，空运，还是较为少见的，设计物流优化方案，成本维修，设计最为合理的优化路线，减少企业运输成本，做一笔大的计算。综合来看，本文关于物流配送的路线优化方案提出了一个意见，解决车辆路径问题，争取做到成本的最小化，企业利益的最大化。5594配送中心632781配送中心分店车辆路线图3-1好又多的配送模式这个问题是关于好又多配送模式的图形分析，分送式的模式是由一个总的供应商，分发到各个分点，满足各个分点的需求，发货到货卸货，根据配送中心路程的远近来分发货物，确定适当的路线配送，有秩序的发送，防止在一定程度上也会出现迂回运输。虽然会受到各种条件的制约，不管是里程还是车辆实载率，交通运输问题，客户的需求量，都需要去考虑，争取做到企业利益最大化。本文研究的是不考虑时间窗的非满载车辆优化调度问题。表述如下：将货物从配送中心配送到各分配送中心,由分配送中心派出容量为的货车承运，现有m辆车，各分店对所需求的货物有一定的要求，第i个分店的货运量为gi，（i=1，2……l）已知，在途中只有卸货任务,完成任务后返回配送中心,求满足配送需求的费用最少行车线路。分配送中心1分配送中心1分配送中心2分配送中心3..........................分店1分店2分店3分店4.............配送中心图3-2好又多配送体系结构3.2模型的构建为建模方便，需考虑以下几个前提假设条件：（1）配送中心不会出现缺货的可能并且对顾客的基本配送资料（需求量、地理位置）为已知，配送中心的位置也已知；（2）不考虑配送时间限制，即客户对货物的需求没有时间窗的规定；（3）不考虑每辆车为每个客户的服务时间，即不考虑每个客户的卸货时间；（4）一个配送中心根据配送条件可以负责多个客户，即一个配送中心服务多个客户；（5）车辆由配送中心出发，服务被指定的需求点后，再返回配送中心，区域内的需求点假设为固定数量且位置已知，不发生变动。（6）配送中心拥有一定数量的单一车型的配送车辆，且每辆车的容量已知。（7）每条配送路径上各客户需求量之和不超过配送车辆的容量；（8）每个客户只能由一辆配送车辆送货；（9）每辆车配送总里程不超过其最大行驶距离；（10）各道路均顺畅，不考虑交通堵塞拥挤等特殊情况。将配送中心编号为0，车辆编号为k，任务编号为i=1,2........,所有车型载重量单一，每辆汽车的最大载重量为g，需要向L个需求点送货，每个需求点的需求量为，并且满足，需求点i到j的运距为，配送中心到各个需求点的距离为，再设为第辆汽车配送的需求点数（=0表示未使用第辆汽车），用集合表示第k条路径，其中的元素表示需求点在路径中的顺序为（不包括配送中心），令=0表示配送中心，为每辆车单位里程的行驶费用，为每辆车的派遣费用，考虑运输量约束,停车点车辆数目等约束,可以定义如下的基本模型:(3-1)(3-2)(3-3)(3-4)(3-5)(3-6)3.3基于遗传算法的好又多配送路线优化3.3.1遗传算法介绍遗传算法是由美国Michigan大学的Holland教授于1969年提出,后经DeJong、Goldberg等人归纳总结所形成的一类模拟进化算法。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。应用遗传算法求解如图3-3：解空间最优化问题描述解空间最优化问题描述第二步第一步建立优化模型确定决策变量,约束条件第二步第一步建立优化模型确定决策变量,约束条件第五步确定适应度转换规则第三四步编码,解码第五步确定适应度转换规则第三四步编码,解码个体基因型x适应度F(X)个体基因型x适应度F(X)第六步设计遗传算子第六步设计遗传算子第七步确定运行参数第七步确定运行参数遗传算法空间遗传算法遗传算法空间遗传算法图3-3应用遗传算法求解问题示意图3.3.2算法思想与算法流程首先根据每项任务的需求量qi，总任务量以及每辆车的最大载重量q，每辆车的任务不超过其最大载重量g，确定至少需要m辆车来完成任务,最后计算每辆车的总里程，其中总里程最小的即为所求任务安排。（1）构造染色体设车辆的可行线路可以编成自然数编码的长度为m+的染色体（i11，i12，i13，..........i1s；i21，i22.......i2t；......................；im1，im2.........im.），ikj为有需求的分店,即第ikj项任务,为分店的总数目，m为车辆从配送中心出发,经过各分店后,又回到配送中心的各条回路，即m辆车；车辆行驶线路为：第一辆车从配送中心出发，每个分店访问一次，经过i11，i12，i13，..........i1s的路线，又回到配送中心，形成子路径1；第二辆车从配送中心出发，每个分店访问一次，经过以前未经过的i21，i22.......i2t路线，又回到配送中心，形成子路径2；这样重复，直到每个分店都被访问到且每个分店只访问一次，项任务全部完成为止；其中i1s与i2t交换位置,表示行驶路径的改变,也使函数目标改变；算出每条路径的总行程，其中总行程最小的即为所求的最优化路径，其总运输费用最小。如染色体12345678表示行车路线：子路径π1：配送中心—任务1—任务2—配送中心子路径π2：配送中心—任务3—任务4—任务5—配送中心子路径π3：配送中心—任务6—任务7—任务8—配送中心这种染色体结构子路径内部是有序的，若子路径π1中点1，2交换位置，会使函数目标值改变；而子路径之间是无序的，若子路径π1和子路径π2交换位置，却不会改变目标函数的值。（3）适应度函数对种群中的每个染色体Vi(i=1,2,…..l)根据目标函数的式子计算其值为Ui,若染色体对应的是不可行解，则赋予其目标函数值一个很大的整数，适应度函数可以设为：fi=1/Zi+M*1000,则fi>0，Zi为染色体Vi对应的运输成本；fi为染色体Vi的适应度，fi越大，其性能越好，其对应的解越接近最优解。（4）遗传算子1)选择算子个体选择的分配方法:按比例的适应度分配。利用比例于各个体适应度的概率决定其子孙的遗留可能性，选择概率公式为:pi=fi/fi即适应度越大，其选择概率越大。根据计算父代和子代的适应度，并将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用轮盘赌选择法产生。2)交叉算子对通过选择操作的新群体，除排在第一位的最优个体外，另N-1个个体要按交叉概率pc进行配对交叉重组。本文采用顺序法实施交叉操作：a)随机在你代个体中选取一个交配区域,如两父代个体及交配区域定为：A=47|8563|921，B=83|4691|257；b)将B的交配区域加到A的前面，A的交配区域加到B的前面，得：A‘=4691|478563921，B’=8563|834691257；c)在A‘，B’中自交配区域后依次删除与交配区相同的自然数，得到最终的两个个体分别为：A‘‘=496178532，B‘’=856349127。3)变异算子以一定的变概率Pm随机选取发生变异的个体染色体，然后在该染色体上随机选取2个非零基因位，把这2个位置上的基因互换形成新的基因串。（5）控制参数和算法的终止条件1)参数设置交叉概率Pc=0.6；变异概率Pm=0.01；终止代数T=100；初始种群N=100；δ=0.65；车辆数m=[qi/δ]+1（gi为需求点i的货运量）；g=8吨；2)终止条件由于计算时间的机器容量都是有限的，代数不能无限长，故当迭代次数达到规定值T时，停止计算。3.3.3优化后的结果表3-2运行结果分析所需车辆数行驶距离（KM）运输成本（元）第1次7376.8712706第2次7372.6312579第3次7333.5211406第4次7381.5912848第5次7416.6913901第6次7374.5812637第7次7383.3612901第8次7291.5710147平均值7366.3512291最小值7291.5710147表3-3优化后路线优化后路线行驶距离（KM）实载量（吨）准载量（吨）实载率%0-11-13-19-0267.6895%0-10-5-7-0886.5881.25%0-20-3-1-013.95.5871.25%0-12-16-18-025.17.8897.5%0-8-9-6-036.27.4892.5%0-4-17-2-023.17.9898.75%0-15-14-0192.9836.25%合计231.345.656（平均）81.78%优化后只需要7辆车，减少了5辆车；实载率增加到81.78%，提高了31.43%;总成本减少了610元。D=291.57KM;K=7辆;minZ=10147元.3.4基于节约里程算法的好又多配送路线优化3.4.1节约算法的基本原理节约算法的核心思想是将运输问题中存在的两个回路（0，…，i，0）和（0，j，…，0）合并成一个回路（0，…，i，j，…，0）。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离[6]。相应的变化值，叫做节约距离，如式（1）所示。（1）调整过程如图3所示。jjjji0i00ii调整前调整后图3-4节约算法的图像描述3.4.2节约里程算法主要步骤已知条件:需求点集={1,2,…,n},各点需求量,各点间最短距离。第一步,形成一个初始解。确定各车辆配送点集令,=1,2,…,n(先采取单点配送)。第二步,进行节约度的计算。计算所有点对的节约度QUOTE，然后对计算结果进行升序排列。第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始，直到节约里程的队列空为止,重复下列步骤:按照节约里程队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i,j连接起来,即可令。如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对。3.4.3基于节约算法的配送路线优化表3-4每个分店（一年365天）平均每天的需求量分店12345678910需求量（吨）2324123513分店11121314151617181920需求量（吨）2342121322现有路线是固定不变且为已知,每条线路行驶距离可由表3-5求得,配送中心与商店之间，商店与商店之间的距离分析如下表：表3-5配送中心与分店之间,分店与分店之间的距离(0点表示配送中心)0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.862173.61.427153.6237.113625626.41306.12136101611191614181310137.15.17.2211234.57.86.1018345131314119.2209.24.51519.25196.1422112118050145.4311281038261533171814361753039363450037452641434020253624344139153369.22.8105143708.3189.26.44.224121204.2114.5234.5717616135.4458.30269.23.65.132209.22712148.5311289.22111133126182602725237.11118214161712179177191412419.29.22705.86.132189.528132013289.210163.616118436.43.6255.802.231187.22611158.5289.211131.4149.210404.25.1236.12.2029165248.5147.1267.11215271820382024327.1323129014245.12023249.223136.415139.2262512201118181614011119.11714108.9148.53.6104.5153619.2189.57.2524110193.6125223.615112313153324202722826245.11119016181911191657.17.1117344.2121413118.5209.13.6160105.1195.11711135.19.21841111416201514231712181007.12615189.267.2514394.58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512179.29.27.1238.93.6195.1158.5190设每个车辆的运输能力是8吨，根据案例可知，好又多平均每天所用车辆数为12辆。现在用节约算法对该配送线路问题进行求解。根据配送中心与分店之间,分店与分店之间的距离距离表，计算出用户间的节约里程，表3-6节约值矩阵表12345678910111213141516171819201025.4038.74.804237.48.50530.40.520618.45.68.717.22.207237.48.533.6217.9080.24.60.70.213.20.40.209224.47.52761724.8-0.801024.46.49.530318.829.40.227.201123.65.48.32531824.9-0.823.926.801203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.44.43.47.401416.94.98.55.52.516.716.3-0.31617.316.5-0.53.901504.40.50200.2118.201020.96.40.5016-0.14.38.510110100.29109.502.39.90017014.36.31509.2144.28121030.47.54601815.28.48.717.20.213.917.71.413.216.715.10.21.212.71.29.113.201920.40.51301.2112.243220.811.41.515100.202014.52.96.913.55.513.213.50.716.315.314.40.5613.40.58.44.59.24.50从表3-6中选出节约值最大值为33.6，其对应的两点为4、7。4、7两处的需求量之和为7，未超过一辆车的运输能力8，因此，连接4、7成回路，即0-4-7-0.再将顶点4和7的节约值赋为0.结果如表3-7所示。表3-712345678910111213141516171819201025.4038.74.804237.48.50530.40.520618.45.68.717.22.207237.48.50217.9080.24.60.70.213.20.40.209224.47.52761724.8-0.801024.46.49.530318.829.40.227.201123.65.48.32531824.9-0.823.926.801203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.44.43.47.401416.94.98.55.52.516.716.3-0.31617.316.5-0.53.901504.40.50200.2118.201020.96.40.5016-0.14.38.510110100.29109.502.39.90017014.36.31509.2144.28121030.47.54601815.28.48.717.20.213.917.71.413.216.715.10.21.212.71.29.113.201920.40.51301.2112.243220.811.41.515100.202014.52.96.913.55.513.213.50.716.315.314.40.5613.40.58.44.59.24.50从表3-7中选出节约值最大为30，其对应的两个顶点为4、10。如果连接4和10，则与上述线路合并，其总需求量为10，超过一辆车的运输能力8，因此，4和10不能连接，7和10也不能连接，则将4、10与7、10的节约值赋为0。继续选出节约值最大为30，其对应两个顶点为5、19。5和19两处的需求量之和为3，未超过一辆车的运输能力8，因此，连接,5、19成回路，即0-5-19-0.再将顶点5和19的节约值赋为0。继续选出节约值最大为27.2，其对应两个顶点为9、10。9和10两处的需求量之和为4，未超过一辆车的运输能力8，因此，连接9、10成回路，即0-9-10-0.再将顶点9和10的节约值赋为0。选出节约值最大为27，其对应的两个顶点为4、9。如果连接4和9，则与上述两条线路合并，其总需求量为11，超过一辆车的运输能力8，因此，4和9不能连接，7和9也不能连接，则将4、9与7、9的节约值赋为0。选出节约值最大为26.8，其对应的两个顶点为10、11。如果连接10和11，则与上述线路合并，其总需求量为6，未超过一辆车的运输能力8，因此，连接0-9-10-11-0成回路，则将9、11与10、11的节约值赋为0。同时，由于顶点10成回路的中间点，则与顶点10相关的节约值都赋为0，表示顶点10不可能再与其他点相连，其结果如下表所示。表3-812345678910111213141516171819201025.4038.74.804237.48.50530.40.520618.45.68.717.22.207237.48.50217.9080.24.60.70.213.20.40.209224.47.506170-0.801000000000001123.65.48.32531824.9-0.80001203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.403.47.401416.94.98.55.52.516.716.3-0.316016.5-0.53.901504.40.50200.2118.200020.96.40.5016-0.14.38.510110100.2909.502.39.90017014.36.31509.2144.2801030.47.54601815.28.48.717.20.213.917.71.413.2015.10.21.212.71.29.113.201920.40.5101.2112.240220.811.41.515100.202014.52.96.913.55.513.213.50.716.3014.40.5613.40.58.44.59.24.50选出节约值最大为25，其对应的两个顶点为4、11。如果连接4和11，则与上述两条线路合并，其总需求量为13，超过一辆车的运输能力8，因此，4和11不能连接，7和11也不能连接，则将4、11与7、11的节约值赋为0。选出节约值最大为25，其对应的两个顶点为5、12。如果连接5和12，则与上述线路合并，其总需求量为6，未超过一辆车的运输能力8，因此，连接0-12-5-19-0成回路，则将5、12与12、19的节约值赋为0。同时，由于顶点5成回路的中间点，则与顶点5相关的节约值都赋为0，表示顶点5不可能再与其他点相连，其结果如下表所示。表3-912345678910111213141516171819201025.4038.74.804237.48.50500000618.45.68.717.2007237.48.50017.9080.24.60.70.200.40.209224.47.500170-0.801000000000001123.65.48.300180-0.80001203.4-0.5-100.2017.100-10133.4-0.21.72.403.63.44.65.403.47.401416.94.98.55.5016.716.3-0.316016.5-0.53.901504.40.5000.2118.200020.96.40.5016-0.14.38.510010100.2909.502.39.90017014.36.31509.2144.2801030.47.54601815.28.48.717.2013.917.71.413.2015.10.21.212.71.29.113.201920.40.5101.2112.2402011.41.515100.202014.52.96.913.5013.213.50.716.3014.40.5613.40.58.44.59.24.50从表3-7中选出节约值最大为23.6，其对应的两个顶点为1、11。如果连接1和11，则与上述线路合并，其总需求量为8，未超过一辆车的运输能力8，因此，连接0-9-10-11-1-0成回路，则将与顶点1、9、10、11相关的节约值都赋为0，表示顶点1、9、10、11不可能再与其他点相连，其结果如下表所示。表3-8123456789101112131415161718192010200304.80407.48.50500000605.68.717.200707.48.50017.90804.60.70.200.40.20900000000010000000000011000000000001203.4-0.5-100.2017.10000130-0.21.72.403.63.44.60007.401404.98.55.5016.716.3-0.3000-0.53.901504.40.5000.2118.200020.96.40.501604.38.510010100.200002.39.90017014.36.31509.2144.200030.47.54601808.48.717.2013.917.71.40000.21.212.71.29.113.201900.40.5101.2112.2000011.41.515100.202002.96.913.5013.213.50.70000.5613.40.58.44.59.24.50从表3-8中选出节约值最大为20.9，其对应的两个顶点为12、15。如果连接12和15，则与上述线路合并，其总需求量为7，未超过一辆车的运输能力8，因此，连接0-15-12-5-19-0成回路，则将5、15；12、15与15、19的节约值赋为0。同时，由于顶点12成回路的中间点，则与顶点12相关的节约值都赋为0，表示顶点12不可能再与其他点相连，其结果如下表所示。表3-9123456789101112131415161718192010200304.80407.48.50500000605.68.717.200707.48.50017.90804.60.70.200.40.209000000000100000000000110000000000012000000000000130-0.21.72.403.63.44.6000001404.98.55.5016.716.3-0.300003.901504.40.5000.2118.200006.40.501604.38.510010100.200002.39.90017014.36.31509.2144.200000.47.54601808.48.717.2013.917.71.400001.212.71.29.113.201900.40.5101.2112.2000011.41.50100.202002.96.913.5013.213.50.70000613.40.58.44.59.24.50从表3-9中选出节约值最大为18.2，其对应的两个顶点为8、15。如果连接8和15，则与上述线路合并，其总需求量为12，超过一辆车的运输能力8，因此，8、19；8、5；8、12和8、15也不能连接，则将8、19；8、5；8、12和8、15的节约值赋为0。继续选出节约值最大为17.9，其对应的两个顶点为6、7。如果连接6和7，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，6和7不能连接，4和6也不能连接，则将6、7和4、6的节约值赋为0。选出节约值最大为17.7，其对应的两个顶点为7、18。如果连接7和18，则与上述线路合并，其总需求量为10，超过一辆车的运输能力8，因此，7和18不能连接，4和18也不能连接，则将7、18和4、18的节约值赋为0。选出节约值最大值为16.7，其对应的两点为6、14。6、14两处的需求量之和为4，未超过一辆车的运输能力8，因此，连接6、14成回路，即0-6-14-0.再将顶点6、14的节约值赋为0。选出节约值最大为16.3，其对应的两个顶点为7、14。如果连接7和14，则与上述两条线路合并，其总需求量为11，超过一辆车的运输能力8，因此，7和14不能连接，4和14也不能连接，则将7、14和4、14的节约值赋为0.选出节约值最大为15，其对应的两个顶点为4、17。如果连接4和17，则与上述线路合并，其总需求量为8，未超过一辆车的运输能力8，因此，连接0-17-4-7-0成回路，则将与顶点4、7、17相关的节约值都赋为0，表示顶点4、7、17不可能再与其他点相连，其结果如下表所示。表3-10123456789101112131415161718192010200304.8040000500000605.68.700070000000804.60.7000.4009000000000100000000000110000000000012000000000000130-0.21.7003.604.6000001404.98.50000-0.300003.901504.40.5000.20000006.40.501604.38.5001000.200002.39.90017000000000000000001808.48.70013.901.400001.212.71.29.1001900.40.5001.2012.2000011.41.50100.202002.96.90013.200.70000613.40.58.409.24.50选出节约值最大为13.9，其对应的两个顶点为6、18。如果连接6和18，则与上述线路合并，其总需求量为7，未超过一辆车的运输能力8，因此，连接0-18-6-14-0成回路，则将6、18与14、18的节约值赋为0。同时，由于顶点6成回路的中间点，则与顶点6相关的节约值都赋为0，表示顶点6不可能再与其他点相连，其结果如下表所示。表3-11123456789101112131415161718192010200304.8040000500000600000070000000804.60.7000009000000000100000000000110000000000012000000000000130-0.21.700004.6000001404.98.50000-0.300003.901504.40.50000000006.40.501604.38.500000.200002.39.90017000000000000000001808.48.700001.400001.201.29.1001900.40.5000012.2000011.41.50100.202002.96.900000.70000613.40.58.409.24.50选出节约值最大为13.4，其对应的两个顶点为14、20。如果连接14和20，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，14和20不能连接，6和20；18和20也不能连接，则将6、20；14、20和18、20的节约值赋为0。选出节约值最大值为11.4，其对应的两点为13、19。如果连接13和19，则与上述线路合并，其总需求量为11，超过一辆车的运输能力8，因此，13和19不能连接，13、19；13、5；13、12和13、15也不能连接，则将13、19；13、5；13、12和13、15的节约值赋为0。选出节约值最大为9.9，其对应的两个顶点为14、16。如果连接14和16，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，14和16不能连接，6和16；18和16也不能连接，则将6、16；14、16和18、16的节约值赋为0。选出节约值最大为8.7，其对应的两个顶点为3、18。如果连接3和18，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，3和18不能连接，3和18；3和6；3和14也不能连接，则将3、18；3、6和3、14的节约值赋为0。选出节约值最大为8.5，其对应的两个顶点为3、16。如果连接3和16，其总需求量为4，未超过一辆车的运输能力8，因此，连接3、16成回路，即0-3-16-0.再将顶点3和16的节约值赋为0。选出节约值最大为8.4，其对应的两个顶点为2、18。如果连接2和18，则与上述线路合并，其总需求量为10，超过一辆车的运输能力8，因此，2和18；2和6；2和14也不能连接，则将2、18；2、6和2、14的节约值赋为0。选出节约值最大为8.4，其对应的两个顶点为16、20。如果连接16和20，其总需求量为6，未超过一辆车的运输能力8，因此，连接16、20成回路，即0-3-16-20-0.再将顶点16、20和3、20的节约值都赋为0.同时，由于顶点16成回路的中间点，则与顶点16相关的节约值都赋为0，表示顶点16不可能再与其他点相连，其结果如下表所示。表3-12123456789101112131415161718192010200304.8040000500000600000070000000804.60.7000009000000000100000000000110000000000012000000000000130-0.21.700004.600000140000000-0.300003.901504.40.500000000000.5016000000000000000017000000000000000001800000001.400001.201.20001900.40.500000000001.50000.202002.9000000.70000600.50004.50选出节约值最大为6，其对应的两个顶点为13、20。如果连接13和20，则与上述线路合并，其总需求量为10，超过一辆车的运输能力8，因此，13和20不能连接，13和3；13和16也不能连接，则将13、3；13、16和13、20的节约值赋为0。选出节约值最大为4.8，其对应的两个顶点为2、3。如果连接2和3，则与上述线路合并，其总需求量为9，超过一辆车的运输能力8，因此，2和3不能连接，2和16；2和20也不能连接，则将2、3；2、16和2、20的节约值赋为0。选出节约值最大为4.6，其对应的两个顶点为2、8。如果连接2和8，其总需求量为8，未超过一辆车的运输能力8，因此，连接,2、8成回路，即0-2-8-0.再将与顶点2和8相关的节约值都赋为0，表示顶点2和8不可能再与其他点相连。选出节约值最大为4.5，其对应的两个顶点为19、20。如果连接19和20，则与上述两条线路合并，其总需求量为13，超过一辆车的运输能力8，因此，15、3；15、16；15、20；19、3；19、16和19、20也不能连接，则将8、3；8、16；8、20；19