Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications
by Lakhmi C. Jain; N.M. Martin
CRC Press, CRC Press LLC
ISBN: 0849398045   Pub Date: 11/01/98
  

Previous Table of Contents Next


3.1.1 Vehicle Routing Applications

In a VRP context, the input vectors are the two-dimensional coordinate vectors of the vertices and a different ring is associated with each route. The weight learning algorithm is also slightly modified. For academic vehicle routing problems based on the Euclidean metric, the weight vector of the winning output unit is the closest to the coordinate vector of the current vertex in Euclidean distance (rather than the one with the largest correlation with the input vector; see maximization of the inner product in Step 2). Also, the algorithm typically stops when there is a weight vector (unit) sufficiently close to each vertex.


Figure 3  Evolution of three rings in (a), (b), (c), and the final solution (d)

Given that multiple rings are used, the winning unit is determined among all units over all rings. Then, units located on the ring of the winning unit are moved toward the current vertex. At the end, each vertex is assigned to the closest unit. Through this assignment, the ordering of the units on each ring defines an ordering of the vertices on each route. Furthermore, since neighboring units on a given ring tend to migrate toward neighboring vertices in the Euclidean plane, short routes are expected to emerge. Figure 3 depicts the evolution of the rings in a two-dimensional Euclidean plane during the application of the weight adjustment algorithm, starting from the initial configuration illustrated in Figure 3(a). The vertices are large white nodes and the units are small black nodes; the location of each unit in the Euclidean plane is determined by its current weight vector.

At the start, no solution of the problem can be inferred. However, as the weight vectors migrate towards the vertices, the solution progressively emerges. The final solution is determined during the final assignment of vertices to units on the rings (c.f., Step 4).

3.1.2 The Hierarchical Deformable Net

The Hierarchical Deformable Net (HDM) [10, 11] illustrates the application of a self-organizing map to the VRP. The model involves a competition at two different levels: a deterministic competition among units on each ring, and a stochastic competition among the rings. The number of rings is fixed, and this model is applied with an increasing number of rings (routes) until a feasible solution is found. The HDM model can be summarized as follows.

Step 1. Initialization. Randomly order the vertices. Then, create one ring per route. Each ring contains 2×ceiling(n/m) units, where n is the number of vertices and m is the number of routes. Initialize the parameters h and G to 1 and 4×ceiling(n/m), respectively (see below).
Step 2. Repeat Step 3 to Step 8 until there is a weight vector sufficiently close to each vertex.
Step 3. Select the next vertex v and set the current input vector I to its coordinate vector (if all vertices are done, restart at the first vertex).
Step 4. Competition within each ring. Determine the winning unit uj*k on each ring rk. This unit is the one whose weight vector is closest to the current input vector I.
Step 5. Competition among the rings. Assign the following winning probability to each ring rk:

where h is a parameter of the algorithm, m is the number of rings, d(Tj*k,I) is the Euclidean distance between the coordinate vector I and the weight vector Tj*k of winning unit uj*k on ring rk, ΔQ is the difference between the capacity of the vehicle and the total demand on ring rk (including vertex v).
Step 6. Select the winning ring rk*, using a selection probability for each ring rk proportional to p(rk). Vertex v is assigned to unit uj*k*.
Step 7. Move the weight vector Tjk* of each unit j on the winning ring rk* toward the coordinate vector I of vertex v, as follows:

where dL(j,j*,k*) is the lateral distance between unit j and the winning unit j* on ring rk*.
Step 8. Slightly decrease the value of parameters h and G, by setting hnew=0.99 hold and Gnew = 0.9 Gold.

In Step 5, parameter h is used to modify the probability distribution over the rings. When the value of h is high, the selection probability of each ring is about the same. When the value of h is small, the probability distribution favors the ring closest to the current vertex among all rings that satisfy the capacity constraint (with the addition of the current vertex). In Step 7, parameter G controls the magnitude of the moves. When its value is reduced, the magnitude of the moves is also reduced. Hence, the values of both parameters h and G are gradually lowered to favor convergence toward good feasible solutions.

In a later study [12], Ghaziri extended the HDN to address the time-constrained VRP. In this case, the selection probabilities are adjusted through the introduction of an additional component that takes into account the time limit constraint. As opposed to the capacity constraint, however, the time limit constraint relates to the total duration of a route which, in turn, depends on the sequence of vertices on the route. At each iteration, a TSP procedure is thus applied to the currently assigned vertices on each ring (including the current vertex) to identify a plausible ordering. This ordering is then used to compute the selection probabilities.

Ghaziri has applied the HDN to a few VRPs taken from the test set in [2]. Although the solutions produced by HDN are of good quality, they are not competitive with the best solutions produced with alternative problem-solving methods, in particular, tabu search [9, 35].


Previous Table of Contents Next

Copyright © CRC Press LLC