基于ArcLogistics的油库二次配送最优路径研究

李媛　解婷婷

摘 要：GIS技术其蕴含的巨大经济价值已经被人们所广泛认知。GIS系统拥有强大的数据管理、分析能力，能够有效处理大量复杂的地学问题，在地理信息系统的平台上研究分析成品油二次配送路径优化问题问题概括来讲主要有三个优点：界面可视化、对空间数据的管理分析能力、分析功能。本文所以研究的内容是在GIS环境下，对最优路径问题进行分析建模，进而求解出成品油二次配送的最優化路径，在对比分析多种不同算法后，选取Dijkstra算法作为求解最优路径问题的核心算法。

关键词：GIS技术；路径优化；二次配送；Dijkstra算法

二战后全球能源需求的大量增加，使得原油的供需矛盾逐步显现，中国也从上世界九十年代起，由石油出口国转为石油进口国，随着中国经济的不断发展，工业体系的不断壮大，可以预期的是，在可替代能源尚无法大规模使用的大背景下，我国对石油资源的需求量在未来很长时期还将继续保持较为快速的增长，对外依存度也在逐年增加。因此利用GIS技术来提升物流配送效率是当前环境下的必然结果。

1 最优化问题的相关算法

（1）Floyd算法

Floyd算法又被称为插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法[18]。该算法名称以创始人斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法在求解最优化路径问题的是时候，是将区域道路网看做一个带权矩阵，我们假设以A节点为起点，B点为目标点，Floyd算法的解救过程就是遍历所有由A通向B的路径，然后从中选择最优路径。在Floyd算法的运算过程中，对于弧的权值没有限制，正负均可，其主要优点是算法易于理解，代码实现上不存在太大的技术障碍。但是Floyd算法时间复杂度是0（），在实际，不适合对大规模数据进行运算。

（2）蚁群算法

蚁群算法的诞生，最初来源于对蚂蚁发现进食路径的研究，关于蚁群算法的系统性研究最早出现在Marco Dorigo的博士论文中，这是一种仿生模拟进化算法[19]。我们可以重现蚂蚁觅食的全部过程，蚂蚁会在移动的过程中释放生理激素，而这种激素会对其他蚂蚁选择移动方向产生影响。因为我们不难推测，最初的时候蚂蚁的活动范围就如同一张白纸，并不带有任何的生理激素也就是路径信息，而伴随着蚂蚁活动的增加，生理激素的浓度水平也会随之逐步提升，不难发现信息素浓度越高的路径，就是蚂蚁活动越频繁的路径，反之路径上生理激素的浓度越低，蚂蚁的活动就越不活跃，伴随着这种行为的不断进行，生理激素浓度水平越高的道路就是蚂蚁活动的最优化路径。蚁群算法的时间复杂度是0（**m）其中为模拟次数，n为节点数，m为蚂蚁种群规模。

（3）Dijkstra算法

Dijkstra算法其本质是将现实中的道路交通分解为节点和弧，并对弧进行赋值权值，可以表示道路的长度，路况等多种影响因素，通过建立一个带权值的无向图来模拟实际交通网络中的实际道路情况，可以将无向图看作树，起始节点可以看作树的根，从根到树的各节点权值最小的路径就是我们所需要的最优路径。Dijkstra算法适用于求解单源点到各个节点的最优路径问题。Dijkstra算法的时间复杂度为0（）， n表示中节点的个数。

从结点 A 到结点 J 的最短路径是 A1→B2→E5→F6→H8→J10，权值求和为10.8。不难发现，利用Dijkstra算法所需的求解步骤为45.使用 Dijkstra算法求解最优化路径问题时，为了使算法能够正常运行会占用一定的内存空间。在实际应用中，数据的处理量往往很大，对于系统也要求实时性，所以实际使用中，对于服务器和客户端性能会有一定的要求，因此，如果能够对Dijkstra 算法进行结构优化，可以很大程度上缩小计算步骤，但是随着处理器技术的不断发展进步，处理器的计算能力不断提升，在实际求解最优化路径问题的过程中，Dijkstra算法的缺陷，其实并不会成为最首要的障碍

（4）三种算法对比

Dijkstra算法复杂度较低，可以解决单元点问题算法，但是适应性差；Floyd算法易于理解，但是时间复杂度较高不适合大规模计算；蚁群算法适应性强，正反馈性好缺点是收敛速度慢。综合考虑，本文采用Dijkstra算法，并对其进行适当优化从而求解最短路径问题

2 最优化路径分析模型的构建

从本质上来讲，Dijkstra算法最终的到的结果其实是道路网络模型的权值，因此如果要使Dijkstra算法能够用于解决实际问题，其关键在对于权值的处理。文本对于权值的处理考虑以下几个因素：距离、路况。以此构建出来的优化模型为： ，其中为道路的长度，为道路的通行状况。影响通行状况的因素很多，包括车流量、道路宽度、路面养护情况等。对于这些影响因素目前尚没有高效的评价分析模型，如果一一探讨，工作量大，且没有任何意义。在这里我们可以用平均通行速度来表示道路的通行状况，因为无论车流量、路面养护情况如何影响道路的通行状况，其最终的影响形式就是影响车辆的通行速度。我们因此可以构建道路的通行状况模型=，其中 为车辆经过该路段的平均速度， 为我们所设定的标准速度。所以权值的计算结果为，在系统的实际使用过程中，我们会在GIS系统里面对道路属性进行直接赋值，避免在运算过程中重复计算，进而有效减少系统的计算量。

3 结语

在GIS平台的基础之上在算法的选取上采用Dijkstra算法，在分析物流配送体系的基础之上，建立了最优化路径的算法模型，本系统的功能模块包括地图数据的导出、地图标注、属性查询以及最优化路径查询模块，系统采用Visual Studio 2008+AE组件的方式，实现了所需要的系统功能。具有较高的实际应用价值。

参考文献

[1] 徐洪勇.基于GIS的最短路径算法改进对比研究：（硕士学位论文）.北京：中国地质大学，2008.

[2] 陈琥.交通网络最优路径分析研究[D].北京：解放军信息工程大学，2007.

[3] 阮洁，钟宝荣. Dijkstra算法在物流配送运输中的最短路径优化研究[J].产业聚焦，2007， 第16卷（第8期 ）：42-44.

[4] 黄贵玲. 基于蚁群算法的最短路径问题的研究与应用[J]. 计算机工程与应用， 2007，43（13）..

[5张学敏.GIS环境下的动态交通最优路径算法研究：（硕士学位论文）.长沙：中南大学.2009.

作者简介

李媛 （1992—），女，硕士，最优化理论与应用。