TSP using Kaggle's World Cities dataset https://www.kaggle.com/datasets/juanmah/world-cities verifying the tour found by GPT-4 in https://docs.google.com/document/d/1IrcK1FfcEfq2NzHfQD0UGUar-w7jfwG1Q7-EHOSpbW4/edit via https://twitter.com/JFPuget/status/1653148628335075330

gpt4_tour_check.py

import folium
import numpy as np
import pandas as pd
from python_tsp.exact import solve_tsp_dynamic_programming
from sklearn.metrics import DistanceMetric

cities = ["London", "Paris", "Madrid", "Berlin", "Rome"]
print("Cities:", cities, "\n")
# Source: https://www.kaggle.com/datasets/juanmah/world-cities
df = pd.read_csv("worldcities.csv")
df = df[df.city.isin(cities) & (df.capital == "primary")]
idx2city = dict(enumerate(df.city))
print("Capitals:\n", df, "\n")

xy = np.radians(df[["lat", "lng"]].values)
dist = DistanceMetric.get_metric("haversine")
geo_radius = 6371000 / 1000
dist_matrix = dist.pairwise(xy) * geo_radius
# print("Distance matrix:\n", dist_matrix)

tour_perm, tour_dist = solve_tsp_dynamic_programming(dist_matrix)
optimal_tour = df.city.iloc[tour_perm].tolist()


def verify_tour_length(dist_matrix, tour_result, verbose=False):
    tour_dists = []
    for i, current_city in enumerate(tour_result):
        current_city = tour_result[i]
        next_city = tour_result[(i + 1) % len(tour_result)]
        step_dist = dist_matrix[current_city][next_city]
        tour_dists.append(step_dist)
        if verbose:
            print(f"{idx2city[current_city]} -> {idx2city[next_city]} = {step_dist}")
    return sum(tour_dists)


pytsp_city_tour = [idx2city[i] for i in tour_perm]
print("Optimal tour:", pytsp_city_tour)
print("Total distance:", tour_dist)
checked_length = verify_tour_length(dist_matrix, tour_perm)
print("Verified distance:", checked_length)

alt_tour = "London Paris Madrid Rome Berlin".split()
print(f"Found same tour: {pytsp_city_tour == alt_tour}")

show = False
use_alt = False

if use_alt:
    tour = [cities.index(c) for c in alt_tour]
else:
    tour = tour_perm

if show:
    # Create a map centered at the first city in the tour
    m = folium.Map(
        location=[df.iloc[tour[0]].lat, df.iloc[tour[0]].lng],
        zoom_start=5,
    )

    # Add markers for each city
    for i, row in df.iterrows():
        folium.Marker(location=[row.lat, row.lng], tooltip=row.city).add_to(m)

    # Create a list of coordinates for the tour
    coords = [[df.iloc[i].lat, df.iloc[i].lng] for i in tour] + [
        [df.iloc[tour[0]].lat, df.iloc[tour[0]].lng]
    ]

    # Draw the tour on the map
    folium.PolyLine(coords, color="red").add_to(m)

    # Display the map
    m.show_in_browser()

requirements.txt

folium
numpy
pandas
python-tsp
scikit-learn

Cities: ['London', 'Paris', 'Madrid', 'Berlin', 'Rome'] 

Capitals:
        city city_ascii      lat      lng         country iso2 iso3       admin_name  capital  population          id
35   London     London  51.5072  -0.1275  United Kingdom   GB  GBR  London, City of  primary  11262000.0  1826645935
36    Paris      Paris  48.8567   2.3522          France   FR  FRA    Île-de-France  primary  11060000.0  1250015082
88   Madrid     Madrid  40.4169  -3.7033           Spain   ES  ESP           Madrid  primary   6211000.0  1724616994
159  Berlin     Berlin  52.5200  13.4050         Germany   DE  DEU           Berlin  primary   4473101.0  1276451290
281    Rome       Rome  41.8931  12.4828           Italy   IT  ITA            Lazio  primary   2872800.0  1380382862 

Optimal tour: ['London', 'Paris', 'Madrid', 'Rome', 'Berlin']
Total distance: 4874.6003609154095
Verified distance: 4874.6003609154095
Found same tour: True

GPT-4's answer:

The shortest route is London -> Paris -> Madrid -> Rome -> Berlin -> London, with a total distance of:
344 + 1053 + 1365 + 1186 + 932 ≈ 4880 km