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

ZHANG Yong; GAO Xinxin; WANG Yujie

doi:10.11999/JEIT170484

Volume 40 Issue 2

Feb. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2018 > 40(2): 363-370

ZHANG Yong, GAO Xinxin, WANG Yujie. Solving the Time Optimal Traveling Salesman Problem Based on Hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm[J]. Journal of Electronics & Information Technology, 2018, 40(2): 363-370. doi: 10.11999/JEIT170484

Citation:

ZHANG Yong, GAO Xinxin, WANG Yujie. Solving the Time Optimal Traveling Salesman Problem Based on Hybrid Shuffled Frog Leaping Algorithm-Genetic Algorithm[J]. Journal of Electronics & Information Technology, 2018, 40(2): 363-370. doi: 10.11999/JEIT170484

Citation:

PDF( 292 KB)

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

doi: 10.11999/JEIT170484

Funds:

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

Received Date: 2017-05-18
Rev Recd Date: 2017-11-08
Publish Date: 2018-02-19

Abstract

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

FullText(HTML)

References(25)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views