论文部分内容阅读
随着电子商务的发展,其便利快捷的购物特性,让越来越多的人们选择网上购物这种方式,电商在人们生活中占据越来越重要的位置。由于其远距离特性,因此需要物流行业在其中起着配送的作用。由于在物流业务中,快递普遍成本过高并且效率低下,因此提高运送效率和降低快递成本对于降低网购成本具有很大的现实意义,车辆路径规划问题(Vehicle Routing Problem,VRP)是公认的解决物流配送问题求解最低货物成本的理论模型。货物配送服务的关键是服务速度和质量,在一个给定的期间内,一组客户和一组车辆,这些车辆被分配到一个或更多集运点。通过对一个车队来进行约束操作并使用适当的公路网络,VRP问题的解被称为确定的一组路线,每个车辆的起点和终点都在自己的集运点。如此,所有的客户都被满足,所有的操作约束都被满足,并且整体的运输费用最低。在过去的数十年中对快递优化方案正在逐渐增加,大量现实实例证实,使用大量的计算机程序应用于规划分配计划中,可以在整体运输成本中产生大量的节约(通常较不做规划节约5%-20%)。很容易看出来,这些节约在整体行业成本中是很重大的,事实上,运输过程包括生产和分配系统的全过程。并且运输成本也是最终成本的相关因素。车辆路径规划问题的研究可以减少很大一部分物流开销。到目前为止,出现了很多求解车辆路径问题的算法,有精确算法(accurate algorithm)和启发式算法(heuristicsalgorithms)。其中,精确算法用来求解问题最优解的方式是严格的数学方法,启发式算法则利用对状态空间的位置评价来找到较好的位置,再基于这个位置进行搜索,直到找到目标为止。随着问题规模不断地扩大,精确算法的计算量越来越大,还不能直接用来解决实际问题。启发式算法则可以根据不同的问题要求来求解问题。基于VRP问题的本质,不太可能使用精确的方法求解VRP的大规模的实例。因此,大部分方法都依赖于启发式方法来获取近似解。许多方法已经被用到了这个领域中,其中有选择使用标准优化技术的算法,例如,蚁群算法、遗传算法、模拟退火和约束编程。我们在这里关注于元启发式算法,主要是蚁群算法。蚁群算法是启发式算法中主流的一种算法。由Marco Dorigo于1992年受到蚂蚁觅食行为启发而提出,将其应用到了组合优化问题中。通过实验结果表明,蚁群算法可以找到相对较好的解,而且具有很强的鲁棒性。在本文中,我们基于已有的研究成果,将自适应思想与最大最小蚂蚁系统相结合。在每次搜索循环的过程中,我们可以自适应的决定精英蚂蚁的数量。只要在搜索的过程中,达到了一定的要求,我们就可以把它当作精英蚂蚁,将它的信息素保留下去。在更新一条路径上的信息素时,考虑两点之间的距离,而不是均匀的将信息素释放在路径在。提出奖励惩罚制度,将蚂蚁当前走过的路径与上一次的最优路径进行比较,对蚂蚁进行等级划分,将排名靠前的蚂蚁所在的路径上的信息素予以增强,排名靠后的蚂蚁所在的路径上的信息素予以减少。通常,可以寻找到较优解。