# Around The World In 80 Hours: An Optimization Competition

## Update:

Results are now posted! They can be viewed here.

Last week, we were happy to see that this question about efficiently routing a UPS delivery was a challenge to the community. It inspired us to ramp up the problem and throw a quick mini competition to see who could find the shortest possible route for a worldwide delivery.

## The Setup

As part of a promotion to demonstrate their global service, UPS has decided to ship a single package around the world to hundreds of different cities. Help them plot a route that will minimize its travel distance. The journey must be a complete circuit; in other words, you must begin and end in the same location, and you must visit each city in the list.

LIST OF CITIES

Note: Make the simplifying assumption that the earth is a sphere with a radius of 6371 kilometers. There is a problem here about finding distances on a spherical earth, if you want a test case.

## How Do I Enter The Competition?

This is a time limited competition, so submit your answer by 11:59 PM GMT on 1/26/2014 to this form.

The following are required for a complete submission:

3. The total distance of the journey (in km).
4. A list of the cities’ index numbers, sorted in your optimal order.
5. A copy of your code.

## How Do I Win?

The person who submits original code that generates the shortest route linking all of the cities wins. Ties will be broken based on who submitted their answer first.

## What are the Prizes?

Grand Prize: The winner will receive a brand new Android tablet, a winner’s certificate, a Brilliant.org t-shirt, and some secret awesomeness.

Honorable Mentions: The runner-up as well as other notable submissions (as judged by Brilliant staff) will receive certificates and Brilliant.org t-shirts.

Feel free to comment or ask questions below.

Good luck!

Note by Peter Taylor
7 years, 2 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Hi everybody. I just wanted to check in. We will be announcing the winner, the runner up and the honorable mentions in a separate note within the next day. Feel free to discuss your approaches all you want. We are currently reviewing people's codes to pick out our honorable mentions. Thanks for participating!

Staff - 7 years, 2 months ago

Any update on this?

- 7 years, 2 months ago

Sorry about the delay,I have posted the results right here.

Staff - 7 years, 2 months ago

hello can u please change my name to asdfgh rfvcm

- 5 years, 9 months ago

This sounds really fun! Unfortunately my knowledge of the Travelling Saleman problem and how to optimize it is far too minimal for me to enter this competition (not to mention my abysmal coding skills), but good luck to anyone who joins!

- 7 years, 2 months ago

"How Do I Win? The person who submits original code that generates the shortest route linking all of the cities wins. Ties will be broken based on who submitted their answer first."

In my opinion this is an extremely bad way to break ties. It should be based on which solution runs the fastest. (otherwise they could create an extremely slow bruteforce program to do this)

- 7 years, 2 months ago

Seems hard to submit first (or ever) with a brute force approach to this problem.

Staff - 7 years, 2 months ago

You can use some other program to find the value. Then you submit the brute force program. Obviously, this isn't going to work.

- 7 years, 2 months ago

That means the submitter would have to trick Brilliant.org into thinking that they have access to a computer the likes of which has never been seen, if their brute force program were to actually finish in time for the contest. I think you have to give Brilliant more credit than that!

Staff - 7 years, 2 months ago

Try sorting them first and then go on to make a cycle

- 7 years, 2 months ago

False. I thought of a brute-force algorithm right away when I saw this.

- 7 years, 2 months ago

good luck trying to check most of 300! possibilities

- 7 years, 2 months ago

A certain person named Shwandrew Patian told me that O(n!) would be fast for n<10000.

- 7 years, 2 months ago

Well, they were wrong. Your typical computer can do a couple billion calculations per second. I doubt if you can find a calculator that'll even tell you what 300! is, let alone 10000! :)

- 7 years, 2 months ago

My TI-89 just informed me what the value of $300!$ is (something like $306057512216440636......\leftarrow$ not the full value)

- 7 years, 2 months ago

In any case, my TI-84 won't manage it :) Still, even that's far outside any sort of reasonable time limit for this problem, and 10000! is just plain insane.

- 7 years, 2 months ago

300! is only 306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000

10000! is only 10000!

Staff - 7 years, 2 months ago

Nice. What did you use to create that?

- 7 years, 2 months ago

I use Mathematica but you could have WolframAlpha compute it (for free) as well.

Staff - 7 years, 2 months ago

Nice :) I suppose that rules out O(n!) for n = 10000.

- 7 years, 2 months ago

hmm I thought he was better than that... probably trolling.

- 7 years, 2 months ago

How long did it take to finish?

Staff - 7 years, 2 months ago

I did not try it. I am not participating. I suspect though that if I leave it on at a university computer, it should take a time $t > T$, where $T$ is the time the contest is open.

P.S. (there is no private message system on Brilliant) I know this is off-topic, but is there any way to contact you besides Brilliant, Josh? I know you may not like to share your e-Mail but I have a special question for you, which should be kept private.

- 7 years, 2 months ago

I think we agree, if someone does try a brute force solve, it won't finish by the time the contest is finished.

Sure, send me a message at: josh_ahaan@hmamail.com

Staff - 7 years, 2 months ago

Thanks; I'll e-Mail you within the next couple of days! Wow, a special e-Mail address for me. :P

- 7 years, 2 months ago

it will self destruct 6 days from now! if you don't have the message yet just email me there and we can talk using my non self-destructing email address.

Staff - 7 years, 2 months ago

I am e-Mailing you later today!

- 7 years, 2 months ago

it's an anonymous disposable email lol

- 7 years, 2 months ago

I agree. Someone can just use a built in algorithm (I'm sure there are many) to find the answer and just post a code where it just checks all possible cases.

- 7 years, 2 months ago

Also, you could do the problem beforehand and just print the answer.

- 7 years, 2 months ago

On the bright side, someone who submits late, but gets it right and has a really neat algorithm might get honorable mention :)

- 7 years, 2 months ago

I can't agree more with this. Some people have commitments on Saturdays or commitments on Sundays or both and it is hard to pin ties down to who submits first. Time zone issues have been a problem in the past on Brilliant but they have been resolved. I hope, for the sake of those participating, that this is taken as seriously. Again, I am not participating, so good luck to the others!

- 7 years, 2 months ago

There's also a very large chance that someone's already won.

- 7 years, 2 months ago

I've reformatted the list to a JSON file, available here for anyone who could find it useful (I'll try to solve it via AS3, so JSON files suit better)

- 7 years, 2 months ago

Nice work done. Now, I have replaced my ugly code of reading that file with this nice looking reformatted one.

Thanks a lot and good luck.

- 7 years, 2 months ago

can i submit solution more than once ?

- 7 years, 2 months ago

When are you going to release the results?

- 7 years, 2 months ago

This is enraging! The best I could do is 258999 km, which seems horrible. I feel if I just put tacks on a styrofoam ball and used yarn to eyeball it, I should be able to do it so much better.

- 7 years, 2 months ago

I've just managed to solve the problem. I used a bunch of pre-processing and 3rd party tools thus the source code is something not well defined. I don't know if this is OK with the rules. What should I post exactly in this case and is it allowed to solve the issue with my approach?

Edit: as the competition is over :) let me plot my proposal:

- 7 years, 2 months ago

Nice use of Google Maps API! This is my route, found using some messy Python code I hacked together:

tehmap

If anyone else wants to plot their routes, check out this handy Google Maps API example code

- 7 years, 2 months ago

Assuming optimal tour should have the same length even if different permutation is used is it possible the difference in the solutions to be due to rounding issues (or one of them is not optimal :) )? It will be interesting to recalculate the distances and check this but our jury certainly will do it :).

- 7 years, 2 months ago

It is very hard to calculate the most optimal travelling salesman tour. I am certain that mine is not optimal, as I actually used quite a naive algorithm.

- 7 years, 2 months ago

I've managed to prove that the optimal tour is at least 189858.4 km long

- 7 years, 2 months ago

Cost of the minimum spanning tree?

- 7 years, 2 months ago

The cost of the minimum spanning tree + the maximum remoteness (I define the remoteness of a city as the distance to the closest other city). Turns out that city is Honolulu with remoteness of 3690.1 km.

- 7 years, 2 months ago

I personally think that this competition should have been formulated as the winner solution is the one that can produce the shortest tour among all the participants. This way we would develop heuristic algorithms and the fun would be great :). I understood the goal is to find the optimal tour and this algorithm is not possible to be created from scratch for two days so I used the time to investigate which are the top achievements and adopted one of them which is not heuristic algorithm but should be exact. However, the difference above should mean I've done some mistake in the formulas. We'll see :). I cannot wait for some feedback from the staff :)

- 7 years, 2 months ago

That's what it is about, maybe you misunderstood "The person who submits original code that generates the shortest route linking all of the cities wins. ". Shortest - as in shorter than anyone else's.

- 7 years, 2 months ago

You might be right. Anyway, the problem is too famous and there are too many implementations available such as Lin Kernighan algorithm which cannot be beaten easily (if possible at all).

- 7 years, 2 months ago

The Lin Kernighan heuristic is far from optimal. It is a heuristic, which means by definition it makes assumptions that sacrifice optimality, but give a "good enough" result in most cases. Plus, LK is a local search, which means it can get stuck in local minima. I'm curious as to which software package you borrowed to do this task? Also, feel free to check my tour length if you want to ensure it has no rounding errors: http://pastebin.com/dvrz6XPr

- 7 years, 2 months ago

Oh gosh, your tour is zero-indexed!

- 7 years, 2 months ago

Ah, whoops. Thanks for catching that. I think I fixed that when I submitted.

- 7 years, 2 months ago

I used mainly the Concord library from TSPLIB project.

P.S LK is not so far from optimum in the general case. For this problem my test gave difference a few hundred km only.

- 7 years, 2 months ago

I agree with that! In the spirit of true programming, I wrote my own solution from scratch in C++ and brought my length down to 218,667 km. Still didn't beat you two but a very good score in my opinion. I'll publish it if anyone is interested.

- 7 years, 2 months ago

If a laptop could check one billion arrangements per second, it would only take about $\displaystyle \frac{300!}{24\times 60\times 60\times 10^9} \approx 3.54 \times 10^{600}$ days for the brute force algorithm to finish.

Staff - 7 years, 2 months ago

Good Luck to everyone who is participating as I am a highly stupid and dismal programmer.

- 7 years, 2 months ago

Downvoted for the low self-esteem. Modesty is good but underconfidence is not. Be confident and try things!

- 7 years, 2 months ago

Awesome!! This sounds so cool! Will try to go for the kill :D

- 7 years, 2 months ago

Just wanted to know how's everybody doing. With the given order of cities I am getting the distance of about 2 million km if travelled in that order. So far I have managed to reduce it to 1 million km using a different route. Just to make sure that I am going in the right direction, can anyone tell me what's the distance they are getting of the trip if they went through cities in the order mentioned in the List of Cities.

All the best to everyone!

- 7 years, 2 months ago

I get 1978459 km for that tour.

- 7 years, 2 months ago

1978459.5589

Staff - 7 years, 2 months ago

I got about 10,000km less than that... is that an issue? could it have something to do with the precision of doubles in c++?

- 7 years, 2 months ago

i'm not sure about that. here is a list of the distances i calculate between each pair of cities in the list as given: http://pastebin.com/yus6TChg

Staff - 7 years, 2 months ago

I did forget, actually... thanks for pointing that out

- 7 years, 2 months ago

Yep, me too getting the distance of about 2 million km if travelled in order. Good luck! :D

- 7 years, 2 months ago

Question: Sorry if I sound like a hollow cylinder. As somebody who is not participating, it should sound rather rare for me to ask this question, that too when the competition is in progress, but when will the results and winning code be declared? I'd really like to see the cheekiest algorithm out there. :)

- 7 years, 2 months ago

Hi Brilliant. Fun idea—I look forward to future competitions. There's an issue this time with the choice of challenge—it's frustratingly difficult to parse the input file, then the actual maths puzzle is a famous problem for which good algorithms and excellent libraries exist online. No-one designing an algorithm or coding from scratch is likely to beat them.

Anyway, I'm sure these problems can be rectified in future competitions. Thank you for hosting this one.

- 7 years, 2 months ago

I can't second this enough. Both brilliant competitions I've looked into have been very bizarre.

- 7 years, 2 months ago

i like it.

- 7 years, 2 months ago

great i will try to achieve target

- 7 years, 2 months ago

i like challenges ... and i feel happy achieving them... i will surely participate ......

- 7 years, 2 months ago

Should the submission be zero- or one-indexed?

- 7 years, 2 months ago

My thoughts :

A purely formal / theoretical approach would possibly try to fit a least squares great circle on the sphere that minimizes the sum of squared distances from the above to each of these points. Alternatively, if one tries to minimize the maximum deviation etc, one would possibly be lead to the chebyshev norm (and possibly the associated polynomials (links with spherical harmonics ???)).

Proceeding statistically (for example if we did not have the information that they lie on the sphere etc), one would try to find the eigenvectors of the distance matrix and possibly the principal components of the data set which would possibly help in ordering the points in 1 or higher dimensions. This could be a preliminary input to a travelling salesman algorithm since we have reduced the number of possibilities from N ! to just N (the choice of starting point)

Of course, in a practical scenario, one would tend to apply some sort of clustering algorithm (either directly or in the space of principal components) and try to exploit similarities of terrain / region and even culture (for example travelling across the EU) even if the solution is sub-optimal to some extent. This also possibly incorporates visa formalities etc !!! :-)

For example, one may divide the list into regions , for example

India , Pakistan, Afghanistan, Iran, Central Asia / Northwest China / Mongolia Azerbaijan / Caucasus / Georgia and possibly South Russia / Turkey Iraq and Arab countries Libya / Egypt East Africa Central and South Africa West Africa North Africa (Tunisia / Algeria / Morocco etc) Portugal / Spain France / Western Europe Central / Eastern Europe Northern Russia Northern europe North America' Central America South America Pacific (Including hawaii though it is a US state) Australia South East asia (Indonesia, Singapore, Malaysia, Laos, Cambodia etc) Far east (Including Russia)

- 7 years, 2 months ago

Remember, this is a competition! So just submit your code. ;)

- 7 years, 2 months ago

I did a little research on the travelling salesman problem. I think this problem is a little harder than I had originally anticipated.

- 7 years, 2 months ago

If you like algorithms puzzles, try also Google Code Jam. They're very good at inventing original puzzles for which you won't find algorithms or code online. Eg. This world cup tickets puzzle I remember <https://code.google.com/codejam/contest/635102/dashboard#s=p1>

- 7 years, 2 months ago

Out of interest, how is everyone doing so far? Best I've done is 249603 km

- 7 years, 2 months ago

Wow, I'm really curious to know which algorithms did you use for that, :D

Mine is 258891.567 km.

- 7 years, 2 months ago

Well done! I got 261930.

- 7 years, 2 months ago

260228 here

- 7 years, 2 months ago

Alright! Post your scores! I got 653,000.

- 7 years, 2 months ago

I got 261930.

- 7 years, 2 months ago

261931 km is the distance using the greedy approach, starting at Peace River, Canada.

I plotted the route and you can see a number of criss-crosses and other unoptimized portions. I'd post a picture, but you really have to be able to interact to see it. Here's the code I used (where cities is a list of objects with latitude and longitude in radians) - you'll notice that the routes don't actually follow the great arc (instead, they cut through the earth!), but you can still get a sense of what is going on.

from math import cos, sin, pi
from matplotlib import pyplot
from mpl_toolkits.mplot3d import axes3d

def plot_cities(cities):
xs = []
ys = []
zs = []

#city.lat and city.lon are in radians
for city in cities + [cities[0]]:
xs.append(sin(city.lat-pi/2)*cos(city.lon))
ys.append(sin(city.lat-pi/2)*sin(city.lon))
zs.append(cos(city.lat-pi/2))

fig = pyplot.figure()

ax.plot(xs, ys, zs)
pyplot.show()


- 7 years, 2 months ago

thats cool i will try my best.

- 7 years, 2 months ago

I have been facing difficulty while opening the List of Cities file. The problem is that the characters are not being read correctly by Python IDLE. I have tried utf-8 encoding but still it doesn't help. Weird characters like '/qap' are appearing instead of '°'. Any suggestions regarding this will be greatly appreciated and thanks for introducing this optimization competition.

- 7 years, 2 months ago

Lokesh,

Python has some issues with UTF-8 encoded text. The important points are:

1. put an encoding hint at the beginning of the file (like this: # coding=utf-8 )
2. put a "u" before any string that you enter with UTF-8 characters (like this: my_string = u"êńcöded" )

Here's an example with the cities list in Python code that is working. Keep in mind though that Python's UTF-8 support is less than ideal, and you may still run into bugs. In this case, converting to ASCII (which causes loss of special characters) might be a better option, since the important point is the order of the cities, not the spelling of their names.

Hope that helps!

Staff - 7 years, 2 months ago

Thanks, I got it worked in a different manner.

- 7 years, 2 months ago

I would take this problem seriously, but I have an SAT to take on Saturday :(

- 7 years, 2 months ago

Awww sorry about that. Good luck on the SAT. Think of it is a game. Like most standardized tests it's more of an endurance test than anything else.

Staff - 7 years, 2 months ago

I just took the SAT this morning. Tried to do exactly this. :P

- 7 years, 2 months ago

Sorry, can we manipulate the format of the input file?

Actually I don't mind to use the original input but it much easier for me to read only the main part: the coordinates. So the manipulated input file will be only consist of number and cardinal direction (e.g. the first line will be "34 20 N 62 12 E").

- 7 years, 2 months ago

Of course! You aren't required to submit anything except your code, a sorted index of the cities, and the total distance. We'll use the sorted list of city index numbers to verify your distance.

Staff - 7 years, 2 months ago

An ordinary TSP problem?

- 7 years, 2 months ago

Is it possible to have a distance checker? I have a program which computes some order and the total distance travelled but I would like to know if I did the right math to compute those distances.

- 7 years, 2 months ago

Amazing challenge! But I have a question. Some useful algorithms to find the shortest path are availables in python's libraries. Is the competition idea to develop all the code or we can use the library's functions? Thanks in advance! JJD

- 7 years, 2 months ago

FYI: There is a duplicate entry in the list of cities: apparently we have to visit Kinshasa twice.

- 7 years, 2 months ago

how do i get a link on my profile

- 7 years, 2 months ago

https://brilliant.org/profile/shubham-41uopo/

- 7 years, 2 months ago

I've just run my ACO again and get 244730.789682 km Unfortunately, I submit the 269596.408278 km. I've just finished my programming yesterday so I don't have much time to run it.

- 7 years, 2 months ago

Should the tour be closed (a cycle) or open (a path)?

- 7 years, 2 months ago

It is stated that it has to be closed.

Staff - 7 years, 2 months ago

- 7 years, 2 months ago

How many cities we have to include?

- 7 years, 2 months ago

There is a cities file in the OP!

- 7 years, 2 months ago

Solving the same in C++ was quite tedious.I had to input each of the 340 values as there is no copy-paste option. :(((((((((((((

- 7 years, 2 months ago

Good luck to everybody who participated! I won't have time for this unfortunately. :(

- 7 years, 2 months ago

My city Pune is not included though it is bigger and more important than Nagpur.. :(

- 7 years, 2 months ago

lol

- 7 years, 2 months ago

Wait how would this become coding? I'm sort of confused, as I am a horrible coder.

# lolfail

- 7 years, 2 months ago