Accession Number:

ADA179992

Title:

Addressing the Travelling Salesman Problem through Evolutionary Adaptation

Descriptive Note:

Interim rept. Apr-Jul 1986

Corporate Author:

TITAN CORP LA JOLLA CA TITAN SYSTEMS INC

Personal Author(s):

Report Date:

1987-01-01

Pagination or Media Count:

38.0

Abstract:

The optimization of the traveling saleman problem continues to receive attention for three reasons 1 its solution is computationally difficult although the algorithm itself is easily expressed 2 it is broadly applicable to a variety of engineering problems and 3 it has become somewhat of a comparison benchmark problem. The task is to arrange a tour of n cities such that each city is visited only once and the length of the tour or some other cost function is minimized. For an exact solution the only known algorithms require the number of steps to grow at least exponentially with the number of elements in the program. Brute force methods of finding of the shortest path by which a traveling salesman can complete a tour of n cities requires compiling a list of n-1 alternative tours, a number that grows faster than any finite power of n. The task quickly becomes unmanageable.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE