Article ID Journal Published Year Pages File Type
4635690 Applied Mathematics and Computation 2007 8 Pages PDF
Abstract
This article presents an approach to solve the travelling salesman problem using linear optimisation with a suitable set of constraints. Such approaches are well known as Cutting Plane methods but previously applied algorithms still suffer from the NP-completeness of the problem causing an exponential number of computational steps in the worst case. The method presented in this paper both tolerates non-integer results for a dedicated class of solutions (symmetric solutions) and avoids other ones (asymmetric solutions). It is thus able to deal with the inherent complexity of the travelling salesman problem.Therefore the overall complexity of the optimisation algorithm remains polynomial in the worst case.
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
,