高德地图及改进ACA在车辆路径寻优中的应用*

刘庆华 汪 晶

（江苏科技大学计算机学院 镇江 212000）

1 引言

随着经济和科学技术的快速发展，现实生活中车辆的普及率越来越高，汽车私人拥有量也急剧增加。而这些都使得出行者迫切需要正确的出行路径，因此路线规划问题成为了广大国内外学者研究的一项重要课题［1～3］。近些年来，国内外许多学者对路径规划问题进行了大量的研究，这些研究主要集中在理论及算法领域方面，其中旅游业和物流业等行业中合理的路线规划能够为商家节约成本，创造更高的价值［4～6］。

在国外汽车行业相对于国内较为发达，所以早在1959年Dantzig和 Ramser等［7］首次提出了物流配送路径优化问题，之后便引起了计算机应用等诸多领域的研究者们的高度重视，并很快成为了组合优化领域和运筹学的研究热点及前沿问题。从而使得各个领域学者们对上述问题进行了大量的资料查找、理论研究和实验分析，并获得了较大的进步和成果。20世纪末Dorigo M等［8］在他们的论文中提出了蚁群系统（ACS），一种应用于旅行商问题（TSP）的分布式算法，也就是通过ACS算法研究路径规划问题，在文中他们通过ACS算法和模拟退火算法等进行比较结果表明ACS算法理论上更好地解决了TSP问题。Juyoung等［9］在他们的研究中针对大型货柜在建筑工地及购物区堆积大量的垃圾，提出了一种滚动式废物收集车辆路径优化问题。Mahmoudi M等［10］提出了基于时空交通网络中车辆承载状态集成的VRPPDTW时间离散多商品网络流模型，通过时间窗口（VRPPDTW）解决了一类复杂的车辆路线问题。在国内，张维泽等［11］建立了带约束条件的物流配送问题的数学模型，运用蚁群算法解决物流配送路径优化问题，同时将遗传算法的复制、交叉和变异等遗传算子引入蚁群算法，以提高算法的收敛速度和全局搜索能力。程碧荣［12］等针对救援关键期内应急物资可能供应不足的特点，考虑适当的优化目标，建立了随机需求环境下应急物流车辆路径问题的优化模型，并基于遗传算法设计了模型的求解方法。

对于车辆路径优化问题，绝大多数研究者们在众多的仿真实验案例中都是采用道路节点之间的线性距离之和最短作为最优解，但是在实际的道路节点之间会存在诸多因素导致与节点之间的线性距离相差甚远。由此本文根据镇江市的实际物流配送路径合理规划为出发点，提出了一种首先通过高德地图提供的对应API接口来获取各个道路节点之间的实际道路距离，然后交给改进的蚁群算法进行优化得到最优解，从而有效地将理论与实际物流配送路径相结合，具有高度的可行性和实用性。

2 高德地图API简介

高德地图API是一组基于云的地图服务接口，包括互联网地图API和手机地图API。高德地图API通过互联网、移动互联网向桌面和移动终端用户提供丰富的地图服务功能，如地图显示、标注、位置检索、驾车出行方案检索、公交查询、地址解析等。通过高德地图API，开发者可以轻松地在自己的应用中定制强大、快速、轻便的地图功能。基于高德地图的云服务接口，开发者无需考虑系统维护，无需购买地图数据，便可以结合业务需求快速构建地图应用，可大大降低地图服务的使用成本［13］。其中高德Web服务API向开发者提供HTTP接口，开发者可通过这些接口使用各类型的地理数据服务，返回结果支持JSON和XML格式。本文中提到的道路节点之间的实际距离就是通过高德Web服务API中的对应请求接口获取的。

3 物流配送的数学模型建立及蚁群算法

3.1 物流配送的数学模型

3.1.1 物流配送过程介绍

本文物流配送的过程可以描述为从物流中心通过一定数量的车辆分别向若干个客户点派送货物，车辆配送完货物后则返回物流中心。每辆车的载货量有限，为了节约成本以及提高派送货物的效率，则必须合理的规划车辆行驶路线。

3.1.2 数学模型建立

建立数学模型需要引入以下符号定义：物流汽车数量K（1，2…K），汽车的载重量Qk；配送的客户点个数为L，客户点集合为R=（R=｛i｝|i=1，2…L），客户点的需求量为qi；dij为客户i到客户j的距离，其中i、j=0，1，2…L，当i=j=0时表示配送中心；nk为车辆k（k=1，2…K）配送的客户总数，当 nk=0时，表示车辆k没有参与配送；Rk为车辆k配送的客户点集合，当 nk=0时，Rk=Φ ，当 nk≠0时，Rk=其中表示在车辆k配送客户点集合中第i个配送的客户。根据实际情况物流配送路线优化需要满足如下约束条件。

1）某一个客户点的货物需求只能由一辆车辆来配送；

2）任意一条路径上的客户需求总量之和不能超过汽车的载重量Qk；

3）所有客户点都必须完成配送

因此，本文的物流配送问题需要达到的最优路径理论目标值为

3.2 基本蚁群算法

3.2.1 蚁群算法的基本原理

蚁群算法是受自然界蚂蚁觅食行为的启发而产生的一种自然模拟进化算法。20世纪90年代，M.Dorigo在他的博士论文中阐述了蚁群算法，并对其数学模型做了分析解释。

蚂蚁从蚁穴到目的地觅食的大致过程可以描述如下：起初蚂蚁选择路径是随机的，后来路径的选择会随着觅食的过程而适应性的搜索新的路径，原因在于蚂蚁会在它们经过的地方释放信息素这一化学物质，而路径上的信息素浓度与路径长度有关，经过路径越长，则路径上的信息素浓度相对越低，同时路径上的信息素也会随着时间的流逝按照一定的比例逐渐减少，因此对于较短的路径上蚂蚁释放的信息浓度会更高，如此反复形成正反馈效应，直到最后所有的蚂蚁都会走信息素浓度最高的那条路径，也就是最短路径。关于蚂蚁觅食过程的简要流程图如图1所示。其中图1中（a）表示所有蚁群都在起点处，路径上尚未有信息素，（b）表示蚁群开始分别以相等的概率向不同的方向觅食，（c）表示走较短路径的蚁群首先到达觅食终点，（d）表示蚂蚁返回起点过程中由于较短路径上信息素浓度较高，所以蚂蚁选择较短路径的概率要大于较长路径的概率，最终根据正反馈效应蚂蚁都会集中在较短路径上［14～15］。

图1 蚁群觅食行为图

现实生活中的人工蚁群算法原理就是根据蚁群觅食的这种正反馈过程来实现的，但是人工蚁群算法在自然界的蚁群算法上做了改进，原始自然界中的蚁群是没有记忆功能的，而人工蚁群算法具有一定的记忆功能，它会记住已经访问过的节点。另外就是人工蚁群算法在选择下一条路径的时候并不是完全毫无无目的性的去选择，而是按照一定的算法规律去寻找最短路径。

3.2.2 蚁群算法的基本求解模型

当蚂蚁在客户点i时，它在t时刻由客户点i向客户点j转移的概率为

在式（7）中ηij，τij分别表示某时刻客户点i到客户点j的可见度以及i到j路径上的信息素浓度，且ηij=1/dij；α为信息启发因子，β为期望启发因子，大小分别对应蚂蚁对信息素量和路线距离长短的敏感程度；由于每只蚂蚁每次巡回只能访问客户节点一次，所以用tabu（k）表示第k只蚂蚁已经访问过的客户点，allowed（k）=R-tabu（k）表示第k只蚂蚁尚未访问的客户点。

当所有的蚂蚁完成一次配送循环后，需要根据各个蚂蚁遍历的好坏程度，更新相关路径上的信息素，因为信息素是影响文中算法收敛性的重要因素，相关路径上信息素的更新规则如下：

式（8）、（9）中ρ表示信息素挥发系数，0≤ρ＜1，1-ρ表示信息素残留系数和分别表示本次循环过程中路径（i，j）上的信息素增量和第k只蚂蚁留在该路径上的信息素数量；m表示该循环过程中蚂蚁数量；τij(t+n)和τij(t)分别表示对应时刻在路径上的信息素数量。最后在上述基础上得到蚁群算法的基本求解模型：

式（10）中Q为常数，表示信息素强度，它在一定程度上会影响算法的收敛速度，Lk为第k只蚂蚁在本次循环中走过的路径总长度［16］。

3.3 蚁群算法的改进

3.3.1 客户点选择策略的改进

图2 蚂蚁简略寻迹图

如图2所示，假设蚂蚁在D点，ABC为已经去过的客户点，EFG为没去过的点，现在蚂蚁要在EFG中选择一个点作为下一步要到达的点。且D到E，F，G点的信息素/距离如图2所示，那么理论上在α=1，β=2根据式（7）算得D到E，F，G的概率为24%，60%，16%，这样选择会导致一个问题，每只蚂蚁到了D点都会选择F点作为下一个访问点，同样在其他的点上也会有这种情况发生，就是每只蚂蚁选择的下一个点都是同一个点，这会导致所有蚂蚁找到的路径都是相同的，会使蚂蚁失去探索新路径的机会，算法陷入停滞。因此文中采用轮盘选择法，在［0，1］之间取一个随机数R。然后用R减D到E的概率，如果减去后的结果小于等于0就选E作为下一个点，如果减去后还大于0，就继续再减去D到F的概率，直到减去后的结果小于等于0。然后用最后减去时的那个概率值对应的点作为下一个点。使用轮盘选择法可以使蚂蚁往概率值大的地方走的可能性大，但也有一定的可能往概率小的地方走，这样可以使蚂蚁探索新的路径，避免算法停滞或者进入局部最优解。

3.3.2 信息素挥发系数ρ的取值改进

信息素挥发系数ρ是一个常量，它的取值直接影响算法的求解结果，若ρ取值过小，则影响算法的收敛速度，取值过大，则会使没有被搜索过的路径被选择的概率减小，影响算法的全局搜索。所以在求解过程中对ρ的取值进行调整，在算法初期为了尽快地找到较优解ρ的取值应该比较大；到了后期当算法停滞不前就可以将ρ的取值减小，减小信息素对蚁群的影响，取得更优的解。ρ的调整公式如下：

式（11）中r为循环次数；rmax为一常量；μ∈（0，1），它是一个常量，控制ρ的衰减速度；ρmin为ρ的最小值，确保ρ不会因为过小而影响收敛速度。这里当r达到设定的rmax时就减小ρ，然后对r重新计数，反复循环，直到ρ达到最小值ρmin为止。

3.3.3 客户节点间计算距离改进

本文算法中求解最优路径结果时去掉基本的蚁群算法通过传统方法来计算任意两个节点的距离，而是通过程序调用高德地图web服务API接口返回任意两个节点间的实际导航距离来求得最优解。通过该改进，可以提高算法的实用性和运行速度。

该接口的服务地址为https：//restapi.amap.com/v3/distance？parameters，接口的请求参数包括key（请求服务权限），origins（出发点），destination（目的地），type（路径计算的方式和方法），output（返回数据格式类型xml或json，本文中取json），callback（回调函数），上述请求参数tpye本文中直接取缺省值，表示驾车导航距离。返回结果参数包括status（0：表示请求失败，1：表示请求成功），info（返回状态说明），result（距离等信息列表）。这里得到的任意两个客户节点之间的距离是实际道路之间的有向距离，而不是传统算法所采取的根据勾股定理来计算的直线距离，而且通过接口在不同时间段取得的值不同，因为服务接口中考虑了实时路况，躲避了交通拥堵等。

3.4 物流配送的算法流程图

物流配送的算法流程简图如图3所示。

图3 算法流程简图

4 实验与结果分析

4.1 实验问题描述

本文物流配送以镇江市实际道路点为基础，分别向本市十个不同的客户点进行物流配送，寻求最优的配送路径。这里以镇江站位置为物流配送中心，以十里长山、镇江南站、江苏大学、江科大东校区、大港中学、明都大饭店、金山公园、中医院、江大附属医院、八佰伴为客户点位置。物流配送中心车辆充足，且每辆车载重量为8吨，10个客户点的需求量qi如表1所示，现在要求合理安排车辆及规划路线，使配送过程的总路程最短。

表1 客户点需求量（单位：吨）

根据表1可知客户总需求量为29.4吨，而每辆车的载重量为8吨，初始估计配送车辆为4辆。算法初始化参数设置为信息启发因子α=1，期望启发因子β=2，信息素挥发系数初始值ρ=0.95，后期根据实际情况在程序中对ρ的取值进行调整，迭代次数为200。

4.2 实验结果分析

通过高德地图服务API得到的物流配送中心与各个客户点以及客户点和客户点之间的实际道路距离如表2所示。其中（0，0）表示物流中心，1-10表示十个客户节点，由表1中可知dij和dji的距离是不相等的，这是因为表2中所有节点之间的距离都是根据API接口取得的实时驾车导航距离，而不是传统的道路节点之间的直线距离。另外程序在取得道路节点间的实际距离时可以根据接口传参考虑诸多因素，如实时路况，是否躲避交通拥堵路段，还是不考虑路况直接走最短路线路段，以及不走高速且避开收费等，所以通过高德地图API取得的实际道路距离来通过蚁群算法求得最优解更具有实际意义。

根据上述初始化条件，程序运行结果可以得到表3所示的物流配送路径的优化结果对比表，表中总结出了具有代表性的10次配送路径，以及对应的根据传统方式得到的节点间直线行驶路程和根据实际道路行驶得到的行驶路程。由表3可知节点间最小直线行驶路程的最优解为62.598km，但是与其对应的节点间的实际道路行驶路程却不是最小的，而是表中第5行所对应的路径得出的实际道路行驶路程89.378km才是最小值。这充分说明了在实际应用中，最优路径求解根据节点间的直线距离来计算最小路程是难以解决实际问题的，应该根据本文中提出的由实际道路节点距离来计算最优路径，这样才能得到实际的最优解。这里由于文中提供的客户点较少且距离比较近，所以不同路径所对应实际道路行驶路程相差不是太大，但是在客户点较多或客户点之间相距比较远时，这种差距就会十分明显，且更能体现由实际道路距离作为最优路径求解结果的正确性与优越性。

在算法的收敛性方面，文中的最优解在迭代40次以上基本上已经趋于稳定，迭代过程中平均路径长度和最短路径长度如图4所示。

图4 路径优化结果收敛图

表2 各节点之间的实际道路距离（单位：km）

表3 路径优化求解结果对比表

最后，在实验中根据传统蚁群算法和文中改进的蚁群算法同样在迭代200次的基础上以及同样的约束条件下，取得的直线最短路程，平均路程和最大路程做了一个简单对比如表4所示。根据结果可知文中改进的算法相比于未改进之前增强了算法的正反馈机制，很好地避免了算法停滞现象，对路径规划问题具有较好的适应性和实用性。

表4 算法改进前后数据对比表

5 结语

本文以物流配送路径优化问题出发，以镇江市实际道路节点为基础，通过改进的蚁群算法来求得配送过程中所走的实际道路节点的最短路程。在前人研究的基础上，文中求得的最短路径并非通过节点间直线行驶最短距离来求得，而是通过高德API服务接口获取各道路节点之间的实时导航距离并由改进的蚁群算法求得最优解。实验结果证明，传统求解方式难以运用于实际，而本文提出的求解方式在实际应用中具有更好应用价值，实用性更高。