A Labelling Method for the Travelling Salesman Problem
The travelling salesman problem (TSP) is a problem whereby a finite number of nodes are supposed to be visited exactly once, one after the other, in such a way that the total weight of connecting arcs used to visit these nodes is minimized. We propose a labelling method to solve the TSP problem. The...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-05-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/11/6417 |
| _version_ | 1797597922625323008 |
|---|---|
| author | Trust Tawanda Philimon Nyamugure Santosh Kumar Elias Munapo |
| author_facet | Trust Tawanda Philimon Nyamugure Santosh Kumar Elias Munapo |
| author_sort | Trust Tawanda |
| collection | DOAJ |
| description | The travelling salesman problem (TSP) is a problem whereby a finite number of nodes are supposed to be visited exactly once, one after the other, in such a way that the total weight of connecting arcs used to visit these nodes is minimized. We propose a labelling method to solve the TSP problem. The algorithm terminates after <i>K</i>−1 iterations, where <i>K</i> is the total number of nodes in the network. The algorithm’s design allows it to determine alternative tours if there are any in the TSP network. The computational complexity of the algorithm reduces as iterations increase, thereby making it a powerful and efficient algorithm. Numerical illustrations are used to prove the efficiency and validity of the proposed algorithm. |
| first_indexed | 2024-03-11T03:12:07Z |
| format | Article |
| id | doaj.art-062f974a6f3549fbbeab7b1e2f7e09bf |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-11T03:12:07Z |
| publishDate | 2023-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-062f974a6f3549fbbeab7b1e2f7e09bf2023-11-18T07:31:50ZengMDPI AGApplied Sciences2076-34172023-05-011311641710.3390/app13116417A Labelling Method for the Travelling Salesman ProblemTrust Tawanda0Philimon Nyamugure1Santosh Kumar2Elias Munapo3Department of Statistics and Operations Research, National University of Science and Technology, Ascot, Bulawayo P.O. Box AC 939, ZimbabweDepartment of Statistics and Operations Research, National University of Science and Technology, Ascot, Bulawayo P.O. Box AC 939, ZimbabweDepartment of Mathematical and Geospatial Sciences, School of Sciences, RMIT University, Melbourne, VIC 3001, AustraliaDepartment of Business Statistics and Operations Research, School of Economic Sciences, Mafikeng Campus, North West University, Mmabatho 2745, South AfricaThe travelling salesman problem (TSP) is a problem whereby a finite number of nodes are supposed to be visited exactly once, one after the other, in such a way that the total weight of connecting arcs used to visit these nodes is minimized. We propose a labelling method to solve the TSP problem. The algorithm terminates after <i>K</i>−1 iterations, where <i>K</i> is the total number of nodes in the network. The algorithm’s design allows it to determine alternative tours if there are any in the TSP network. The computational complexity of the algorithm reduces as iterations increase, thereby making it a powerful and efficient algorithm. Numerical illustrations are used to prove the efficiency and validity of the proposed algorithm.https://www.mdpi.com/2076-3417/13/11/6417travelling salesman problemnon-directed networkminimum cost touralgorithm |
| spellingShingle | Trust Tawanda Philimon Nyamugure Santosh Kumar Elias Munapo A Labelling Method for the Travelling Salesman Problem Applied Sciences travelling salesman problem non-directed network minimum cost tour algorithm |
| title | A Labelling Method for the Travelling Salesman Problem |
| title_full | A Labelling Method for the Travelling Salesman Problem |
| title_fullStr | A Labelling Method for the Travelling Salesman Problem |
| title_full_unstemmed | A Labelling Method for the Travelling Salesman Problem |
| title_short | A Labelling Method for the Travelling Salesman Problem |
| title_sort | labelling method for the travelling salesman problem |
| topic | travelling salesman problem non-directed network minimum cost tour algorithm |
| url | https://www.mdpi.com/2076-3417/13/11/6417 |
| work_keys_str_mv | AT trusttawanda alabellingmethodforthetravellingsalesmanproblem AT philimonnyamugure alabellingmethodforthetravellingsalesmanproblem AT santoshkumar alabellingmethodforthetravellingsalesmanproblem AT eliasmunapo alabellingmethodforthetravellingsalesmanproblem AT trusttawanda labellingmethodforthetravellingsalesmanproblem AT philimonnyamugure labellingmethodforthetravellingsalesmanproblem AT santoshkumar labellingmethodforthetravellingsalesmanproblem AT eliasmunapo labellingmethodforthetravellingsalesmanproblem |