韵达快递蚌埠市物流配送线路优化设计

1、毕业设计(论文)太原市韵达快递物流配送线路优化研究学 院 ：专业（班级）：作者（学号）： （51301071002）指导教师：姓名（括号内填写职称或学位）完成日期： 2017年4月15日蚌埠学院教务处制目 录中文摘要1英文摘要21 绪 论31.1 研究的作用及意义31.2 国内外研究现状31.2.1 国外研究现状31.2.2 国内研究现状41.3 研究思路52 配送线路的优化方法62.1 节约算法62.2 扫描算法72.3 分子交换探索法72.4 配送线路优化的意义83 太原市韵达快递的配送现状及路径优化93.1 太原韵达配送现状93.2 太原市韵达快递分点分布及需求量统计93.2.1 太原市

2、韵达快递分点布局93.2.2 韵达快递运输车辆车型及装卸货物的方法93.3 韵达快递线路优化的VRP数学模型103.4 基于节约算法的企业配送路线优化113.5 基于扫描法的企业配送路线优化143.6 基于分支交换探索法的企业配送路线优化173.7 三种配送线路优化分案比较分析20结论22致 谢23参 考 文 献24太原市韵达快递物流配送线路优化设计摘 要：配送线路的设计与优化，是近几年来在物流业内比较关注的一个重点问题。配送线路的选择，不仅是物流企业日常经营活动的一个重要组成部分，并且对物流企业的营运成本有着重大的影响。一套合理的的配送方案可以为物流企业节约成本，降低运价，从而提高企业的整体

3、竞争力。因此，配送线路的选择与设计应该合理、有序并且符合实际需求。而物流企业作为一种大型且运送品种繁杂的第三方物流托运，配送中心对各分点的配送路线的选择就显得尤为重要。本文以韵达快递合肥市物流配送线的优化为例，详细介绍线路优化中经常使用到的节约算法，扫描算法及分支交换探索法，并且分别应用以上提及的计算方法对韵达快递中一组较有代表性的需求数据进行配送线路的设计与优化。通过对公司配送问题的总结分析以及对优化过程中使用方法的总结，为韵达快递在配送方案的设计上提供一些参考。关键词：扫描法；节约算法；分支交换探索法；线路优化Optimal design of Taiyuan express logist

4、ics distribution lineAbstract: The design and optimization of distribution lines is a key issue in the logistics industry in recent years. The choice of distribution line is not only an important part of the daily operation of logistics enterprises, but also has a significant impact on the operating

5、 costs of logistics enterprises. A reasonable distribution plan can save cost and reduce freight rate for logistics enterprises, so as to improve the overall competitiveness of enterprises. Therefore, the selection and design of distribution lines should be reasonable, orderly and in line with the a

6、ctual needs. The logistics enterprises as a large and complex transportation of the third party logistics consignment, distribution centers on the distribution of the various routes of choice is particularly important. In this paper, optimization of courier logistics distribution line in Hefei City

7、Yun as an example, introduces the route optimization algorithm often used in the scanning algorithm and explore the branch exchange method, calculation method and application of the above mentioned rhyme express in a group with the design and optimization of demand data representative of the distrib

8、ution line. Through the summary and analysis of the companys distribution problems, as well as the summary of the methods used in the optimization process, this paper provides some references for the design of the distribution plan.Keywords:vehicle routing; saving algorithm; sweep algorithm; branch

9、exchange heuristics1 绪 论1.1 研究的作用及意义随着经济技术的发展，物流业在不断发展，成为了中国经济的加速器，影响着我国的经济发展。物流业的发展非常迅速，在短时间内迅速膨胀起来，而物流业的配送则成为了最为重要的环节，在物流业的整个发展过程中，物流业的发展让企业看到了更好，更加广阔的前景。物流业的配送研究重要内容主要在，运用科学的方法，合理的方式，最为经济，最为缩短路径的方式来设计物流配送方案，进而解决物流配送的重大问题，有关学者在这方面也做出了大量的研究，配送路径的优化需要整个的一个设计图，从最早期的物流配送模式，逐渐发展，变成现在的最优化路径。生活条件的改善，人们生活

10、需求的增加，物流业的趋势越来越明显，从而对于物流模式以及配送方式也在不断调整与改变，运用算法计算出最短优化路径，学者们做了大量的研究，取得了一定的成效。但是在物流配送方面关于绿色能源配送仍然做的不够到位，还需要进一步加强。实施研究物流配送路径最优化具有极其重大的意义，也具有很重要的实践意义，物流配送的效率得到提高。企业对于物流配送有一个较为全面的掌握，可以进行系统的分析和掌握，在现有基础之上，实现更大的价值。本篇论文选题是对于太原韵达快递的物流配送最优化路径进行研究探讨，设计出一套最适合韵达快递物流公司的方案极其线索。1.2 国内外研究现状1.2.1 国外研究现状一些发达国家的物流配送服务较为

11、专业，合理化，发达国家起步早，在这方面有了更多的经验。发达国家之所以发展的比较好，是因为受到地理，人文，习惯，思维，技术多方面的影响，发达国家的体制较为健全，当然发展的相对好很多。而美国的物流业是最强大的，物流的观念新颖，发展十分迅速，在不断探索与实践中，形成了本公司的独特理念以及方法，领先其他国家，成为了现代物流业的先进国家。据美国而言，人们对于物流货物的要求非常高，企业如果不做到，那将是很难发展下去，配送的及时性，准确性，服务质量等等都是需要关注的因素，美国在这个方面做了很多的研究。对于日本来说，日本物流业公司在这些方面也是一点也不亚于美国，服务质量一流，货物到达的及时性，做了多方面的研究

12、，力求进步，不断提升。美国学者在一本书中提到，过去的几十年当中，逐步建立自己的框架结构，一系列的运营模式，运货方式的多种多样，管理监督，服务配送都在关注着，落实到每一个细节。运用系统方法提高工作效率，进而达到更好的发展，在货运体系当中，扮演着重要的角色，运用于每个部门，在实践过程中，提出了货运的微观仿真模型，为企业的长期发展做了一定的打算与策划，物流运货体系更加完善。Miller&Gillet在1974年提出扫描法,并且把扫描算法和当时存在的几种算法求出解进行比较，从而证明扫描算法是当时算法中所得的解相对比较合理，更适合当时解决物流配送等相关问题。Jame Asher在1993年通过对区域物流

13、配送问题的研究，最后在区域内物流配送的模型思想下对区域内物流过程中的配送车辆行驶的路径问题进行了合理的优化，并对区域物流配送路径以及配送中心的选址等相关问题做了相关的研究。Fisher在2002年通过对区域物流配送模型的分析过后，成功把区域物流配送问题分成两个问题，第一个问题是配送前的车辆调度问题也就是VRP问题，其次是配送过程中的路径优化问题，所以在配送过程中要根据问题的不同。从而运用不同优化方法。由于问题的不同导致在大型的物流公司有着功能不同的配送中心比如有生产型的配送中心、调度以及运输配送中心。1.2.2 国内研究现状发达国家的物流跟本国的物流研究存在很大差异，国内学者对于物流业的研究方

14、向在于物流配送的中心管理，配送模式，物流的管理系统是否完善，配送的布局与建设，主要的研究方向。对于最优化路径需要在以下几个方面进行研究，如:技术，管理，人员，车辆安排等方面。国内对于物流业的研究还不够全面，但是国内学者们在不断研究与学习，努力改善物流业的现状。研究方法主要是运用几种方法的有力结合，对此进行分析，运用策略去解决。各国群众的消费水平不一样，商品价格，人们的需求都是存在很大差异，在完善物流业体系的同时，降低成本，做到提高效率，在这些方面多做研究。王静指出，本国的物流市场操作不规范，配送过程的合理化程度不高，物流运输路途堵塞，加重了运输成本，车辆的运输受到限制，出现这样的问题，体系都是

15、不够完善的，物流业的发展还需要进一步加强。在倡导绿色物流的方面，有关学者指出，物流配送出现的问题，道路难，无法进去，导致货物积压停留，耽误时间，间接的导致了企业物流的运输成本加大，车辆的迂回运输，交通不畅，装货，卸货麻烦，等等一系列问题，这也是值得本国物流业需要去努力改善的。计娜在研究物流现状一书中提到，当前本国物流业配送发展模式还不够健全，物流模式过于粗狂，没有较为全面的物流配送模式，缺少运输人员的培训，配送人员的素质不高，配送的技术较为落后，导致企业的生存发展。还有学者提出，关于物流配送的算法路径优化问题，最主要的是要去解决车辆配送，以及物流配送模式的形成，解决时间问题，进而提高工作的效率

16、，为企业带来最大化的效益。物流配送路线的最优化，归根结底，本质上就是要使得路线的最短化，如何选择路线，设计路线，既能满足客户的需求，又可以为企业带来效益，路线设计的是否合理，就是最优化路径的设计。采用动态规划的算法，以及其他算法加以改进，根据地理位置，可以给他分成若干个子网络，然后依次计算，以此求得节点数，以及路径数，确定数据，方案，进而提高路径搜索的效率问题。这样一定程度上可以节约企业的运输时间，成本，物流均在网络上进行操作，节省了大批的操作人员。谈到车辆调配的问题，在1959年第一次提到物流配送车辆问题的时候，一直发展到今天，还仍然无法进行一定程度上的路线合理优化与调配，在不同的经济条件下

17、，受到了很大的制约，选择最为合适的物流运输路线，争取取得利益的最大化，各种指标的优化，不断提升，实现企业的效益最大化。我国目前对于物流配送的体系，车辆调配问题，较为简单化，只是当现实的复杂问题出现时，各种问题变得非常的复杂化，难易程度加大。设计的物流配送路线体系跟实际路况不符合，做到配送典型模型的不合理化，理论上的送货一体化模式，根本行不通。在实际问题当中，很多的物流企业都是运用一个模式，一条龙的一体化生产，送货，运货，卸货的一体化，可是在实际过程当中，配送需要考虑多方面的因素，车辆的调配问题，路程的突发情况，受到很多的限制，这个需要我们在物流优化路径当中去考虑全面，综合考虑，合理分析与操作。

18、国内对于物流配送的模式已经逐渐发展壮大，各种模型也有一定的研究，学者们做出了一些系统的分析与把握，运用普遍采取的做法进行简单计算，加一个其他因素在里面，虽然算法不能太过于全面，但是人无完人，缺点肯定是有的，但可以最大化的去减小差距。缪立新4和相关学者在2003年关于物流行业中的VRP问题提出了神经网络算法。这种新的算法给车辆调度问题的解决带来很大的作用。钱小燕5和相关学者在2004 年针对随机需求的配送点的配送车辆调度问题做出相关研究。并在解决配送车辆调度问题上提出了两阶段模拟退火算法。魏抒茵和胡晓枫6在2005年提出了物流业配送的发展趋势，物流业配送模式由生产者和销售商自营改变成快递企业进行

19、；物流业配送模式将走向计划化、规模化；物流配送管理技术与方法将实现现代化。同年朱树人和李文彬等人将轮盘赌法加入到遗传算法中，创新了交叉和变异概率的自适应调整技术，并取得了优化解。1.3 研究思路关于太原市韵达快递的网点分布，进了解研究，熟悉情况，物流配送的最优化。根据调查了解到物流配送存在的问题，还有需要去完善的地方，对比进行详细记录，以便后期遇到相同问题时，可以进行修改，运用所学知识，根据设计路径的方式，进行整改，对现有的配送路线进行一定程度的微调，每个环节的严格把控，争取做到各个环节的最细致化，理论联系实际，做到最好的路径优化。物流业的飞速发展，经济不断发展，需求量增大，物流成为了当今社会

20、的主流，无论是发达国家还是非发达国家，都是物流的最大市场，对于物流的研究需要更多人的投入，不断实施，不断设计，不断做出新的成绩。快递服务的业务不断增多，服务更加的看重，行业竞争加大，服务意识观念还需提升。更为精确的计算，加上理论的研究，设计出合理的物流配送方案，形成合理的配送模式体系。2 配送线路的优化方法2.1 节约算法节约算法（Saving Algorithm）是Clarke和Wright在1964年提出的它是目前解决VRP模型最有名也是应用最普遍的启发式算法。节约算法是用来解决运输车辆数目不确定（运输车辆数目在VRP问题中是一个决策变量）的VRP问题，这个算法对有向和无向问题同样有效。他

21、的核心思想就是将运输问题中存在的两个回路（0，,i,0）和（0，j，0）合并成为一个回路（0，i,j,，0）。在整个合并的过程中，整个运输问题的总距离将会发生变化，如果变化后的总运距下降，则称节省了运输距离。相应的变化值，叫做节约距离5。节约算法的一般步骤：第一步，形成一个初始解。形成初始解时，需要使每个顾客的要求都得到满足，而且使所有的约束条件得到满足。初始解可以由具有运载限制的最近邻点法得到。第二步，进行节约度的计算。计算所有点对的节约度： ，i,j=1,2,，n 且然后对结果进行升序排列。第三步，进行回路的合并。从升序排列的节约度序列的最上面的值开始对已有的回路进行合并，将回路中的部分路

22、径（0，j）和（i，0）删除，然后得到新的回路（0，i,j,，0）在解决实际问题的过程中，合并时要考虑整个回路在体积或重量上的运载限制，当合并会导致回路上各个点的需求总量在体积或重量上超出限制时，要停止合并，并开始设计新的回路。2.2 扫描算法扫描算法（Sweep Algorithm）是Gillett和Miller在1974年首先提出的，他也是求解车辆数目不确定的CVRP问题的常用方法。扫描算法一般分为四个步骤完成：第一步，以起始点作为极坐标系的原点，并以连通图中的任意一顾客点和原点的连线定义角度为零，建立极坐标系。然后对所有顾客所在的位置，进行坐标系的变换，全部都转化为极坐标系。第二步，分组

23、。从最小角度的顾客开始，建立一个组，按逆时针方向，将顾客逐渐加入到组中，直到顾客的需求总量超出了运载车辆体积或重量的负载限制。然后建立了一个新的组，继续按逆时针方向旋转，将顾客继续加入到组中。第三步，重复步骤二的过程，直到所有顾客都被分类为止。第四步，路径优化。对各个分组内的顾客点，就是一个TSP模型的线路优化问题，可以用TSP模型的方法对结果进行优化，选择一个合理的线路6。2.3 分子交换探索法分支交换探索的概念是由Lin和Kemighan在1973年提出的，这种算法是一种局部搜索优化法。该算法的核心思想是始终保持解的可行性而力图向最优目标前进。在每一步，都改变一个可行解而减少总费用，直到这

24、个过程继续到满足停止搜索条件为止。由于搜索的随机性，这种算法很难得到最优解，但可以得到一个接近最优解的方案。分支交换探索法主要是在满足运载限制或其他一些限制的条件下，通过交换或移动路径之间的边或客户来改进当前解。在分支交换探索法中最主要的两个部分是搜索准则和停止条件：分支交换搜索法的搜索准则是在满足约束条件的邻域解中随机的进行搜索，搜索到优于当前解的邻域解即更新该解为当前解，同时完成向最优解的一步移动。然后以新的当前解为标准继续搜索。分支交换探索法的停止准则，一般分为两种形式：第一种是指定一个固定的移动步数，当移动次数达到移动步数限制时即停止搜索，另一种是以一个指定的条件目标（例如运输总距离小

25、于一个定值），只有当通过搜索得到的解满足目标条件时才能够停止搜索。交换分支探索法与其它局部搜索优化法一样，需要在求出一个初始解的情况才能进行优化，得到的解为局部最优解。2.4 配送线路优化的意义对于物流行业而言，配送是个重要的问题，而路线的解决将具有更为重要的意义。在设计路线问题当中，根据客户的不同需求，要求，不同的路线途径来进行设计，达到高效，省力，降低成本以及风险投资的问题，切实的做到更好的服务，对于物流业来说有利无弊的。配送方法不同，过程也就出现不同，运输途径也会有很大差别，需要考虑更多的其他因素，适时适当的利用运输工具来进行调整，道路情况的复杂性，车辆拥堵等这些问题，都需要考虑与解决，

26、企业的目标是把货物最好，最快的送到顾客手中，保证它的及时性，安全性，更加方便，便捷。根据配送路线合理的进行小幅度的调整，争取方案更加合理化，贴近实际路况与过程。配送线路优化对天天物流来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到合作商的手中，提高合作商满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于天天物流在同行中的提高竞争力与效益。配送线路优化对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减

27、少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用。3 太原市韵达快递的配送现状及路径优化3.1 太原韵达配送现状通过数据调查我们得知太原韵达在本地分点配送的基本情况：配送需要2.8吨的车次为5尺，总运输费用为690元，总运输里程为68.2Km。3.2 太原市韵达快递分点分布概述3.2.2 太原市韵达快递分点分布韵达快递分点分布及配送中心的位置如图所示： 图3-1 配送中心及分点分布图注： 0.韵达配送中心 1.解放路店 2.旱西关店 3.新建南路店 4.三道巷店 5.上马街店 6.康乐街店 7.侯家巷店 8.长风街店 9.大王路店 10.并州西街店 11.山西大学店 12.坞城路店

28、13.阳光小区店3.2.2 韵达快递运输车辆车型及装卸货物的方法韵达快递选择的车辆统一为厢式货车，总载重量为2.8吨，其货箱容积约为22，满载时一公里油耗约为0.18升，是一款较为实用的货车。在配送的过程中，仓库在货物装车前先将各门店的货物进行分拣，尽量将每一个门店的货物放置于一个托盘之上，然后在已经拼装成整托盘的货物贴上纸质标签，并用粗水笔标明货物目的地缩写，对与无法拼成整盘的货物要与其他门店货物进行拼盘，但要在每一箱货物的外包装上注明卸货地点。不同门店货物拼盘时要注意将不同门店的货物清楚的区分，即使不能合理利用托盘的全部空间，也要避免将两个门店的货物混在一起，以减少货物的卸车时间，同时避免

29、因卸错货物而在门面店的重复装卸，更要避免因为没有及时发现错卸漏卸而导致的另外加派车辆。另外要注意不能将没有直接线路连接的店面的货物拼在一个托盘内，以免在积载安排时造成困难，也避免在装卸时造成困难和混乱。最后要在拼好的托盘上贴另一种颜色的纸质标签，同时注明卸货地点。装货的过程中要注意“先到后装”的原则，保证先到达的门店的货物被放在最靠近车尾的地方8。这样做可以方便卸车，防止店面在卸载自己的货物时因货物被遮挡而对其他店面的货物进行重复装卸。另外要注意的是两家直接相连门店拼盘装车的货物被放置在先到门店货物与后到门店货物的衔接处并归入先到门店一组，以防漏卸货物。最后所有托盘应将贴有标签的一面面向车尾，

30、以方便卸车时候辨认。在卸货过程中以贴在整盘货物的标签为辨识标准，逐个卸下自己门店的货物，同时注意拼盘货物货物包装上的目的地编号，防止错卸货物。3.3 韵达快递线路优化的VRP数学模型将韵达快递的配送中心编号为0，车辆编号为k，任务编号为1，2，1考虑运输量约束问题可以定意义如下模型： i=0,1,1; j=0,1,1; 式中表示从点i到点j的运输成本。和为变量，定义为：时，车辆从点i行驶到点j，时，车辆没有从i点行驶到j点；=1时，点i的任务由车辆k完成，=0时，点i的任务不由车辆k完成。在式中为第i点的需求量，q为运输车辆的定额载重量。n为在设计方案中所用到的车辆数，D为添加一辆车所需要的固

31、定成本。D主要由车辆的保养费用及司机的工资构成。在本次的计算之中，车辆每公里的固定油耗为0.18升每公共里。柴油价格为每升6元。车辆最大载重辆为2.8吨，最大容积为22。每次配送每派出一辆车的固定费用为100元。3.4 基于节约算法的企业配送路线优化第一步，假设每个点都是由一辆货车进行单独的配送，这样每一个门店的需求都可以得到满足，并且也不会超出车辆的载重与体积限制。我们将这个方案作为节约算法的初始解。图3-2 韵达快递线路设计初始解第二步：计算各点间距离 (由于统计条件有限，各门店之间的距离以地图上所测量出的直线距离进行计算，而并非实际的车辆行驶距离)。各点间距离见表3-1。表3-1 各点间

32、距离表 (单位km)012345678910111213004.15.84.54.92.85.02.55.17.32.96.35.42.4101.61.71.51.42.71.76.24.12.58.26.94.1202.41.73.03.13.37.33.53.89.38.15.5303.12.30.92.24.92.81.86.95.73.4402.34.02.87.75.13.89.68.35.3503.20.55.65.11.94.76.33.2602.94.42.32.16.45.23.5705.15.01.46.95.82.6806.13.82.00.82.8904.48.17.0

33、5.81005.74.51.71101.24.41203.3130对所有点对的节约度进行计算并经过统计排序后，按降序排列，见表3-2。表3-2各点对节约度降序列表点对节约度点对节约度点对节约度11-1210.52-752-83.66-910.03-5510-133.68-129.75-953-133.52-99.61-74.910-113.53-992-104.92-123.12-496-114.91-833-68.63-74.82-112.81-28.35-74.82-132.72-37.97-94.81-122.62-67.73-84.77-82.51-47.58-134.71-132.4

34、1-97.34-74.64-82.34-97.15-64.65-82.31-36.96-74.67-132.33-46.31-104.51-112.28-96.312-134.57-122.14-65.95-114.44-1226-105.811-134.34-1329-105.83-124.25-1326-85.78-104.25-121.99-125.74-1047-111.92-55.67-1044-111.63-105.63-113.91-55.56-133.99-115.59-133.94-55.45-103.86-125.210-123.8第三步，按排列好的节约度降序表，将节约度最

35、大的点对合并，在考虑车辆最大承载能力的情况下得到一个优化方案，其线路图如3-3所示。 图3-3 节约算法法得到的线路图经检验每条回路的载货量均没有超出货车载重限制和体积限制。第四步，计算使用该配送线路所需要的费用：回路0-6-9-2-4-0所经历的里程数：5.0 + 2.3 + 3.8 + 4.9 = 16km回路0-10-3-1-0 所经历的里程数：2.9 + 1.8 + 1.7 + 4.1 = 10.5km回路0-13-7-5-0 所经历的里程数：2.4 + 2.6 + 0.5 + 2.8 = 8.3km回路0-11-12-8-0 所经历的里程数：6.3 + 1.2 + 0.8 + 5.1

36、 = 13.4km总里程为16 + 10.5 + 8.3 + 13.4 = 48.2km每次运输成本为：0.1848.264100=452元。3.5 基于扫描法的企业配送路线优化第一步，将配送中心所在的点0点视为极坐标原点，并建立极坐标系。如图3-4所示。 图3-4 扫描法求解的扫描过程图第二步，扫描算法的分组过程：从角度为零向逆时针方向进行扫描，第一个被分组的是店面4,0.57；下一个被分组的是店面5，0.570.62=1.19，没有超过2.8限制。继续转动，下一个被分组的是门店1，0.570.620.85=2.04,没有超出限制，然后继续转动，门店2被分到第一组。0.570.620.850

37、.53=2.75，仍然没有超出限制。接下来的扫描中遇到门店7，0.57+0.62+0.85+0.53+0.56=3.13，超出了2.8的限制，按规则，需要一个新的分组，这样第一组由店面4、5、1、2组成，在第二组中有店面7，0.56，继续转动，重复上面的步骤，直到所有店面分组完毕，可以得到一个店面的分组如图3-5所示。图3-5 扫描算法求得的各店面分组图第三步，通过在每一组店面内使用最近邻点法可以得到一个线路优化方案，如图3-6所示。 图3-6 扫描算法求得的线路优化方案第四步，对该方案进行成本的计算：回路0-5-1-2-4-0的总距离：2.81.41.61.74.9 = 12.4km回路0-

38、7-3-6-9-0的总距离：2.52.20.92.37.3 = 15.2km回路0-13-10-8-0的总距离：2.41.73.85.1 = 13回路0-12-11-0的总距离：5.41.26.3 = 12.9km该线路设计方案的总运距为：12.415.21312.9 = 53.5km每次配送的成本约为：0.1853.564100 = 458元。通过计算，可以明显看出扫描法在第二阶段使用最近邻点法进行局部回路的设计后，得出的配送方案不太理想，所以要采用其他的优化设计方法对已有方案进行局部回路的优化。3.6 基于分支交换探索法的企业配送路线优化由于通过扫描算法得到的初始解并不理想，所以要用其他方

39、法对已经求出的最初解进行局部优化。而优化的种类根据范围可以分为路径间优化和路径内部优化。现在用来优化的主要方法有遗传算法、蚁群算法、退火算法等，但这些方法较为复杂，需要利用计算机程序进行辅助计算。在这里将采用一种较为简单的优化算法：分支交换探索法。由于计算能力的限制，我们在进行分支交换探索法时只做五步移动。我们对上节得出的结论进行路径间的局部优化，将扫描算法设计出的配送线路作为一个初始解，然后在保持解的可行性的前提下交换不同回路中的一个或几个需求点，以试图找到一个优于当前解的新解。邻域解是一个满足配送过程中的条件限制但又不同于当前解的一个可行解，例如回路0-11-12-0吸收点3构成新回路0-

40、3-11-12-0，然后失去点3的回路吸收点1再构成新的回路，得到一个拥有四条回路的新解，为（0-5-4-2-7-0，0-1-9-6-10，0-3-12-11-0，0-10-13-8-0）如图3-6所示，通过检验，该解在体积和重量上都没有超出回路的运载限制，则该解为最初解的一个邻域解。但这个解并不优于当前解，所以当前解不能向这个解移动。 图3-7 初始解的邻域解分支交换探索法的优化过程实际上就是一个不断对领域解进行探索并向更优的邻域解移动的过程。当搜索到解（0-4-2-1-0，0-3-9-6-0，0-13-10-7-5-0，0-8-12-11-0）时，该解的总运距为49.1km，小于初始解的5

41、3.5km，所以将该解作为新的当前解，为了避免重复搜索，以及方便比较。我们对已经找到的解记录到下表。此时完成第一次移动。表3-3记录表之一1（0-4-2-1-0，0-3-9-6-0，0-13-10-7-5-0，0-8-12-11-0）23当搜索到解（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）时该解总运距为48.6km，小于原有的49.1km，将该解更新为当前解。完成第二步，进行记录后继续搜索。表3-4记录表之二1（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）2（0-4-2-1-0，0-3-9-6-

42、0，0-13-10-7-5-0，0-8-12-11-0）3搜索到解（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）时该解总运距为48.4km，小于原有的48.6km，将该解更新为当前解并记录。第三步移动结束。表3-5记录表之三1（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）2（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）3（0-4-2-1-0，0-3-9-6-0，0-13-10-7-5-0，0-8-12-11-0）搜索到解（0-5-1-2-4-0，0-1

43、0-6-9-3-0，0-13-7-0，0-8-12-11-0）时该解总运距为47.9km，小于原有的48.4km，将该解更新为当前解，将该解进行进行记录。因为记录表已满，按照“先进先出”的原则将最先进入记录表中的解退出记录表，第四步结束，然后继续搜索。表3-6 记录表之四1（0-5-1-2-4-0，0-10-6-9-3-0，0-13-7-0，0-8-12-11-0）2（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）3（0-4-2-1-0，0-10-6-9-3-0，0-13-7-5-0，0-8-12-11-0）搜索到解（0-4-2-1-5-0,0-7

44、-3-9-6-0,0-13-10-0,0-8-12-11-0）时该解总运距为47.6km，小于原有的47.9km，将该解更新为当前解，将该解加入到记录表。将最先进入记录表中的解删除，此时已经完成全部五步的移动。表3-7记录表之五1（0-4-2-1-5-0, 0-7-3-9-6-0, 0-13-10-0, 0-8-12-11-0）2（0-5-1-2-4-0，0-10-6-9-3-0，0-13-7-0，0-8-12-11-0）3（0-4-2-1-5-0，0-3-9-6-0，0-13-10-7-0，0-8-12-11-0）因为此时的最优解为（0-4-2-1-5-0, 0-7-3-9-6-0, 0-1

45、3-10-0, 0-8-12-11-0）所以将该方案定为分支交换探索法得到的局部优化方案。如图3-8所示。图3-8 分支交换探索法得到的配送方案按此路线配送的成本约为：回路0-4-2-1-5-0的总运距为： 2.81.41.61.74.9 = 12.4 km回路0-7-3-9-6-0的总运距为：2.52.22.82.35.0 = 14.8 km回路0-13-10-0 的总运距为：2.41.72.9 = 7.0 km回路0-8-12-11-0的总运距为：5.10.81.26.3 = 13.4 km该设计方案的总运距为：12.414.87.013.4 = 47.6 km该设计方案的配送成本为：0.

46、1847.664100= 451 元 。3.7 三种配送线路优化分案比较分析关于天天物流的线路优化研究，我们用了节约算法、改进后的插入算法、扫描算法三种方法进行计算，我们通过表3-8进行了简单的比较，并选出较为满意的配送方案。表3-8 3种方案比较分析表状态优化前优化后节约算法扫描算法分支交换探索法车型车次(次)2.8t5444总运输里程(km)68.248.253.546.7节约里程数（km）2014.721.5运输成本（元）690452458451从上表中我们看到从总运输里程角度考虑，优化后的三种方案的总运输里程分别为48.2千米、53.5千米及46.7千米，相比较，分支交换探索法的总运输

47、里程比其他两种方法的运输里程分别减少1.5和6.8千米，能减少公司车辆的损耗和资源的浪费，给公司带去更多的效益。因此，从运输里程的角度考虑，我们选择通过分支交换探索法计算出来的配送路线。从车型车次来看，三种方法的所需车辆数及车型都相同。因此可选择任意一种方法计算出的配送路线。从车辆运输成本的角度来看，节约里程法中车辆的运输成本为452元，扫描算法中车辆的运输成本为452元，分支交换探索法中车辆的运输成本为451元，三者相差无几，因此从车辆运输成本的角度出发，我们可以可选择任意一种方法计算出的配送路线。 综合以上三个方面，因为三种方法计算出的配送路线中，车辆运输成本以及所需车辆数的相差程度不大，

48、而在总里程方面，分别相差了1.5和6.8千米。因此，我们更倾向于用分支交换探索法计算出来的配送路线。结 论近年来物流业的发展突飞猛进，从顺丰，申通，中通这三家来自不同物流公司跻身于前列开始，标志着物流模式的普及化和物流业的迅速崛起，而随着物流分店的增多配送成本的合理控制就显得尤为重要。然而很多国内的物流业既没有采用较为先进的越库配送模式，也没有对自己的配送线路做出很好的规划，造成物流成本高，资源严重浪费。本文利用节约算法，扫描算法，分支交换法对太原韵达快递比较具有代表性的一组数据进行配送线路的设计与优化，期望能为韵达快递今后每次解决具体配送问题提供方法上的参考。最后，需要指出的是，该文章在计算方面仍存在着许多不足之处，例如本文采用的需求量数据是静态的，而现实中的实际需求量却是围绕该组静态数据上下波动的一组动态数据，但由于时间原因和商业保密原因，所能获得的数据精确程度也只能局限于此。另外在本文中各点间的距离一律采用了直线距离，这与实际的行车距离产生了较大的出入。车辆的耗油量也统一按照满载时的耗油量进行计算。因为存在以上原因，使得计算得到的结果的精确程度受到很大影响。致 谢我的论文到这里将接近尾声了，为期两个多月的努力结果，论文的完成很感谢老师的耐心教导，对我的论文提出了诚恳的意见，给了我很多的启示。在老师同学的帮助下，我的