Resolution of the Traveling Salesman Problem with Precedence Constraint Applying Genetic Algorithm

Journal of South China University of Technology(Natural Science Edition) ›› 2004, Vol. 32 ›› Issue (4): 97-100.

Resolution of the Traveling Salesman Problem with Precedence Constraint Applying Genetic Algorithm

Zhu Ling-xiang Liao Qin Zou Liang

Dept．of Applied MathematicsSouth China Univ．of Tech．Guangzhou510640GuangdongChina

Received:2003-06-25 Online:2004-04-20 Published:2015-09-08
Contact: 朱玲湘（1979－）女硕士研究生主要从事数理统计和优化算法研究． E-mail:hcitys＠163.com
About author:朱玲湘（1979－）女硕士研究生主要从事数理统计和优化算法研究．

Abstract

Abstract: The Traveling Salesman Problem with Precedence Constraint （TSPPC） was introduced and the localization of the general genetic algorithm （GA） to solve TSPPC was pointed out．It is found that a lot of illegal chromosomes would be generated by using the general GAthus reducing the searching efficiency of the algorithm．To overcome the disadvantages mentioned abovethe species initializationcrossover and mutation based on the precedence constraint of TSP were proposed．None of these genetic operations would generate any illegal chromosomewhich makes the searching efficiency of the algorithm higher．This conclusion was finally verified by corresponding theorems and examples．

Key words: traveling salesman problem with precedence constraint, genetic algorithm, species initialization, crossover, mutation

CLC Number:

O242.1

Zhu Ling-xiang Liao Qin Zou Liang. Resolution of the Traveling Salesman Problem with Precedence Constraint Applying Genetic Algorithm[J]. Journal of South China University of Technology(Natural Science Edition), 2004, 32(4): 97-100.

[1]	QIU Yudong, WANG Zhan, XIE Zhishen. Optimization for Steel Frames with Semirigid Connections Based on Hybrid Algorithms [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(6): 72-77.
[2]	WENG Jiancheng, WANG Maolin, LIN Pengfei, et al. Cross-line Combined Bus Scheduling Optimization Method Based on Passenger Flow Characteristic Identification [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(9): 39-48.
[3]	QIN Yaqin, QIAN Zhengfu, XIE Jiming, et al. Cooperative Lane Change Decision-Making Model of Bottleneck Emergency Section in Weaving Area Based on Social Force [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(7): 66-75.
[4]	ZHENG Yajing, LI Yaohui, JIN Wenzhou. Connection Scheme Optimization of Last Trains of Urban Mass Transit Network Based on Considering the Transfer Passengers [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(5): 32-39,72.
[5]	XIA Qinxiang, LI Kai, MA Jun, et al. Die Electrode Scheduling Problem Solution Based on Genetic Algorithm [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(3): 80-87.
[6]	ZHOU Zhong, DENG Zhuoxiang, CHEN Yun, et al. Strength Prediction of Foam Light Soil Based on GA-BP Neural Network [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(11): 125-132.
[7]	LIU Xuan, WANG Zihang, ZHANG Tongrui, et al. Optimal Control Strategy for Lateral Stability of Port Heavy-Duty AGV [J]. Journal of South China University of Technology(Natural Science Edition), 2021, 49(8): 113-121.
[8]	LI Jing WANG Chen ZHANG Jiaxu. Vehicle Speed Estimation Based on UniTire Model [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(5): 47-55.
[9]	LUO Yutao, ZHOU Tianyang, XU Xiaotong. Time-Varying LQR Control of Four-Wheel Steer /Drive Vehicle Based on Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(3): 114-122.
[10]	JIN Gang HE Zhihao WANG Yingjun. 5G Frequency Selection Surface Shape Optimization Method Based on Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(11): 95-105.
[11]	LI Jiale LIU Zhenbo WANG Xuefei. Distribution Path Optimization of Electric Vehicles Considering Charging and Discharging Strategy in Smart Grid [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(10): 31-40.
[12]	JIN Wenzhou, HU Weiyang, DENG Jiayi, et al. Flexible Scheduling Model of Demand Ｒesponse Transit Based on Hybrid Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(1): 123-133.
[13]	LIU Gang, GUO Deming, ZHENG Wencheng, et al. Axial Thermal Circuit Model-Based Calculation of Contact Ｒesistance of Contact Surface Between the Overhead Ground Wire and Armor Rod [J]. Journal of South China University of Technology (Natural Science Edition), 2020, 48(7): 9-19.
[14]	MA Hongwei CHEN Fengshou. Optimal Arrangement of Dampers Based on Coarse-Grained Parallel Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2019, 47(11): 104-112.
[15]	ZHANG Kaisheng LIU Haotian WANG Qiang ZHANG Baocheng. Optimization of Multi-Organism Cooperative Propulsion Efficiency of Bionic Thunniform Fish Robot [J]. Journal of South China University of Technology (Natural Science Edition), 2018, 46(7): 109-115,122.

Resolution of the Traveling Salesman Problem with Precedence Constraint Applying Genetic Algorithm

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles 0

Metrics

Comments