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


Chapter 6
Vehicle Routing through Simulation of Natural Processes

Jean-Yves Potvin
Centre de Recherche sur les Transports
and
Département d’Informatique et de Recherche Opérationnelle
Université de Montréal
Canada

Sam R. Thangiah
Department of Ccomputer Science
Slippery Rock University
U.S.A.

Vehicle routing problems hold a central place in distribution management. Their economic importance has motivated both academic researchers and private companies to find ways to efficiently perform the transportation of goods and services. A vehicle routing problem requires the allocation of each customer to a particular vehicle and the ordering of these customers on each route to minimize the transportation costs, subject to various constraints such as vehicle capacity and route time duration. In this chapter, we review recent attempts at solving those problems, using methods motivated by natural processes, like genetic algorithms and neural networks.

1. Introduction

Neural networks and genetic algorithms both come from the realization that simulating natural processes, even at a high level of abstraction, can bring valuable insights into complex real-world problems. Due to the success of these paradigms in many diverse application areas [5, 21], researchers have recently tackled the field of combinatorial optimization, where an optimal solution is sought among a finite or a countable infinite number of alternatives. An abundant literature may be found, in particular, on applications of these methods for solving the well-known Traveling Salesman Problem (TSP) [24, 25].

In this chapter, we report about recent attempts at solving a class of extensions to the TSP, known as vehicle routing problems. These problems are pervasive in the real world as they hold a central place in transportation systems, like school bus routing, and in logistics systems where goods or services are distributed from central facilities (plants, warehouses) to customers. These problems require the construction of vehicle routes, that is, the allocation of each customer to a particular vehicle and the ordering of these customers on each route to minimize the total routing costs, subject to a variety of constraints such as vehicle capacity and route time duration.

To introduce this subject, the chapter is organized along the following lines. A classification of prominent vehicle routing problems is first presented in Section 2. Then, applications of neural networks and genetic algorithms for some of these problems are reported in Sections 3 and 4, respectively. Finally, conclusions are drawn in Section 5.

2. Vehicle Routing Problems

An abundant literature may be found on useful abstractions or models of routing problems found in practice. One of the most popular models is the vehicle routing problem (VRP) which is formally defined on a directed graph G=(V,A), where V={v0,..., vn} is the vertex set and A={(vi, vj): vi, vj ∈ V, i≠j} is the arc set. Vertex v0 is a central depot housing a fleet of identical vehicles, while the remaining vertices represent customers to be serviced. A nonnegative distance or cost matrix D={dij} is defined on A, where dij is the distance or cost to travel from vertex vi to vertex vj. The VRP then consists of determining m vehicle routes of total minimum cost, each starting and ending at the depot, such that every customer is visited exactly once. Figure 1 illustrates a solution to this problem using m = 3 vehicles. In this figure, the black square stands for the central depot and the white circles are customers to be serviced.


Figure 1  Three vehicle routes servicing eight customers

Different versions of this model are reported in the literature depending on the side constraints to be satisfied.

  Capacitated VRP: a nonnegative demand qi is associated with each vertex and the total demand on a route may not exceed vehicle capacity Q.
  Distance (time) constrained VRP: the matrix D stands for distances (travel times) between vertices, and the total distance (duration) of any route may not exceed a prespecified bound.
  VRP with precedence constraints: a precedence constraint between two vertices vi and vj exists if it is required to visit vi before vj. In the VRP with backhauls, for example, mixed routes servicing both pick-up and delivery locations must be constructed. Vehicles are loaded at a central depot and must first service the delivery locations. The vehicles are then allowed to pick up (backhaul) goods en route back to the depot.
  VRP with time windows: each vertex vi must be visited within a time interval [ai, bi], where ai and bi are the earliest and latest service times, respectively. Typically, a vehicle is allowed to wait if it arrives at a customer location before its earliest service time.

Though the VRP is simple to state, yet, it is extremely complex to solve and belongs to the class of NP-complete problems [8, 20]. That is, the computation time to obtain the optimum increases exponentially with the number of vertices. Exact algorithmic procedures for this problem do exist, but they are computationally expensive and can be applied only to relatively small instances. Another disadvantage of exact approaches is their unpredictability as they can produce an optimal solution to one instance of the problem but fail to terminate on a smaller instance of the same problem. To obtain solutions that are close to the optimum in a reasonable amount of time, heuristic search strategies are widely used. In the following, we will focus on heuristic methods inspired by nature to address some of the vehicle routing problems mentioned above, as well as other variants found in practice.


Previous Table of Contents Next

Copyright © CRC Press LLC