Computer tools for solving the traveling salesman problem
-
DOIhttp://dx.doi.org/10.21511/dm.18(1).2020.03
-
Article InfoVolume 18 2020, Issue #1, pp. 25-39
- Cited by
- 1093 Views
-
2096 Downloads
This work is licensed under a
Creative Commons Attribution 4.0 International License
The task of the traveling salesman, which is to find the shortest or least costly circular route, is one of the most common optimization problems that need to be solved in various fields of practice. The article analyzes and demonstrates various methods for solving this problem using a specific example: heuristic (the nearest neighbor method, the most profitable neighbor method), metaheuristic (evolutionary algorithm), methods of mathematical programming. In addition to classic exact methods (which are difficult to use for large-scale tasks based on existing software) and heuristic methods, the article suggests using the innovative features of the commercially available MS Excel software using a meta-heuristic base. To find the optimal solution using exact methods, the Excel (Solver) software package was used, as well as the specialized GAMS software package. Comparison of different approaches to solving the traveling salesman problem using a practical example showed that the use of traditional heuristic approaches (the nearest neighbor method or the most profitable neighbor method) is not difficult from a computational point of view, but does not provide solutions that would be acceptable in modern conditions. The use of MS Excel for solving the problem using the methods of mathematical programming and metaheuristics enabled us to obtain an optimal solution, which led to the conclusion that modern tools are an appropriate addition to solving the traveling salesman problem while maintaining the quality of the solution.
- Keywords
-
JEL Classification (Paper profile tab)C6, C61, C63
-
References17
-
Tables6
-
Figures6
-
- Figure 1. An example of solving the traveling salesman problem using the nearest neighbor algorithm
- Figure 2. An example of solving the TSP problem using the most profitable neighbor algorithm
- Figure 3. Filled form of restrictive conditions for TSP
- Figure 4. General route sequence
- Figure 5. Program code in the GAMS software system for TSP solving
- Figure 6. Initial Settings for Configuring Solutions
-
- Table 1. Distance matrix D
- Table 2. Frequency matrix E
- Table 3. Source data and auxiliary calculation results in MS Excel
- Table 4. Restrictive conditions
- Table 5. Initial data and the results of solving the traveling salesman problem
- Table 6. Results of solving the traveling salesman problem by various considered methods
-
- Ball, W. (1939). Mathematical recreations and essays. New York.
- Bellman, R. (1960). Combinatorial processes and dynamic programming, Combinatorial Analysis. American Mathematical Society.
- Brezina, I., Čičková, Z., & Gežík, P. (2012). Sieťová analýza. Bratislava: EKONÓM.
- Čičková, Z., Brezina, I., & Pekár, J. (2008). An alternative method for solving traveling salesman problem by evolutionary algorithm. Management Information Systems, 3(1), 17-22.
- Čičková, Z., Brezina, I., & Pekár, J. (2013). Open traveling salesman problem with time windows. Logistics International, 13, 40-43.
- Čičková, Z., Brezina, I., & Pekár, J. (2016). Solving the routing problems with time windows. In D. Davendra, I. Zelinka (Ed.), Self-organizing migrating algorithm: methodology and implementation (pp. 207-236). Springer.
- Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling salesman problem. Journal of the Operations Research Society of America, 2(4), 393-410.
- Flood, M. (1956). The traveling-salesman problem. Operations Research, 4(1), 61-75.
- Hellmich, K. (1960). Die Reiseroute kűrzester Weglänge. Dauer.
- Lin, S., & Kernighan, B. (1973). An efficient heuristic for the traveling salesman problem. Operations Research, 21(2), 17-28.
- Little, J., Murty, K., Sweeney, D., & Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 863- 1025.
- Menger, K. (1931). Bericht über ein mathematisches Kolloquium 1929/30. Monatshefte für Mathematik und Physik, 38, 17-38.
- Miliotis, K. (1978). Using cutting planes to solve the symmetric travelling salesman problem. Mathematical Programming, 15, 177-188.
- Miller, C., Tucker, A., & Zemlin, R. (1960). Integer Programming Formulation of Traveling Salesman Problems. Journal of the ACM, 7, 42-49.
- Padberg, M., & Rinaldi, G. (1987). Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters, 6(1), 1-7.
- Pekár, J., Brezina, I., & Čičková, Z. (2017). Synchronization of capacitated vehicle routing problem among periods. Ekonomický časopis, 65, 66-78.
- Robinson, J. (1949). On the Hamiltonian game and traveling-salesman problem. RAND Research.