Post-improving the Capacitated Vehicle Routing Problem Using a Max-SAT Solver

SAT solvers are used to solve a wide variety of problems in artificial intelligence, especially the Weighted Max-SAT variation that contributes significantly to solving combinatorial optimization problems. In this paper, the capacitated vehicle routing problem is reduced to a weighted partial Max-SAT to improve solution quality with a reduced computational cost. An adaptation of Clarke and Wright’s savings algorithm and the 2-opt algorithm have been implemented to construct the initial solution. The search space is expanded by adding the k-nearest neighbors to enable post-improvement by the SAT solver. Benchmarks of instances from the literature suggest a significant improvement in solution quality for a reasonable computational cost.