Please add support for EDGE_WEIGHT_TYPE : GEOM

[IngvarX]

Hello! Thanks for your library, I'm using tsplib95-0.7.1. Could you please add support for EDGE_WEIGHT_TYPE : GEOM in tsp files, like in world.tsp. Right now tsplib95 throws an error when I try to load such file:

KeyError: 'GEOM'

[rhgrant10]

Hey, thank you - glad you find it useful :)

The KeyError happens in your case because the problem specifies EDGE_WEIGHT_TYPE: GEOM but GEOM isn't a valid option according to the spec. I'm guessing it's supposed to be GEO?

[rhgrant10]

Also, I think the error message here doesn't really help point you to the problem very well, so I'll improve that for the next version 👍

[IngvarX]

Changing GEOM to GEO worked for me. Seems that world tsp file is not valid according to spec. Mb it's better to interpret GEOM as similar to GEO in code?

[rhgrant10]

Excellent - glad it's working for you.

While I want to agree, that's a pretty slippery slope. What about GEOS? Maybe GEOG? Or how about GEOGRAPHIC? I think instead it's easier if we just correct files that don't adhere to the spec :)

[IngvarX]

In this case you can check GEO substring 😃 I agree that incorrect files should be corrected. The only reason that I see to add GEOM is to save time for people who will download same tsp file in future. www.math.uwaterloo.ca tsp files collection is the most popular one so probably someone will face same problem 😄

[rhgrant10]

Okay, so I visited the site and read about the World TSP challenge at http://www.math.uwaterloo.ca/tsp/world/. It says:

Each of the cities is specified by its latitude and longitude, given in decimal form (rather than minutes and seconds). The cost of travel between cities is specified by an approximation to the great circle distance on the Earth (treating the Earth as a ball). This cost function is a variation of the TSPLIB GEO-norm, adjusted to handle decimal degrees and scaled to provide the distance in meters rather than in kilometers. We call this cost function the GEOM-norm; a fragment of C-code to compute the travel costs can be found here.

That lists some C code for calculating GEOM distances:

#undef M_PI
#define M_PI 3.14159265358979323846264

int geom_edgelen (int i, int j, CCdatagroup *dat)
{
     double lati, latj, longi, longj;
     double q1, q2, q3, q4, q5;

     lati = M_PI * dat->x[i] / 180.0;
     latj = M_PI * dat->x[j] / 180.0;

     longi = M_PI * dat->y[i] / 180.0;
     longj = M_PI * dat->y[j] / 180.0;

     q1 = cos (latj) * sin(longi - longj);
     q3 = sin((longi - longj)/2.0);
     q4 = cos((longi - longj)/2.0);
     q2 = sin(lati + latj) * q3 * q3 - sin(lati - latj) * q4 * q4;
     q5 = cos(lati - latj) * q4 * q4 - cos(lati + latj) * q3 * q3;
     return (int) (6378388.0 * atan2(sqrt(q1*q1 + q2*q2), q5) + 1.0);
}

So this is actually a GEOM problem and they're distinct from GEO problems. The trouble is I haven't provided a good way for you to use a custom "predefined" distance function like GEOM. However, it can be done. Instructions below.

Obviously, the first thing you'll want to do is translate that C code into a Python function. Next, you need to add it to the map of EDGE_WEIGHT_TYPEs to distance functions. Afterwards, you can load your GEOM problem and it should find and use the custom function instead of producing a KeyError.

All together, it should look something like this:

import math
import tsplib95

def geom_edgelen(a, b):
    lat_i = math.PI * a / 180.0
    ...
    return int(6378388 * math.atan2(math.sqrt(q1 * q1 + q2 * q2), q5) + 1)

# make sure we do this before we try to load the problem
tsplib95.distances.TYPES['GEOM'] = geom_edgelen

problem = tsplib95.load('path/to/world.tsp')