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

• Pedro H. Ferreira UFC
• Alexandre M. Arruda UFC

DOI: https://doi.org/10.5753/wbl.2025.8630

Resumo

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.

Referências

Ansotegui, C., Bonet, M. L., and Levy, J. (2010). A new algorithm for weighted partial maxsat. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pages 3–8.

Clarke, G. and Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4):568–581.

Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6):791–812.

Gebser, M., Kaufmann, B., Neumann, A., and Schaub, T. (2007). clasp: A conflict-driven answer set solver. In Baral, C., Brewka, G., and Schlipf, J., editors, Logic Programming and Nonmonotonic Reasoning, pages 260–265, Berlin, Heidelberg. Springer Berlin Heidelberg.

Golden, B., Bodin, L., Doyle, T., and Stewart, W. J. (1980). Approximate traveling salesman algorithms. Operations Research, 28(3-part-ii):694–711.

Gong, W. and Zhou, X. (2017). A survey of sat solver. AIP Conference Proceedings, 1836(1):020059.

Helsgaun, K. (2000). An effective implementation of the lin–kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106–130.

Huerta, I. I., Neira, D. A., Ortega, D. A., Varas, V., Godoy, J., and Asín-Achá, R. (2022). Improving the state-of-the-art in the traveling salesman problem: An anytime automatic algorithm selection. Expert Systems with Applications, 187:115948.

Kao, Y. and Chen, M. (2013). Solving the cvrp problem using a hybrid pso approach. In Madani, K., Dourado, A., Rosa, A., and Filipe, J., editors, Computational Intelligence, pages 59–67, Berlin, Heidelberg. Springer Berlin Heidelberg.

Khadilkar, H. (2022). Solving the capacitated vehicle routing problem with timing windows using rollouts and max-sat. In Eighth Indian Control Conference, pages 1–6.

Larrosa, J., Heras, F., and de Givry, S. (2008). A logical approach to efficient max-sat solving. Artificial Intelligence, 172(2):204–233.

Lima, J., Rocha, A., Arruda, A., and Jr., D. (2024). Application of weighted partial max-sat for post-improvement of the multiple traveling salesman problem. In Proceedings of the 5th Brazilian Workshop of Logic, pages 9–16, Porto Alegre, RS, Brasil. SBC.

Rintanen, J. (2012). Planning as satisfiability: Heuristics. Artificial Intelligence, 193:45–86.

Rocha, A. C., Lima, J. P., Arruda, A., and Dmontier (2023). Using a max-sat solver as a post-improvement move for traveling salesman problem. Computers and Industrial Engineering, 2:908–916.

Sohanghpurwala, A. A., Hassan, M. W., and Athanas, P. (2017). Hardware accelerated sat solvers—a survey. Journal of Parallel and Distributed Computing, 106:170–184.

Tosoni, D., Galli, C., Hanne, T., and Dornberger, R. (2022). Benchmarking metaheuristic optimization algorithms on travelling salesman problems. In Proceedings of the 8th International Conference on E-Society, e-Learning and e-Technologies, ICSLT ’22, page 20–25, New York, NY, USA. Association for Computing Machinery.

Vidal, T. (2022). Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood. Computers Operations Research, 140:105643.