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

• João P. Lima UFC
• Anne C. Rocha USP
• Alexandre Arruda UFC
• Dmontier Jr. UFC

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

Resumo

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.

Referências

Anbuudayasankar, S. P., Ganesh, K., and Mohapatra, S. (2014). Survey of Methodologies for TSP and VRP, pages 11–42. Springer International Publishing, Cham.

Ansótegui, C., Bonet, M. L., and Levy, J. (2010). A new algorithm for weighted partial MaxSAT. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI’10, page 3–8. AAAI Press.

Cheikhrouhou, O. and Khoufi, I. (2021). A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Computer Science Review, 40:100369.

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.

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.

Jiang, C., Wan, Z., and Peng, Z. (2020). A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert Systems with Applications, 139:112867.

Karabulut, K., Öztop, H., Kandiller, L., and Tasgetiren, M. F. (2021). Modeling and optimization of multiple traveling salesmen problems: An evolution strategy approach. Computers Operations Research, 129:105192.

Lin, S. (1965). Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 44(10):2245–2269.

Matai, R., Singh, S., and Mittal, M. L. (2010). Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches. In Davendra, D., editor, Traveling Salesman Problem, chapter 1. IntechOpen, Rijeka.

Reinelt, G. (1991). TSPLIB—A Traveling Salesman Problem Library. ORSA Journal on Computing, 3(4):376–384.

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. volume 2, page 908 – 916. Computers and Industrial Engineering.

Sakai, M. and Nabeshima, H. (2015). Construction of an ROBDD for a PB-Constraint in Band Form and Related Techniques for PB-Solvers. IEICE Transactions on Information and Systems, E98.D(6):1121–1127.

Segerstedt, A. (2014). A simple heuristic for vehicle routing – A variant of Clarke and Wright’s saving method. International Journal of Production Economics, 157:74–79. The International Society for Inventory Research, 2012.

Shokouhi rostami, A., Mohanna, F., Keshavarz, H., and Rahmani Hosseinabadi, A. A. (2015). Solving Multiple Traveling Salesman Problem using the Gravitational Emulation Local Search Algorithm. Applied Mathematics Information Sciences, 9:1–11.

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.

Vizel, Y., Weissenbacher, G., and Malik, S. (2015). Boolean Satisfiability Solvers and Their Applications in Model Checking. Proceedings of the IEEE, 103(11):2021–2035.

Zha, A., Gao, R., Chang, Q., Koshimura, M., and Noda, I. (2020). CNF Encodings for the Min-Max Multiple Traveling Salesmen Problem. In 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), pages 285–292.