论文部分内容阅读
旅行商问题(Traveling Salesman Problem,TSP)是一个经典的NP-hard组合优化问题,多旅行商问题(Multiple Traveling Salesman Problem,MTSP)作为其扩展模型,具有更强的实际意义。而在理想情况下的旅行商问题及多旅行商问题几乎是不存在的,本文介绍了两种更符合实际意义的限容量多旅行商问题(Multiple Traveling Salesman Problem With Limited Capacity,LCMTSP)和不确定性多旅行商问题(Uncertain Multiple Traveling Salesman Problem,UMTSP)模型,并设计了遗传算法(Genetic Algorithm,GA)对这两种模型进行求解。本文首先对LCMTSP问题模型进行了研究,将容量限制条件加入到多旅行商问题模型中,以控制每个旅行商访问城市个数范围。鉴于问题的复杂性,本文在传统GA的种群初始化过程中,采用完全随机法和适用于多旅行商问题模型的次优选择法,并在交叉算子中加入最小路径交叉等规则,且引入DI算子和3-opt算子。实验结果证明了所设计IGA求解LCMTSP问题时的可行性和有效性以及较高的计算效率。考虑到理想化的多旅行商问题在现实环境中的不可靠性,本文将现实情况下的不确定性因素归纳为一种路况系数,从而构建了不确定性多旅行商问题(UMTSP)模型。针对该问题,设计了遗传算法对其进行了求解,并比较基本MTSP问题与UMTSP问题的实验结果。实验结果证明了UMTSP问题模型的实际意义以及所提遗传算法的可行性与实用性。