改进的蚁群算法解决车辆路径问题及其web gis实现

来源：互联网   发布日期：2011-09-29 16:46:38   浏览：102752次  

随着问题规模的扩大，组合优化问题常常会呈现组合爆炸特征，此类问题无法使用常规方法来求解，属于np-hard问题,车辆路径问题就是典型的组合优化问题。蚁群算法(aco)是受自然界中蚂蚁搜索食物行为启发而提出的一种智能优化算法。研究发现，蚁群算法可以较好地求解vrp(vehicle routing problem，车辆路径优化)等组合优化问题。蚁群算法发现较好解的能力很强，具有分布式计算、鲁棒性强、易于与其他方法结合等优点，具有十分广阔的应用前景。然而，蚁群算法存在求解速度慢，在规模扩大后带来收敛慢等问题。对车辆路径问题解决上，现有的蚁群算法存在难以回归原点等问题。此外在如何将蚁群算法建模到物流软件系统中，使之成为一种web应用而投入到实际应用也成为当前急需解决的问题。这些问题也是我们面临的巨大挑战。 本文主要依据蚁群算法解决配送路线的优化问题，文章从以下几个方面展开：首先充分概括了当前的蚁群算法在车辆路径问题上的研究。详细分析了基本蚁群算法的原理，然后详细阐述了vrp问题并引用了其数学模型，并介绍了蚁群算法解决vrp问题的方法以及现状面临的挑战。在创新方面，本文提出节点之间的路线实际上存在大量冗余信息，这是因为节点间的距离太大或太小时可以简化蚁群算法输入，具体做法是通过对距离较长的路线进行屏蔽、对距离较短的路线进行合并处理，这样的产生聚合组来优化网络，以便于蚁群算法的快速收敛，聚合后的组在算法完毕后需进行类tsp处理使得最终形成一条完整路径。然后，针对车辆路径问题，传统的蚁群算法公式中没有涉及到回配送中心问题，随后学者所改进的算法公式虽然可以使车辆在适当的时刻回到配送中心，但代价是破坏了经典蚁群算法公式，而使得算法中参数大小无法确定，对此情况，本文改进了算法公式，提出了一个新的概率，这个概率的由车载重和车与配送中心的距离决定，车辆根据此概率来决定是否返回配送中心，通过对公式的证明和最终实验我们确定新的概率公式的正确性。最后，文章通过使用web gis（地理信息系统），将算法融合到可视化地图中，通过web服务发布出去，方便了客户的浏览与使用。再将带有蚁群算法的地理信息系统作为智能物流配送管理系统的一个模块，使得其支持多个用户的进行计划、计算、查看、修改配送路线等操作。 本文第一章是绪论部分，概述了研究背景与现状以及本文结构。第二章首先讲述了一些基本理论概念，包括介绍了蚁群算法的基本原理以及车辆路径问题的定义和数学建模。然后综述了利用蚁群算法解决车辆路径问题的一些思路，并总结了已有的改进蚁群算法对车辆路径问题的解决。接着本文介绍了地理信息系统的一些概念。第三章开始是本文的核心部分，提出了一系列改进方法，如何分组，分组后如何计算等等，提出了一套切实可行的方案，并提出了对算法的改进。第四章是智能物流配送管理系统的实现部分，通过jsp / servlet、gis等技术发布服务，提高了用户的可视化与可操作性。第五部分是总结与展望，提出了未来的一些研究方向。

赞助本站