择要：车辆路径题目首要研究物流配送中车辆线路优化以进步物流配送的服从。本体系实现基于百度舆图API及智能算法求解车辆路径题目。起首通过百度舆图API获取节点间现实门路的间隔数据，然后将百度舆图API获取的门路现实间隔数据提交给改良的蚁群算法求解最短路径模子，淘汰配送车辆的在途时间，接纳电子舆图表现最优的车辆路径。
关键词：蚁群算法 物流配送 路径优化 空间信息
1 弁言
应急物流是指为应对严峻天然灾难、突发性公共卫生变乱、公共安全变乱及军事辩论等突发变乱而对物质、职员、资金的需求举行告急保障的一种特别物流运动。
应急物流可以分为军事应急物流和非军事应急物流。非军事应急物流可以细分为天然灾难应急物流、人为灾难应急物流和疫情应急物流。天然灾难应急物流配送首要针对救灾物资的网络、分类、包装、运输和救灾物资发放作业,整个救济物流的运输与配送中，都是围绕着灾区的受灾职员。
随着情况灾难对社会及国家产业酿成的造访丧失，怎样进步应急物流配送程度成为亟待办理的题目。在车辆路径题目的研究中，通常接纳节点间直线间隔之和作为最短路径最优求解的数据根底，而节点间直线间隔和与门路现实间隔通常相去甚远，使得其最优路径安排难于真正运用英魂在现实需求中。
因此通过百度舆图获取节点间现实门路的间隔数据，通过增添束缚条件、修改节点间间隔的盘算、更换选择计谋、调解信息挥发因子等方法改良根本蚁群算法，末了将百度舆图获取的门路现实间隔数据提交给改良蚁群算法求解。
面临都会各类突发公共变乱发生频仍的严肃形势，面向都会建立中急需办理的应急物品运输路径题目，联合突发变乱、地理信息技能、盘算机技能、智能盘算等范畴的最新希望，通过对物品运输路径的分析和研究，使用理论与实践相联合的方法，研究与救济车辆行驶时间密切相干的路网交通参数，创建路网状态变革模子。
在此根底上，创建基于蚁群算法的最短路径模子并优化求解过程，淘汰物品配送车辆的在途时间，提拔都会灾难应抢救灾和减灾程度，为保障都会人民生命产业和地区可连续开展提供科学依据和技能支持。
我国是一个天然灾难多发的国家。灾难威胁我国都会安全，造成了巨大的经济丧失和职员伤亡。应急物流是都会遇灾处置惩罚体系中紧张的构成部门，关于应急物流配送研究对于减小都会灾难丧失和扩大有着紧张的引导意义。应急配送路径选择和车辆调理是物流配送中非常紧张的一项运动。本研究搜集都会根底地理数据资料，利用蚁群算法的最短路径模子并优化求解过程，使得须要时为受灾都会提供实时救济和公道资助。
2、蚁群算法
蚁群算法（Ant Colony Optimization，ACO）是一种群智能算法，最早是由意大利学者Colorni A.,Dorigo M.等[1]在1991年提出。颠末多年的开展，蚁群算法已得到巨大的进步。
2.1 根本道理
蚁群算法是由天然界中蚂蚁觅食的举动而开导的。天然界中，在蚂蚁探求食品过程中，蚁群总能探求到一条最优路径去搬运食品。如图表现了如许一个觅食的过程。
蚂蚁觅食
如图（a），假设A点蚁巢，E点为食品，蚂蚁在活动过程中会开释一种叫做信息素的物质，蚂蚁会沿着信息素浓度最高的路径活动，在没有停滞物的时间，对于最开始的几只蚂蚁而言，沿直线活动的蚂蚁搬运一次食品所需时间更短，则在雷同的时间内，沿直线活动的蚂蚁最多，假设每一只蚂蚁在活动时所开释信息素的量完全雷同，则直线路径所积聚的信息素浓度最高，以后的蚂蚁就会沿着信息素浓度最大的路径活动，即直线路径；
如图 (b)，出现停滞物时，蚂蚁会以雷同的概率从停滞物的两侧绕过，从H点大概C点绕过停滞物，由图可知从C点绕过停滞物的路径最短，则该路径所积聚的信息素浓度高，则会有更多的蚂蚁从C点绕过停滞物，如图(c)所示。
2.2 实现过程
假设蚁群中全部蚂蚁的数目为antcount，节点数目为citycount（此中配送中央的数目为1，配送点的数目为citycount-1），全部节点之间的间隔矩阵用distance表现，信息素矩阵用tao表现，最好路径为besttour。每只蚂蚁都有本身的内存，内存中用一个禁忌表（unvisitedcity）来存储该蚂蚁已访问过的节点，当值为0时表现未访问过，值为1时，表现访问过，意味着其在以后的搜刮中将不能访问这些节点；
在每次迭代和选择过程中，用tour表现当前门路，容量为citycount+1，此中第一个值与末了一个值雷同，包管蚂蚁末了回到出发点；另有别的一些数据，比方一些控制参数 (alpha=1.0，beta=2.0，rou=0.5)，该蚂蚁行走玩全程的总间隔（bestlength），等等。假定算法的迭代次数为maxgen，运行时间为runtimes。
蚁群算法盘算过程如下：
（1）初始化。
设runtimes=0，初始化bestlength为一个无穷大的数，bestTour为空。初始化全部的蚂蚁的tao矩阵全部元素初始化为0.1，unvisitedcity表中的值全部设为0。同时，通过函数SelectFirstCity()选定配送中央为蚂蚁的起始位置，将其在unvisitedcity矩阵中对应的值变为1，并将其参加到tour表中。
（2）为每只蚂蚁选择下一个节点。
用函数SelectNextCity()为每只蚂蚁选择下一个节点，该节点只能从unvisitedcity矩阵中值为0的节点当选择，此中每个节点以某种概率搜刮到，每搜到一个，便将其在unvisitedcity矩阵中对应的值变为1，并将其参加到tour表中。该过程重复citycount-1次，直到全部的节点都遍历一次。遍历完全部节点后，将起始节点再次参加到tour中，即tour的第一个元素和随后一个元素均为配送中央节点，此时tour表元素数目为citycount+1。
末了通过函数CalTourLength()盘算总的路径间隔，比力每个蚂蚁的路径间隔，然后和bestlength比力，若它的路径间隔比bestlength小，则将该值赋予bestlength，而且将其tour赋予besttour。
（3）用函数UpdateTao()更新信息素矩阵。
（4）查抄停止条件
当达迭代次数到达maxgen时，算法制止，转到第（5）步；否则，重新初始化全部的蚂蚁的tao矩阵全部元素初始化为0.1，unvisitedcity表中的值全部设为0。同时，通过函数SelectFirstCity()选定配送中央为蚂蚁的起始位置，将其在unvisitedcity矩阵中对应的值变为1，并将其参加到tour表中。重复履行（2），（3）,(4)步。
（5）输出最优值。
算法流程图如图所示：
蚁群算法流程图
3、体系实现
为到达总运行时间最短的目的，接纳改良的蚁群算法优化导航门路，用以优化配送路径，并表现优化效果，从而为应急配送体系的构建提供行之有用的信息化本领。
通过将蚁群算法与百度舆图联合起来实现配送，为将蚁群算法与百度舆图的联合更直观的表现出来，该模块的计划接纳了frame框架，将该模块分为摆布两个部门，左边为物流节点选择区，右边为百度舆图。配送员可以在左边栏当选择一个配送中央（出发点）、多个配送点（目的场合），由蚁群算法盘算出最优路径，终究可得到路径规划效果。
图1舆图查询模块界面
4、结论
本文是基于百度舆图API、javascript和JSP编写的一个路径优化体系。体系将全部的地理数据存放到数据库中，可查询所效劳点的具体位置，表现各配送点之间的导航门路。为到达总运行时间最短的目的，接纳改良的蚁群算法优化导航门路，用以优化配送路径，并将最好路径用百度舆图出现出来，从而为配送体系的构建提供行之有用的信息化本领。
参考文献
[1] Colorni, A., M. Dorigo and V. Mariiezzo., 1991. Distributed Optimization by Ant Colonies, in: Proc. Eearop. Conf. Articial Life, ed. F. Varela and P. Bourgine.
（本文作者：张子寒 朱海佳 郭腾飞 亓呈明 泉源：北京团结大学都会轨道交通与物流学院）
300x180 AD
说点什么...