A Novel Solution to the ATT48 Benchmark Problem

Details A Novel Solution to the ATT48 Benchmark Problem A Novel Solution to the ATT48 Benchmark Problem

2007-10-02

arxiv.org/abs/0710.0539v1

Computer Science

Data Structures and Algorithms

Scientific paper

A solution to the benchmark ATT48 Traveling Salesman Problem (from the TSPLIB95 library) results from isolating the set of vertices into ten open-ended zones with nine lengthwise boundaries. In each zone, a minimum-length Hamiltonian Path (HP) is found for each combination of boundary vertices, leading to an approximation for the minimum-length Hamiltonian Cycle (HC). Determination of the optimal HPs for subsequent zones has the effect of automatically filtering out non-optimal HPs from earlier zones. Although the optimal HC for ATT48 involves only two crossing edges between all zones (with one exception), adding inter-zone edges can accommodate more complex problems.

Affiliated with

Also associated with

No associations

Rating

A Novel Solution to the ATT48 Benchmark Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Novel Solution to the ATT48 Benchmark Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Novel Solution to the ATT48 Benchmark Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7412