A Variable Neighborhood Search Approach for the Capacitated m-Ring-Star Problem
In this paper, we proposed an algorithm based on variable neighborhood search (VNS) for the capacitated m-Ring-Star problem. This problem has several real applications in communications networks, rapid transit system planning and optical fiber networks. T
- PDF / 908,475 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 196 Views
2
Universidad Católica de Colombia, Bogotá, Colombia [email protected] Universidad Distrital Francisco José de Caldas, Bogotá, Colombia {erlopezs,gmendez}@udistrital.edu.co
Abstract. In this paper, we proposed an algorithm based on variable neighborhood search (VNS) for the capacitated m-Ring-Star problem. This problem has several real applications in communications networks, rapid transit system planning and optical fiber networks. The problem consists in design m rings or cycles that begins of a central depot and visits a set of customers and transition or steiner nodes. While the nodes don’t belong to a ring these must be allocated or assign to a customer or steiner node that belongs to a ring. The number of customers allocated or visited in each ring must not exceed the maximum capacity. The goal is to minimize the visiting and allocation cost. For solving the problem, we propose a VNS approach based on random perturbation for escaping from the local optimal solutions. Our method reached the optimal solution in a reasonable amount of time in a set of instances from the literature. Keywords: m-Ring-Star problem Variable neighborhood search design Combinatorial optimization
Network
1 Introduction The capacitated m-Ring-Star problem (CmRSP) was introduced by Baldacci et al. [1]. This problem is a variant of the classical capacitated vehicle routing problem with one depot. The CmRSP consists in designing a set of rings (with size m) passing throw a central depot and visiting a subset of customers and a subset of steiner nodes. Rings may include transit nodes (Steiner nodes) so that star connections can be established between a customer and a ring through a transit node. Each ring and its star connections (ring-star) is limited by a maximum number of customers. A feasible solution is represented by a set of m rings. Each node is a visited node if is in a ring, if not, is an allocated node. If in a node is assigned an allocated node, it is call a connecting node. Figure 1 gives an example of a feasible CmRSP solution, where there are three rings, and nodes assigned with the dotted line are the allocated nodes. The goal is to minimize the total cost of visiting and assigning the customers to the routes that comes from the depot. This problem has many real-world applications like optical fiber networks, rapid transit system planning and telecommunication systems.
© Springer International Publishing Switzerland 2016 D.-S. Huang et al. (Eds.): ICIC 2016, Part I, LNCS 9771, pp. 3–11, 2016. DOI: 10.1007/978-3-319-42291-6_1
4
C. Franco et al.
Fig. 1. An example of a feasible CmRSP solution
There are two variations of this problem, the ring star problem and the steiner ring star problem. In the ring star problem the steiner nodes are not available and the capacity constrain are not imposed. The problem consist in design a cycle through a subset of know customers looking for minimize the cycle length and the cost of assign a non-visited customer to the nearest customer visited. There are several algorithmi
Data Loading...
