![]() |
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 |
The work presented here [33] is very different from the developments reported in Section 3.1 with respect both to the selected application, namely, a courier service, and the type of neural network model used. First, the problem is dynamic in the sense that the customers (or vertices) to be serviced are not known in advance, but occur in a continuous fashion. Hence, a solution cannot be constructed beforehand; new customers are incorporated in the planned routes as these routes are executed. Second, the neural network model is based on supervised learning, that is, desired outputs or responses are provided to the network to guide its weight adjustment procedure.
In the following, we first characterize the problem to be investigated. After a brief review of feedforward models with backpropagation, we explain how this paradigm is exploited to address the courier service application.
Dynamic vehicle routing and dispatching refer to a wide range of problems where information on the problem is revealed to the decision maker concurrently with the determination of the solution [29]. These problems have recently emerged as an active area of research due to recent advances in communication and information technologies that now allow real-time information to be quickly obtained and processed. The courier service application considered here is an instance of this class of problems and can be described as follows.
A courier service receives customer calls for the pick-up and delivery of express mail in a local area. Each customer specifies a pick-up and a delivery location, as well as a due date for the delivery. Since most customers demand fast service, the routing and scheduling is done in real time. In such a demand responsive context, the dispatching situation is looked at when a new customer calls into the dispatch office. At that time, some of the earlier customers have been serviced and are no longer considered. Other customer requests have been assigned to vehicles, and are either waiting to be picked up or en route to their delivery location. The problem is to determine the assignment of each new request to a particular vehicle, as well as the new planned route for that vehicle (i.e., the ordering of previously assigned but yet unserviced requests, plus the new request). In solving this problem, the dispatcher must find a compromise between two conflicting objectives: minimizing the operations cost, like the total distance traveled, and maximizing customer satisfaction, in particular, satisfaction of the desired due dates.
Currently, this problem is solved by human dispatchers who represent a key element in courier service companies. Specific skills are required to adequately perform the dispatching task; thus, it takes a long time to train dispatchers. Furthermore, their professional career lasts only a few years due to the high level of stress associated with reacting properly and quickly to a dynamically changing environment. Given the difficulty to formalize the knowledge of dispatchers using classical decision rules, and the absence of a clearly-defined objective function to be optimized, a neural network dispatching system was developed to learn the dispatchers decision procedure through previous decision examples. The basic neural network model is presented in the following; then, its application to the courier service problem is discussed.
Feedforward neural networks with backpropagation [31] constitute one of the most popular neural network models. Their supervised learning procedure is based on a simple idea: if the network gives a wrong answer, the weights on the connections are adjusted to reduce this error and increase the likelihood of a correct response in the future.
The model is typically composed of three layers of simple units, namely, the input layer, the hidden layer, and the output layer. Each layer is fully connected to the previous and next layer through weighted connections that propagate the signal in a forward direction from the input to the output (see Figure 4). No processing takes place at the input layer. That is, the input vector provided to the input layer is directly propagated to the hidden layer through the weighted connections. Assuming p input units and q hidden units, each hidden unit j computes its activation level aj, according to the following formula:
In this formula, Ii is component i of input vector I (or, equivalently, the activation level of input unit i), Tij is the connection weight between input unit i and hidden unit j, and θj is the input bias of unit j. Note that the activation level of each hidden unit is in the interval [0,1] due to the sigmoidal transformation. These activation levels are then propagated to the output units through the weighted connections between the hidden and output layers. The same processing takes place at each output unit and the final activation levels of these units (or output vector) represent the response of the network to the input vector I.
Figure 4 A three-layer feedforward model
The power of this model comes from its ability to adjust the connection weights to perform a particular task. To do this, the backpropagation learning algorithm uses a training set of examples that characterizes the task: in this set, each input vector is associated with a desired response or output vector. These examples are processed one by one by the network and the weights are adjusted accordingly. The mean-squared error between the outputs calculated by the network and the desired outputs (over all examples in the training set) is typically used to monitor the networks performance. The training stops when this error measure stabilizes. We will not go into the details of the backpropagation algorithm; the interested reader is referred to [31] for further details.
Previous | Table of Contents | Next |