基于ArcGIS的运输路径优化研究
——以贵州省湄潭县某茶业公司物流配送为例

薛 亮，黄 新，郑 琰 XUE Liang,HUANG Xin,ZHENG Yan

（1.南京林业大学 汽车与交通工程学院，江苏 南京 210037；2.南京林业大学 土木工程学院，江苏 南京 210037）

(1.School of Automobile and Traffic Engineering,Nanjing Forestry University,Nanjing 210037,China;2.School of Civil Engineering,Nanjing Forestry University,Nanjing 210037,China)

0 引言

地理信息系统是一种用来获取、保存、操作、探究、管理空间或地理数据的类数据库系统。具体来说，GIS就是用在广泛学科领域的一种大地理信息学科，能够将工程、规划、物流、保险、电信、商业连接起来，并在此基础上进行数据分析和可视化服务。该技术在世界范围内都十分普及，是实现可视化、智能化、数字化的物流规划的重要部分。结合有效的算法，能够很好地改善贵州省茶农、茶叶制造厂的配送路径，提高效率，促进贵州省茶叶物流的发展。

1 车辆路径问题及算法介绍

1.1 车辆路径问题。在国外，车辆线路优化问题属于VRP问题（Vehicle Routing Problem），起源于旅行商问题[1]。车辆路线问题可以描述为如下数学模型：如有一配送中心点，有S个商铺，N辆配送车辆。车辆从配送中心出发，配送所有商铺，每个商铺需求被满足，且容量不能超过车辆上限，最终实现总成本最小的目标。中心仓库配送、公共交通工具路线制定、纸媒邮件投递、大型交通工具（飞机、火车）时间表安排、工业废品后期处理等，都包括在车辆路线的实际问题中。本文考虑的车辆路径优化问题是针对茶叶企业实际的单配送中心、单一车型、单向送货、有回路的实际问题。

1.2 车辆路径算法。解决目前车辆路径问题的算法主要有：精确算法、传统启发式和现代启发式算法[2]。

通过表1对各种算法的分析比较，传统启发式算法改善程度有限，难以得到满意解，所以在最短路径问题中应用较少；遗传算法和禁忌算法是目前用于解决大规模车辆路径优化问题的主流方法，对参数、数据要求较高，相对复杂。如果是以整个贵州省为优化目标，选用基于K-MEANS的禁忌算法较好，但是解决本案例中的单配送中心、单车型、纯送货、有回路的车辆路径问题，通常选用精确算法，现将采用几种算法对比研究。

表1 各种算法优劣势对比

2 ArcGIS图层设计

2.1 数据采集、录入

（1）数据采集与录入作为建立地理信息系统的第一步，为以后的各项步骤奠定基础。本文使用的电子地图来源于网络，并根据百度地图提供的数据进行修改增删。如果想要使得网络分析功能实现，那么有三个部分不可或缺。首先就是仓库（或者说配送点）和商超专卖店分布信息，然后是仓库的容量、商超的容量，最后是货车从仓库到商超的所有可能经过的路径。

（2）最短路径问题解决的主要问题是仓库（配送点）和目标商超之间的路径问题，所以商超的地理分布位置应该作为首要解决的问题。同样地,商超专卖店应该包含以下内容：准确无误的经纬度坐标信息，相关次要因素信息。一般来说，我们应该提前建立仓库（配送点）和商超专卖店的数据档案，建立数据服务器或者本地档案，方便直接调用。与此同时，系统能够根据实际需要，随时增添、修改或删除对应的相关信息。

2.2 数据结构选择

按照数据组织结构的不同分类，主要有两大类：矢量数据结构和栅格数据结构。

（1）栅格数据结构。按照一定规则将需要分解的工作区域平面进行行列划分，形成网状结构，每一个网格单元称为像元。而栅格数据结构实质上等于像元按矩阵形式有序组合排列。每一个像元坐标位置由行列号组合形成的二元坐标定位，类似于常见的笛卡尔X-Y坐标轴。

（2）矢量数据结构。矢量是具有一定大小方向的量，代表着有序、有独有特征的有向线段，它们的集合就构成了图像。矢量数据就是代表地图特征的各离散数据的有序集合，主要用于表示地图上各种各样的组成元素，表现了几何和属性数据的一定关系。

2.3 属性数据

属性数据主要用来表示确定位置的地理对象的特殊属性，空间位置的变化不一定使属性改变，例如人行道的具体位置确定，由普通斑马线变为人行天桥等。本文涉及到的属性数据主要包括城市、道路、超市商店（服务点）的属性数据。城市的属性数据包含以下几个词条：ID、name（名称）、class（等级） 等；道路：ID、name（道路名称）、kind（道路等级）、shapelength（长度）等；商超：ID、name、kind（种类）等。根据实际需要增加或减少数据类型。

3 贵州湄潭县某茶业公司配送路径优化问题求解

贵州湄潭县某茶业有限公司，依托100万亩优质茶叶基地，企业发展蒸蒸日上，迄今已实现从中国茶叶行业百强企业，到贵州省重点龙头企业，再到国家级重点龙头企业的跨越式发展。但是物流作为该公司的短板，已经严重影响到该公司的发展，下面将结合各算法，就该问题进行探讨。

3.1 蚁群算法求解。蚁群算法是一种用来寻找优化路径的概率型算法。通过阅读文献[3-4]，确定在蚂蚁数量为m，信息素重要程度参数α或者β区间为［1,5］，信息素蒸发系数Rho区间为［0.3,0.5］，信息素增加强度系数Q=100时，能够保证在小规模计算中，较为快速地求出最优路径。那么根据本文已有的参数，可以求得蚂蚁数量为4或者5，而蚂蚁数量越多越能提升搜索量，提高搜索效率，故蚂蚁数量设置为5。经过间隔0.1的组合优化，发现当α=1.5，β=2.0时运算效率较高。在其他参数确定的情况下，多次试验发现Rho=0.4时比较适合本案例。

建立距离矩阵（如表2所示），采用蚁群算法求解最短路径。通过Matlab编程，多次运行程序（最大迭代次数为100），可以得到路径分析结果，最短路径是11-6-10-7-8-9-3-2-5-4-1，路径长度为12 039m。

3.2 遗传算法求解。在设计遗传算法过程中，某些参数的选择影响着算法的可行性和准确性，极大影响算法性能，但是由于参数选择至今没有一个统一的标准，所以目前的解决措施是依靠先验知识来选择，与此同时参考国内部分文献资料[5-6]。

种群规模直接影响最优解的质量，种群规模的大小与最优解质量呈正相关。伴随着种群数量的增大，算法运算时间呈指数级上升，而一般种群数量约为商超数量的1～2倍，因此本文选取一个适中的种群数量20。

表2 10个商超之间的距离矩阵

适应值归一化淘汰加速指数，根据经验默认取值范围｛1,2,3,4｝且取值不能偏大，此处由于数据较少，试验得出当该数值等于2时，比较合适。本文采取固定交叉概率，取值范围为 ［0.9 , 0.999］，由于商超数量较小及试验佐证，选取0.9作为交叉概率数值可行。同理，选取变异概率Pmutation=0.1，满足遗传算法参数选取经验。

主要输入参数包括：商超（包括出发点）个数N=11，种群个数M=20，迭代次数C=100，适应值归一化淘汰加速指数m=2，交叉概率Pc=0.9，变异概率Pmutation=0.1。运行程序,可以得到路径分析结果，最短路径是11-1-9-2-3-8-5-4-7-10-6，路径长度为12 278m。随着迭代次数的增多，无限接近于最优路径，但是次数少往往不能得到最优解，只能获得较为接近最优解的最佳解，并且随着迭代次数增多，运算时间大大加长，对电脑硬件要求较高，且出现内存不足的情况。

3.3 免疫算法求解过程。由于免疫算法与遗传算法拥有极大相似性，所以主要参数设置基本与遗传算法相同，此处不再赘述。定义：商超个数N=11，种群个数M=N-1，字符变异概率pStrChange=0.4，字符交叉概率pCharReCompose=0.4，最大迭代次数MaxIterateNum=100。

运行程序,可以得到路径分析结果，最短路径是11-9-7-8-4-10-6-5-2-3-1，路径长度为12 039m。多次迭代可以找出最短路径，但是会出现路径不是最优的情况。免疫算法适合数量较大的问题，对于数量级较小的问题，难以迅速求出最优路径，但是对比遗传算法则快了许多。

3.4 ArcGIS自带Dijkstra算法求解。ArcGIS本身具有网络分析功能，其中最基础的功能即是最佳路径分析功能。在网络分析中，有最短和最优两种路径分析的工具模块，前者在解决最短路径问题方面比较适用，后者在路径分析方面主要用于城市基础设施网络如各种城市设施建设、地下排污管道、通信光缆等的线路路径分析。另外，在进行网络分析之前，这两种工具都需要在构建道路网络的拓扑关系的基础上，建立网络数据集。路网拓扑关系构建比较复杂，且往往不能得到所需的最优解。采用ArcGIS计算上例中的最短路径，结果显示：具体路径是11-9-2-4-6-7-8-10-5-1-3-11，长度为14 336m。

3.5 算法比较。过上述四种方法分别求得物流配送的最短路径，下面从几个方面进行分析，如表3所示。

表3 各算法理论最短路径比较

对比各项数据，就本例而言，采用蚁群算法比较合适。它可以在硬件条件受限时迅速得出最短路径，且编程比较容易获取，其他算法都存在一定的限制。遗传算法的参数设置要求比较高，如果设置不合适，会出现过早收敛，找不到最优解而是次优解。但迭代次数比较大时（大于1 500），会出现内存不足的情况，可见当迭代次数增加时，对硬件条件的要求也相应地提高了；免疫算法类似于遗传算法，但是又与之不同。最典型的就是免疫算法可以结合其他算法，吸收其他算法特点。因此，免疫算法在很大程度上将依赖其他算法。

3.6 蚁群算法与GIS集成效果。本例采用的是自行绘制的贵州省湄潭县的道路网络，空间数据主要有点、线、面三种矢量格式。根据实际需要，分为网络交通路网、优化路径图层，以及需要停靠的商超店面等图层。在处理编辑过的空间数据与组织形式后，得到准确有效的GIS地图，利用GIS中的网络分析功能解决最短路径问题，实现GIS配送路径与蚁群算法的结合，如图1所示。

最短的配送路径应该是茶城大道向东行驶4 600m，至农贸街东侧尽头720m，环西路1 600m，茶乡北路300m，小北街200m，浙江路100m，湄江南路400m，塔坪路1 000m，中山西路 300m，茶海路600m，天文大道1 400m，双拥路600m，茶城大道1 000m，总计13 720m。

某公司原本运用Dijkstra算法作为主要算法，根据上文的数据对比，可以发现，采用与蚁群算法的结合，可以减少600m左右的运输路径。按照该公司一天一次，两车一起运输的常规配送，至少可以节约1 200m运输路径，按照92号汽油6.8元/L、小吨位冷藏车百公里20L油耗来算，该公司仅在湄潭县内运输一年至少可以节约1 200元。如果将该法推广至整个贵州省88个县级行政区划单位，加上配送车辆及配送网络的增加，至少可以节约十几万至几十万元不等，能产生较好的经济效益和社会效益。

4 结论

ArcGIS软件与蚁群算法的结合有利于降低茶叶物流配送成本，并且能够实现可视化配送，大大降低配送难度，提升配送效率。本文采用四种算法各自计算最短路径，并对计算结果、时间进行比较，最终确定蚁群算法与ArcGIS软件的结合，对于茶叶配送效率提升最大，每一趟能够缩短600m左右的路程，对整个贵州省茶叶配送具有一定的参考意义。但是，该算法是否具有普适性，ArcGIS的适用与否，都应因地制宜。因此，企业应该根据自身实际情况，做好前期的可行性调研。

图1 蚁群算法与ArcGIS集成效果图