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


4.1.1 Genetic Sectoring (GenSect)

GenSect [36] is modeled after the sweep heuristic of Gillett and Miller [13] for the capacitated VRP. Starting from some seed point and using the central depot as a pivot, the ray from the depot to the seed is swept clockwise or counter-clockwise. Customers are added to a sector as they are swept until the capacity constraint forbids the inclusion of the next customer. This customer then becomes the seed point for the next sector. This is repeated until all customers are assigned to a particular sector (see Figure 7). Routes are then constructed within each sector. One of the drawbacks of this algorithm is its sensitivity to the selection of the first seed point. Although the algorithm tries to compensate for this by exchanging customers between adjacent sectors at the end, it does not look at all customers during the sweep. GenSect tries to compensate for this by using a GA to adaptively look at all customers in a global manner.

We assume a set of n customers with planar coordinates (xi, yi) and a polar coordinate angle pi. The GenSect method assumes that the initial number of vehicles m required to solve the problem is known. In the case of the capacitated VRP, this number can be obtained using, for example, the Clarke and Wright [3] or the Gillett and Miller algorithm. The Gensect method divides the customers into m clusters by identifying a set of seed angles, s0, ..., sm and by drawing a ray from the depot in the direction of each seed angle. The initial seed angle s0 is assumed to be 0°. The first sector will thus lie between seed angles s0 and s1, the second sector will lie between seed angles s1 and s2, and so on. GenSect assigns customer i to sector k if sk-1 < pi ≤ sk, k = 1, ..., m.


Figure 7  Three sectors identified by the sweep algorithm

Each seed angle sk is computed from the previous one by adding a fixed angle F and an offset ek. That is,

The fixed angle corresponds to the minimum angular value for a sector; it assures that each sector gets represented. The fixed angle is computed by taking the customer with maximum polar angle and dividing this value by 2m. The offset is the extra region from the fixed angle that allows the sector to encompass a larger or a smaller area. If the addition of the fixed angle F and the offset ek to sk-1 exceeds 360°, then Sk is set to 360°, thereby allowing the method to consider less than m vehicles to service the customers. Once the sectors are identified, the sequencing of the customers within each sector to produce the final routes is done with a cheapest insertion heuristic [30].

The GA is used to search for the offsets that result in the best routes. A set of m offsets is encoded in base-2 notation on each chromosome. A chromosome that uses four bits to encode each offset with m = 3 is shown below.

The decimal conversion of each offset is then mapped between 0° and 360°. The fitness of the chromosome is the total routing costs obtained with the cheapest insertion heuristic when applied to the sectors encoded on the chromosome. Since there is no guarantee that feasible routes can be produced, the routing costs correspond to the total distance traveled plus a penalty term for violated constraints. In the case of the capacitated VRP, we have

α × total distance + β × total overload, α + β = 1.

Hence, chromosomes associated with infeasible solutions are penalized and are less likely to be selected for mating.

Classical one-point crossover and mutation operators are then used to evolve the population of chromosomes. As the crossover operator exchanges a portion of the bit string between two chromosomes, partial information about sector divisions is exchanged. The GenSect system thus uses selection, crossover, and mutation to adaptively explore the search space for the set of sectors that will produce the best possible routes. Note that there is no guarantee that a feasible solution will ever be produced during the genetic search. At the end of the search, the best solution returned by the GA is thus improved through local reoptimization methods that move customers from one route to another or from one position to another in the same route. Through this process, a better solution may be found (if the solution produced by the GA is already feasible) or a feasible solution may emerge from an infeasible one.

Gensect was applied to different types of vehicle routing problems with time windows [36, 39, 40, 41]; it has led to the development of GenClust, which is described in the following.

4.1.2 Genetic Clustering with Geometric Shapes (GenClust)

Quite often, it is desirable to have routes with particular shapes, like petal or circular shapes when each vehicle starts at the depot, visits a set of customers, and returns to the depot. In [4], it is shown that geometric shapes can be used to interactively design routes for the VRP. In fact, geometric shapes are indicated if those shapes are good approximations of the route shapes that result from the minimization of the routing costs.

GenClust [42] follows the general principles of GenSect, but uses geometric shapes to cluster customers. A particular geometric shape can be described by a set of attributes. For example, two attributes may be used for a circle, namely, the origin (x,y) and the radius r. Similar to GenSect, a chromosome encodes the attribute values associated with a given shape in base-2 notation. In GenSect, each chromosome encodes m different circles, one for each cluster, and the GA is then used to search for the set of circles that lead to the best solution. Different heuristic rules are used to associate a customer with a particular cluster, when it is not contained in exactly one circle (i.e., none or many). For example, when a customer is not contained in any circle, it is associated with the closest one.

GenClust was applied to a multi-depot extension of the VRP, where customers can be serviced from more than one depot. It has found the best known solution to 12 of the 23 benchmark problems found in the literature [44].


Previous Table of Contents Next

Copyright © CRC Press LLC