Date of Award

2000

Document Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Advisor

Dr. Albert C. Esterline

Abstract

This thesis presents an evolutionary algorithm (EA) to efficiently solve large instances of the time dependent travelling salesman problem (TDTSP). In this approach, the path the salesman must follow is structured as an ordered list of cities. The path may optionally have two kinds of constraints. Precedence constraints specify that a specific city must be visited before another specific city. "Time windows" specify the time at which specific cities must be visited. This work demonstrate that EAs are more effective than traditional methods, such as linear or dynamic programming, for solving general TDTSPs of up to 50 cities. This thesis also describes an improved dynamic programming heuristic that produces better solutions in less CPU time on TDTSPs of up to 400 cities.

Download

Share

COinS