เรื่องเล่าของ Travelling Salesman Problem (TSP) และ Ulysses16

เข้าใจว่าถ้าที่ปรึกษาได้แอบมาอ่าน Blog ก็จะคิดในใจว่า .. “ทำไมทำ (มัน) Thesis ไปไม่ถึงไหนสักที (วะ) ?” .. ก็พอจะเข้าใจได้เพราะก็แวะเวียนทุกที่ที่คิดว่าน่าสนใจ ตั้งแต่ 2 เดือนก่อนแล้ว DFS, BFS, Backtracking, Greedy, Dynamic Programming, Branch & Bound, .. และตอนนี้ ก็ถึง GA เสียที (หากมีเวลาจะกลับมาเก็บ Local Search, 2-OPT, Simulated Annealing, TABU อีกนะ)

แต่แน่นอน ไม่ว่าจะแนวคิดไหน Concept ใดก็ต้องมีที่มาที่ไป และข้อดีข้อเสียด้วยกันทั้งนั้น ก็เลยลองเขียน Branch & Bound สู้กับ GA (อ่อนๆ) สักตั้ง .. ดูซิว่าจะเป็นอย่างไร … ซึ่งก็แน่นอนว่าจะสู้กัน ก็ต้องมี Input เหมือนกัน ก็เลยหยิบ Ulysses16 มาลองเล่นดู … แต่เอ คุณ ‘อุลัย’ แกเป็นใคร ???? … เปิด wiki ก็พอได้ Idea ว่า อ้าว.. เทพนิยายมหากาพย์ Odessey นั่นเอง

ไม่เพียงเท่านั้น ยังได้

ประวัติ TSP

แถมมาด้วย จึงขอแปะไว้ก่อน เผื่อวันหลังอยากอ่านจะได้กลับมาดู

The Travelling Salesman Problem (TSP)

The travelling salesman problem is an optimization problem. Therefore it is not sufficient to find an arbitrary solution.
Instead, one is interested in the best (or at least a very good) solution.

The travelling salesman problem is quite simple: a travelling salesman has to visit customers in several towns, exactly one customer
in each town. Since he is interested in not being too long on the road, he wants to take the shortest tour. He knows the distance
between each two towns he wants to visit (The travel costs are symmetric in the sense that traveling from city X to city Y costs just
as much as traveling from Y to X; the “way of visiting all the cities” is simply the order in which the cities are
visited.) To put it differently, the data consist of integer weights assigned to the edges of a finite complete graph; the objective
is to find a hamiltonian cycle (that is, a cycle passing through all the vertices) of the minimum total weight. In this context,
hamiltonian cycles are commonly called tours.

The picture shows two possible tours for an example with five cities. For such a small example the problem is easy to solve. But
examples with 100 or 1000 cities show that a systematic search for a solution is very expensive. Let’s number the cities from 1
to n ,and let city 1 be the city-base of the salesman.Also let’s assume that c(i,j) is the visiting cost from i to j.There can be
c(i,j)<>c(j,i).Apparently all the possible solutions are (n-1)!.Someone could probably determine them systematically,find the
cost for each and everyone of these solutions and finally keep the one with the minimum cost.These requires at least (n-1)! steps.

If for example there were 21 cities the steps required are (n-1)!=(21-1)!=20! steps.If every step required a msec we would need about
770 centuries of calculations.Apparently,the exhausting examination of all possible solutions is out of the question.Since we are not
aware of any other quick algorithm that finds a best solution we will use a heuristic algorithm. According to this algorithm whenever
the salesman is in town i he chooses as his next city,the city j for which the c(i,j) cost,is the minimum among all c(i,k) costs,
where k are the pointers of the city the salesman has not visited yet.There is also a simple rule just in case more than one cities
give the minimum cost,for example in such a case the city with the smaller k will be chosen.This is a greedy algorithm which selects
in every step the cheapest visit and does not care whether this will lead to a wrong result or not.

So far, nobody was able to come up with an algorithm for solving the traveling salesman problem that does not show an exponential
growth of run time with a growing number of cities. There is a strong belief that there is no algorithm that will not show this
behaviour, but no one was able to prove this (yet). But one was able to prove that the traveling salesman problem is a kind of
prototypical problem for a big class of problems (the famous class NP) that show this exponential behaviour. This is the reason why
many reasearch groups are interested in the traveling salesman problem, since techniques developed for this problem can be transfered
to other problems of this class.

A Pictorial Survey of the History of the Traveling Salesman Problem

The origins of the TSP are obscure. In the 1920’s, the mathematician and economist Karl Menger publicized it among his colleagues
in Vienna. In the 1930’s, the problem reappeared in the mathematical circles of Princeton. In the 1940’s, it was studied by
statisticians (Mahalanobis (1940), Jessen (1942), Gosh (1948), Marks (1948)) in connection with an agricultural application and the
mathematician Merill Flood popularized it among his colleagues at the RAND Corporation. Eventually, the TSP gained notoriety as the
prototype of a hard problem in combinatorial optimization: examining the tours one by one is out of the question because of their
large number, and no other idea was on the horizon for a long time.

  • A breakthrough came when George Dantzig, Ray Fulkerson, and Selmer Johnson (1954) published a description of a method for solving
    the TSP and illustrated the power of this method by solving an instance with 49 cities, an impressive size at that time. They created
    this instance by picking one city from each of the 48 states in the U.S.A. (Alaska and Hawaii became states only in 1959) and adding
    Washington, D.C.; the costs of travel between these cities were defined by road distances. Rather than solving this problem, they
    solved the 42-city problem obtained by removing Baltimore, Wilmington, Philadelphia, Newark, New York, Hartford, and Providence. As
    it turned out, an optimal tour through the 42 cities used the edge joining Washington, D.C. to Boston; since the shortest route
    between these two cities passes through the seven removed cities, this solution of the 42-city problem yields a solution of the
    49-city problem.
  • Proctor and Gamble ran a contest in 1962. The contest required solving a TSP on a specified 33 cities. There was a tie between
    many people who found the optimum. An early TSP researcher, Gerald Thompson, was one of the winners.
  • Groetschel (1977) found the optimal tour of 120 cities from what was then West Germany.
  • Padberg and Rinaldi (1987) found the optimal tour of 532 AT&T switch locations in the USA.
  • Groetschel and Holland (1988) found the optimal tour of 666 interesting places in the world.
  • Applegate, Bixby, Chvatal, and Cook (1998) found the optimal tour of the 13,509 cities in the USA with populations > 500.

และสำหรั
ตัวอย่าง LIBTSP ที่ใช้ทดสอบ .. พร้อมผลเฉลย

An example from;

Odyssey of Ulysses (Groetschel and Padberg)

NAME: ulysses16.tsp

TYPE: TSP

COMMENT: Odyssey of Ulysses (Groetschel/Padberg)

DIMENSION: 16

EDGE_WEIGHT_TYPE: GEO

DISPLAY_DATA_TYPE: COORD_DISPLAY

NODE_COORD_SECTION

1 38.24 20.42

2 39.57 26.15

3 40.56 25.32

4 36.26 23.12

5 33.48 10.54

6 37.56 12.19

7 38.42 13.11

8 37.52 20.44

9 41.23 9.10

10 41.17 13.05

11 36.08 -5.21

12 38.47 15.13

13 38.15 15.35

14 37.51 15.17

15 35.49 14.32

16 39.36 19.56

Optimal solution for the problem:

NAME : ulysses16.opt.tour

COMMENT : Optimal solution for ulysses16 ( 6859 )

TYPE : TOUR

DIMENSION : 16

TOUR_SECTION

1 14 13 12 7 6 15 5 11 9 10 16 3 2 4 8

-1

http://www.macmes.com/konugoster.asp?id=5256

ปัญหาที่มักพบกัน .. Coordinate System แบบ GEO

จาก http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html

Q: I get wrong distances for problems of type GEO.

A: There has been some confusion of how to compute the distances. I use the following code.

Let x[i] and y[i] be coordinates for city i in the above format. First the input is converted to geographical latitude and longitude given in radians.

PI = 3.141592;
deg = nint( x[i] );
min = x[i] – deg;
latitude[i] = PI * (deg + 5.0 * min / 3.0 ) / 180.0;

deg = nint( y[i] );
min = y[i] – deg;
longitude[i] = PI * (deg + 5.0 * min / 3.0 ) / 180.0;

The distance between two di erent nodes i and j in kilometers is then computed as follows:

RRR = 6378.388;
q1 = cos( longitude[i] – longitude[j] );
q2 = cos( latitude[i] – latitude[j] );
q3 = cos( latitude[i] + latitude[j] );
dij = (int) ( RRR * acos( 0.5*((1.0+q1)*q2 – (1.0-q1)*q3) ) + 1.0);

เพราะว่าระยะทางไม่ได้ผ่านถึงกันแบบเส้นตรง แต่จะโค้งตามผิวโลก อ้างอิงจาก TSPLIB95 ซึ่งยังพบบาง blog ก็พูดถึงประเด็นนี้เหมือนกัน http://www.neverreadpassively.com/2008/05/tsplib-library-of-standard-tsp.html

Del.icio.us : , , ,
Technorati : , , ,

Advertisements

2 thoughts on “เรื่องเล่าของ Travelling Salesman Problem (TSP) และ Ulysses16

  1. จาก FAQ

    2.4 Geographical distance
    If the traveling salesman problem is a geographical problem, then the nodes correspond to
    points on the earth and the distance between two points is their distance on the idealized
    sphere with radius 6378.388 kilometers. The node coordinates give the geographical lat-
    itude and longitude of the corresponding point on the earth. Latitude and longitude are
    given in the form DDD.MM where DDD are the degrees and MM the minutes. A positive lati-
    tude is assumed to be \North”, negative latitude means \South”. Positive longitude means
    \East”, negative latitude is assumed to be \West”. For example, the input coordinates for
    Augsburg are 48.23 and 10.53, meaning 48
    o
    23 North and 10
    o
    53 East.

    Let x[i] and y[i] be coordinates for city i in the above format. First the input is converted
    to geographical latitude and longitude given in radians.
    PI = 3.141592;
    deg = nint( x[i] );
    min = x[i] – deg;
    latitude[i] = PI * (deg + 5.0 * min / 3.0 ) / 180.0;
    deg = nint( y[i] );
    min = y[i] – deg;
    longitude[i] = PI * (deg + 5.0 * min / 3.0 ) / 180.0;

    The distance between two di erent nodes i and j in kilometers is then computed as follows:

    RRR = 6378.388;
    q1 = cos( longitude[i] – longitude[j] );
    q2 = cos( latitude[i] – latitude[j] );
    q3 = cos( latitude[i] + latitude[j] );
    dij = nint( RRR * acos( 0.5*((1.0+q1)*q2 – (1.0-q1)*q3) ) + 1.0);

    The function \acos” is the inverse of the cosine function

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s