NUS HomeTSP
Home | Up


Results on Traveling Salesman Problem

Problem Definition

The Traveling Salesman Problem is the problem of a salesman who wants to find a shortest possible trip: (1). starting from his home town, (2). go through a given set of customer cities, and (3). return to his home town.

 

Formally, TSP can be represented by a complete weighted graph G=(V,E) with V being the set of vertices, representing the cities, and E the set of edges fully connecting the vertices. Each edge is assigned a value d<i-j>, which is the distance between vertex i and j, with i and j element of V. Then, TSP is the problem of finding a minimal length Hamiltonian circuit of the graph, where a Hamiltonian circuit is a closed tour visiting exactly once each of the vertices of G. For symmetric TSP, the distances between the cities are independent of the direction of traversing the edges, that is, d<i-j>=d<j-i> for every pair of nodes. In the more general asymmetric TSP (ATSP) at least for one pair of nodes (i,j) we have d<i-j>!=d<j-i>.

Some example of TSP Instances

Benchmark TSP instances can be found in TSPLIB.
Here are some examples of TSP instances based on the distribution of cities.


Left to right: gil262 (random spread), d198 (several clusters), pr107 (grid pattern), tsp225 (grid pattern).

 

Fitness Landscape and Search Trajectory Analysis

 

Observable characteristics of TSP fitness landscape:

-. There exist "Big Valley" characteristic in various (if not all) TSP instances where good solutions are clustered near to each other, and there is only "one" such cluster.

-. This is quite logical as good (near optimal) TSP solutions are generally share a lot number of similar edges.

-. When the best found solution is placed in the center of the screen, then other blue circles (good), green triangles (medium), and yellow rectangles (bad) are encircling it, with the black dots (very bad) further outside.
 

TSP Fitness Landscape, zoomed out

The same landscape, zoomed in

Observable behavior of Iterated Local Search (ILS):

1. TSP-ILS (vdf) on lin105 (TSPLIB)

The standard TSP-ILS manages to find position near the best found solution, but once it is trapped in a (deep) local optima, its standard perturbation fails to bring the ILS out of that region. The search is trapped. The final best solution reported by the ILS will be the local optima in this unfortunate search region. This phenomenon is also observed using Run Time Distribution (RTD) - a stagnation.

 


 

2. TSP-ILS-T (vdf) on lin105 (TSPLIB)

The tuned TSP-ILS-T (Tuned) is TSP-ILS, but this time, after certain number of iterations elapsed without improvement, force a stronger diversification (much stronger than the ILS perturbation strength) to force it escape from the current search region. The ILS will end up in different place somewhere near the best found solution and resume from there. This TSP-ILS-T has higher potential to hit the best found solution than TSP-ILS.

 

References

These results are reported in more details in our publications (download the local copy of those papers here):

  1. S. Halim, R. Yap, H.C. Lau. An Integrated White+Black Box Approach for Designing and Tuning Stochastic Local Search. In Principles and Practice of Constraint Programming (CP 2007, Providence, Rhode Island, USA, September 23-27, 2007): 332-347

  2. S. Halim, R. Yap, H.C. Lau. Viz: A Visual Analysis Suite for Explaining Local Search Behavior. In User Interface System and Technology (UIST 2006, Montreux, Switzerland, October 15-18, 2006): 57-66

This document, results_tsp.html, has been accessed 3902 times since 05-Sep-08 17:52:03 SGT. This is the 2nd time it has been accessed today.

A total of 2003 different hosts have accessed this document in the last 3387 days; your host, 54.82.79.109, has accessed it 1 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.