论文部分内容阅读
旅行商问题(Traveling Salesman Problem,TSP)是一个经典的组合优化问题,现实生活中的许多问题都可以抽象成TSP进行求解。由于TSP是NP-hard问题,目前还只能求解小规模的TSP,对于大规模的TSP求解,学者们一直在研究能够快速收敛最优解的近似算法。另外,依据该问题在不同领域的应用,由TSP又衍生出了许多该问题的扩展问题,在本文中主要讨论两类TSP扩展问题:多人旅行商问题(Multiple Traveling Salesman Problem,MTSP)和动态旅行商问题(Dynamic traveling salesman problem,DTSP)。针对这两类TSP的扩展问题,本文采用改进的遗传算法及其融合算法对两类TSP延伸问题进行求解,主要的研究工作和创新如下:(1)对经典TSP延伸研究了MTSP,提出了一种二阶段启发式算法(Two Phase Heuristic Algorithm,TPHA)进行求解。阶段一通过加入容量限制的改进k-means算法根据节点位置和容量限制约束将节点分区聚类形成m个节点集合,阶段二采用遗传算法对m个节点集合进行路线规划。特别对遗传算法的选择操作采用保留最佳结合轮盘赌策略,在保留最优个体的同时,保证了适应度较大的个体进入下一代。通过Matlab实验验证,实验结果表明本文所提出的TPHA在求解均衡节点的MTSP和系统开销方面比基于遗传算法的路线规划具有更优秀的性能表现。(2)对经典TSP扩展研究了DTSP,分析了TSP中由于城市数量的改变以及城市之间费用值发生改变所引起的DTSP。指出了DTSP的数学模型并依据TSPLIB建立仿真模型再现DTSP中各种复杂情况。提出了基于二边逐次修正法的遗传算法(Genetic Algorithm Based on Two Side Correction Method,TSC-GA),该算法融合了GA优秀的全局搜索能力以及二边逐次修正法(Two Side Correction Method)快速的收敛能力,使得该算法能够在较短的时间内求出满意解。通过在仿真平台上实现该算法,验证了算法解的质量以及求解速度均有很大的提升。(3)基于百度地图构建原型系统,将MTSP运用于旅游路线规划,系统通过GPS模块定位游客所在的位置,然后通过路线规划模块将游客所选择的景点先进行分区聚类在进行路径规划,为游客几天的行程安排一套游玩计划。将DTSP运用于超市配送的场景中,超市配送根据车辆到达某个超市配送点时,根据实时的交通信息,调整路线,节约配送时间。