A Clustering-Based Max-SAT Hybrid Approach for the Capacitated Vehicle Routing Problem with Time Windows

• Pedro H. F. da Silva USP
• Francisco D. C. da Silva UFC
• Rafael F. Dantas UFC
• Carlos V. D. Araújo UECE
• Alexandre M. Arruda UFC

DOI: https://doi.org/10.5753/etc.2026.22144

Resumo

This paper proposes a hybrid approach for the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) that combines k-means clustering and SAT-based optimization to improve solution quality on benchmark instances. Clustering decomposes the problem into smaller routing subproblems. For each cluster, an initial feasible route is generated and subsequently improved using the 2-Opt local search heuristic. The search space is then expanded using the k-nearest neighbors algorithm, and the solution is finally refined using a SAT-based optimization model. Experiments on the Solomon benchmark instances show competitive improvements compared with a state-of-the-art approach, highlighting the potential of this strategy for CVRPTW.

Referências

Cover, T. M. and Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1):21–27.

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

Ferreira, P. and Arruda, A. (2025). Post-improving the capacitated vehicle routing problem using a max-sat solver. In Anais do VI Workshop Brasileiro de Lógica, pages 32–39, Porto Alegre, RS, Brasil. SBC.

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.

Khadilkar, H. (2022). Solving the capacitated vehicle routing problem with timing windows using rollouts and max-sat.

Le, T. D. C., Nguyen, D. D., Oláh, J., and Pakurár, M. (2022). Clustering algorithm for a vehicle routing problem with time windows. Transport, 37(1):17–27.

Liu, F., Lu, C., Gui, L., Zhang, Q., Tong, X., and Yuan, M. (2023). Heuristics for vehicle routing problem: A survey and recent advances.

Nanda Kumar, S. and Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 04.

SINTEF (2022). Solomon benchmark. [link]. Accessed: Mar 2026.