Genetic Algorithm on MTSP within Polar Coordinates and Time Consumption with Respect to Various Variables

Haocheng Ren ； Haixiang Huang ； Zhangxian Song ； Hengfei Liu

《International Core Journal of Engineering》 7卷1期 (2021/01) Pp. 291-296

https://doi.org/10.6919/ICJE.202101_7(1).0039

摘要

Multi-Agent Travelling Salesman Problem also known as MTSP, which consists of at least two salesmen and a specific number of cities (city # ＞ agent #), extends the issue of classical travelling salesman problem (TSP). Under the conditions of a set of cities, a starting point, where all salesman or agents are, and a cost measure, the objective is to determine combinatorial routes for all agents, minimizing the total cost of M routes. A general genetic algorithm (GA) based in the polar coordinate system is introduced to solve MTSP in this paper. The main structure focuses on making sub problems. The paper will address how GA can solve MTSP by dividing it into many TSPs, and how solution time scales with various variables such as population size and generation.

關鍵字

Genetic Algorithm ； Polar Coordinates System ； Multi-Agent Travelling Salesman Problem ； Variables Control ； Solution Time

參考文獻

Durbin, R., Willshaw, D. (1987) An analogue approach to the travelling salesman problem using an elastic net method. Nature 326, 689–691. https://doi.org/10.1038/326689a0.

ScienceDirect (2011) A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. Available at: https://doi.org/10.1016/0377-2217(94)00299-1 (Accessed:).

ScienceDirect (2011) Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Available at: https://doi.org/10.1016/j.asoc.2011.01.039 (Accessed:).

C. Yang and K. Y. Szeto, (2019) "Solving the Traveling Salesman Problem with a Multi-Agent System," IEEE Congress on Evolutionary Computation (CEC), Wellington, New Zealand, 2019, pp. 158-165, doi: 10.1109/ CEC.2019.8789895.

He J. (2014) Solving the Multiobjective Multiple Traveling Salesmen Problem Using Membrane Algorithm. In: Pan L., Păun G., Pérez-Jiménez M.J., Song T. (eds) Bio-Inspired Computing - Theories and Applications. Communications in Computer and Information Science, vol 472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45049-9_27.