A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1
 |
International Journal of Recent Engineering Science (IJRES) |  |
| © 2021 by IJRES Journal | ||
| Volume-8 Issue-1 |
||
| Year of Publication : 2021 | ||
| Authors : Souhail Dhouib |
||
| DOI : 10.14445/23497157/IJRES-V8I1P102 |
How to Cite?
Souhail Dhouib, "A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1," International Journal of Recent Engineering Science, vol. 8, no. 1, pp. 6-10, 2023. Crossref, https://doi.org/10.14445/23497157/IJRES-V8I1P102
Abstract
In this paper, a new column-row method named Dhouib-Matrix-TSP1 is designed to solve the Traveling Salesman Problem (TSP) in polynomial time. 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 the 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.
Keywords
Traveling Salesman Problem, Combinatorial opptimization, Polynomial time.
Reference
[1] Omar Cheikhrouhoua, and Ines Khoufi, “A Comprehensive Survey on the Multiple Traveling Salesman Problem: Applications, Approaches, and Taxonomy,” Computer Science Review, vol. 40, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[2] Mohsen Mosayebi, Manbir Sodhi, and Thomas A. Wettergren, “The Traveling Salesman Problem with Job-times (TSPJ),” Computers & Operations Research, vol. 129, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[3] Shijin Wang, Ming Liu, and Feng Chu, “Approximate and Exact Algorithms for an Energy Minimization Traveling Salesman Problem,” Journal of Cleaner Production, vol. 249, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[4] Moshe Kaspi, Moshe Zofi, and Ron Teller, “Maximizing the Profit Per Unit Time for the Traveling Salesman Problem,” Computers & Industrial Engineering, vol. 135, pp. 702-710, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[5] Juan C. Pina-Pardo, Daniel F. Silva, and Alice E. Smith, “The Traveling Salesman Problem with Release Dates and Drone Resupply,” Computers & Operations Research, vol. 129, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[6] Xin Wei et al., “Multi-core-, Multi-Thread-Based Optimization Algorithm for Large-Scale Traveling Salesman Problem,” Alexandria Engineering Journal, vol. 60, no. 1, pp. 189-197, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[7] Cemal Aykut Gencel, and Barış Keçeci, “Traveling Salesman Problem with Hotel Selection: Comparative Study of the Alternative Mathematical Formulations,” Procedia Manufacturing, vol. 39, pp. 1699-1708, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Christian Doppstadt, Achim Koberstein, and Daniele Vigo, “The Hybrid Electric Vehicle—Traveling Salesman Problem with time windows,” European Journal of Operational Research, vol. 284, no. 2, pp. 675-692, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[9] Kostas Florios, and George Mavrotas, “Generation of the Exact Pareto set in Multi-Objective Traveling Salesman and Set Covering Problems,” Applied Mathematics and Computation, vol. 237, pp. 1-19, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[10] Aimin Zhou, Feng Gao, and Guixu Zhang, “A Decomposition-Based Estimation of Distribution Algorithm for Multi-Objective Traveling Salesman Problems,” Computers & Mathematics with Applications, vol. 66, no. 10, pp. 1857-1868, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[11] Yannis Marinakis, Magdalene Marinaki, and Georgios Dounias, “Honey Bees Were Mating Optimization Algorithm for the Euclidean Traveling Salesman Problem,” Information Sciences, vol. 181, no. 20, pp. 4684-4698, 2011.
[CrossRef] [Google Scholar] [Publisher Link]
[12] Briana Couto, “Using Matrices And Hungarian Method To Solve The Traveling Salesman Problem,” Mathematics Honors Theses, Ph.D. at Digital Commons at Salem State University, 2018.
[Google Scholar] [Publisher Link]
[13] Sevgi Erdoğan, and Elise Miller-Hooks, “A Green Vehicle Routing Problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 48, no. 1, pp. 100-114, 2012.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Hadi Basirzadeh, “One's Assignment Method for Solving Traveling Salesman Problem,” Journal of Mathematics and Computer Science, vol. 10, pp. 258-265, 2014.
[Google Scholar] [Publisher Link]
[15] Janusz Czopik, “An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem,” American Journal of Computational Mathematics, vol. 9, pp. 61-67, 2019.
[CrossRef] [Google Scholar] [Publisher Link]