Operators of the Two-Part Encoding Genetic Algorithm in Solving the Multiple Traveling Salesmen Problem

doi:10.1109/TAAI.2011.64

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Proceeding > Item 987654321/121481

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/121481

Title:	Operators of the Two-Part Encoding Genetic Algorithm in Solving the Multiple Traveling Salesmen Problem
Authors:	Chen, S. H.;Chen, M. C.
Keywords:	mTSP;two-part chromosome;crossover operators;nutation operators
Date:	2011-11-11
Issue Date:	2021-10-14 12:13:16 (UTC+8)
Publisher:	IEEE
Abstract:	The multiple traveling salesmen problem (mTSP) considers the m salesmen to visit n cities. This problem involves the assignment of the salesmen to some locations and we have to optimize the sequence within the route, so it is even harder than the traveling salesman problem (TSP) in nature. As a result, there are some algorithms used to solve the mTSP when the problem size is large. Particularly, genetic algorithm (GA) is quite famous in solving this problem while the problem size is large. When we compare the major existing encoding methods for mTSP, the best approach could be the two-part chromosome encoding due to its solution space is the smallest. The two parts are responsible for the sequence and the number of cities should be visited by each salesman. However, because the two-part chromosome technique is the recently proposed encoding method, the better combination of the crossover operators and mutation operators have not studied for this encoding method. As a result, this paper investigates the genetic operators could be used for this purpose by design-of-experiments (DOE). The appropriate genetic operators are suggested in this paper and it could be used to applied in the GA which employs the two-part chromosome encoding technique.
Relation:	2011 International Conference on Technologies and Applications of Artificial Intelligence, p.331-336
DOI:	10.1109/TAAI.2011.64
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Proceeding

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	63	View/Open
Operators of the Two-Part Encoding Genetic Algorithm in Solving the Multiple Traveling Salesmen Problem.pdf		337Kb	Adobe PDF	2	View/Open

Loading...