PARALLEL TRAVELING SALESMEN PROBLEM

Muhamad Aidil bin Amis #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 aidil.amis77@gmail.com
2 faidzms@ieee.org

 
 
Abstract—Traveling Salesman Problem (TSP) is a standout amongst the most well-known concentrated on issues in combinatorial streamlining. Given the rundown of urban areas and separations between them, the issue is to locate the briefest visit conceivable which visits every one of the urban communities in rundown precisely once and closes in the city where it begins. In spite of the Traveling Salesman Problem is NP-Hard, a great deal of techniques and arrangements are proposed to the issue. TSP is by all accounts restricted for a couple application ranges, notwithstanding it can be utilized as a part of a ton of issue arrangements.

Keywords: Traveling Salesman Problem, Shortest tour



REFERENCES

[1]   	Flood, M. M. (1956). The traveling-salesman problem. Operations Research,4(1), 61-75.

[2]   	Fan Yang (2010), Solving Traveling Salesman Problem Using Parallel Genetic Algorithm   and Simulated Annealing.

[3]   	Er, H. R., & Erdogan, N. (2014). Parallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster. arXiv preprint arXiv:1401.6267.

[4]          Verma, A., Llorà, X., Goldberg, D. E., & Campbell, R. H. (2009, November). Scaling genetic algorithms using mapreduce. In Intelligent Systems     Design and Applications, 2009. ISDA'09. Ninth   International Conference on (pp. 13-18). IEEE.

[5]   	Reisleben, B., & Merz, P. (1996, May). A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. InEvolutionary Computation, 1996., Proceedings of IEEE International Conference on (pp. 616-621). IEEE.

[6]   	Oberlin, P., Rathinam, S., & Darbha, S. (2010). Today's traveling salesman problem. Robotics & Automation Magazine, IEEE, 17(4), 70-77.

[7]   	Mühlenbein, H., Gorges-Schleuter, M., & Krämer, O. (1988). Evolution algorithms in combinatorial optimization. Parallel Computing, 7(1), 65-85.

[8]   	Muhlenbein, H. (1991). Evolution in time and space-the parallel genetic algorithm. In Foundations of genetic algorithms.

[9]   	Fiechter, C. N. (1994). A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics, 51(3), 243-267.

[10]   	Randall, M., & Lewis, A. (2002). A parallel implementation of ant colony optimization. Journal of Parallel and Distributed Computing, 62(9), 1421-1432.

[11]   	Chatterjee, S., Carrera, C., & Lynch, L. A. (1996). Genetic algorithms and traveling salesman problems. European journal of operational research,93(3), 490-510

[12]   	Mohan, J. (1983). Experience with two parallel programs solving the traveling salesman problem (No. CONF-8308190-). IEEE Computer Society Press, Silver Spring, MD.

[13]   	Reisleben, B., & Merz, P. (1996, May). A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. InEvolutionary Computation, 1996., Proceedings of IEEE International Conference on (pp. 616-621). IEEE.

[14]   	Tan, Q., He, Q., & Shi, Z. (2012). Parallel max-min ant system using mapreduce. In Advances in Swarm Intelligence (pp. 182-189). Springer Berlin Heidelberg.