图论在快递网点优化设计中的应用

1、    图论在快递网点优化设计中的应用    陈艳仙快递作为一种新型的运输服务，中外有很多学者专家对快递进行了深入的研究，例如快递路径选择的优化、网点的优化，并且相应的给出了模型及算法，本文在前人的基础上运用图论的知识对玉溪市个别圆通快递选址进行研究，网点的选址及收送包裹路径的选择可以规划为收、发件的物流网络优化问题，选址时以路径最短所花时间最少为目标。纵观玉溪市近几年的快递企业发展，玉溪市每年的快递累计完成业务量逐年增加，同比增长也越来越大，经济增长比也是逐年增加，玉溪市快递业持续保持平稳发展，快递服务业普遍满足快递市场的基本需求，随着快递市场需求的快

2、速增长，业务规模不断扩大，快递企业不断增多，市场主体不断优化，业务转型持续改善，快递行业整体实力进一步增强。整个快递行业发展呈现快中趋稳的现象，快递行业具有产业结构不断更新优化，能力转换不断持续加快的特点，使得快递服务业对经济社会发展的基础性作用进一步增强，快递行业的经济影响力逐渐扩大。快递服务业通过不断完善自身、规范经营模式、提高服务水平和质量等一些方式，对自身进行不断地优化完善，在做好服务的基础上努力保证自己快递种类的优势与市场份额，并积极寻求更大的市场，这就需要运用将所学的理论知识对快递网址及路径在各方面的条件下进行优化以保持本快递的优势在竞争的潮流中屹立不倒。本文运用图论知识对网点选址

3、及收送包裹路径进行分析，运用图论知识已解决数学中众多难以解决的问题。有最先开始的“七桥问题”到后面的“中国邮路问题”、“旅行售货员问题”都得到了很好的解决，从中我们可以看出图论在解决实际问题中存在巨大的价值，现阶段我们在前人研究的基础上运用图论知识对小范围的快递网点进行选址分析。图论知识背景图论创建于18世纪30年代，二百多年来经过几代人的不懈努力，使图论发展成为重要的数学分支。图论的不少研究成果具有很高的实用价值，它们在各个科技领域（包括计算机科学理论和技术）都有广泛的用途。在离散数学的领域中，图论知识的运用占有一定的主导地位，在解决实际问题方面，图论的运用也具有直观、清晰、简捷等特点，现实

4、生活中的许多问题可以转化为等价的图论问题而得到解决。图论知识具有广泛的应用价值，图论可将各种复杂的工程系统和管理问题用“图”来描述，进而设计算法求得最优结果，给管理者提供最优化的方案。图论中研究的“图”是由若干顶点（表示事物）和若干边（表示事物之间的一定关系）。图论中的“图”的顶点位置、边的长短之间没有太大关系，一般可以设定边的不同权值来表示顶点之间的简单关系的强度。图论知识作为离散数学重要的组成部分，已经成为当前算法设计中一项重要内容，图论和算法问题之间有着密切联系，事实上，许多算法问题大多数都直接或间接地和图有关。模型的假设仅在一定的备选取地点范围内考虑新的快递网点的配置；不考虑各小区与网

5、点的实际覆盖面积，简化为点处理；每个小区的快递包裹是快递员送至小区门卫处，同时由快递员收件带走；在现有小区与网点的基础上拆分优化网点位置；用户的需求量按区域总计；假定路况一致，快递员在途中按照规定的速度匀速行使。问题重述问题背景。现下社会经济飞速发展，电子商务迅猛崛起，物流业面临机遇的同时亦面临巨大的挑战，尤其是占物流比例居多的快递行业，为了使快递行业平稳的发展，进一步提高快递企业的服务质量和水平，为客户提供更加舒适合理的服务平台，提高快递企业的收益，同时满足客户时效需要与费用要求，快递行业必须以降低成本、提高效率、提升覆盖率来提高自身的竞争力，而合理的选择快递网点、降低快递网点所需成本、规划

6、快递网点规模和数量进而降低快递企业运营成本及运输货物费用，提高快递企业的总收益，并且在最短的时间内满足客户的需求，为客户提供最为优质的服务是快递企业当前的首要目标。问题的提出。我们对玉溪市红塔区的部分有代表性的区域进行了走访调查，对玉溪市红塔区龙马路56号北苑区总店、玉溪市红塔区康井路28号圆通快递这两个网点获取了比较详细的相关数据。下面我们以第一个网点的优化为例，讲述分析、建模、求解的过程。男一个网点的优化求解作为模型的应用放在第6节。玉溪市红塔区龙马路56号北苑区总店（现有网点）业务范围内的区域中共有11个地点（10个单位或小区，1个快递网点），分别用a，b，c，i，j，o来标记。任何两个

7、小区之间都是相通的，只是有小区是有道路直接相连，有的是通过其他小区联系在一起，各个小区对应详细相关数据如下：对于每个地区网点的建立与否，可以通过计算到网点的距离最短或是小区间的最短送货路线来确定，然后充分利用小区的包裹数量以及小区间的路线数据，采用合适的方法搜索网点，求得最优解。本文主要解决以下两个问题，选取最优网点。问题一：利用优化模型检测当前网点是否是所管辖的区域的最优网点；问题二：从n个小区组成区域内中，选出两个最优点设立网点，建立网点网络，实现快递员收送包裹的路线总距离最小；模型的建立本文采用优化的flovd-warshall算法计算出小区间最短路线矩阵，再用0-1整数规划的穷举法获得

8、模型目标函数的最优解，选取最优网点。利用小区间路线数据。进而构造邻接矩阵l：若小区j和j间没有直接相连的路线，则令（1，j）元素aij为正无穷大；否则aij（j=1，2，n，j=1，2，n）为j和j直接相连的路线长度。模型的求解问题一优化检测模型根据matlab程序及lingo程序求解运行结果分析确定玉溪市红塔区龙马路56号北苑区总店（现有网点）是其所管辖区域内的最优网点，包裹数量加权总路线长度为143620米。问题二网点拆分模型在现有网点的管辖区域内新建网点达到缩短路线距离，提高运营效率的目的，根据matlab程序及lingo程序求解运行结果分析确定当前网点北苑区总店和公安局生活二区为网点拆

9、分后的最优网点，优化后的包裹数量加权总路线距离为112520.0米。网点拆分后二者所管辖的区域如下：模型的应用另一个网点的优化本文选取玉溪市红塔区康井路28号圆通快递针对问题一、二的模型进行检验分析，調查数据类型与玉溪市红塔区龙马路56号北苑区总店相一致。根据我们调查收集整理的数据用matlab程序及lingo程序求解运行结果分析确定玉溪市红塔区康井路28号快递网点为所管辖区域的最优网点，并知现有网点的包裹数量加权总路线长度为45100米。网点拆分模型检验根据matlab程序及lingo程序求解运行结果分析确定康井路28号和乡镇小区为网点拆分后的最优网点，优化后的包裹数量加权总路线距离为224

10、10.0米。网点拆分后二者所管辖的区域如下：模型的评价与推广本文在基于所处的环境条件下考虑到的因素略有所不足，除本文考虑到的因素外也可以考虑一些其他的因素比如：各家快递企业之间合作收送件目的、人口数量、居民自主取件、快递网点附近是否有停车场、停车数量及时间等等。除了选择合适的快递网址得以提高经济效益及服务效益外，还可以根据当地网址的实际情况定制相应包裹收送计划，进行合理计划收送，把包裹客户按地区、包裹数量分为不同的层次，再按包裹客户层次等分将包裹进行分拣，根据合理快捷收送路线，进行送货服务，让包裹到达客户手中定时化、高效化。除此之外，网点与网点之间还应进行业务联合，发展联合收送包裹业务，可以达到降低快递收送成本，缓和交通拥堵。实行多家快