论文部分内容阅读
摘要：传统的蚁群算法在求解车辆路径问题时迭代速度较慢，且求解精度较低，易陷入局部最优。针对这些问题，利用DB-SCAN聚类算法对车辆路径问题中的各个物料配送点进行聚类划分，并根据聚类划分的情况对蚁群算法中的信息素矩阵合理初始化，实现对蚁群算法的改进，使得改进后的蚁群算法能有更高的求解精度和更快的收敛速度。通过MAT-LAB2019A对实验结果进行仿真测试，并与其他算法橫向对比，可得改进后的蚁群算法在求解辆路径问题时有着更高的求解精度和更快的收敛速度，特别是在配送点分布相对密集和各配送点需求量较小时有着明显的效果。
关键词：蚁群算法;DBSCAN聚类算法;车辆路径问题
中图分类号：TP391 文献标识码：A
文章编号：1009-3044（2020）19-0182-05
开放科学（资源服务）标识码cOSID）：
1 概述
随着互联网科技的不断完善，人们越来越多的选择通过网上购物来满足自己的购买需求。因此合理的物流方案设计，也成为物流配送中的难点与焦点。早在1959年，Dantzig和Rems-er提出了车辆路径问题（Vehicle Routine Problem）[1]，将复杂的物流问题抽象成了图论问题供学者研究，该问题的优化目标为货车在载重有限的情况下如何规划路径使得完成货物配送所经过的路程长度最短。VRP问题属于NP问题，随着所要配送的点数增多，用精确算法求解会导致计算量过大，因此精确算法求解VRP问题并不适用。1986年，Solomon首次提出用启发式算法来求解VRP问题[2]，研究发现，启发式算法能在保证一定的求解精度的情况下有着较小的算法复杂度，因此更适用于VRP问题的求解。1999年，Dorigo和Gamberdella首次提出利用启发式算法中的一种：蚁群算法来求解VRP问题[3-4]，由于蚁群算法本身具有良好的鲁棒性和较高的求解精度，国内外学者开始尝试利用改进的蚁群算法或是相关的混合算法来求解VRP问题，例如，赵群在文献[5]中提出利用蚁群算法和遗传算法的混合算法求解VRP问题;刘春英在文献[6]中提出利用粒子群算法和蚁群算法的混合算法求解VRP问题;石华踽在文献[7]中将车辆转移规则应用到算法中使算法具有更强的应用;郑文艳在文献[8]中更改了信息素更新方式和可行解构造以提高算法的求解精度。
此外Dhawan C.Kumar Nassa V在文献[9]中总结了前人的研究，在蚁群算法解决VRP问题上做了总结，比对了各代改进算法的优缺点，为今后的研究做了导向。M artin等人对DB-SCAN算法进行了简单的阐述[10]，该算法能在具有噪声的空间数据库中发现任意形状的簇，可将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类。作为一种知名的聚类算法，BDSCAN算法广泛地应用于各个领域，例如无线电技术[11]，复杂环境监测[12]屏常数据处理[13]等.在物流管理问题中也有着应用，张洪奉在文献[14]中提出了利用BDSCAN算法的改进算法来设计物流信息管理系统。前人对于蚁群算法求解VRP问题的改进有着明显的效果，但是都未考虑到信息素矩阵的合理初始化对于算法收敛的导向作用。本文对传统的蚁群算法进行改进，通过BDSCAN算法将VRP问题中的各个物料配送点进行划分聚类，并以此作为信息素矩阵初始化的依据，使得初始信息素矩阵对算法的收敛有导向作用，让算法有着更高的求解精度和更快的收敛速度。
2 背景知识和算法描述
2.1 VRP问题
Dantzig和Remser提出了车辆路径问题（Vehicle RoutineProblem，简称VRP），它是运筹学重要的研究问题之一。VRP问题关注一个供货商与k个销售点的路径规划的情况。该问题可以简述为：给定配送中心、一个车辆集合和一个顾客集合，车辆运载能力和顾客需求量已知，每辆车都从配送中心出发，完成运送任务后重新返回配送中心，目标是在特定的约束条件下满足客户需求并且使得成本最小化，配送订单最大化，满载率最大化。图形表示如下：
2.2 蚁群算法
蚁群算法（Ant Colony Algorithm，AC）由Dorigo和Gam-berdella首次提出，该算法能够模拟自然界中蚂蚁的觅食行为。昆虫学家们发现蚂蚁在行走过程中能够释放用来标识自己行走路径的称为“信息素”的物质，路径长远可以通过信息素浓度大小表示，信息素浓度越高，对应的路径越短。该算法的其基本思路为：将蚂蚁的行走路径作为待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁所释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐提高，选择该路径的蚂蚁也随之越来越多。最终，整个蚂蚁群体通过信息素交换路径信息在正反馈的作用下集中到最佳路径上，该路径对应的就是待优化问题的最优解。
蚁群算法流程如下：
（1）初始化参数
对相关参数进行初始化，如蚂蚁数量m、信息素重要程度因子a、启发函数重要程度因子6、信息素挥发因子a、路径信息素常量Q、最大迭代次数iter max、迭代次数初值iter=1。
（2）构建解空间
将各个蚂蚁放于不同出发点，对每个蚂蚁根据概率公式计算其下一个访问城市，直到遍历完所有城市。
（3）更新信息素
计算各个蚂蚁经过的路径长度，记录当前迭代次数中的最优解（最短路径），同时进行信息素浓度的更新。
（4）判断是否终止
如果iter
关键词：蚁群算法;DBSCAN聚类算法;车辆路径问题
中图分类号：TP391 文献标识码：A
文章编号：1009-3044（2020）19-0182-05
开放科学（资源服务）标识码cOSID）：
1 概述
随着互联网科技的不断完善，人们越来越多的选择通过网上购物来满足自己的购买需求。因此合理的物流方案设计，也成为物流配送中的难点与焦点。早在1959年，Dantzig和Rems-er提出了车辆路径问题（Vehicle Routine Problem）[1]，将复杂的物流问题抽象成了图论问题供学者研究，该问题的优化目标为货车在载重有限的情况下如何规划路径使得完成货物配送所经过的路程长度最短。VRP问题属于NP问题，随着所要配送的点数增多，用精确算法求解会导致计算量过大，因此精确算法求解VRP问题并不适用。1986年，Solomon首次提出用启发式算法来求解VRP问题[2]，研究发现，启发式算法能在保证一定的求解精度的情况下有着较小的算法复杂度，因此更适用于VRP问题的求解。1999年，Dorigo和Gamberdella首次提出利用启发式算法中的一种：蚁群算法来求解VRP问题[3-4]，由于蚁群算法本身具有良好的鲁棒性和较高的求解精度，国内外学者开始尝试利用改进的蚁群算法或是相关的混合算法来求解VRP问题，例如，赵群在文献[5]中提出利用蚁群算法和遗传算法的混合算法求解VRP问题;刘春英在文献[6]中提出利用粒子群算法和蚁群算法的混合算法求解VRP问题;石华踽在文献[7]中将车辆转移规则应用到算法中使算法具有更强的应用;郑文艳在文献[8]中更改了信息素更新方式和可行解构造以提高算法的求解精度。
此外Dhawan C.Kumar Nassa V在文献[9]中总结了前人的研究，在蚁群算法解决VRP问题上做了总结，比对了各代改进算法的优缺点，为今后的研究做了导向。M artin等人对DB-SCAN算法进行了简单的阐述[10]，该算法能在具有噪声的空间数据库中发现任意形状的簇，可将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类。作为一种知名的聚类算法，BDSCAN算法广泛地应用于各个领域，例如无线电技术[11]，复杂环境监测[12]屏常数据处理[13]等.在物流管理问题中也有着应用，张洪奉在文献[14]中提出了利用BDSCAN算法的改进算法来设计物流信息管理系统。前人对于蚁群算法求解VRP问题的改进有着明显的效果，但是都未考虑到信息素矩阵的合理初始化对于算法收敛的导向作用。本文对传统的蚁群算法进行改进，通过BDSCAN算法将VRP问题中的各个物料配送点进行划分聚类，并以此作为信息素矩阵初始化的依据，使得初始信息素矩阵对算法的收敛有导向作用，让算法有着更高的求解精度和更快的收敛速度。
2 背景知识和算法描述
2.1 VRP问题
Dantzig和Remser提出了车辆路径问题（Vehicle RoutineProblem，简称VRP），它是运筹学重要的研究问题之一。VRP问题关注一个供货商与k个销售点的路径规划的情况。该问题可以简述为：给定配送中心、一个车辆集合和一个顾客集合，车辆运载能力和顾客需求量已知，每辆车都从配送中心出发，完成运送任务后重新返回配送中心，目标是在特定的约束条件下满足客户需求并且使得成本最小化，配送订单最大化，满载率最大化。图形表示如下：
2.2 蚁群算法
蚁群算法（Ant Colony Algorithm，AC）由Dorigo和Gam-berdella首次提出，该算法能够模拟自然界中蚂蚁的觅食行为。昆虫学家们发现蚂蚁在行走过程中能够释放用来标识自己行走路径的称为“信息素”的物质，路径长远可以通过信息素浓度大小表示，信息素浓度越高，对应的路径越短。该算法的其基本思路为：将蚂蚁的行走路径作为待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁所释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐提高，选择该路径的蚂蚁也随之越来越多。最终，整个蚂蚁群体通过信息素交换路径信息在正反馈的作用下集中到最佳路径上，该路径对应的就是待优化问题的最优解。
蚁群算法流程如下：
（1）初始化参数
对相关参数进行初始化，如蚂蚁数量m、信息素重要程度因子a、启发函数重要程度因子6、信息素挥发因子a、路径信息素常量Q、最大迭代次数iter max、迭代次数初值iter=1。
（2）构建解空间
将各个蚂蚁放于不同出发点，对每个蚂蚁根据概率公式计算其下一个访问城市，直到遍历完所有城市。
（3）更新信息素
计算各个蚂蚁经过的路径长度，记录当前迭代次数中的最优解（最短路径），同时进行信息素浓度的更新。
（4）判断是否终止
如果iter