A hybrid ant colony system algorithm for solving the ring star problem
- PDF / 956,058 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 26 Downloads / 173 Views
A hybrid ant colony system algorithm for solving the ring star problem Xiaoning Zang 1 & Li Jiang 2,3 & Bin Ding 1 & Xiang Fang 4 Accepted: 7 November 2020 # Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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. Keywords Ring star problem . Ant colony system . Bi-level programming . Pheromone
1 Introduction The ring star problem (RSP) aims to construct a minimum total cost Hamiltonian cycle over a set of nodes, in which each node that is non-visited on the cycle is assigned to its closest node on the cycle. The total cost includes the routing and assignment costs. The RSP has several applications in telecommunications and logistics network design problems. The first version of the RSP is also called the median cycle problem (MCP1), and Perez et al. [1] proposed a heuristic algorithm combined variable neighborhood search and tabu search (VNTS) to solve the median cycle problems (MCP1 and MCP2) and their neighborhood structures include cycle
* Li Jiang [email protected] 1
School of Management, University of Science and Technology of China, Hefei 230026, Anhui, People’s Republic of China
2
School of Management, Hefei University of Technology, Hefei 230009, Anhui, People’s Republic of China
3
Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei, People’s Republic of China
4
Sheldon B. Lubar School of Business, University of Wisconsin-Milwaukee, 3202 N Maryland Ave, Milwaukee, WI 53201, USA
reduction, cycle increment, and vertex exchanges. Renaud et al. [2] proposed two types of heuristic algorithms for MCP, namely, multi-start greedy add algorithm and random keys evolutionary algorithm (RKEA). Labbe et al. [3], Kedad-Sidhoum et al. [4], and Simonetti et al. [5] proposed branch-and-cut algorithms for RSP, and the difference is that Labbe et al. [3] proposed an algorithm based on several families of valid inequalities, Kedad-Sidhoum et al. [4] proposed facet-defining inequalities to develop their efficient branch-and-cut algorithm, and Simonetti et al. [5] introduced a integer programming formulation to formulate RSP. Calvete et al. [6] de
Data Loading...
