Search code examples
algorithmtraveling-salesman

Understanding EUC_2D edge weighting

I'm in the process of building a hyper heuristic framework for the travelling salesman problem.

I'm currently working from a cost matrix which looks like the following (excuse the PHP syntax):

("New York") => array(0, 2451,  713),
("Los Angeles") => array(2451,    0, 1745), 
("Chicago") => array( 713, 1745,    0),

This is fairly self explanatory, the Distance from NY to LA 2451, NY to Chicago 713.

I'm attempting to build a parser which parses EUC_2D edge weighting to the format I showed above. Problem is I can't get my head around the semantics of EUC_2D edge weighting.

An example of EUC_2D weighting is shown below (taken from here):

1 0 13
2 0 26
3 0 27
4 0 39
5 2 0
6 5 13
7 5 19
8 5 25
9 5 31
10 5 37

Can anyone explain how EUC_2D edge weighting works?

Solution

  • The example you mentioned contains list of cities on a map. Each row describes one city using 3 numbers.

    city_number - coordinate_x - coordinate_y

    So for example row

    60 28 43

    means, that city number 60 is located on the map with coordinates (28, 43).

    The distance between to cities A and B defined as

    A x1 y1
    B x2 y2

    is calculated using Eulidean distance rounded to the nearest whole number:

    dist(A, B) = round(sqrt((x1 - x2)^2 + (y1 - y2)^2))