RL Problem Description

RL Problem Description

The ring loading problem is defined on a network whose nodes are connected to form a ring, as shown in Figure 1. We consider the nodes to be indexed from 1 to n going clockwise around the ring. Similarly, the links are indexed from 1 to n so that index i corresponds to the link on the clockwise side of node i.

Figure 1. A 12 node ring

Given a set D of demands between nodes on the ring, the ring loading problem seeks a routing for each demand-either clockwise or counter-clockwise-such that the maximum load on a link is minimized. A demand k from the set of demands D is defined by a pair of nodes ik and jk and some amount dk of traffic between them. We assume that dk is nonnegative and integer. A particular demand k, partitions the links of the ring into two sets: those that are traversed in a clockwise routing of demand k and those that are traversed in a counter-clockwise routing. Let C(k) be the clockwise links, and let CC(k) be the counter-clockwise links. Given these definitions, the ring loading problem is:

[RL]: Minimize z
subject to (Eq. 1)
(Eq. 2)
(Eq. 3)

The constraints (1) ensure that each demand is routed. The left-hand side of each constraint (2) computes the traffic on a particular link l. Hence, the objective value z will be the maximum amount of traffic on any link of the ring. Since [RL] is formulated using binary variables, a particular demand is routed either entirely clockwise or entirely ounter-clockwise. By relaxing this "all-one-way" requirement, we could formulate the ring loading problem to allow some ortion of a demand to route clockwise and the remainder to route counter-clockwise. If the demands may be split arbitrarily, then ring loading is equivalent to solving a linear program and, therefore, polynomially solvable. Although ring loading may be viewed as a mathematical program in binary, integer, or continuous variables, the binary ring loading problem is the only one that is computationally difficult.

The objetive for the ring loading problem is to minimize the maximum load on the links of a ring. Thus, for each individual in the population, a fitness value is assigned based on the maximum link load it induces. The particular fitness function we use is shown in equation 4.

(Eq. 4)