基于改进遗传算法的限容量多旅行商问题研究

摘要

旅行商问题是一个经典的NP-hard组合优化问题,多旅行商问题作为其扩展模型,具有更强的实际意义.本文提出一种更符合实际意义的限容量多旅行商问题模型,并对传统遗传算法稍加改进后用于该模型的求解.在遗传算法种群初始化过程中采用改进的最近邻域法与完全随机法,在交叉算子中加入最小路径交叉规则(MPC),在局部搜索过程中加入单点插入算子(SΙ)、两点插入算子(DΙ)及OPT算子.实验结果证明了该遗传算子的可行性和有效性以及较高的计算效率,并且运用该算子解决LCMTSP模型的解的质量比MTSP更优.