基于空间信息的应急物流配送路径优化研究

叔有胸肌36C

摘要：车辆路径问题主要研究物流配送中车辆线路优化以提高物流配送的效率。本系统实现基于百度地图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. Artificial Life, ed. F. Varela and P. Bourgine.
（本文作者：张子寒 朱海佳 郭腾飞 亓呈明 来源：北京联合大学城市轨道交通与物流学院）