A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1

  IJETT-book-cover  International Journal of Recent Engineering Science (IJRES)          
© 2021 by IJRES Journal
Volume-8 Issue-1
Year of Publication : 2021
Authors : Souhail Dhouib


MLA Style: Souhail Dhouib "A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1" International Journal of Recent Engineering Science 8.1(2021):6-10. 

APA Style: Souhail Dhouib. A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1  International Journal of Recent Engineering Science, 8(1), 6-10.

In this paper, a new column-row method named Dhouib-Matrix-TSP1 is designed to solve in polynomial time the Traveling Salesman Problem (TSP). At first, the distance matrix is defined, and then four steps are launched: 1) Selecting the starting position 2) Choosing Rows 3) Discarding by column 3) Transforming route to a tour. Some numerical examples are presented to illustrate the effectiveness of the proposed method. It can be concluded that the Dhouib-Matrix-TSP1 method consumes a small number of iterations (just n iterations, where n represents the number of cities) to solve the TSP, and its result is the closest to the optimum solution.

[1] O. Cheikhrouhoua and I. Khoufi ― A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches, and taxonomy, Computer Science Review, 40(2021) 100369.
[2] M. Mosayebi, M. S. Thomas and A. Wettergren ― The Traveling Salesman Problem with Job-times (TSPJ), Computers & Operations Research, 129(2021) 105226, 2021.
[3] S. Wanga, M. Liu and F. Chu ― Approximate and exact algorithms for an energy minimization traveling salesman problem, Journal of Cleaner Production, 249(2021) 119433.
[4] M. Kaspia, M. Zofiab, and R. Teller ― Maximizing the profit per unit time for the traveling salesman problem, Computers & Industrial Engineering, 135(2019) 702-710.
[5] J. C. Pina-Pardoa, D. F. Silvab and A. E. Smith ― The traveling salesman problem with release dates and drone resupply, Computers & Operations Research, 129(2021) 105170.
[6] X. Wei, L. Ma, H. Zhang, and Y. Liu ― Multi-core-, multi-thread-based optimization algorithm for large-scale traveling salesman problem, Alexandria Engineering Journal, 60(1)(2021) 189-197.
[7] C. A. Gencel and B. Keçeci ― Traveling Salesman Problem with Hotel Selection: Comparative Study of the Alternative Mathematical Formulations", Procedia Manufacturing, 39(2019) 1699-1708.
[8] C. Doppstadt, A. Koberstein, and D. Vigo ― The Hybrid Electric Vehicle—Traveling Salesman Problem with time windows, European Journal of Operational Research, 284(2)(2020) 675-692.
[9] K. Florios and G. Mavrotas ― Generation of the exact Pareto set in Multi-Objective Traveling Salesman and Set Covering Problems, Applied Mathematics and Computation, 237(2014) 1-19.
[10] A. Zhou, F. Gao, and G. Zhang ― A decomposition-based estimation of distribution algorithm for multi-objective traveling salesman problems, Computers & Mathematics with Applications, 66(10)(2013) 1857-1868.
[11] Y. Marinakis, M. Marinaki, and G. Dounias ― Honey bees were mating optimization algorithm for the Euclidean traveling salesman problem, Information Sciences, 181(20)(2011) 4684-4698.
[12] B. Couto ― Using Matrices And Hungarian Method To Solve The Traveling Salesman Problem, Ph.D. at Digital Commons at Salem State University, USA, (2018).
[13] S. Erdogan and E. Miller-Hooks ―A Green Vehicle Routing Problem, Transportation Research Part E: Logistics and Transportation Review, 48(1)(2012) 100-114.
[14] H. Basirzadeh ― One's Assignment Method for Solving Traveling Salesman Problem, Journal of Mathematics and Computer Science, 10(2014) 258-265.
[15] J. Czopik ― An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem, American Journal of Computational Mathematics, 9(2019) 61-67.

Traveling Salesman Problem, Combinatorial Optimization, Polynomial Time