基于蚁群算法西安市长安区配送路线优化研究.docx

《基于蚁群算法西安市长安区配送路线优化研究.docx》由会员分享，可在线阅读，更多相关《基于蚁群算法西安市长安区配送路线优化研究.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于蚁群算法西安市长安区配送路线优化研究 题目： 基于蚁群算法的西安市长安区配送 线路优化探讨 院 系： 管理工程系 专 业： 物流管理 学 号： 姓 名： 指导老师： 2016年12月 摘要 随着国民生活水平的不断提升，物流配送在人民生活中所占比例不断提升。并且在市场经济中，物流配送不仅关系到企业服务水平和综合竞争力，还与国民民生休戚相关。而物流配送过程中的路径规划优化探讨不仅能够提升企业整体服务水平以及大幅度提高企业在市场经济中的综合竞争水平，还能够提升企业在国家民生建设中的优良形象。 本文首先针对物流配送路径优化问题的探讨背景、目的、意义进行相关的阐述，归纳总结了物流配送行业的国内外探讨

2、现状，为本文基于蚁群算法的西安市长安区配送路途优化问题的探讨供应了背景涵盖，然后针对蚁群算法的基本概念以及算法的机制原来进行探讨，分析了蚁群算法的实现流程，通过相关探讨归纳了蚁群算法在物流配送路径优化问题中的优缺点。其次，针对西安市长安区的配送路途的现状进行了分析，归纳了现阶段西安市长安区配送路途的交通状况，以及该区域内配送路途存在的问题。通过上述蚁群算法和西安市长安区物流配送路途的现状分析，为后续结合蚁群算法，优化配送路途的途径的探讨供应了理论基础和问题描述。最终针对西安市长安区的物流配送路径问题设计了基于蚁群算法的路径规划思路。通过本文探讨工作，实现了西安市长安区的物流配送过程中的路径优化

3、，实现了物流配送成本的降低和配送效率的提升，使得企业服务水平和企业受益的大幅度提高，并且保证了企业在市场经济中的综合竞争力以及在国家民生建设中的形象。 关键词：蚁群算法；物流；配送；路径；优化 Abstract With the continuous improvement of peoples living standards, logistics and distribution in the proportion of peoples lives rising. And in a market economy, logistics and distribution is not only

4、 related to the level of enterprise service and comprehensive competitiveness, but also closely related with the peoples livelihood. The study of path planning optimization in the process of logistics and distribution can not only enhance the overall service level of enterprises and improve the comp

5、rehensive competition level of enterprises in the market economy, but also enhance the enterprises image in national livelihood construction. In this paper, the research background, purpose and significance of logistics distribution route optimization are summarized, and the domestic and internation

6、al research status of logistics distribution industry is summarized. This paper provides the research of distribution route optimization problem in Changan District of Xian based on ant colony algorithm. Then the basic concept of ant colony algorithm and the mechanism of the algorithm are researched

7、, and the realization process of ant colony algorithm is analyzed. The advantages and disadvantages of ant colony algorithm in the logistics distribution path optimization problem are summarized by the related research. Secondly, this paper analyzes the current situation of distribution routes in Ch

8、angan District of Xian, and sums up the traffic situation of distribution routes in Changan District of Xian and the problems of distribution routes in this area. Through the ant colony algorithm and the analysis of the logistics distribution route in Changan District of Xian, this paper provides th

9、e theoretical foundation and the problem description for the follow - up study of the ant colony algorithm and the optimization of the distribution route. Finally, the path planning method based on ant colony algorithm is designed to solve the logistics distribution problem in Changan District of Xi

10、an. Through this research, the route optimization of logistics and distribution in Changan District of Xian is realized, the cost of logistics and distribution is reduced and the delivery efficiency is improved, which greatly improves the service level of enterprises and the benefit of enterprises,

11、and ensures that the enterprises The comprehensive competitiveness in the market economy and the image in the national livelihood construction. Key words: Ant Colony Algorithm; Logistics; Distribution; Route; Optimization 目 录 1 绪论 6 1.1 探讨背景 6 1.2 探讨意义 6 1.3 主要探讨内容 7 1.4 国内外探讨现状 7 1.4.1 国内探讨现状 7 1.4

12、.2 国外探讨现状 8 2 基本蚁群算法的相关概述 10 2.1蚁群算法的定义 10 2.2 蚁群算法的机制原理 10 2.3 蚁群算法的实现 11 2.4 蚁群算法的优缺点 12 2.4.1 蚁群算法的优点 12 2.4.2 蚁群算法的缺点 13 3 目前西安市长安区的配送路途现状分析 14 3.1西安市长安区配送路途的交通概述 14 3.2 西安市长安区目前配送路途存在的不足 14 3.2.1食品“断链”问题严峻 14 3.2.2食品链物流温控手段差 15 3.2.3从业人员素养不高 15 3.2.4成本问题 15 3.2.5管理问题 15 3.2.6服务问题 16 4 结合蚁群算法，优化

13、配送路途的途径 17 4.1 信息素浓度表的实现 18 4.2 集合tabu的确定 19 4.3 车辆序列的初始化 20 4.4 车辆不足状况及惩处成本 20 4.5 运力利用率 21 5 结论与展望 22 5.1 结论 22 5.2 展望 22 参考文献 23 1 绪论 1.1 探讨背景 随着我国经济水平的不断提高，国民经济快速提升，人民生活水平大幅度提高，人们对商品的需求也随之提升，特殊是对商品交易过程中的商品运输的要求也有了较大的提升。现如今，物流活动在人们日常生活、企业经营等过程中起先占据重要地位。此外，物流在现代化经济、全球化经济发展中的重要地位日益凸显，对新时代的经济发展起着重要作

14、用，渐渐发展为企业发展、竞争的一个重要领域。特殊是近几年电子商务的快速发展，为物流产业、技术的发展供应了更大的发展空间，使得物流与人们的生活亲密相关。所谓物流配送就是指与销售、供应、选购、生产等企业各方面的经营活动相互协调和与之相对应的包装、运输、存储、装卸、搬运、配送以及信息传递等商品物流活动综合起来的一种集成化的管理系统。物流配送的目的就是如何采纳最低的成本为客户及企业用户供应最优质的服务，以此来提高企业的整体竞争力和经济效益。因此，针对物流成本的探讨成为物流领域探讨的一个重点，据相关的数据统计表明，在不考虑商品在各个环节的额外费用以及商品的损失，我国运输、存储成本也许占我国国民生产总值的

15、20%以下，近年来经济运行成本快速增加。由于行业性质不同，物流总成本在不同的行业领域中所占比例各不相同，其中在成品制造业中物流运输成本所占比例最大，接近80%，在原材料生产业中所占比例相对较小，接近60%。因此，针对如何降低物流总成本是削减企业运营成本，提高企业竞争力的一个重要手段。物流运输过程中的配送路途与物流运输成本亲密相关，所以，针对配送路途的优化探讨具有重要的意义。 1.2 探讨意义 随着近几年电子商务的快速发展，小批量物品多批量配送以及快速、实时的配送方式在整个物流运营中所占的比例渐渐上升。电子商务给物流领域带来活力和朝气的同时也使得物流行业有了新时期的特点，例如Automatic

16、and Informational、Flexible、Network、Social、Standardized等特性。特殊是“最终一公里”概念的提出，该问题已经成为关系国民民生工程的一项重要活动。而囿于我国的基本国情和国民生活状况等，物流配送在新时代背景下出现很多不行避开的问题：1）物流配送成本相对较高，较高的成本使得企业的服务水平和经济效益都受到了严峻的影响；2）物流配送效率相对较低，较低的配送效率导致企业的服务质量难以满意人们的要求；3）物流配送路途规划不合理，不合理的规划路径不仅大幅度提升了物流配送的成本和效率，还对城市的交通带来极大的压力，导致人民的生活、出行等负担大幅度提升。因此针对物

17、流配送路途的探讨不仅关系到企业运营成本、企业服务水平以及市场经济中的综合竞争力，还关系到民生的大问题。通过对物流配送路途的优化探讨可以实现企业资源的合理配置，使得企业的服务水平、综合竞争力大幅度提升，还可以使得企业获得最大化的收益以及在国家民生中的优良形象。1.3 主要探讨内容 通过对国内外路径优化问题的归纳总结针对西安市长安区的路径优化问题进行模型建立，并且依据蚁群算法的实现思路建立符合西安市长安区路径优化问题求解的合适方案，并通过实例验证所设计方案的有效性。详细探讨内容为： 1）分析配送路途探讨的国内外现状，归纳总结现有的优化方法通过已有的探讨基础为本文的探讨工作供应思路； 2）归纳总结了

18、蚁群算法的相关概述，通过对基本蚁群算法的探讨，总结了相应的算法基础机理和实现流程并归纳总结了相应的优缺点； 3）针对西安市长安区的配送路途的问题进行调研，归纳了长安区的交通状况并总结了现阶段长安区物流配送所存在的一些问题，通过该部分的探讨为本文的方案设计供应了相应的背景支撑； 4）通过归纳总结西安市长安区配送路途的相关现状以及基本蚁群算法的相关理论基础，针对长安区的配送路径优化问题设计了相应的蚁群算法，并对详细实现流程进行设计，并利用实例对所设计的优化方案进行验证，验证结果表明白所设计方案的有效性。1.4 国内外探讨现状 1.4.1 国内探讨现状 所谓蚁群算法又称为蚂蚁算法（Ant Colon

19、y Optimization, ACO），该算法是放生算法的一种，主要用来搜寻最优化的路径。最初，蚁群算法1992年是由Marco Dorigo1在其博士论文中提出的，该算法的设计灵感是来源于自然环境中蚁群外出觅食过程中发觉食物，达到食物所在位置的路径选择的本能进行模拟的。在最初阶段，蚁群算法主要是用来解决旅行商问题，经过国内外探讨学者的努力探讨，现在已经发展成为一个多领域应用的智能优化算法，例如通讯网络中的路由问题、大规模集成电路问题、图片着色问题等。现阶段已经应用较为成熟的几个领域为最小树生成问题、旅行商问题、批量处理问题、车辆路径问题、二次安排问题等。其中，本文探讨的重点，物质配送路径优

20、化问题时车辆路径问题的一种，该问题是于1959年由Rmser和Dantzig2共同提出的，该问题主要解决肯定数量的物品通过肯定数李量的车辆通过合适的行车路途达到各个物质配送点的问题。并且在运输过程中须要考虑客户满足度和消耗、成本、路程等问题。Fisher3于1960年将车辆路径问题探讨工作划分为三个阶段，首先是启发式方式，该阶段时间为1960年到1970年这一阶段；然后是采纳数学规划进行启发式的1970年到1980年的这一个10年阶段，最终是采纳较新的智能优化算法的1980年以后的阶段。其中，蚁群算法是解决该问题的一个较新的思路，该方法具有较强的自组织性、鲁棒性、并行计算等优点。而经过国内外学

21、者的探讨针对蚁群算法计算时间长、收敛速度慢等缺点进行了解决。1.4.2 国外探讨现状 针对路径配送问题和蚁群算法的探讨，近年来国内也取得了较为优异的成果。杨从平4于2014年发表的基于蚁群算法的快递物流配送路径优化论文中，针对蚁群算法中的信息素更新规则和状态转移概率算法进行了设计，使得其快递车辆的路径优化问题有了较好的解算方案，并且将所设计的方案应用与广西桂林市的某快递公司中。倪益华和李巧玲5于2015年发表的基于改进的蚁群算法的困难制造系统物流配送路径优化论文中针对物流网络的规划问题进行了探讨，采纳有向图理论针对物流配送问题进行建模，并将时间和流量作为优化的约束条件进行了最优路径优化的求解。

22、黄浩6于2015年发表的供应链环境下物流配送路径的蚁群算法优化论文中，针对产品供应链下的物质配送问题进行了具体的探讨工作，依据相关的问题建立的供应链物流配送路径优化问题的数学模型，针对该最优化问题基于蚁群算法设计了相应的最优化方案，最终通过实例对所提出的算法进行了验证。经过多数探讨学者的探讨，现阶段针对物质配送路径优化问题以及蚁群算法的探讨都取得了大量的探讨成果，并且在已经广泛应用于多个领域中，特殊是蚁群算法针对车辆路径优化问题的求解具有较好的优化结果。基于此优势，本文针对西安市长安区的物流配送路径优化问题进行深化的调查探讨，设计了基于蚁群算法的最优路径选择方案，实例验证表明所设计的优化方案的

23、有效性。 2 基本蚁群算法的相关概述 本章针对蚁群算法的基本概念以及相关理论进行概述，首先对蚁群算法的定义进行阐述，探讨了蚁群算法的机制原理和实现的方法，最终针对蚁群算法的优缺点进行了归纳总结，通过本章的探讨工作为后续西安市长安区物流配送路径优化问题供应了理论支撑。 2.1蚁群算法的定义 人们经常针对自然界中的生物的一些“本能”进行探讨，通过对生物的一些习性进行仿生实现一些问题的求解。最简洁的例子，人们对鸟类飞行行为进行探讨独创了飞机7-9；通过对鱼类水中游的探讨独创了船、潜艇等。而蚁群算法就是仿生算法的一种，通过对蚂蚁觅食行为的探讨，总结其觅食行为的特征：1）蚂蚁在觅食过程中可以对四周一个范

24、围内的状况进行感知，进而发觉四周是否存在食物；2）蚂蚁在觅食过程中会释放一种带有气味的化学物质，该化学物质会随着时间的推移而挥发，这里成该化学物质为信息素。基于人们对蚂蚁觅食过程的探讨发觉，蚂蚁在觅食过程中释放的信息素不仅能够自身确定食物找寻的路径，还可以将确定的信息传递给其他蚂蚁，当蚂蚁在找寻食物的时候会沿着信息素朝着浓度较高的方向上进行找寻，当某一只蚂蚁找到食物时也会释放信息素，这样在其找寻到食物的路径上的信息素浓度也会随之变高，这样会吸引其他蚂蚁通过该路径到达该食物处，在此过程中其他蚂蚁也会在该路径上释放信息素，在该循环的作用下，该路径上的信息素浓度越来越高，这样就确定了一条找寻食物的最

25、佳路途10-13。针对上述蚂蚁觅食过程的探讨，人们对蚂蚁觅食的“本能”进行探讨，设计具有记忆功能的人工蚂蚁算法，并利用该算法针对蚂蚁觅食的过程进行仿生，以此设计出了一种智能算法，称之为蚁群算法。2.2 蚁群算法的机制原理 通过对蚂蚁觅食行为的仿生人们设计了蚁群算法，最早期时该算法在旅行商售货问题上应用较为广泛，随着科学技术水平的进步，蚁群算法在智能路径规划中起先进行应用14，本文针对西安市长安区配送路径的优化问题采纳蚁群算法进行探讨。实际中，配送路径优化问题就是旅行商问题的拓展。其本质上，这两个问题都是最佳路径的选择问题，旅行商问题15就是在几个城市中的某一个城市中有一个旅行商，该旅行商须要对

26、每一个城市进行一次服务，然后再全部服务完成后返回最初那个城市，这一服务过程中到达每个城市的路途支配，在旅行商问题中只须要考虑路径最短即可，但是在本文的物流配送问题中不仅须要针对路径进行考虑还须要考虑运输载体的运输实力以及运输载体的运输时间问题，假如运输载体的运输实力不足以满意客户要求的物品限制时，就须要进行多次重复运输，因此针对物流配送问题的路径优化问题的探讨要比旅行商问题更加困难，其意义也更大。为了解决物流配送中更加困难化的问题16，在物流配送问题中，将客户要求的配送服务的车辆设置为“人工蚂蚁”，但是限于运输车辆、人员的限制，所以在客户增加导致车辆、人员所能负责的最大限制时，“人工蚂蚁”就须

27、要返回动身点进行再次的配送服务，此时，在该算法中将该“人工蚂蚁”看作能够接着为其他客户进行配送服务的另外一辆配送车，直到当全部的服务要求都完成后，“人工蚂蚁”就完成了该次配送任务，当全部的“人工蚂蚁”都完成了配送任务时，表明一次任务循环完成。当一次任务循环完成后，依据“人工蚂蚁”的配送结果进行信息素的分析，并且计算信息素的增量，一次对各个路径上的信息素浓度信息进行更新，这样就可以进行下一循环的最有路径的选择17。实质上，针对物流配送问题的探讨思路就是将该问题转换为多个旅行商问题进行综合求解的过程。2.3 蚁群算法的实现 蚁群算法的实现流程如图2.1所示，首先将配送中心作为起点由第一只蚂蚁起先进

28、行某一配送点的物质配送，当到达该配送点后则接着为下一个配送点进行服务，以此类推，直到完成全部配送任务返回配送中心为止，其次只蚂蚁则在第一只蚂蚁返回配送中心后起先动身，采纳第一只蚂蚁相同的配送方式进行服务，以此类推，当全部蚂蚁完成配送任务后，针对最有路径进行记录保存并且更新信息素18。然后，全部蚂蚁依据信息素实现其次次的路径搜寻19，最终,再次更新信息素，进行循环，直到全部的运行次数完成后，依据算法运行的结果进行最优路径的选择20。由算法的实现过程可以看出，依据物流配送问题所设计的蚁群算法的实现流程和蚂蚁觅食的过程相同。 图2.1 蚁群损法基本流程 2.4 蚁群算法的优缺点 2.4.1 蚁群算法

29、的优点 与其他智能算法相比，蚁群算法具有较强的搜寻实力和较好的稳定性能，这也使得蚁群算法在最优化路径选择问题中应用较为广泛。此外，遗传算法还具有以下优点： 1）算法并行 蚁群算法是依据蚂蚁觅食行为进行设计的，也就是说在这一过程中每一只蚂蚁都是一个独立的个体，能够单独实现最有路径的选择。因此，据此设计的蚁群算法是散点运行的多代理系统，基于此特性，在配送路径优化问题中则可以针对每一个配送单位进行单独的优化，以此实现最终的最优路径的选取，保证了算法的实际操作性能和牢靠性能21。 2）自组织性 所谓自组织性就是指该系统可以通过与外界的信息、实力、物质等交换，并且在优化限制的作用下实现结构化、多功能化以

30、及有序化的转换，这一转变本质上是由于外参量和内部结构之间的持续相互作用产生的，而这一特性运用于物质配送问题中可以使得配送路径实现有序的改变22。3）鲁棒性 蚁群算法在实现过程中，针对单个“蚂蚁”个体的独立搜寻实力的作用发挥的较为明显，这就使得其对初始的路径要求不高，这就大大提高了算法的鲁棒性能23。2.4.2 蚁群算法的缺点 虽然蚁群算法具有上述稳定性、鲁棒性、自组织性和算法并行的优点使得其在路径优化等问题中应用较为广泛，但是其具有一些不行忽视的缺点。1）收敛速度慢 由蚁群算法搜寻过程中的特性可以看出，其最优路径是通过多次循环的“信息素”进行浓度选择进行获得的，这就使得其收敛的速度须要依靠于多

31、次的循环得到，这就导致蚁群算法的收敛速度较慢24。2）算法运行时间过长 虽然由于算法能够并行运算大大提高了蚁群算法的计算效率，但是在蚁群算法恶毒实现过程中须要进行多次路径选择，这就造成了算法的运行时间较长，这也是智能优化算法存在的一个严峻问题25。3）易出现过早停滞 由于蚁群算法的搜寻是各个个体针对目标接近的路径的多次循环更新，在更形过程中易陷入局部最优的状况，这就会导致算法简单出现过早停滞的现象。 3 目前西安市长安区的配送路途现状分析 上一章针对所要采纳的蚁群算法进行了具体的介绍，为本文的探讨供应了理论支撑，本章则针对现阶段西安市长安区的配送路途的现状进行分析，主要针对西安市长安区配送路途

32、的交通状况和现阶段西安市长安区配送路途存在的不足进行具体的探讨、归纳。为后续的配送路径优化算法的探讨供应相关的探讨基础。 3.1西安市长安区配送路途的交通概述 配送路途的优劣关系着物流配送效率，也干脆关系着用户对服务的满足度，针对配送过程中的路径优化不仅能够降低物质配送的成本还干脆关系着企业在新时期的市场经济中的综合竞争力，所以针对配送过程中的路径规划问题进行探讨具有非常重要的意义。而在这之中的车辆路径问题就是指配送员从物质配送中心动身把物质配送至相应的配送点所经过的路径集合，在这之中，不行避开的须要对配送过程中的路径的交通问题进行考虑。西安市长安区位于关中平原的腹地，南依秦岭，下属有25个街

33、道办事处，并且拥有清华山、五台山、阿房宫遗址等旅游景点。是一个以农业为第一产业的旅游城市。市内有神禾大道、长安大道、城南大道、雁引路等多条主要干道。作为一个拥有旅游资源且人口近百万的城市，西安市长安区在主要上下班时间段以及旅游旺季市内交通压力较大，并且还需考虑物质配送过程中行驶路途的交通信号问题以及交通管制等问题，因此针对配送过程中的交通问题进行考虑是配送路途优化问题所要考虑的一个重点。3.2 西安市长安区目前配送路途存在的不足 3.2.1食品“断链”问题严峻 随着电子商务的发展，现在足不出户就能品尝到世界范围内的美食，为了保证美食的平安和健康经常须要特定的温度、存储方式进行保存，而在食品运输

34、过程汇总经常须要严格的存储方式，然而在现如今的物流运输过程中，这一方面存在着严峻的问题，例如在食品冷链物流中就经常出现“两头冷中间热”、“冷链不冷”等断链问题的发生，为了针对该问题进行处理，须要针对物流行业建立明确的机制，这样采纳保证食品链不会出现断链问题。3.2.2食品链物流温控手段差 食品的存储多为低温存储，这就须要在食品运输过程中保证相应的温度，这就须要具有较好的温控手段，而西安市长安区的冷链基础设施的建设不完善，图3.1给出了西安市长安区的冷链基础设施分布比例图。此外，在运输途中所具有的冷藏运输车数量不足，有些冷藏车制冷效果不明显。都干脆导致食品运输的平安问题。 图3.1 西安市长安区

35、的冷链基础设施分布比例图 3.2.3从业人员素养不高 由于现阶段针对物流行业的相关政策及监管还不是太健全，因此物流行业恶毒从业人员素养普遍不高。此外，由于物流行业的发展过于快速，相应的基础理论探讨相对不成熟，虽然现如今各大高校已经具有物流管理等专业，但是实际中，服务于第一线的物流配送人员多是没有受过专业培训的人员，专业技术水平普遍不高，这就干脆导致物流行业的人员素养参差不齐。这一问题干脆导致了用户满足度不高等问题。 3.2.4成本问题 由近几年关于物流行业的数据统计信息可知，物质运输、存储等花费的成本占企业物质生产总成本的60%80%左右，依据行业的不同所占比例有所波动，但是物流成本仍是占据大

36、部分成本的份额。因此，物流配送的成本问题是针对物流行业提高利润一个重要方面，而物流配送过程中的运输代价又占据着重要的一部分，这也就是为什么须要针对物质配送路途进行优化的主要缘由。3.2.5管理问题 由于近几年经济的快速发展，特殊是电子商务的发展，使得物流配送行业发展非常快速，这就干脆导致其管理出现问题，最明显的就是市场管理法规和市场竞争机制不健全，相关的产业规划方案和产业政策还没有制定出台，这就使得物流行业的推出、进入以及竞争的基本规则都没有相关的法规和法律进行遵循，这就使得在行业内的不正值竞争严峻。3.2.6服务问题 由上述分析可知，现阶段物流行业的相关监督机构相关法律法规等都尚未完善，并且

37、，物流行业的从业人员素养普遍不高，这也就使得在物流配送过程中物流的一线服务存在着严峻的问题。此外，由于物流链的断链和相应的温控手段不足，以及运输过程中造成的物品受损等问题，使得用户对配送服务的满足度不高等问题。 4 结合蚁群算法，优化配送路途的途径 经过针对蚁群算法和目前西安市长安区的配送路途现状的分析，明确的路径规划问题的理论基础和问题背景，为了实现蚁群算法和配送路途的完备结合，本章针对基于蚁群算法的西安市长安区配送路径优化问题进行探讨，设计了相应的算法流程。 为了实现路径的优化这里首先定义蚂蚁的数量也就是配送员的数量为，配送点数量为，各个配送点之间的距离表示为，当前时刻处于某一配送点的配送

38、员的数量为，这里有，在给个配送点之间的连线上的信息量为，这里在算法运行初始时刻各个路径上的信息量是相同的，即。配送员在物质配送过程中依据每一条路径上的信息量进行路径的选择，在路径选择过程中，配送员选择某一路径的概率为： (4-1) 这里，为配送员下一时刻所被允许到达的城市。这里为了避开配送员走过的城市再一次进行运算，在蚂蚁中加入了记忆功能，即采纳针对配送员这一时刻所走过的城市进行记录。配送员从某一城市到达另一城市的期望度采纳来表示，这里采纳某一种启发式进行确定。在配送员运动过程中积累的信息和在启发式中选择的路径作用采纳和进行表述。这样就可以针对信息素随着时间而渐渐耗散的性质进行模拟，这里采纳对

39、信息耗散程度进行表述，而在每一个配送员完成一次循环后的信息素的调整则采纳： (4-2) (4-3) 其中，表示配送员在上一个配送循环过程中在路径上留下的信息量。可以采纳如下所示的式子描述： (4-4) 这里，表示配送员在该路径上运动的路径长度，为定义的常数。初始条件下。这里常数可以采纳多次的计算进行最优组合的选择。依据上述西安市长安区配送路径优化的蚁群算法模型设计如图4.1所示的算法流程图。 图4.1 基于蚁群算法的西安市长安区配送路径优化流程图 4.1 信息素浓度表的实现 由于物流中心车辆和蚂蚁不同，其具有不同的运载实力，这就可能产生下述状况，也就是同意目的的物质可以通过两种不同的车辆进行运

40、输，这样就使的在配送过程中产生干扰，为了解决这一问题，这里采纳多种信息素浓度表进行表述。也就是针对不同的车辆类型设计不同的信息素浓度表，这样不同类型的车辆在物质运输过程中产生的信息只能存储在与其对应的信息浓度表中。这样，就能够使得相同的车辆共享同一份信息浓度表，而不同类型的车来那个则不能运用与之不同的信息浓度表，这样就可以避开不同类型之间的干扰问题。 为了更加明白的表示信息浓度表的实现，这里采纳4辆载重3吨和1辆载重5吨的车辆进行如图4.2所示的信息浓度分布表述。C3：2T C2：1T C1：2T C0 0.0 0.0 0.8 0.8 0.8 3吨车信息素分布 C3：2T C2：1T C1：2

41、T C0 0.2 0.2 0.2 0.0 0.2 5吨车信息素分布 图4.2 信息浓度表示意图 4.2 集合tabu的确定 所谓tabu集合就是指在配送员在物质配送过程中不允许选择的配送点。一般来说，他不集合就是指配送员所达到过的配送点，但是在西安市长安区配送问题中还须要进行如下因素的考虑： 1）到达配送点的路途的距离超过该配送员的配送范围； 2）配送点所要求的物质总量超过配送员所能携带物质的总量； 3）达到配送点的路途中有配送员所乘交通工具的限制； 4）配送点的物质要求只能由一个配送员完成。本文采纳的tabu集合就是将上述4点因素的配送点和配送员已经到达过的配送点的集合。4.3 车辆序列的初

42、始化 在西安市长安区物质配送过程中，全部的配送员都是相互独立的，可以不考虑配送员之间的先后问题，但是在蚁群算法实现过程中，须要一次针对配送员的路途进行支配，这样就产生了一个先后的依次，在加上不同的车配送员所能运输的物质量不同，使得不同配送员的路径搜寻的先后就会对最终的优化结果产生影响，假如每次都采纳相同的依次就可能导致无法搜寻到全局最优的路径。本章采纳随机序列来解决配送员搜寻先后的问题，首先，在蚁群算法实现过程中，在每一个蚂蚁（也就是配送员）进行路径搜素之前利用随机发产生一个配送员序列，然后让每个配送员根据随机序列进行路径的搜寻。这样就避开了由于搜寻序列造成的最终路径不是最优的问题。4.4 车

43、辆不足状况及惩处成本 在实际物流配送过程中，全部的配送员全部工作也无法一次完成全部物质的配送，这时就须要一部安排送员进行多次的配送路途的选择，然而，在基础的优化算法中，假如一次无法完成全部的配送任务就会认为该配送任务无法完成，这就和实际无法相符。常用的解决方法就是不考虑配送员的数量，干脆进行最优化路途的安排，当最终优化结果所需配送员数目大于现有配送员数目时，就让配送员多次进行物质配送。但是这样就会使得部分货物无法第一时间进行配送，这样就无法完备的实现最终配送任务的最优。这里针对配送员不足的状况引入惩处成本，当配送员配送时间超过物质应当到达的时间时，就为该次配送成本加上肯定的惩处成本。该思路的引

44、入不仅能够结局配送先后依次的问题，还可以结局多次配送的问题。本章所设计的惩处成本算法为： 1）定义为配送员已经配送的路径距离； 2）为了计算便利将客户所期望的时间转换为距离为； 3）依据配送员配送距离和客户期望时间判定是否须要加上惩处成本，定义为惩处成本； 4）依据上述判定加上惩处成本：。4.5 运力利用率 为了更加高效的利用现有的配送资源，这里针对西安市长安区物质配送路径优化问题中引入“运力利用率”的概念，也就是在蚁群算法中的评估函数中加入运力的利用率。这里采纳配送员所能配送物质的总量和配送员实际配送量的比作为运力利用率进行计算。为了验证本章所设计的基于蚁群算法的西安市长安区配送路途优化算法

45、的有效性，这里采纳如下实例来进行验证，通过对西安市长安区某物流配送公式进行假设，假设某一配送中心有3个配送员为9个配送点进行物质配送，每个配送员所能配送的物质位3吨，最大配送范围为100千米，配送中心和配送点的坐标及每个配送点的物质量如表4.1所示。ID X坐标 Y坐标 需求量 ID X坐标 Y坐标 需求量 0 28.4 25.4 0 5 32.0 34.6 0.8 1 32.0 20.2 0.1 6 21.2 27.9 1.0 2 31.3 15.5 0.4 7 14.3 18.6 1.5 3 46.0 25.8 1.2 8 17.1 1.9 0.6 4 51.0 38.7 1.5 9 19

46、.7 38.4 1.2 采纳本文所设计的算法，得到如下配送方案： 三个配送员一共配送距离为161.97KM。配送路途如图4.3所示。 图4.3 物资配送路途图 5 结论与展望 5.1 结论 西安市长安区配送路途优化问题是一个典型的组合优化问题，为了实现企业的综合效益以及保证企业在市场经济中的综合竞争力，针对物质配送路径的优化探讨是非常有必要的，而蚁群算法则是人们依据蚁群觅食的行为而设计的一种智能优化算法。本文针对西安市长安区的配送路径优化问题进行探讨，采纳蚁群算法设计了基于蚁群算法的路径优化方案。通过本文的探讨工作，主要取得以下探讨成果： 1）针对国内外物质配送的探讨现状进行探讨，归纳总结了国

47、内外先进的路径规划方案，为本文的西安市长安区物质配送路途优化问题的解决供应了思路； 2）针对蚁群算法进行探讨，深化分析了蚁群算法的机制原理和蚁群算法的实现过程，归纳、总结了蚁群算法的优缺点； 3）针对目前西安市长安区的配送路途问题进行调查探讨，为本文的设计工作供应了基本背景支撑； 4）针对现有的西安市长安区配送所存在的问题，采纳蚁群算法设计了基于蚁群算法的物质配送路径优化方案，并进行实例验证所设计的算法的正确性。 5.2 展望 蚁群算法是一种新型的智能优化算法，将来还具有更加广袤的探讨空间，例如如何解决蚁群算法的收敛速度慢、算法运行时间过长、易出现过早停滞等问题。此外，针对西安市长安区配送路径

48、的分析还能够建立更加完善的、接近实际的优化模型，以此更加精确、高效的进行路径优化。 参考文献 1 Dorigo M, Maniezzo V, Colorni A. Ant System:Optimization by a Colony of Cooperating Agents. Man and Cybernetics-Part B,1996,26(1) :29. 2Dantzig G, Ramser J. The Truck Dispatching ProblemJ.Management Sience,1959,10(6): 80. 3Fisher M L, Jaikumar R. A Generalized Assignment Heuristic for Vehicle RoutingJ.Networks,1981，11:109. 4杨从平. 基于蚁群算法的快递物流配送路径优化J. 物流工程与管理,2014,(04):65. 5李巧玲, 倪益华. 基于改进的蚁群算法的困难制造系统物流配送路径优化J. 轻工机械, 2015, 33(2):106. 6黄浩. 供应链环境下物流配送路径的蚁群算法优化J. 物流技术, 2015, 34(6):118. 7张伟.