论文部分内容阅读
物流有企业“第三利润源泉”之称。在现代商业发展环境中,如何优化物流系统,降低物流成本已经成为企业要考虑的重要问题。车辆路径问题(Vehicle routing problem, VRP)是物流配送中的核心问题,合理安排配送车辆的路径对企业降低运营成本,提高服务质量有着重要意义。车辆路径问题是典型的NP难解问题,大多用启发式算法求解。和声搜索算法是一种新颖的启发式算法,最近几年得到了迅速发展,但是新提出的新和声算法在求解车辆路径问题方面研究并不充分。本文研究了基于和声搜索算法求解车辆路径问题的方法,并且提出了有效的改进方法。主要研究内容包括:(1)研究了和声算法、多种改进的和声搜索算法,在原算法的基础上,加入了2-opt算子,应用到VRP问题求解中,实验表明和声搜索算法能求得较高质量的可行解。(2)对带有容量限制的车辆路径问题(CVRP),提出了一种改进的全局最优和声搜索算法。该算法采用自然数编码,在新和声的生成过程中,增加了和声约束,避免了不可行解的生成,并利用2-opt算子对新的和声进行了优化,从而压缩了搜索空间,提高了算法效率。实验表明改进后的算法提高了搜索效率。(3)针对和声搜索算法容易陷入局部最优以及自然数编码不便于结合其他算法等问题,提出了萤火虫和声搜索算法(FGHS)来求解CVRP。算法采用了实数编码,在新解生成过程中,引入了萤火虫算法的更新公式,利用萤火虫的仿生特性改进和声搜索算法的音调调节,使算法不易陷入局部最优;提出了一种和声库重置方法,在算法陷入局部最优时,利用混沌扰动系统增加和声记忆库中解的多样性来帮助算法跳出局部最优,同时用局部搜索来增强寻优能力。