A hybrid ant colony system algorithm for solving the ring star problem

摘要

The ring star problem (RSP) involves finding a minimum-length cycle over a set of nodes, for which each node that is non-visited on a cycle is assigned to its closest node on the cycle. The goal is to minimize routing and assignment costs. This study proposes a mathematical model to formulate RSP by using bi-level programming ideas, which consist of one leader and one follower sub-problems. The leader sub-problem refers to constructing a cycle over a subset of nodes in the network, whereas the follower sub-problem is related to assigning the remaining nodes to the nodes on the cycle. An efficient hybrid ant colony system (ACS) algorithm is developed on the basis of the bi-level programming formulations, in which ACS with assignment pheromone is proposed to solve the leader sub-problem. Lastly, the hybrid ACS is tested on 153 benchmark instances. Results show the good performance of the proposed approach.