基于PSO-GA混合算法的时间优化的旅行商问题的研究

摘要

为了给游客提供更好的路径推送服务，针对经典的旅行商问题(TSP，TravelingSalesman Problem)进行了延伸研究，提出了一种时间优化的旅行商问题(TOTSP，Time Optimal TSP)，旨在寻找一条旅行时间最短的游览路径。该路径推送给游客从而节省游客在景区内进行游玩的旅行时间。通过混合粒子群遗传算法(PSO-GA，Particle Swarm Optimization-Genetic Algorithm)对提出的问题进行仿真实验，并将旅行时间作为PSO-GA的目标函数，其中的旅行时间包括三个部分:游客从一个景点走向另一个景点所行走的总时间、游客在每个景点排队等待的总时间以及游客在每个点进行游览所需要的总时间。本研究将PSO-GA求出的最短旅行时间及所需的CPU执行时间同遗传算法GA以及蚁群算法(ACO，Ant ColonyOptimization)求出的结果进行了对比。仿真实验表明PSO-GA在解决提出的TOTSP问题上具有较好的性能。　　本文研究的是时间优化的旅行商问题，文中将对TOTSP问题求解得到的路径称为时间优化的路径(TOP，Time Optimal Path)，对TSP问题求解得到的路径称为长度优化的路径(LOP，Length Optimal Path)。本论文的主要研究工作可以总结为以下几点:　　(1)提出TSP问题的一种扩展问题:TOTSP问题，并对其概念和数学模型进行介绍，将游客的行走、排队和游玩等因素融入到该模型中;　　(2)利用PSO-GA混合算法求解TOTSP问题，介绍了该混合算法的在求解LOP、TOP过程中的相关原理，并突出TOTSP问题的旅行时间函数的求解方法和含义;　　(3)对不同游客密度下的时间优化的旅行商问题用PSO-GA混合算法进行求解，并同GA和ACO进行对比，可以得出TOP游览路线在不同的游客密度下较传统的TSP问题的LOP游览路线所需的旅行时间更短，能够为游客节省旅游时间。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景

1．1．1 研究概述

1．1．2 中国旅游业发展现状

1．1．3 研究的理论基础

1．2 传统优化算法和群智能优化算法的比较

1．3 研究的目的和方法

1．4 本文研究内容

第二章 TOTSP问题

2．1 TSP问题的概念

2．1．1 TSP问题的定义

2．1．2 TSP问题的数学模型

2．2 TSP问题的算法

2．2．1 TSP问题的精确算法

2．2．2 TSP问题的近似算法

2．3 TSP问题的扩展

2．4 最短路径问题的优化算法

2．5 TOTSP问题

2．5．1 TOTSP问题的概念

2．5．2 TOTSP问题的旅行时间函数

2．6 本章小结

第三章 解决TOTSP问题的PS0-GA混合算法

3．1 遗传算法

3．1．1 进化计算的基本概念

3．1．2 进化计算的算法

3．1．3 遗传算法概述

3．1．4 个体编码

3．1．5 适应度函数求解

3．1．6 遗传算子

3．1．7 遗传算法的收敛性

3．1．8 遗传算法的改进算法

3．2 粒子群算法

3．2．1 粒子群算法概述

3．2．2 基本粒子群算法

3．2．3 标准粒子群算法

3．2．4 粒子群算法的收敛性

3．2．5 动态环境下的PSO算法

3．2．6 改进的粒子群算法

3．3 TOTSP问题的PSO-GA算法

3．3．1 PSO-GA混合算法的应用和研究现状

3．3．2 PS0-GA混合算法求解TOTSP问题的流程

3．4 本章小结

第四章 仿真实验及分析

4．1 仿真实验模型

4．2 参数设置

4．3 给定游客密度时的仿真结果及数据分析

4．3．1 PSO-GA求解TOP游览路径的收敛过程及对比实验

4．3．2 PSO-GA求出的LOP、TOP游览路径及对比实验

4．3．3 PSO-GA的LOP、TOP的旅行时间及对比实验

4．3．4 PSO-GA、GA和ACO的LOP、TOP的CPU执行时间的对比

4．4 游客密度变化对TOTSP问题求解的影响

4．5 本章小结

第五章 结论与展望

5．1 论文工作总结

5．2 论文工作展望

参考文献

攻读硕士学位期间的学术活动及成果情况