VEHICLE ROUTING PROBLEM IN PHYSICAL DISTRIBUTION USING GENETIC SEARCH

The effective use of truckload motor carriers is required. The investigators of this study examined the vehicle routing problem for supporting transportation systems. The vehicle routing problem involves determining minimum cost route for a vehicle originating and terminating from a certain location. This problem is known to be a prototypical NP-complete problem, and as a result heuristic procedures have been devised. Investigators also proposed a heuristic algorithm using a convex hull. Genetic algorithms (GAs) are proposed as a new learning paradigm for combinatorial optimization problems that models a natural evolution mechanism. In this paper, the authors attempt to apply GAs to the vehicle routing problem. The traditional crossover operators for GAs could fail to produce legal tours, and do not attach importance to the preservation of character for descendents. A new crossover operator is proposed based on adjacency relations. The GA using the new crossover operator is compared with the GA using the traditional crossover operator, a heuristic algorithm, and a branch-and-bound method. Some experiments are performed on digital road maps. The new GAs' solution are within 1.9 percent of the optimal solutions. Results show that the GA using the new crossover operation is clearly superior to the GA using the traditional crossover operator and the heuristic algorithm.

• Supplemental Notes:
  • Five volumes of papers and one volume of abstracts comprise the published set of conference materials.
• Corporate Authors:

  VERTIS

  TORANOMOM 34 MORI BUILDING 1-25-5
  TORANOMON, MINATOKU, TOKYO 105  Japan 
• Authors:
  • Uchimura, K
  • Sakaguchi, H
• Conference:
  • Steps Forward. Intelligent Transport Systems World Congress
  • Location: Yokohama, Japan
  • Date: 1995-11-9 to 1995-11-11
• Publication Date: 1995-11

Language

• English

Media Info

• Pagination: p. 2051

Subject/Index Terms

• TRT Terms: Algorithms; Costs; Crossovers; Heuristic methods; Intelligent transportation systems; Motor carriers; Optimization; Routes; Transportation
• Uncontrolled Terms: Transportation systems
• Geographic Terms: Japan
• Old TRIS Terms: Route analysis
• Subject Areas: Operations and Traffic Management; Transportation (General); I71: Traffic Theory;

Filing Info

• Accession Number: 00724451
• Record Type: Publication
• Report/Paper Numbers: Volume 4
• Files: TRIS
• Created Date: Aug 21 1996 12:00AM