• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Dong Xueshi, Dong Wenyong, Wang Yufeng. Hybrid Algorithms for Multi-Objective Balanced Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2017, 54(8): 1751-1762. DOI: 10.7544/issn1000-1239.2017.20170347
Citation: Dong Xueshi, Dong Wenyong, Wang Yufeng. Hybrid Algorithms for Multi-Objective Balanced Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2017, 54(8): 1751-1762. DOI: 10.7544/issn1000-1239.2017.20170347

Hybrid Algorithms for Multi-Objective Balanced Traveling Salesman Problem

More Information
  • Published Date: July 31, 2017
  • Balanced traveling salesman problem (BTSP), a variant of traveling salesman problem (TSP), is another combination optimization problem, which can be applied in many fields such as the optimization problem for gas turbine engines (GTE). BTSP can only model optimization problems with the single traveling salesman and task, but can’t model and optimize the problem with multiple salesmen and tasks at the same time. Therefore, this paper firstly provides a multi-objective balanced traveling salesman problem (MBTSP) model, which can model the optimization problems with multiple salesmen and tasks. Specifically it can be applied to the real-world problems with multiple objectives or individuals, for example, the optimization for multiple GTE. Some literatures have proved that ITO algorithm and genetic algorithms can show better performance in solving combination optimization problems, therefore, the paper utilizes the hybrid ITO algorithm (HITO) and hybrid genetic algorithm (GA) to solve MBTSP. For HITO, it utilizes ant colony optimization (ACO) to produce a probabilistic generative model based on graph, and then uses the drift and volatility operators to update the model, and obtains optimum solution. For the hybrid GA, the first is improved by greedy method called GAG, the second GA is optimized by incorporating hill-climbing named GAHC, and the final one is GASA. In order to effectively test the algorithms, the paper makes extensive experiments using small scale to large scale MBTSP data. The experiments show that the algorithms are effective and reveal the different characteristics in solving MBTSP problem.
  • Related Articles

    [1]Sun Qingxiao, Yang Hailong. Generalized Stencil Auto-Tuning Framework on GPU Platform[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440612
    [2]Li Maowen, Qu Guoyuan, Wei Dazhou, Jia Haipeng. Performance Optimization of Neural Network Convolution Based on GPU Platform[J]. Journal of Computer Research and Development, 2022, 59(6): 1181-1191. DOI: 10.7544/issn1000-1239.20200985
    [3]Zhang Shuai, Li Tao, Jiao Xiaofan, Wang Yifeng, Yang Yulu. Parallel TNN Spectral Clustering Algorithm in CPU-GPU Heterogeneous Computing Environment[J]. Journal of Computer Research and Development, 2015, 52(11): 2555-2567. DOI: 10.7544/issn1000-1239.2015.20148151
    [4]Luo Xinyuan, Chen Gang, Wu Sai. A GPU-Accelerated Highly Compact and Encoding Based Database System[J]. Journal of Computer Research and Development, 2015, 52(2): 362-376. DOI: 10.7544/issn1000-1239.2015.20140254
    [5]Tang Liang, Luo Zuying, Zhao Guoxing, and Yang Xu. SOR-Based P/G Solving Algorithm of Linear Parallelism for GPU Computing[J]. Journal of Computer Research and Development, 2013, 50(7): 1491-1500.
    [6]Cai Yong, Li Guangyao, and Wang Hu. Parallel Computing of Central Difference Explicit Finite Element Based on GPU General Computing Platform[J]. Journal of Computer Research and Development, 2013, 50(2): 412-419.
    [7]Wang Zhuowei, Xu Xianbin, Zhao Wuqing, He Shuibing, Zhang Yuping. Parallel Acceleration and Performance Optimization for GRAPES Model Based on GPU[J]. Journal of Computer Research and Development, 2013, 50(2): 401-411.
    [8]Wu Xiaoxiao, Liang Xiaohui, Xu Qidi, and Zhao Qinping. An Algorithm of Physically-based Scalar-fields Guided Deformation on GPU[J]. Journal of Computer Research and Development, 2010, 47(11): 1857-1864.
    [9]Wang Jing, Wang Lili, and Li Shuai. Pre-Computed Radiance Transport All-Frequency Shadows Algorithm on GPU[J]. Journal of Computer Research and Development, 2006, 43(9): 1505-1510.
    [10]Hu Wei and Qin Kaihuai. A New Rendering Technology of GPU-Accelerated Radiosity[J]. Journal of Computer Research and Development, 2005, 42(6): 945-950.

Catalog

    Article views (1810) PDF downloads (695) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return