Exploring Set Partitioning in Combinatorial Optimisation: Revisiting a TSP Example

• H.A. Krüger School of Computer Science and Information Systems, North-West University, Potchefstroom, South Africa https://orcid.org/0000-0001-8514-4422
• I. Mayer School of Computer Science and Information Systems, North-West University, Potchefstroom, South Africa https://orcid.org/0009-0002-8178-5403

Abstract

Large-scale combinatorial problems are often computationally intractable, and alternative solution approaches are frequently used to find effective approximate solutions for these problems. This paper introduces a six-step methodology, adapted from an existing framework in the literature, and based on a set partitioning scheme, aimed at generating near-optimal solutions for combinatorial problems. The proposed approach specifically considers the classic travelling salesman problem, and the methodology’s performance is demonstrated on a real-world 2508-node instance. The results confirm that the proposed set partitioning approach yields satisfactory solution quality and offers practical implementation advantages.