Using ChatGPT to find the shortest travel routes between cities

Photo by Dennis Kummer on Unsplash

This is a benchmark:

I asked chatGPT using GPT4 these 2 prompts, one after the other and I let it keep generating a response until it didn’t want to continue generating anything else:

give me the code for the Held-Karp algorithm in python to calculate the shortest distance to travel between cities given their longitudes and latitudes

Followed by the prompt:

can you make it so the output shows the names of the cities

Disclaimer:

The code being used to benchmark these routes was generated by chatGPT4 as well, I haven’t done extensive efforts to make sure that this benchmarking algorithm is accurate. Instead I simply compared if its calculations between 2 points were equal to this distance calculator that uses latitudes and longitudes: https://www.omnicalculator.com/other/latitude-longitude-distance

Distance between New York and Mexico City (2 locations):
> Omni calculator: 3360.292
> Python algorithm by chatGPT4: 3358.6003067555275 kilometers
> Deviance from Omni: -0.05034% (99.9496563619% of Omni’s)

Travel distance between New York, Mexico City and Sydney (3 locations):
> Omni calculator: 16336.064 km
> Python algorithm by chatGPT4: 16335.465646981818 kilometers
> Deviance from Omni: -0.00366277346% (99.996337226% of Omni’s)

From these results, for practical purposes we will assume that the python benchmarking tool generated by chatGPT4 is about 99.94% accurate.

Benchmark:

1. Route generated by ChatGPT using GPT4, this route was inside a python script that it generated:
   route = [‘New York’, ‘Mexico City’, ‘Fairbanks’, ‘Sydney’, ‘Berlin’, ‘Stockholm’, ‘Moscow’]
   Without return: 39,824.43892207613 km
   With return: 47,356.6765821295 km
2. Bing route when asked in Spanish:
   route = [‘New York’, ‘Mexico City’, ‘Fairbanks’, ‘Moscow’, ‘Stockholm’, ‘Berlin’, ‘Sydney’]
   Without return: 34,290.5484911622 km
   With return: 50,284.72969232206 km
3. Route I created manually (nearest distance each time):
   route = [‘New York’, ‘Mexico City’, ‘Fairbanks’,’Stockholm’, ‘Berlin’, ‘Moscow’, ‘Sydney’]
   Without return: 32,628.19678166211 km
   With return: 55,818.6201232 km
4. Route using the Held-Karp algorithm with return to New York, script generated by GPT4:
   route = [‘New York’, ‘Berlin’, ‘Stockholm’, ‘Moscow’, ‘Fairbanks’, ‘Sydney’, ‘Mexico City’]
   Without return: 40,201.49023855159 km
   With return: 43,560.09054530712 km
5. Route generated by OR Tools by another user (Jack Freeman):
   route = [‘New York’, ‘Mexico City’, ‘Sydney’, ‘Fairbanks’, ‘Moscow’, ‘Stockholm’, ‘Berlin’]
   Without return: 37,157.45952747315 km
   With return: 43,560.090545307125 km

Conclusion:

The Traveling salesman problem (TSP) is a fascinating problem. And even more fascinating is that GPT4 via ChatGPT can generate fairly good solutions intuitively, however, these solutions aren’t optimal.

On the plus side, chatGPT4 hints us towards more efficient algorithms that we should use like Held-Karp’s algorithm. We tasked it with generating the python code for that algorithm, and it failed at it.

After failing to generate the appropriate code, we opened a new chat, where we tasked it to generated Held-Karp’s algorithm in python.

This time, it did successfully generate a working algorithm in python. I’m still looking to test this code more, to see if it’s actually Held-Karp’s algorithm, or as efficient as Held-Karp’s. The python code and installation that chatGPT4 proposed worked, without having to edit them or debug them.

These are the results from the benchmark:

Best at the shortest round trip:

There is a tie between the Held-Karp algorithm generated by chatGPT4, and Jack Freeman’s using OR Tools. The round-trip route we found in a python code that chatGPT4 generated intuitively would rank 3rd best solution, and make the trip 2.2Km longer than the best route in this benchmark.

Best at the shortest one-way trip:

From this benchmark, traveling to the closest city each time is the shortest way to do a one-way trip, which I manually coded. Interestingly Bing chat in Spanish would rank 2nd in this benchmark with the route it generated. Taking about 2 extra kilometers of travel.

Links:

Links to python code:

• Original script that chatGPT4 generated to calculate distances using: geopy.distance:
  https://www.pythonmorsels.com/p/3bjvp/
• Final script it generated “using the Held-Karp algorithm” (the most efficient algorithm that I benchmarked for round-trips from these tests):
  https://www.pythonmorsels.com/p/2xtcj/

Link to chats with chatGPT:

1. Chat where it generates the Held-Karp algorithm:
   https://chat.openai.com/share/e1cb0644-a473-4b29-9c1b-282e3e142524
   [Link to archived chat at: archive.org]
2. Chat where it generates a benchmarking algorithm and is given the problem at hand:
   https://chat.openai.com/share/66c77836-7f64-4b60-b157-a58431f54f3d
   [Link to archived chat at: archive.org]