Abstract

The Vehicle Routing Problem is an NP-complete problem that has been studied extensively since it was introduced in 1958 by G. B. Dantzig and J. H. Ramser. This thesis creates three algorithms that endeavor to find an optimal solution for each problem tested. Two of the algorithms (Simulated Annealing and Tabu Search) have been used previously to solve this problem. These two solution methods are revisited to discover whether a new approach to creating routes will produce the best-known optimal values every time. New routes are created by forming route neighborhoods and then selecting cities from these neighborhoods for insertion. The third algorithm is an original algorithm which combines Simulated Annealing and Tabu Search. The algorithms presented do not produce the best-known optimal values, but are competitive with previously published algorithms.

Department(s)

Computer Science

Comments

This report is substantially the M. S. thesis of the first author, completed December 1993

Report Number

CSC-93-35

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1993 University of Missouri--Rolla, All rights reserved.

Publication Date

01 Dec 1993

Download

Share

 
COinS