Application of Weighted Partial Max-SAT for Post-improvement of the Multiple Traveling Salesman Problem

Abstract

Advances allow SAT solvers to be used to solve problems in the indus- trial sector. Therefore, in this paper, we reduce the multiple traveling salesman problem to a weighted partial max-SAT, with the aim of increasing the qual- ity of the solution at a reduced computational cost. A version of Clarke and Wright’s saving algorithm has been implemented to create the initial solution, while the 2-opt algorithm is applied to each route to improve the routes, the search space is extended by adding k nearest neighbors of each vertex so that post-improvement can be performed by the SAT solver. Benchmarks of four in- stances from the literature suggest a significant post-improvement in the quality of the solution up to 43.51% for a reasonable computational cost.