交通运输专业 长乐永辉连锁超市配送路线优化研究和实现分析研究

目录TOC\o"1-3"\h\u中文摘要 3英文摘要 41引言 51.1研究的作用及意义 51.2国内外研究现状 51.2.1国外研究现状 51.2.2国内研究现状 61.3研究的主要思路 62物流配送概述 72.1物流配送的概念 72.2物流配送的功能 72.3配送路线优化的意义 82.4我国连锁超市配送的现状分析 82.5我国连锁超市配送现状存在的问题 93长乐市永辉连锁超市配送现状及其优化的必要性分析 113.1公司简介 113.2公司配送现状分析 113.3公司配送必要性分析 114配送线路优化方法介绍 134.1节约算法 134.1.1节约算法的基本原理 134.1.2节约算法的求解步骤 134.2扫描算法 144.2.1扫描算法的基本原理 144.2.2扫描算法的求解步骤 145长乐市永辉连锁超市配送路线优化方案 155.1基本数据分析 155.3基于节约算法进行配送线路优化方案 165.4基于扫描算法进行配送线路优化方案 225.5两种优化配送方案对比分析 24结论 26参考文献 27谢辞 28长乐市永辉连锁超市配送线路优化设计摘要：伴随着社会经济的不断进步，物流行业在我国得到了迅猛的发展。通过研究和分析了物流配送的历史和现状，为其在各企业配送合理化提供依据。本设计以长乐市永辉连锁超市配送线路为研究对象，针对其物流配送的现状和存在的问题，选用节约算法和扫描法对其现有的配送路线进行优化设计。最后，通过优化前后的各项指标进行对比，并结合长乐市永辉连锁超市的实际运营情况，选择切实可行的优化设计方案，以达到长乐市永辉连锁超市在日常配送运营中减少配送时间，降低作业成本，提高企业效益，提高客户满意度方面提供有价值的建议，从而为物流配送的线路优化和资源配置提供借鉴。关键词：节约算法；扫描法；路线优化ThedesignofYonghuisupermarketchaindistributionrouteoptimizationinChangleCityAbstract:Withthecontinuousdevelopmentofsocialeconomy,thelogisticsindustryinChinahasbeenrapiddevelopment.Throughtheresearchandanalysisofthehistoryandcurrentsituationoflogisticsdistribution,itprovidesthebasisfortherationalizationoflogisticsdistribution.ThedesignoftheChangleYonghuisupermarketchaindistributionlineastheresearchobject,accordingtoitspresentsituationandproblemsoflogisticsdistribution,thesavingalgorithmandscanningmethodtooptimizethedesignoftheexistingdistributionroute.Finally,throughthecomparisonoftheindicatorsbeforeandafteroptimization,andcombinedwiththeactualoperationsituationofChangleYonghuisupermarketchain,theoptimizationschemeisfeasiblechoice,toachieveChangleYonghuisupermarketchaintoreducedeliverytimedistributionindailyoperations,reduceoperatingcosts,improveenterpriseefficiency,andprovidevaluablesuggestionstoimprovecustomersatisfaction,soastoprovidereferenceforthelogisticsdistributionrouteoptimizationandresourceallocation.Keywords:Savingalgorithm;scanningmethod;Routeoptimization1引言1.1研究的作用及意义物流配送历史悠久，它是一项综合性比较高的物流运动。物流的配送是物流业企业的经济命脉，物流的配送关系到各个行业的快速发展，配送是一个极其重要的环节，是链接发货商与消费者之间的纽带，货物的输送跟他们紧密相连，满足客户的要求，在收货，运货方面全程跟踪，送货，关于客户的要求，颜色搭配，数量，时间等，都需要进行考虑，做到配与送的有机结合。物流配送成本问题，在不断上升，使得运输成本在一定程度出现了很大的提高，车辆的合理利用与分配显得尤为重要。当下，车辆业务运输量增多，城市道路交通堵塞，车辆的等待时间加长，容易造成交通不舒畅，尾气污染，车祸等，都会出现严重的问题，车祸事故以及能源的浪费，都会产生很大的影响，给城市的交通增添了很多的障碍，如果再加上路线选择的不合理，还会使得运输路线拉长，成本无形增加，出现很多多重复的运输，需要去提高配送效率，降低物流成本，尽最大可能限制在大城市停留的时间，舒缓交通的压力[2]。当下永辉超市物流配送存在很大的问题，本篇文章从长远角度来看待问题，致力于长期发展。运用系统的运用与物流配送体系，优化路线，使得配送体系更加完善，建立一个高校快速的快递运输渠道，降低企业成本，增加企业的利益。创造自己的核心竞争力，使得相对应的系统更加完善，合理化，物流配送系统更加的合理化，好又多的物流配送上升一个档次，路线优化问题的解决对于好又多而言，具有非常大的意义。1.2国内外研究现状1.2.1国外研究现状在外国的物流优化配送已经应用到生活的方方面面，各个领域都有设计到。国外在这些方面的研究颇多，取得了一定的成果，运用网络化来进行车辆调配，合理运输。国外的报纸投递，书信，牛奶，衣服，垃圾车，水运，空运，电力，建筑行业服务，等等都有涉及到，物流业的配送发展越来越迅速[3]，加快了经济的发展，促进了人们生活的提高。不断研究设计出最为合适的优化组合路径的方案问题。发达国家物流配送发展较早，受到当地人口，地方文化和科技影响力的发展，比国内更好。美国是最发达的物流，最先进的国家，日本物流理念虽然在五十年代是从美国引进的，但是飞速发展，并形成了自己独特的管理经验和方法，已经成为国家先进的现代物流。由于货物质量高等要求，美国等多个指标，因此配送中心为服务的及时性，准确性和提高质量的研究等等。日本对即时交货的需求也很高，追求及时的分销，如何实现准确高效的研究更多。马修J.Roor在“概念框架”中指出，物流服务代理模型基于[7]，在过去几十年中，货运各种方式，供应链管理和运营研究方法都可以达到改善目的效率。每个货运系统在相互关联的因素中起重要作用，其互动变化的重要性随着时间的推移，是公共部门行为发展的更多货运体系模型，本文提出了运输微观模拟模型的概念框架。这一框架本质上更为全面，为从长期决策基础到短期业务的业务决策提供了一个一致和系统的框架。为了满足客户的迫切需求，加强供应枢纽的战略功能，日本配送中心通过提高货物质量，增加货物种类，增加送货频率。通过提高综合物流的管理能力来控制物流成本，提高物流配送中心处理管理规模变化的能力。物流配送管理必须根据各国的实际情况，根据商品流通的特点和国家的区域特点。如美国主要是机械化和全球化，而日本则主要考虑成本和经营规范。此外，国外少数学者研究物流成本与人员成本之间的关系1.2.2国内研究现状王静（2013）在《浅谈我国物流配送发展》总结出了一些问题，我们要保留现有的模式，去改变一些传统的习惯与规模，配送最优化的路线，降低了配送的成本。打破一辆车只送一条线路的传统模式与方法。城区送货车的增合的一条路线，实现多车走一条线路的送货模式，降低配送成本就是在每辆车的送货模式的方式下，减少出车率，进而降低配送的成本，一切以顾客为核心，满足客户的服务效果，设施各种增值服务，以及代理人增值服务。我们提出的配送运输过程归结为数学建设模型，设计它的求解过程，运用计算机求得合理的优化方案，主要还是车辆的分配和路线的优化问题，这些问题将从理论层次上升到网络层次，统一由计算机系统来进行统一调配。

王天成（2013）在《物流配送车辆优化调度问题概述》中提到，这个问题困扰了我们很多年，物流配送一直受到一定条件的制约，选择最适合的路线，争取最大面积的覆盖到取送货点，优化各个项目，最终达到可观的效益。目前物流配送机构设施还不够健全，系统比较简单，各种因素全部融合考虑，使得构造与现实情况不匹配，我们送货渠道，服务，集体配送，一车装满，一体化程度高，需要综合考虑，这样局限性缩小，速度得到提升。

物流配送途径的各种模型算法是很成熟的，物流配送最短路线目前使用比较多的就是上面提到的Dijkstra算法和Floyd算法，算法都存在它的缺陷，遇到实际问题更加复杂，我们还应该具体对待。

通过阅读各种文献，我们发现国内外的研究也存在一定的问题，很多地方做的不够到位，偏远地区，农村地区的物流配送问题，都是急需要去解决的。我们还会受到自然环境因素，突发事件，道路拥堵问题，这些都是大家反应的比较多，这方面还需要多多解决。电子商务的认识还受到了很大的局限。1.3研究的主要思路关于永乐市永辉超市的网点分布，进了解研究，熟悉情况，物流配送的最优化。根据调查了解到物流配送存在的问题，还有需要去完善的地方，对比进行详细记录，以便后期遇到相同问题时，可以进行修改，运用所学知识，根据设计路径的方式，进行整改，通过节约算法以及扫描算法严格把控每一个细节对现有的配送路线进行微调，每个环节的严格把控，争取做到各个环节的最细致化，理论联系实际，做到最好的路径优化。物流业的飞速发展，经济不断发展，需求量增大，物流成为了当今社会的主流，无论是发达国家还是非发达国家，都是物流的最大市场，对于物流的研究需要更多人的投入，不断实施，不断设计，不断做出新的成绩。快递服务的业务不断增多，服务更加的看重，行业竞争加大，服务意识观念还需提升。更为精确的计算，加上理论的研究，设计出合理的物流配送方案，形成合理的配送模式体系[1]。2物流配送概述2.1物流配送的概念物流配送首先需要了解物流配送的概念以及定义，物流配送是物流企业当中一个重要的环节。国家对于物流术语的定义是货物从供货商那里到达客户手中的一个过程。在实际的需求中，可以将一些基本功能进行很好的结合，包括运货，卸货，储存，包装，运输加工，配送，信息的处理等。物流的配送对于物流企业来说，至关重要，是物流企业的核心骨，物流的字面意思是交货送货的意思。在日本发达国家，对于配送的定义是这样的，他们更为强调的是送货的含义。物流配送其实也就是一种中介服务，是连接生产与消费之间的一种中介服务，是两者之间的一种纽带。做到配与送的有机结合，做到有规模的配送，高质量的服务[6]。2.2物流配送的功能配送是物流企业的重要环节，也是当前一种比较新型的物流形式。随着生产发展的需要，人们生活水平的提高，物流配送的发展在逐步成熟起来，越来越多的人开始进行关注。物流配送的发展，对于企业的发展有着重要的影响，体系的不断完善，企业的更新发展，实现企业利益的最大化，具有举足轻重的作用[8]。（1）配送完善以及优化系统。物流业的不断发展壮大，物流运输配送系统逐步完善，仍有很多地方存在不足，例如，及时性，灵活性，车辆的调配合理性，这样使得运输成本加大，运输成本的不合理化。配送过程可以采取干线运输，支线运输多种方式，去不断完善。（2）配送提高了末端效益。大批量的送货，发货，可以有效的节省成本，不需要迂回运输，重复运输等这些无用功，实现经济的运输，降低成本，使得末端物流经济效益大大提升。（3）配送实现低库存。运用准时制的配送方式，可以安全快速的把货物送到送到了客户手中，不出现库存积压等情况。（4）配送简单，方便。客户订货，直接由一个单位来进行联系，可以邮寄到你需要的地方，这样一方面减轻客户的负担，一方面可以节省企业的成本。（5）配送选取集中库存。采取集中库存，整个社会资源库存低于各企业的分散库存，配送应该具有高度的灵活性，对物资的合理分配有重大作用，减少库存的积压，成本降低，企业效益提升。2.3配送路线优化的意义对于物流行业而言，配送是个重要的问题，而路线的解决将具有更为重要的意义。在设计路线问题当中，根据客户的不同需求，要求，不同的路线途径来进行设计，达到高效，省力，降低成本以及风险投资的问题，切实的做到更好的服务，对于物流业来说有利无弊的。配送方法不同，过程也就出现不同，运输途径也会有很大差别，需要考虑更多的其他因素，适时适当的利用运输工具来进行调整，道路情况的复杂性，车辆拥堵等这些问题，都需要考虑与解决，企业的目标是把货物最好，最快的送到顾客手中，保证它的及时性，安全性，更加方便，便捷。根据配送路线合理的进行小幅度的调整，争取方案更加合理化，贴近实际路况与过程。配送路线的优化，可以从以下三个方面进行入手，第一，从路线的优化来看，可以减少配送时间，提高工作的效率，给企业带来最大化利润。第二，可以加快物流的速度，快递本意就是要快点送到客户的手中，提高客户的满意程度。第三，配送车辆的调配的合理化，提高企业的效率，提高企业的核心力以及竞争力。配送路线优化对于社会来说，可以节省运输的路线，减少里程，减少车辆的空载率，增加企业的利润，降低企业的多余消耗，对于企业的长期发展具有重大的意义。车辆的减少，可以缓解交通的堵塞，对于环境造成的影响降低，很大程度上得到了多方面的改善[10]。2.4我国连锁超市配送的现状分析连锁超市发展有很多年了，发展速度也是突飞猛进，连锁超市在生活中引起了越来越多人的关注，在生活中也是一个非常重要的角色。我国的连锁超市致力于长远发展，但是如果与大型的国际超市相比较，在设施，服务，物流配送方面仍然存在很大差异，还有很多地方需要学习与改进。企业的持续发展，必须拥有核心竞争力，是企业必须思考的问题，也是企业生存的根基。配送行业是企业的最重要的组成部分，更是连锁超市的核心骨。那么，连锁超市配送有几个方面的特点:（1）自建配送中心多，自营配送占主导。大多数超市没有考虑到自己超市本身的规模大小，自己建立的配送中心规模也不可能太大，达不到规模要求，并且对于超市而言，资金链也是一个问题，这样配送中心的效率将会极大降低，不能达到配送的要求，还会造成一定资源的浪费。（2）配送种类增多，服务不够到位。一些连锁超市的商品种类繁多，涉及到生活的方方面面，那么在另一方面对于配送的要求也就在不断增多。加上很多连锁超市都是自己建立的配送中心，配送标准要求不够到位，我国第三方的要求也是标准不一，难以满足客户的需求，物流的配送效率不高，配送水平低，配送的效果更是极大的不理想。（3）统一配送效率低，操作难度大。连锁超市的配送量不稳定，订货量比较多，也有一定的时间要求，如果分配不合理，效率变低，工作效率达不到，运作难度增大，传统的物流企业难以去适应。2.5我国连锁超市配送现状存在的问题成功的连锁超市，高质量的服务是离不开高级的配送，所以对于超市的各个方面都是会相对严格一些，采购成本，运营效率的降低，企业遇到瓶颈，必须分析当前的存在问题，解决当前问题，提高自身连锁企业的竞争力。对于连锁超市存在的问题可以进行一个总结:（1）对物流配送认识存在误区物流企业的配送认识的比较简单，根本没有真正的意识是以客户为中心的服务理念。连锁超市的统一配送必须具备自己的核心竞争力，配送是中间的一个纽带。配送的效率是否高低关于到企业的生存与长期发展，企业专注于物流配送，配送的各个环节都要加以考虑，企业的利益最大化，成本最低化是企业的追求目标。（2）配送中心的配送比率低，配送成本高目前很多的连锁超市配送效率极低，没有很好的进行路线规划设计，成本的运算，配送的效率无法进行提高，企业的利益将一直滞后，企业的效率跟不上，超市的规模也无法发生改变[12]。（3）配送中心设施落后、功能不全很多企业自己建立的配送中心，非常简单，只不过是把仓库简单的进行改造，变成配送中心，机械化，自动化，卸货，操作，搬运这些事情都是由工人来做的，这样显而易见，速度根本提不上来，从而导致效率降低，配送的设施太落后，跟不上进度。（4）配送专业人才短缺，管理水平低下物流配送缺乏专业性的人才，这样就会直接影响到物流配送的效率，路线的规划没有合理，物流信息的加工与不断完善，是企业追求的目标，专业人才，专业的技能都是企业需要的。3长乐市永辉连锁超市配送现状及其优化的必要性分析3.1公司简介永辉超市股份有限公司建立于1998年，公司是以零售为主，用现代物流作为支撑，发展食品以及现代农业，大力以实业开发为基础的大型企业集团产业。永辉超市是中国大陆一家将生鲜农产品引向现代化超市的物流手段，公司以商业跟农业进行结合的双向企业。作为国家的重点企业，荣获"中国驰名商标"。超市采取把生鲜食品引进超市，运用独特的经营模式，找准市场的定位，使得企业迅速发展，不断壮大，得到广大人民群众的认可。它是一种民生超市，以民众为基础，是中国农改超的开创者，有着先进的投资理念，符合传统的模式，又在此基础上进行了改革。现在永辉连锁超市已经有200多家分店，面积也是非常大的，员工达到3万多名，进入世界百强的企业。永辉超市人们的生活超市，商品质量好，服务态度好，提供老百姓方便跟十分便利的一个超市。3.2公司配送现状分析永辉超市是运用自营模式的物流配送，拥有自己的配送中心，物流商品的多样化，多个分点，由总仓库分货然后进行配送到其他分点，进行统一配送模式。先从总公司发单，然后对于订单进行分类，按地址路线进行分配，核对地址，发货量，准确核对之后开始配送模式，然后进行指标打印，仓管部门对于订单进行核查，两者订单是否相符，然后准确的进行单据核对，配送路线可以选择合理的路线，有经验的司机都是知道的，路线的选择仅仅允许有一点点的偏差，这样不会造成太大的影响，尽最大可能的去减小运输成本的损失，防止迂回，重复运输的情况出现，这样一方面会增加企业成本运输费用，一方面加剧了企业经济负担，对于企业是不利的。3.3公司配送必要性分析很多公司仅仅是按照自己的模式来生产运营，不跟其他公司企业进行对比，进行摸索，自己本身的不足无法看到，那也就很难实现根本上的优化路线，配送的合理是根据实际情况以及路线来决定的，路线的不合理，直接就会导致车辆的利用率降低，人员消耗，车辆费用增加，可是就无法获得更高的效益。车辆调配问题跟路线的选择有很大的关系，如果货物不断增加，车辆的不合理调配，运输成本会大力增强，运输成本大大增加。不进行合理的规划，使得货物的及时性无法达到。第一方面，主要是物流的设备达不到，现代化程度低，没有现代化的存储设备，所以很多的操作都得是要人工来进行操作，浪费了很多的时间，还无法提高效率，有时候还会对商品造成一定的破损。这样一来，配送效率降低。第二，配送运输方式不合理，没有合理的措施，在实际生活中出现严重的不合理现象，车辆利用率降低，无法实现最大化的利益，没有进行科学的研究，资源的不合理，造成浪费。第三，运货员任务过大，导致送货效率不高，路线的设计匹配不合理，影响到配送率，劳动力资源匹配不合理。第四，路线规划的不合理，造成了运输费用的增加，这样不仅不能控制成本，还会加大成本的投入。物流配送包括库存费用，管理费用，运输费用，都在内，在这几个方面都要进行计算与管理，运输费用的降低就可以减少物流费用的运输，进而提高公司的效益。关于物流运输路线的安排是否合理化，需要根据实际情况，计算过程，合理安排，以免出现不合理安排的现象运用科学的方法，就是以最少的开支，最少的环节过程，最短最优化的路径，最快的速度来进行产品活动的配送。以此可以得出，对于路线的优化设计是具有重大意义的，永辉超市的合理路线设计存在很大的必要性。4配送线路优化方法介绍4.1节约算法4.1.1节约算法的基本原理他的核心思想就是将运输问题中存在的两个回路（0，…,i,…,0）和（0，j，…，0）合并成为一个回路（0，…，i,j,…，0）。在整个合并的过程中，整个运输问题的总距离将会发生变化，如果变化后的总运距下降，则称节省了运输距离[1]。相应的变化值，叫做节约距离。两节点的原路径与较短路径如下图所示ii0j0ij原路径较短路径图4-1节约算法的图像描述4.1.2节约算法的求解步骤输入：需求点集={1,2,…,n},各点需求量,各点间最短距离;车辆集合={1,2,…,m},各车辆最大载重量，各车辆最大运距。输出：各车辆配送点集第一步,将按从大到小排序,使得;≥≥…≥。第二步,对于所有的客户对(i,j),采用式（7）计算节约里程的值,其中,i=1,2,…,n;j=1,2,…,n,将大于零的从大到小排列形成队列。第三步,求初始可行解。确定各车辆配送点集令={j},j=1,2,…,n(先采取单点配送)。第四步,合并配送路径。直到节约里程的队列空为止,重复下列步骤:按照节约里程队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i,j连接起来,即可令。如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对[11]。4.2扫描算法4.2.1扫描算法的基本原理扫描算法是一种直接针对实际问题的基于平面几何的求解方法，典型的先分组后安排路线的方法。所谓分组，即指派给每辆车一组点。一种简单的分组方法是将以配送中心为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车，然后扩充路线。如果在进行了一次“分组-路线”的路线构造后，还存在未分配点，则再进行“分组-路线”程序。如此反复，直到所有的点均已分配为止。4.2.2扫描算法的求解步骤（1）以起始点0点作为极坐标系的原点，建立极坐标系。（2）分组从最小角度的顾客开始建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量超出了负载的限制。然后继续建立一个新的组，继续按逆时针方向，将客户加入组中。（3）重复（2）中的过程，直到所有客户都被分类为止。（4）路径优化对各个组内的单回路进行路径优化。5长乐市永辉连锁超市配送路线优化方案5.1基本数据分析已知永辉（福州）连锁超市的总仓库在鳌峰洲食品仓库的5号仓库，设其为节点0。公司有6吨的货车十几辆，设各点间的距离为C，C={∣i,j=1……，13}，节约距离△。每部车的载重量为，各连锁超市需求量为=（i=1,……，13），且30公里。现以福州市鼓楼区的13家永辉连锁超市的蔬菜的配送为例，优化永辉连锁超市的配送线路。各连锁超市平均每天需求量如下所示。表5-1各需求点运量节点店名地址需求量（t）1永辉超市江滨大道66号-722公交车站店斗池路22号1.23西门店西洪路57号2.34屏西店屏西路18号1.65西二环中路店西二环中路81号1.36黎明店凤凰新村9号1.57福屿东店洪山园路86号1.88第五连锁店江厝路17号0.99津泰店津泰路93号2.810澳门店澳门路72号2.111屏山店鼓屏路160号2.412湖头街店湖头街89号西湖世家1.713湖前店江厝路76号1.40012675109312114813图5-1各节点的分布图5.3基于节约算法进行配送线路优化方案根据4.1节约算法的介绍，并结合5.1的数据，对永辉连锁超市的配送线路进行优化。其具体计算步骤如下：（1）确定各超市的最短距离。因为距离对称，所以，各超市间最短距离如表所示。表5-2各节点间的最短距离（km）012345678910111213008.88.78.810138.58.40.61.573.12.752.96.4304.8401.43.8501.85.3601.573.1352.96.4704.125.5805.790510033.55.411033.31203.81302）求节约里程计算各点间连接的距离节约值：△=，并由大到小的顺序排列于表5-3中。表5-3节点之间节约值连接点节约里程连接点节约里程连接点节约里程8-1324.54-8244-1322.63-1221.83-421.44-11213-520.33-720.34-1220.13-1119.712-1319.65-719.63-819.63-1319.68-1119.58-1219.35-1219.211-1319.17-1219.14-518.84-718.73-1018.63-918.42-318.211-1218.23-618.15-617.46-717.32-717.24-917.15-8176-12177-816.92-616.95-1316.92-1216.91-316.84-1016.87-1316.84-616.62-416.52-516.51-1216.49-1016.21-716.25-1116.19-111610-12169-12167-11168-915.89-1315.87-1015.65-1015.610-1115.58-1015.410-1315.31-415.11-515.11-615.17-9151-214.96-814.82-814.76-1314.72-1314.62-1014.46-914.26-1014.22-914.15-913.96-1113.92-1113.81-813.31-1313.21-1012.71-912.61-1112.4（3）求初始解令=｛i｝（=1，…，13），最短路径=2（=1，…，13），且公里，载重量，且6T，对13个客户点进行标记（合并次数）。（4）按节约里程从大到小合并路径对于△=24.5km:8∈,13∈，2.3t<6t,△=2*13+2*12.3-24.5=26.1km<30km,。故合并8,13两点。令，2.3t，=26.1km，，。对于△=24km:8∈,4∈，3.9t<6t,+-△=26.1+2*14.4-24=30.9>30km,不满足合并条件。对于△=22.6km:13∈,4∈，3.9t<6t,+-△=26.1+2*14.4-24=30.9>30km,不满足合并条件。对于△=21.8km:3∈,12∈，4t<6t,△=2*12.1+2*11.1-21.8=24.6km<30km,。故合并3,12两点。令，4t，=24.6km，，。对于△=21.4km:3∈,4∈，5.6t<6t,△=24.6+2*14.4-21.4=32km>30km,不满足合并条件。对于△=21km:11∈,4∈，4t<6t,△=2*14.4+2*10.1-21=28km<30km,。故合并4,11两点。令，4t，=28km，，。对于△=20.3km:3∈,5∈，7.1t>6t,不满足合并条件。对于△=20.3km:3∈,7∈，5.8t<6t,△=24.6+2*10-20.3=24.3km<30km,。故合并3,7两点。令，5.8t，=24.3km，，。对于△=20.1km:12∈,4∈，8t>6t,不满足合并条件。对于△=19.7km:3∈,11∈，8t>6t,不满足合并条件。对于△=19.6km:12∈,13∈，6.3t>6t,不满足合并条件。对于△=19.6km:5∈,7∈，7.1t>6t,不满足合并条件。对于△=19.6km:3∈,8∈，6.3t>6t,不满足合并条件。对于△=19.6km:3∈,13∈，6.3t>6t,不满足合并条件。对于△=19.5km:8∈,11∈，6.3t>6t,不满足合并条件。对于△=19.3km:12∈,8∈，6.3t>6t,不满足合并条件。对于△=19.2km:5∈,12∈，7.1t>6t,不满足合并条件。对于△=19.1km:13∈,11∈，6.3t>6t,不满足合并条件。对于△=19.1km:7∈,12∈，无需再合并。对于△=18.8km:4∈，5∈,5.3t<6t,△=28+2*9.9-18.8=29km<30km,。故合并4,5两点。令，5.3t，=29km，，。对于△=18.7km:4∈，7∈,11.1t>6t,不满足合并条件。对于△=18.6km:3∈,10∈，7.9t>6t,不满足合并条件。对于△=18.4km:3∈,9∈，8.6t>6t,不满足合并条件。对于△=18.2km:3∈,2∈，7t>6t,不满足合并条件。对于△=18.2km:12∈,11∈，8t>6t,不满足合并条件。对于△=18.1km:3∈,6∈，7.3t>6t,不满足合并条件。对于△=17.4km:5∈，6∈，6.8>6t,不满足合并条件。对于△=17.3km:6∈，7∈，6.8>6t,不满足合并条件。对于△=17.1km:4∈，9∈,8.1t>6t,不满足合并条件。对于△=17km:5∈，8∈，7.6t>6t,不满足合并条件。对于△=17km:6∈，12∈，7.3t>6t,不满足合并条件。对于△=16.9km:7∈，8∈，8.1t>6t,不满足合并条件。对于△=16.9km:2∈，6∈，2.7t<6t,△=2*8.7+2*8.8-16.9=18.1km<30km,。故合并2,6两点。令，2.7t，=18.1km，，。对于△=16.9km:5∈，13∈，7.6t>6t,不满足合并条件。对于△=16.9km:2∈，12∈，8.5t>6t,不满足合并条件。对于△=16.8km:1∈，3∈，7.8t>6t,不满足合并条件。对于△=16.8km:4∈，10∈,7.4t>6t,不满足合并条件。对于△=16.8km:7∈，13∈，8.1t>6t,不满足合并条件。对于△=16.6km:4∈，6∈，8t>6t,不满足合并条件。对于△=16.5km:4∈，2∈，8t>6t,不满足合并条件。对于△=16.5km:5∈，2∈，8t>6t,不满足合并条件。对于△=16.4km:1∈，12∈，7.8t>6t,不满足合并条件。对于△=16.2km:9∈，10∈,4.9t<6t,△=2*8.5+2*8.4-16.2=17.6km<30km,。故合并9,10两点。令，4.9t，=17.6km，，。对于△=16.2km:1∈，7∈，7.8t>6t,不满足合并条件。对于△=16.1km:5∈，11∈，无需再合并。对于△=16km:9∈，11∈，10.2t>6t,不满足合并条件。对于△=16km:10∈，12∈，10.7t>6t,不满足合并条件。对于△=16km:9∈，12∈，10.7t>6t,不满足合并条件。对于△=16km:7∈，11∈，11.1t>6t,不满足合并条件。对于△=15.8km:9∈，8∈，7.2t>6t,不满足合并条件。对于△=15.8km:9∈，13∈，7.2t>6t,不满足合并条件。对于△=15.6km:7∈，10∈，10.7t>6t,不满足合并条件。对于△=15.6km:5∈，10∈，10.7t>6t,不满足合并条件。对于△=15.5km:10∈，11∈，10.2t>6t,不满足合并条件。对于△=15.3km:10∈，13∈，7.2t>6t,不满足合并条件。对于△=15.1km:1∈，4∈，7.3t>6t,不满足合并条件。对于△=15.1km:1∈，5∈，7.3t>6t,不满足合并条件。对于△=15.1km:1∈，6∈，4.7t<6t,△=18.1+2*8.8-15.1=20.6km<30km,。故合并1,6两点。令，4.7t，=20.6km，，。对于△=15km:9∈，7∈，10.7t>6t,不满足合并条件。对于△=14.9km:1∈，2∈，无需再合并。对于△=14.8km:6∈，8∈，7t>6t,不满足合并条件。对于△=14.7km:2∈，8∈，7t>6t,不满足合并条件。对于△=14.7km:6∈，13∈，7t>6t,不满足合并条件。对于△=14.4km:2∈，10∈，8.1t>6t,不满足合并条件。对于△=14.2km:6∈，9∈，9.6t>6t,不满足合并条件。对于△=14.2km:6∈，10∈，9.6t>6t,不满足合并条件。对于△=14.1km:2∈，9∈，9.6t>6t,不满足合并条件。对于△=13.9km:5∈，9∈，9.9t>6t,不满足合并条件。对于△=13.9km:6∈，11∈，10.2t>6t,不满足合并条件。对于△=13.8km:2∈，11∈，10.2t>6t,不满足合并条件。对于△=13.3km:1∈，8∈，7t>6t,不满足合并条件。对于△=13.2km:1∈，13∈，7t>6t,不满足合并条件。对于△=12.7km:1∈，10∈，9.6t>6t,不满足合并条件。对于△=12.6km:1∈，9∈，9.6t>6t,不满足合并条件。对于△=12.4km:1∈，11∈，10t>6t,不满足合并条件。可得最终的配送线路为：{8,13},即0→8→13→0，2.3t，=26.1km，，车载率：38.3%；{3,7，12}，即0→3→7→12→0，5.3t，=24.3km，，车载率：88.3%；{4,5，11}，即0→4→5→11→0，5.3t，=29km，，车载率：88.3%；={1，2,6}，即0→1→2→6→0，4.7t，18.1km，，车载率：78.3%；{9,10}，即0→9→10→0，4.9t，=17.6km，，车载率：81.7%；共需要5部吨货车，总运输距离为115.1km，平均车载率74.98%。运输路径如图5-3所示。0012675109312114813图5-5用节约算法计算的配送线路5.4基于扫描算法进行配送线路优化方案对永辉连锁超市配送线路采用扫描算法进行优化。其具体的计算步骤为：（1）建立极坐标系以节点0为坐标原点，水平向右方向为角度零，建立极坐标系。（2）分组从角度为零向逆时针方向进行扫描，第一个被分组的是节点13，装载量为1.4t，继续转动。下一个被分组的是节点8，装载量为1.4+0.9=2.3t，继续转动。下一个被分组的是节点11，装载量为2.3+2.4=4.7t,继续转动。下一个被分组的是节点4，装载量为4.7+1.6=6.3t>6t,由于超过了限制范围，按分组规则，需要一个新的组，这样子在第一组里面有节点13，8,11。在第二组中有节点4，装载量为1.6t，继续转动，下一个被分组的是节点9，装载量为1.6+2.8=4.4t，继续转动。下一个被分组的是节点12，装载量为4.4+1.7=6.1t>6t,由于超过了限制范围，按分组规则，需要一个新的组，这样子在第二组里面有节点4,9。在第三组中有节点12，装载量为1.7t，继续转动，下一个被分组的是节点10，装载量为1.7+2.1=3.8t,继续转动，下一个被分组的是节点3，装载量为3.8+2.3=6.1t>6t,由于超过了限制范围，按分组规则，需要一个新的组，这样子在第三组里面有节点12,10。在第四组中有节点3，装载量为2.3t,继续转动。下一个被分组的是节点5，装载量为2.3+1.3=3.6，继续转动，下一个被分组的是节点7，装载量为3.6+1.8=5.4t，继续转动，下一个被分组的是节点2，装载量为5.4+1.2=6.6t>6t,由于超过了限制范围，按分组规则，需要一个新的组，这样子在第四组里面有节点3,5,7。在五组中有节点2，装载量为1.2t，继续转动，下一个被分组的是节点6，装载量为1.2+1.5=2.7t,继续转动，下一个被分组的是节点1，装载量为2.7+2=4.7t,这样子在第五组中有节点2,6,1。所有分组结束（3）组内的线路优化对上面的5组的配送线路进行优化，此问题属于单回路运输问题，所以适用TSP模型进行路径优化，即采用启发式算法中的最近插入法来得到一个相对比较满意的可行解，所得优化的结果如下所示。0→11→8→13→0运输距离：26.8km运量：4.7t，车载率：78.3%；0→9→4→0运输距离：26.7km运量：4.4t，车载率：73.3%；0→12→10→0运输距离：23km运量：3.8t，车载率：63.3%；0→5→3→7→0运输距离：23.5km运量：5.4t，车载率：90.3%；0→2→