![]() |
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 |
Both GenSect and GenClust are generic methods that can be applied with success to real-world vehicle routing problems with specific side constraints. For example, GenSect was used in the context of school bus routing, where students are transported from predefined locations to a school using a fleet of buses with different capacities. The routes obtained in this application were superior to those in use in two school districts [37].
Another complex routing problem is the multi-commodity transshipment problem (MCTP). In the MCTP, each node in a transportation network is a source or sink for a particular commodity and there is an upper bound on the maximum amount of commodities that can be transported on the arcs. The cost of transporting a commodity is proportional to the distance traveled by the commodity from its source node to its sink node. The objective is to maximize the amount of commodities transported and, for this amount, to minimize the fleet size and transportation costs. A natural application is found in airline fleet operation where each major city is a node and passengers traveling between two cities are commodities. A system called MICAH [38], which couples the GenSect method with a MCTP solver, was used to solve a real world MCTP; a solution was found where 13224 units of 54 different commodities are transported between 54 different nodes using a fleet of 18 vehicles. In this application, the MICAH system increased the total transportation of commodities by 38% in comparison with the solution obtained with an MCTP solver combined with manual routing.
A decoder is a hybrid system where a GA is coupled with a simple insertion heuristic. In a vehicle routing context, an insertion heuristic adds customers one by one in the routes, each time using the feasible location that minimizes some cost measure, like the detour. For example, the detour would be diu + duj - dij in Figure 8.
The insertion order (not the route) is specified by a string of integers, where each integer stands for a particular customer. For example, the string 3 1 2 5 4 means that customer 3 should be the first to be inserted in the solution, followed by customers 1, 2, 5, and 4. At any point, a new route can be created to service a given customer if there is no feasible insertion place in the current routes (due to the side constraints). In the case of the string 3 1 2 5 4, a route will first be created to service customer 3. Then, customers 1 and 2 will be inserted in the newly created route. At this point, we assume that there is no feasible insertion place for customer 5. Thus, a new route is created to service this customer. Finally, customer 4 will be inserted in one of the two routes, depending on its best feasible insertion place. Clearly, different insertion orders are likely to lead to different routes. The role of the GA is thus to find an ordering of customers for the insertion heuristic that will lead to the best solution. This problem-solving approach is attractive, because the GA does not need to explicitly consider side constraints; these are handled by the insertion heuristic. It is thus possible to apply this method to problems with different types of side constraints through simple modifications to the insertion heuristic.
Figure 8 Inserting customer u between customers i and j.
In a decoder system, the GA searches the space of possible insertion orderings using specialized crossover and mutation operators that produce valid offspring orderings from two parent orderings. Many operators of this type have been designed, in particular, for the Traveling Salesman Problem (see Chapter 10 of [23] and [25]). These operators can be applied to insertion orders or to the routes themselves when these routes are represented as strings of integers.
In [1], a decoder system for the VRP with time windows is described. This system uses two order-based crossover operators, MX1 and MX2, to produce new insertion orders. Since it is generally desirable to insert customer i before customer j in the solution if the time window at i occurs before the time window at j, the two operators are strongly biased by this precedence relationship.
In Figure 9, we show how the MX1 operator produces a valid ordering from two parent orderings. This example assumes five customers numbered from 1 to 5 and the time window precedence relationship 1 < 2 < 3 < 4 < 5 (i.e., the time window at customer 1 is the earliest and the time window at customer 5 is the latest). Starting at position 1, the customers on the two parent chromosomes are compared and the customer with the earliest time window is added to the offspring. Then, the procedure is repeated for the next position, until all positions are considered. In the example provided in Figure 9, customers 1 and 4 are first compared. Since the time window at customer I occurs before the time window at customer 4, customer 1 is selected and takes the first position on the offspring (a). Now, in order to produce a valid ordering, customers 1 and 4 are swapped on parent 2. Customers 3 and 5 are then compared at position 2, and customer 3 is selected to occupy the second position on the offspring (b). Customers 5 and 3 are swapped on parent 1, etc. The resulting offspring is shown in (e). Note that MX1 tends to push customers with early time windows to the front of the resulting string. These customers are thus the first to be inserted in the solution by the insertion heuristic.
Figure 9 MX1 crossover
Specialized order-based mutation operators have also been designed [25]. The Remove-and-Reinsert (RAR) operator, for example, randomly selects a customer on the chromosome and moves it to another position. The customers located between the two positions are shifted accordingly. In Figure 10, customer 3 is moved from position 2 to position 4. Swapping operators, where two customers exchange their position, are also widely used.
Figure 10 RAR mutation
The generality of the decoder approach has led to its application to complex vehicle routing problems with many side constraints (which prevent the application of more specific problem-solving methodologies). For example, a successful implementation for a vehicle routing problem with backhauls and time windows is described in [28]; solutions within 1% of the optimum, on average, have been produced for problems with up to 100 customers.
Figure 11 The SBX operator
Previous | Table of Contents | Next |