Application of Weighted Partial Max-SAT for Post-improvement of the Multiple Traveling Salesman Problem - Lima, João P.; Rocha, Anne C.; Arruda, Alexandre; Jr., Dmontier (Anais do Workshop Brasileiro de Lógica (WBL); 2024: Anais do V Workshop Brasileiro de LógicaDO - 10.5753/wbl.2024.2458, 2024)
Advances allow SAT solvers to be used to solve problems in the industrial sector. Therefore, in this paper, we reduce the multiple traveling salesman problem to a weighted partial max-SAT, with the aim of increasing the quality 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 instances from the literature suggest a significant post-improvement in the quality of the solution up to 43.51% for a reasonable computational cost.