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.2.3 An Application for a Courier Service

In the case of the courier service application, the neural network model is used to dispatch new requests to appropriate vehicles. To this end, the network processes each candidate vehicle and produces a numerical evaluation in output. Clearly, vehicles with high evaluations are the best candidates for servicing a new request.

The input vector associated with a given vehicle is composed of attribute values that characterize this vehicle with respect to the new service request: detour in time to service the request, pick-up time, delivery time, additional lateness to customers already assigned to the vehicle route (but not yet serviced) due to the inclusion of the new request, etc. It is worth noting that for computing such an input vector, an insertion place for the new request is first chosen by minimizing an insertion cost over all possible insertion places in the vehicle route. Hence, the neural network does not handle the routing component of the problem. Its capabilities are limited to the dispatching task, namely, what vehicle should service the new request given the default insertion locations.

The output vector contains a single output unit; its activation level corresponds to the evaluation of the vehicle whose description has been provided in input. Using a set of examples composed of dispatching situations where the vehicle selected by the dispatcher is known, the neural network model is trained to assign high evaluations to these vehicles. Ideally, for each dispatching situation, the vehicle selected by the dispatcher should be ranked first by the neural network (i.e., it should get the highest evaluation among all available vehicles).

Using 140 requests collected from a courier service company operating a fleet of 12 vehicles in the Montreal area, the authors demonstrated the potential of the neural network model. After training the network with 90 requests, the model was tested on the 50 remaining requests. In 47 cases out of 50, the vehicle selected by the dispatcher was ranked first, second, third, or fourth by the neural network (out of twelve possible ranks). When the vehicle chosen by the expert did not get the highest evaluation, it was often quite close. Furthermore, the vehicle with the highest evaluation was typically a good alternative choice.

In this work, the network was trained in batch mode from previously collected data. However, it would be possible to “link” the neural network model with the dispatcher during one or more operations per day in order to adjust the connection weights in real time after each new decision. At the end of the training period, the network would then be able to mimic the dispatcher’s behavior. Such a network could be used, for example, to facilitate the dispatcher’s task by displaying the neural network evaluation of the best vehicles or to assist less experienced dispatchers when confronted with difficult situations. In each case, it is assumed that the final decision is left to the human expert.

4. Genetic Algorithms

The Genetic Algorithm (GA) is an adaptive heuristic search method based on population genetics. The basic concepts were developed by Holland [15], while the practicality of using the GA to solve complex problems was demonstrated in [6, 14]. Under this paradigm, a population of chromosomes evolves over a number of generations through the application of genetic operators, like crossover and mutation, that mimic those found in nature. The evolution process allows the best chromosomes to survive and mate from one generation to the next.

More formally, the GA is an iterative procedure that maintains a population of P candidate members over many simulated generations. The population members are artificial chromosomes made of fixed length strings with a binary value (allele) at each position (locus). The genotype is the string entity and the phenotype is the decoded string entity (search point, solution). In parameter optimization problems, for example, the string could encode numerical parameter values in base-2 notation. The real parameter values would then correspond to the phenotype. A fitness value is also associated with each chromosome; this value is typically related to the quality of the associated search point or solution.

Denoting the population of chromosomes at a given generation as M(Generation), the flow of the GA can be summarized as follows:

Genetic Algorithm (GA):
GA1: Generation = 0;
GA2: Initialize M(Generation);
Evaluate M(Generation);
GA3: While (GA has not converged or terminated)
Generation = Generation + 1;
Select M(Generation) from M(Generation - 1);
Crossover M(Generation);
Mutate M(Generation);
Evaluate M(Generation);
End (while)
GA4: Terminate the GA.


Previous Table of Contents Next

Copyright © CRC Press LLC