Matrix-Based Ant Colony Optimization for Large-Scale Balanced Multiple Traveling Salesmen Problem

The balanced multiple traveling salesmen problem (BMTSP) is a challenging combinatorial optimization problem with many practical applications. However, as the scale of the problem grows, it becomes computationally expensive to solve in a reasonable amount of time. To address this issue, we propose a matrix-based ant colony optimization (MACO). MACO redefines the ant colony optimization and uses matrix operations to accelerate the path construction, fitness evaluation, and pheromone update processes. We introduce a new encoding method to represent the population and use matrixed roulette wheel selection to speed up the path construction process. Experiments on the TSPLIB benchmark set show that MACO achieves comparable solution quality to traditional CPU-based ACO, while providing higher computational efficiency by utilizing GPU-accelerated matrix operations.