基于SFLA-GA混合算法求解时间最优的旅行商问题

张勇; 高鑫鑫; 王昱洁

doi:10.11999/JEIT170484

基于SFLA-GA混合算法求解时间最优的旅行商问题

doi: 10.11999/JEIT170484

基金项目:

国家科技支撑计划项目(2013BAH52F01)

计量
- 文章访问数: 1274
- HTML全文浏览量: 152
- PDF下载量: 183
- 被引次数: 0
出版历程
- 收稿日期: 2017-05-18
- 修回日期: 2017-11-08
- 刊出日期: 2018-02-19

Solving the Time Optimal Traveling Salesman Problem Based on Hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm

Funds:

The National Science and Technology Support Program of China (2013BAH52F01)

摘要

摘要: 该文以经典的对称旅行商问题(Symmetric Traveling Salesman Problem, STSP)为基础，求解时间最优的旅行商问题(Time Optimal TSP, TOTSP)，将拟合函数引入到混合蛙跳遗传算法(SFLA-GA)的适应度函数来反映景点客流量随时间的变化，旨在旅游旺季为游客提供一条游览时间最短的路径推送服务。实验结果表明：相对于随机游览路径，SFLA-GA混合算法得到的游览路径明显节省了游览时间；与SFLA和混合粒子群遗传算法(PSO-GA)相比较，SFLA-GA混合算法具有计算量少、收敛速度快、对初始种群依赖性低以及全局性更好等优点，在求解TOTSP上搜索性能更强、时间更优。
- 时间最优的旅行商问题 /
- 混合蛙跳遗传算法 /
- 适应度函数 /
- 拟合函数 /
- 游览时间
Abstract: In order to provide a recommended-path service for tourists with the shortest traveling time in the peak-season, the Time Optimal Traveling Salesman Problem (TOTSP) is further studied and the fit function is introduced into the fitness function of the hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm (SFLA-GA) to reflect the change of traffic over time, which is based on the classic and Symmetrical Traveling Salesman Problem (STSP). The experimental results show that compared with the random tour path, the tour path significantly saves the tour time which is obtained by the hybrid SFLA-GA. Compared with SFLA and hybrid Particle Swarm Optimization-Genetic Algorithm (PSO-GA), the hybrid SFLA-GA has some advantages, such as less amount of calculation, fast speed of convergence, low dependency on initial population, good global superiority and so on. The hybrid SFLA-GA has stronger search capability and less search time in solving the TOTSP.
- Time optimal traveling salesman problem /
- Hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm (SFLA-GA) /
- Fitness function /
- Fit function /
- Tour time

HTML全文

参考文献(25)

IACOPO G, FRANCOIS M, and KENJI S. The traveling salesman problem with neighborhoods: MINLP solution[J]. Optimization Methods and Software, 2013, 28(2): 364-378. doi: 10.1080/10556788.2011.648932.

ALFONSAS M, ANDRIUS B, and ANTANAS L. Modified local search heuristics for the symmetric traveling salesman problem[J]. Information Technology and Control, 2013, 42(3): 217-230. doi: 10.5755/j01.itc.42.3.1301.

张勇, 陈玲, 徐小龙, 等. 基于PSO-GA混合算法时间优化的旅行商问题研究[J]. 计算机应用研究, 2015, 32(12): 3613-3617. doi: 10.3969/j.issn.1001-3695.2015.12.019.

ZHANG Yong, CHEN Ling, XU Xiaolong, et al. Research on time optimal TSP based on hybrid PS0-GA[J]. Application Research of Computers, 2015, 32(12): 3613-3617. doi: 10.3969 /j.issn.1001-3695.2015.12.019.

ZHAN Shihua, LIN Juan, ZHANG Zejun, et al. List-based simulated annealing algorithm for traveling salesman problem[J]. Computational Intelligence and Neuroscience, 2016, (5): 1-12. doi: 10.1155/2016/1712630.

PAN G, LI K, OUYANG A, et al. Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP[J]. Soft Computing, 2016, 20(2): 1-12. doi: 10.1007/s00500-014-1522-3.

YANG Jianyi, DING Ruifeng, ZHANG Yuan, et al. An improved ant colony optimization(I-ACO) method for the quasi travelling salesman problem(Quasi-TSP)[J]. International Journal of Geographical Information Science, 2015, 29(9): 1534-1551. doi: 10.1080/13658816.2015.1013960.

王勇臻, 陈燕, 于莹莹. 求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报, 2017, 39(1): 198-205. doi: 10.11999/ JEIT160211.

WANG Yongzhen, CHEN Yan, and YU Yingying. Improved grouping genetic algorithm for solving multiple traveling salesman problem[J]. Jounal of Electronics Information Technology, 2017, 39(1): 198-205. doi: 10.11999/JEIT160211.

胡颖, 庄雷, 兰巨龙, 等. 基于自适应协同进化粒子群算法的虚拟网节能映射研究[J]. 电子与信息学报, 2016, 38(10): 2660-2666. doi: 10.11999/JEIT151434.

HU Ying, ZHUANG Lei, LAN Julong, et al. Energy aware virtual network embedding using particle swarm optimization algorithm based on adaptive[J]. Journal of Electronics Information Technology, 2016, 38(10): 2660-2666. doi: 10.11999/JEIT151434.

程希, 沈建华. 一种基于改进蚁群算法的光网络波长路由分配算法[J]. 电子与信息学报, 2012, 34(3): 710-715. doi: 10.3724/SP.J.1146.2011.01032.

CHENG Xi and SHEN Jianhua. An improved ant colony algorithm for routing and wavelength assignment in optical networks[J]. Journal of Electronics Information Technology, 2012, 34(3): 710-715. doi: 10.3724/SP.J.1146.2011.01032.

HASANIEN H M. Shuffled frog leaping algorithm-based static synchronous compensator for transient stability improvement of a grid-connected wind farm[J]. Iet Renewable Power Generation, 2014, 8(6): 722-730. doi: 10.1049/iet-rpg. 2013.0277.

骆剑平, 李霞, 陈泯融. 基于改进混合蛙跳算法的CVRP求解[J]. 电子与信息学报, 2011, 33(2): 429-434. doi: 10.3724/ SP.J.1146.2010.00328.

LUO Jianping, LI Xia, and CHEN Minrong. Improved shuffled frog leaping algorithm for solving CVRP[J]. Journal of Electronics Information Technology, 2011, 33(2): 429-434. doi: 10.3724/SP.J.1146.2010.00328.

马乐, 叶见新, 王晖. 旅游景区智能客流统计系统应用研究以玄武湖为例[J]. 中国科技信息, 2013, (2): 88-89. doi: 10.3969/j.issn.1001-8972.2013.02.040.

MA Le, YE Jianxin, and WANG Hui. Application research of intelligent statistical system for scenic area passenger flow- take xuanwu lake as an example[J]. China Science and Technology Information, 2013, (2): 88-89. doi: 10.3969/j.issn. 1001-8972.2013.02.040.

文俊浩, 舒珊. 一种改进相似性度量的协同过滤推荐算法[J]. 计算机科学, 2014, 41(5): 68-71. doi: 10.3969/j.issn.1002- 137X.2014.05.015.

WEN Junhao and SHU Shan. Improved collaborative filtering recommendation algorithm of similarity measure[J]. Computer Science, 2014, 41(5): 68-71. doi: 10.3969/j.issn. 1002-137X.2014.05.015.

HWANG Chaoming and YANG Miinshen. New similarity measures between generalized trapezoidal fuzzy numbers using the jaccard index[J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2014, 22(6): 831-844. doi: 10.1142/S0218488514500445.

孙冲. 混合蛙跳算法改进及控制参数优化仿真研究[D]. [硕士论文], 哈尔滨工业大学, 2011.

SUN Chong. Shuffled frog leaping algorithm improvement and simulation research for optimization of control parameters[D]. [Master dissertation], Harbin Institute of Technology, 2011.

麻荣永, 杨磊磊, 张智超. 基于粒子迭代位移和轨迹的粒子群算法C1、C2 参数特性分析[J]. 数学计算, 2013, 2(4): 109-115.

MA Rongyong, YANG Leilei, and ZHANG Zhichao. Analysis the characteristic of C1, C2 based on the PSO of iterative shift and trajectory of particle[J]. Mathematical Computation, 2013, 2(4): 109-115.

施引文献

资源附件(0)

访问统计