交通运输专业 天天物流公司配送线路优化设计和实现分析研究

目录TOC\o"1-3"\h\u中文摘要 1英文摘要 21绪论 31.1研究的作用及意义 31.2国内外研究现状 31.2.1国外研究现状 31.2.2国内研究现状 41.3研究思路 62配送线路的优化方法 62.1节约里程算法 62.2扫描算法 72.3改进后的最近插入法 83天天物流公司简介 93.1天天物流公司概述 93.2天天物流配送线路现状 103.3天天物流企业配送过程中存在的问题 113.4配送线路优化的意义 124天天物流配送线路优化设计 134.1线路优化基础数据处理 134.2基于节约算法的企业配送路线优化 144.3基于改进的最近插入法的企业配送路线优化 184.4基于扫描算法的企业配送路线优化 204.5三种配送线路优化分案比较分析 23结论 25致谢 26 参考文献 27天天物流阜阳市分公司配送线路优化设计摘要：伴物流企业在不断发展，给我国带来了机遇，也带来了压力，紧接着还有巨大的挑战。经济快速发展，物流业的突飞猛进，物流业成为了国家重点扶持的企业，得到了极大的关注度与认可度。物流业的不断强大，市场的竞争也变得愈来愈激烈，在物流业飞速发展的同时，遭到了金融危机的影响，对物流业而言，无疑是不利的。现在本文以阜阳市物流分公司为例，来展开讨论，了解本企业的基本情况，配送路线，管理的一体化等等方面。以及存在的一些问题，来进行一定程度的优化与实施。首先对物流配送的优化目标以及方法进行了简单理论概述，紧接着对于物流业配送路线的优化问题进行了合理的设计，最后要通过计算核算出数据，进行分析，得到最为合理的优化路线途径。用几种方法进行优化，权衡比较讨论出适合的方案，根据实际路程来进行计算，争取获得最为合适的最优化方案，这样可以提高工作的效率，进而降低工作的成本，间接的给企业带来大的收益。在竞争日益激烈的时代，物流业面临巨大的竞争压力，物流业的长远发展必须立足于长远考虑与打算，不断更新，不断摸索。关键词：物流产业；扫描法；节约算法；线路优化DailylogisticsFuyangbranchdistributionlineoptimizationdesignAbstract:Logisticsenterprisesinthecontinuousdevelopmentofourcountryhasbroughtopportunities,butalsobroughtpressure,followedbyahugechallenge.Withtherapiddevelopmentofeconomyandtherapiddevelopmentoflogisticsindustry,thelogisticsindustryhasbecomeanationalkeysupportenterprise,whichhasreceivedgreatattentionandrecognition.Withthecontinuousdevelopmentofthelogisticsindustry,thelogisticsindustryisbecomingmoreandmorefierce.Intherapiddevelopmentofthelogisticsindustry,ithasbeenaffectedbythefinancialcrisis.Inthispaper,thelogisticsbranchofFuyangCity,forexample,toexpandthediscussion,tounderstandthebasicsituationoftheenterprise,distributionlines,theintegrationofmanagementandsoon.Aswellassomeproblems,toacertaindegreeofoptimizationandimplementation.First,theobjectofoptimizationoflogisticsdistributionandsummarizesthemethodofsimpletheory,thentheoptimizationproblemsinthelogisticsdistributionrouteofreasonabledesign,finallythroughthecalculationofaccountingdata,analysis,gettingthemostreasonablewaytorouteoptimization.Optimizedbyseveralmethodstocomparediscussasuitableplan,accordingtotheactualdistancetocalculate,getthemostsuitableoptimizationscheme,whichcanimproveworkingefficiency,thusreducingthecostofworkindirectlytotheenterprisebroughtbiggains.Intheeraofincreasinglyfiercecompetition,thelogisticsindustryisfacingtremendouscompetitivepressure,thelong-termdevelopmentofthelogisticsindustrymustbebasedonlong-termconsiderationsandplans,constantlyupdated,andconstantlyexplore.Keywords:Logisticsindustry;scanningmethod;Savingalgorithm;RouteoptimizationTOC\o"1-3"\h\u1绪论1.1研究的作用及意义物流业的发展从小范围开始，逐渐的发展壮大，物流业首先关心的则是配送问题，而配送又包括两个方面，一个是一般配送，另一个是特殊配送，这两个是有差别的，一般配送主要是运货，送货，卸货，包装，保管，运输配送到达目的地，这种方式称之为一般配送，或者是普通配送。而特殊配送，还必须加以活动在里面，它的范围更为的广泛，跟普通的配送，最明显的差别在于它需要分拣配货，这是一个特殊的服务，也是它的独特之处，最终的目的都是一样的，都是将货物送到客户的手中在目的。配送的两种手段，其实也可以将它看成就是运输配送方式的不同。本质都是一样的，主体活动有些许差异。配送线路优化在配送优化中的占有非常重要的作用，在配送货物的过程中，配送线路的优劣对配送所用的时间、成本和效率有很大的影响，如果设计了合理高效的配送路线，可以对运输进行合理的分工，大大减少配送的时间，降低配送的成本，提高配送的效率，则能够更好地为顾客服务，吸引更多的顾客，提高公司的良好形象。配送线路优化是对多个发货点和收货点之间的路线进行合理的安排，让运输车辆在各个节点之间高效的运送货物，在满足一定条件下，达到所需的目标，例如行驶路程最短、所需费用最小、所用车辆最少等目标。但在配送货物的过程中情况复杂且有许多变量，比如配送点比较多，货物的大小尺寸问题，道路行驶情况复杂多变，驾驶员的熟练程度等情况，使线路优化问题呈现多种不一的解决方法，目前基于各种算法的线路优化研究，如节约里程法、扫描法、蚁群算法、遗传算法等等，本论文将针对聚力分析法和节约里程法对天天物流阜阳分公司配送线路进行优化设计。期望能提出有价值的建议！1.2国内外研究现状1.2.1国外研究现状Pirkul与Jayaraman建立了一个配送策略模型，但这个模型仅从一个配送中心来限制用户的供应需求，应用范围比较狭窄，没有建立配送策略模型，具有一定的局限性。尽管国外对物流配送的定量研究成果颇多，但是涉及到快递企业配送定量研究相对较少，而快递企业在配送过程上更具复杂性，需要在理论上不断的创新。Karen2001年在《Designandoperationofmultimode》一文中研究了包裹快递运输企业的物流系统设计方案和运作规划战略，这些企业具有多种运输方式并且能够提供多种服务水平，作者研究了长期战略决策问题和短期战略决策问题，建立了连续逼近模型和数值优化模型的组合模型，说明了这两种模型的互补性，提出了快递的运输网络和地面运输网络的整合方式，通过模式方法对运输网络路径问题进行了优化。在国外一些物流发达的国家，对车辆路线问题的研究较早，也取得了丰富成果，物流配送车辆优化调度问题最早是由Dantzing和Ramser于1959年首次提出的。主要包括运输路线安排问题（VRP）。自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大进展。该问题一般定义为：对一系列装货点和（或）卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程短、费用最少、时间尽量少、使用车辆数尽量少等）。JameAsher在1993年通过对区域物流配送问题的研究，最后在区域内物流配送的模型思想下对区域内物流过程中的配送车辆行驶的路径问题进行了合理的优化，并对区域物流配送路径以及配送中心的选址等相关问题做了相关的研究。Fisher在2002年通过对区域物流配送模型的分析过后，成功把区域物流配送问题分成两个问题，第一个问题是配送前的车辆调度问题也就是VRP问题，其次是配送过程中的路径优化问题，所以在配送过程中要根据问题的不同。从而运用不同优化方法。由于问题的不同导致在大型的物流公司有着功能不同的配送中心比如有生产型的配送中心、调度以及运输配送中心。Rao等人对VRP中应用列生成方法求解。提出优化对偶变量向量，对该简化问题松弛，求解列中的最小边际成本，确定最优解。1.2.2国内研究现状由于我国快递行业发展较晚，对这方面的研究也很少，但随着近几年我国快递市场的迅速发展，许多专家学者也注意到了这个领域，正逐步对这个领域进行开发和研究。张潜和李钟慎[7]等人在2006年对一类模糊物流路径优化相关问题进行了研究，通过启发式算法求得了最优解。同年，张良智和何爱民等人讨论了一类客户点具体位置的VRP问题，将时限加入到传统遗传算法中，为后面研究多客户点运算及结合实时路网的研究提供了有力的支持。李前喜和王耀球等人在2008年介绍了日本快递业的物流系统、经营战略、市场竞争体系并对其发展趋势进行了分析。同年杜培全和陈森发从在分析各小区域潜在的顾客群的特点及其构成的基础上，结合了快递物流的特点，建立了混合0-1整数规划的快递服务网点的地址优化模型。李雪光和胡松峰[8]在2010年从配送的角度，以同城快递参与国内物流的方式来降低物流风险和提高配送质量，研究了同城快递完善C2C配送模式。徐柳和贾继红等人从民营物流企业特别是终端物流配送和管理上分析现代城市中快递物流管理与服务的优缺点，并提出了改进措施及管理方法。1.3研究思路需要得到一套最为合理化的方案，需要多个方面的考虑与考察。一开始从网上以及亲戚朋友进行走访，了解蚌埠市顺丰的各个网点，配送路线情况，以及它的配送优化方案。如果有条件的情况下，可以对于配送进行全程的跟踪服务，争取及时发现问题，解决问题，可以不断的进行完善。做一定的记录，有利于配送过程服务的不断优化，不断提升。根据相关的交通规则路线问题，结合实际情况，进行研究跟分析，争取做到每个环节的更加详细化，准确化，得到最为合理的优化路线，去客服一些问题，做到实际问题与方案更加合理化。经济发展飞速，物流业也在不断的迅速发展，物流业新起了很大的一段风波，热潮来袭，快递也服务不断增加，需求量加大，我们的业务增多，任务不断加重，这时候也在要求方案更加的优化，合理。2配送线路的优化方法2.1节约里程算法节约里程算法的核心思想是将运输问题中存在的两个回路（0，…，i，0）和（0，j，…，0）合并成一个回路（0，…，i，j，…，0）。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离。相应的变化值，叫做节约距离，如式（1）所示。（1）调整过程如图2-1所示。jjjji0i00ii调整前调整后图2-1节约算法的图像描述节约里程法的基本步骤如下：已知条件:需求点集={1,2,…,n},各点需求量,各点间最短距离。第一步,形成一个初始解。确定各车辆配送点集令,=1,2,…,n(先采取单点配送)。第二步,进行节约度的计算。计算所有点对的节约度QUOTE，然后对计算结果进行升序排列。第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始，直到节约里程的队列空为止,重复下列步骤:按照节约里程队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i,j连接起来,即可令。如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对。2.2扫描算法扫描算法是在1974年被提出来的，用于解决车辆数目不限制的问题。扫描法可以分为两种，一种是先分组后路径，另一种是先路径后分组。在本文中，我们采用的是先分组后路径的方法来进行计算优化。扫描法没说一定是一种逐渐逼近法来计算的，此方法存在一定的漏洞，虽然不是最佳的选择，但是可以求得解，可以有效的去解决一定的路径问题，物流配送车辆路径优化问题，当遇到多种客户编号不一样时，可以用扫描法来进行求解，这样效率大大提高，满意度也会增加，增加它的计算量。研究路线计算得出，这种方法适合用于必须满足两个条件，第一，必须这条线路的客户量大，第二，路线不是千变万化的，相对简单一些。这样的情况下，采用扫描法还是比较合适的，求得的解是有效的。扫描算法分四个步骤完成：（1）以起始点作为极坐标系的原点，并以连通图中的任意一顾客点和原点的连线定义为角度零，建立极坐标系。然后对所有的顾客所在的位置，进行坐标系的变换，全部都转换为极坐标系。（2）分组。从最小角度的顾客开始，建立一个组，按逆时针方向，将顾客逐个加入等到组中，直到顾客的需求总量超出了负载限制，然后建立一个新的组，继续按逆时针方向，将顾客继续加入到组中。（3）重复（2）的过程，直到所有的顾客都被分类为止。（4）路径优化。对各个分组内的顾客点，就是一个个单独的TSP模型的线路优化问题，可以用前面介绍的TSP模型的方法对结果进行优化，选择一个合理的线路。2.3改进后的最近插入法TSP模型是单回路运输问题的最为典型的一个模型，它的全称是TravelingSalesmanProblem1，中文叫做旅行商问题。它是一个典型的NP-Hard问题，对于大规模的线路优化问题，无法获得最优解。最近插入法就是一种解决此问题的启发式算法。最近插入法是Rosenkrantz和Stearns等人在1977年提出的一种用于解决TSP(旅行商)问题的算法。基于参考点的插入法对参考点的选择有很大的依赖性，一个简单的改进方法是基于多个随机参考点进行的多次搜索，进而选出性能最好的解，但这显然势必会大大增加搜索量，另外对于大规模问题参考点的位置的改变对性能的改进也很有限。最近插入法由四步完成：（1）找到最小的节点，形成一个子回路（subtour），。（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。（3)在子回路中找到一条弧（i，j）,使得+-最小，然后将节点插入到节点，之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点加入到子回路中。（4）重复步骤（2）、（3），直到所有的节点都加入到子回路中。这样，子回路就演变为了一个TSP的解。由于最近插入法解决的是单回路运输问题，故在此方法基础上进行改进和修正，使其能解决多回路运输VRP问题。有改进的方法如下：（1）找到最小的节点，形成一个子回路（subtour），。（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。若此时回路的总货运量未超过车的载重限制，则继续步骤（3），否则，转（1）寻找新的一条回路。（3）)在子回路中找到一条弧（i，j）,使得+-最小，然后将节点插入到节点，之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点加入到子回路中。若此时该回路的总路程为未超过车辆的行程限制，则继续步骤（4），否则转步骤（1），寻找新的一条回路。（4）重复步骤（2）和（3），直到每一个节点都被归入某一个子回路中。3天天物流公司简介3.1天天物流公司概述国内的物流很多，每个物流他们的宗旨与服务是不一样的。天天物流始终秉承以客户服务为中心，随时为客户服务，把客户放在第一位，坚持创新，打造自己的品牌，做自己的特色，争取提供更好的服务给客户，快速高效，及时准确，高端服务，给客户创造更大的服务与价值，客户是企业生存的根基。天天物流的运输方式目前两种，一种是汽车运输，另一种是空中运输，但是两种所占比例不一样，汽车运输占到百分之74左右，而空中运输占到百分之26左右，空运业务在不断减少，占主导地位的还是汽车运输，占绝大多数。天天物流在不断开发自己的新产品，还做一些其他业务，保价运输，客户贷款，安全包装，通过这样一些渠道来增加自己企业的利益。物流业发展着实迅速，但是并不是没一家都特别好，做企业必须要有自己的核心竞争力，要不然迟早会被淘汰出局。对于物流货物物件比较小的接单比较容易，可是对于超过30kg的以及到1t的货物，很少有物流可以把它做好，快递公司必须要有一个合理的定位，把核心力抓好，做的更加的专业，把它当作企业的长远发展目标来进行，天天物流不局限于小的货物，把超过30kg的货物做的更加专业，更加精通。天天物流明确了自己的目标，拥有自己的特色，抓住核心竞争力，使得企业获得更好更快的发展。3.2天天物流配送线路现状天天物流的发展目前在全国已经有30个省，市，自治区，网点也在不断扩大，目前已经达到3000多家，覆盖全国90％以上的物流业网点，大部分地区都有它的分布，特别是经济相对发达的城市，人口集中的地区发展更加的迅速，而在一些贫困地区，网点还没法真正落实下来，货物量的减少，车辆开往过去不方便，车辆的空车率增高，无形中浪费程度增大。已知阜阳天天物流分公司位置为0点，分别向阜阳市内9家合作汽车商合作，现要给其配送汽车配件。现将9个合作商编号为1、2、3、4、5、、6、7、8、9。其拥有一辆7吨的车和两辆11吨的车，7吨卡车最大容量为300个汽车配件，11吨卡车最大载量为500个。设各点间的距离为，节约距离为。各点需求量为，每辆车的行驶里程为，公里，合作商点1，2，…，9。如表3-1表3-1各点的需求量和配送距离合作商123456789需求量（个/日）18012012060802207090200配送距离（km）7.598.9218.6717.035.715.388.78.158.25（资料来源：阜阳天天物流信息系统）各配送线路的里程，所需司机数量的基本情况如表3-2所示表3-2配送信息表路线运距运货量车型司机0-1-2-021.37km3007吨货车10-3-4-037.34km1807吨货车10-5-6-031.54km3007吨货车10-7-8-020.27km1607吨货车10-9-016.50km2007吨货车1（资料来源：阜阳天天物流信息系统）由上表可知，公司每日需7吨货车5车次配送，司机5人次，运输总里程为127.02千米。3.3天天物流企业配送过程中存在的问题从物流配送行业的现实情况来看，以阜阳天天物流调查为例，进行研究。天天物流公司的各大业务都在实施业务流程信息化的管理，都是运用网络来进行操作，更加的便捷方便。天天物流并不是说没有弊端，还有很多地方需要去完善，以阜阳天天物流为例，进行详细的介绍以及配送问题的很多地方需要去不断完善。（1）对流运输。相向运输，同一种类货物彼此之间可以相互代替，再同一路线上，或者同一线路之间，交错路线都是可以的，制定合格的产品运输路线图。（2）运输返程问题，车辆的空车回来，这样造成一定程度的损失，也是一种不合理的物流运输方式，这个我们必须做周密的打算与计划，防止出现资源的匹配不合适，运输的不合理，在实际运输过程中，是不允许的。（3）.重复运输。它的定义是指在车辆运货送往目的地途中，还没有到达目的时，在之前将货物卸下，然后再回去进行二次运输的方式，称之为重复运输。重复运输还有一种其他的方式，同种货物重复运输，在一个点进货，一个点出货，然后再运输出去的方式。这样做的目的，会无形中增加成本，运输时间长，导致运货速度慢，论时间，货物，人力，花费都是不划算的。（4）迂回运输。是一种舍近求远的方式。明明可以选择物流路径的最短路程，可偏偏要选择最长的路程，这是一种极其不合理的选择路线方式。（5）倒流运输。使得货物回流的一种现象，这种运输也是极其不合理的，往返两程都是极其不合理，没有必要的，形成了浪费，或是隐蔽对流。（6）远距离运输。舍近求远的运输。近处的资源不加以利用，跑到远处去寻找资源，造成了很大程度上的浪费，这样肯定会加大浪费的，远距离的不方便，耗时长，运输周转慢，综合各种资源都是不合理的。阜阳物流业公司存在很多方面的问题，不单单只是这些，诚信度不够高，信息化机械化程度不高，各方面还需要不断完善。3.4配送线路优化的意义对于物流行业而言，配送是个重要的问题，而路线的解决将具有更为重要的意义。在设计路线问题当中，根据客户的不同需求，要求，不同的路线途径来进行设计，达到高效，省力，降低成本以及风险投资的问题，切实的做到更好的服务，对于物流业来说有利无弊的。配送方法不同，过程也就出现不同，运输途径也会有很大差别，需要考虑更多的其他因素，适时适当的利用运输工具来进行调整，道路情况的复杂性，车辆拥堵等这些问题，都需要考虑与解决，企业的目标是把货物最好，最快的送到顾客手中，保证它的及时性，安全性，更加方便，便捷。根据配送路线合理的进行小幅度的调整，争取方案更加合理化，贴近实际路况与过程。配送线路优化对天天物流来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到合作商的手中，提高合作商满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于天天物流在同行中的提高竞争力与效益。配送线路优化对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用。4天天物流配送线路优化设计4.1线路优化基础数据处理根据上文天天物流的配送线路现状，我们已知n=9,m=3,W1=7,W2=W3=11，L1=L2=L3=60，令W4=W5=W6=W7=W8=W9=7，L4=L5=L6=L7=L8=60下图4-1为天天物流与顾客分布的连通图15.3815.383.429.1412.688.1511.578.335.78.257.598.9210.7212.011.6.49.734.8615.470123456879图4-1天天与顾客点分布的连通图解：（1）通过各点之间的最短距离计算,我们得到了个点间的最短距离,如下表4-1中所示：表4-1各点间的最短距离表县市V0V1V2V3V4V5V6V7V8V9V007.598.9218.0616.425.7015.3811.578.158.25V104.8614.5916.2313.2922.9719.1615.7415.47V209.7311.3714.6223.3820.4917.0717.17V301.6412.3613.6521.9825.2226.31V4010.7212.0120.3423.5824.67V5021.0817.2713.8513.95V608.3311.5720.71V703.4212.68V809.14V904.2基于节约算法的企业配送路线优化运用节约法确定物流配送路线，必须需要去满足以下条件，第一，车辆不超载，第二，所有客户的需求，第三，单辆车的运货时间不超过一定的范围，第四，客户的货物到达时间。以上几个条件的做到，还是需要通过精心计算的，符合企业与客户最短路线，最短车辆路程来进行配送运输，争取做到路线的合理配送，使得客户满意，企业得到一定的利益，取得一定的收益。节约里程数是由公式，i,j=0,1,2,3,4...9计算得出，计算结果如下所示：011.6511.067.7800000.37017.2513.9700.92000032.8411.419.797.650.990011.419.797.650.990=00000018.6211.962.92016.37.1407.260（1）将按从小到大的顺序排列如下表4-2所示：表4-2排序表Vi，VjVi，VjVi，Vj3-432.841-211.657-97.143-619.793-511.46-92.924-619.794-511.43-80.996-718.621-311.064-80.992-317.251-47.782-60.927-816.33-77.651-90.372-413.974-77.656-811.968-97.26（2）按从大到小合并路径①对,,令,,，②对，，，，，，，，③对，，，，∴不满足合并条件④对，，，，，，，，⑤对，，，∴不满足合并条件⑥对，，，∴不满足合并条件⑦对，，，∴不满足合并条件⑧对，，，与⑥同理，不满足合并条件⑨对，，，，，，⑩对，∴不满足合并条件，同理时，也不符合满足条件⑪对，，，∴不满足合并条件，同理也不满足合并条件⑫对，与已经在同一个回路中，同理，与也已经在同一条回路中⑬对，，，令，，，⑭对，不符合合并条件，同理，，，也不符合合并条件⑮对，，，∴不满足合并条件∴最终的配送路径为，即，，，即，，，即，，，即，，最后得到的最优结果如表4-3所示。表4-3节约法优化结果表路线运距运货量车型司机0-3-4-6-7-051.61km47011吨货车10-1-2--021.37km3007吨货车10-8-9-025.54km2907吨货车10-5-011.4km807吨货车1由上表可知，需4车次配送，司机4人次，运输总里程为109.92km。如图4-2所示00123456879图4-2优化线路图4.3基于改进的最近插入法的企业配送路线优化关于车辆路线问题的研究方法，前面用到的插入法，主要是根据顾客点插入物流路线途径来搭建物流配送的，运用最短路线来进行建立，一开始选择离站最近的地方，把它作为路线的种子点，然后再以此根据临近的点插入，使得插到最小值，然后运用公式计算出最大值插入点，重复进行操作，一条路线的单程设计，直到超过车辆的载货量，再开始建立另外一条路线。插入法的计算步骤如下：①令T={0},N={0，1，2……,9}，比较表4-2中从0出发的所有路径大小。因为，所以就有顾客点0，5构成一个子回路，，此时，。②在剩余顾客点（1，2，3，4，6，7，8，9）中寻找到0和5中某一点的最小距离，，,因为，所以在子回路插入点1。由于对称性，无论将1插入到0和5之间往返路径中，结果都是一样的，这样，构成了一个新的子回路，，。③再次寻找剩余顾客点到0，1，5中某一点的最小距离：可知最小距离为，此时,，因为，所以在子回路插入点2。④将点2分别插入（0，1），（1，5），（5，0）中，比较得：插入到（1，5）中增量最小，。此时构成了一个新的子回路，，。⑤再次对剩余的顾客点按照上诉方法进行优化，可构成另子回路和子回路利用改进的最近插入法得到优化结果如表4-4所示，优化线路结果如图4-3所示。表4-4改进的最近插入法优化结果路线运距运货量车型司机0-1-2-5-032.77km38011吨货车10-3-4-6-043.84km470.911吨货车10-7-8-9-029.51km323.811吨货车1由上表可知，需司机3人次，运输总里程为106.12km。优化以后得线路如图4-3所示。00123456879图4-3优化线路图4.4基于扫描算法的企业配送路线优化扫描法分为两阶段性步骤：第一阶段：利用极坐标来表示各需求点的区位，然后任取一需求点为起点，以车辆容量为分群的约束，再以该需求点为零度按顺时针或逆时针的方向，进行顾客的扫描分群。第二阶段：依据求解旅行商问题的算法，求解各顾客群的排程。关于扫描算法的企业配送线路优化，我们通过以不同客户为起始点进行扫描计算分析并比较，我们得到的最优方案是以1为起始点的方案，计算如下图3-4所示：00123456879图4-4优化线路图建立极坐标系，以O为极坐标系的原点分组。从角度为零向逆时针方向进行扫描，第一个被分组的是合作商1，Load1=180；继续转动，下一个被分组的是合作商2，Load1=300。由于负载还没有超过限制Loadlimit=500，继续转动。下一个被分组的是合作商5，Load1=380，继续转动；下一个被分组的是合作商3，，Load=500；于是这段路径已经达到最大限度，需要一个新的组，这样在第一个组里面只有合作商1、2、5、3。在第二组中有合作商4、6、7、8，Load2=440。继续上面的步骤，第三组中有合作商9，Load3=200，至此所有的合作商都被分配完毕。分组结果如下图4-5：0120123456879图4-5扫描法分组图组内的线路优化。对上面三个组都已经是一个单回路运输问题，下面用最近邻点启发式算法进行路径优化：由表3-1可知，1、2、5、3之间的最短距离，则先令， ，，，路线为0—1—2—3—5—0由表3-1可知3、4、5、9之间的距离。则先令，，，，路线为0—4—6—7—8—0由表3-1可知0、9之间的距离。则路线为0—9—0优化线路结果如下表4-5所示。表4-5改进的最近插入法优化结果图路线运距运货量车型司机0-1-2-3-5-040.24km50011吨货车10-4-6-7-8-048.33km44011吨货车10-9-016.5km2007吨货车1由上表可知，需司机3人次，运输总里程为105.07km。4.5三种配送线路优化分案比较分析关于天天物流的线路优化研究，我们用了节约算法、改进后的插入算法、扫描算法三种方法进行计算，我们通过表4-6进行了简单的比较，并选出较为满意的配送方案。表4-63种方案比较分析表状态优化前优化后节约算法改进后的最近插入法扫描算法各车型车次(次)7t530111t0132总运输里程(km)127.02109.92106.12105.07节约里程数（km）17.120.921.95司机（次）5433节约人力（次）122根据上表4-6我们结合车次需求数，总运输里程，人力资源消耗等角度综合比较分析，本文假设11吨的车与7吨的车油耗相等，每公里油耗为0.12升，司机的工资为每月为3500元,柴油价为7.3元每升。我们发现节约算法的日节约里程数为17.1km，可算出每日可节约14.98元，每月节约449.39元，节约算法可少一个司机，所以每月总共可节约3949.39元。改进后的插入法节约里程数为20.9km，可算出每日节约18.31元，每月为549.25元，可少2个司机，所以每月总共可节约7549.25元。扫描算法可节约里程数为21.95km，可算出每日节约19.23元，每月为576.85元，可少2个司机，所以每月总共可节约7576.85元。通过三者的对比我们发现扫描法优化的配送路线方案较为满意，每月可为阜阳天天物流节省7576.85元。但是，本文的配送距离略有超出配送最佳范围，模型存在着一定的缺陷。在计算过程中也将一些因素理想化了，与实际情况不完全相符。例如，并未考虑具体的道路信息，运输规章，车辆的