Расчет расстояний в TSPLIB ⇐ Python

[Anonymous]

Здравствуйте, у меня проблема с расчетом расстояний между городами из библиотеки tsp: http://www.math.uwaterloo.ca/tsp/world/countries.html. У меня есть этот набор данных (города в Джибути): http://www.math.uwaterloo.ca/tsp/world/dj38.tsp. Я использовал эту функцию для расчета расстояний в этом QaA здесь: http://comopt.ifi.uni-heidelberg.de/sof ... SPFAQ.html. я запрограммировал это на Python, и теперь это выглядит так, вот мой код:

Код: Выделить всё

cityCoords = {
1:(11003.611100,42102.500000),
2:(11108.611100,42373.888900),
3:(11133.333300,42885.833300),
4:(11155.833300,42712.500000),
5:(11183.333300,42933.333300),
6:(11297.500000,42853.333300),
7:(11310.277800,42929.444400),
8:(11416.666700,42983.333300),
9:(11423.888900,43000.277800),
10:(11438.333300,42057.222200),
11:(11461.111100,43252.777800),
12:(11485.555600,43187.222200),
13:(11503.055600,42855.277800),
14:(11511.388900,42106.388900),
15:(11522.222200,42841.944400),
16:(11569.444400,43136.666700),
17:(11583.333300,43150.000000),
18:(11595.000000,43148.055600),
19:(11600.000000,43150.000000),
20:(11690.555600,42686.666700),
21:(11715.833300,41836.111100),
22:(11751.111100,42814.444400),
23:(11770.277800,42651.944400),
24:(11785.277800,42884.444400),
25:(11822.777800,42673.611100),
26:(11846.944400,42660.555600),
27:(11963.055600,43290.555600),
28:(11973.055600,43026.111100),
29:(12058.333300,42195.555600),
30:(12149.444400,42477.500000),
31:(12286.944400,43355.555600),
32:(12300.000000,42433.333300),
33:(12355.833300,43156.388900),
34:(12363.333300,43189.166700),
35:(12372.777800,42711.388900),
36:(12386.666700,43334.722200),
37:(12421.666700,42895.555600),
38:(12645.000000,42973.333300)
}

def calcCityDistances(coordDict):
cities = list(coordDict.keys())
n = len(cities)
distances = {}
latitude = []
longitude = []
RRR = 6378.388;
PI = 3.141592;

for i in range(1,n+1):
cityA = cities[i-1]
latA, longA = coordDict[cityA]
deg = int(latA)
Min = latA - deg
latitude.append(PI * (deg + 5 * Min / 3) / 180)
deg = int(longA);
Min = longA - deg;
longitude.append(PI * (deg + 5 * Min / 3) / 180)

for i in range(1,n+1):
for j in range(i + 1, n + 1):
q1 = cos(longitude[i-1] - longitude[j-1]);
q2 = cos(latitude[i-1] - latitude[j-1]);
q3 = cos(latitude[i-1] + latitude[j-1]);
key = frozenset((i, j))
distances[key] = {}
dist = RRR * acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0
distances[key]['dist'] = dist
distances[key]['pher'] = init_fer
distances[key]['vis'] = 0

return  distances

distances = calcCityDistances(cityCoords)

Моя проблема в том, что расстояния, рассчитанные с помощью этого алгоритма, не соответствуют действительности в огромном масштабе. средняя длина одного маршрута между городами составляет 10 000 км, и проблема в том, что оптимальный маршрут TSP равен 6635. Вы можете себе представить, что когда я применю это к алгоритму моей системы Ant Colony, результат составит около 110 000 км. это действительно отличается от 6 тысяч. Может кто-нибудь объяснить, что я делаю не так, пожалуйста?

Подробнее здесь: https://stackoverflow.com/questions/497 ... -in-tsplib