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:

A link to your brilliant profile page.
Your email address.
The total distance of the journey (in km).
A list of the cities’ index numbers, sorted in your optimal order.
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!

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 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"

Math

Appears 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}

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 = fig.add_subplot(111, projection='3d') ax.plot(xs, ys, zs) pyplot.show()

lolfail

Thomas Luo - 7 years, 4 months ago

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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!

Peter Taylor Staff - 7 years, 4 months ago

Any update on this?

Quimey Vivas - 7 years, 4 months ago

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

hello can u please change my name to asdfgh rfvcm

Kaustubh Miglani - 5 years, 11 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!

Daniel Liu - 7 years, 4 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)

Nicky Sun - 7 years, 4 months ago

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

Josh Silverman Staff - 7 years, 4 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.

Taehyung Kim - 7 years, 4 months ago

@Taehyung Kim – 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!

@Josh Silverman – Try sorting them first and then go on to make a cycle

Priyatam Roy - 7 years, 4 months ago

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

Ahaan Rungta - 7 years, 4 months ago

@Ahaan Rungta – good luck trying to check most of 300! possibilities

Ryan Soedjak - 7 years, 4 months ago

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

@Nicky Sun – 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! :)

Carl Denton - 7 years, 4 months ago

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

Michael Diao - 7 years, 4 months ago

@Michael Diao – 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.

@Carl Denton – 300! is only 306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000

10000! is only 10000!

@Josh Silverman – Nice. What did you use to create that?

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

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

@Nicky Sun – hmm I thought he was better than that... probably trolling.

@Ahaan Rungta – How long did it take to finish?

@Josh Silverman – 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.

@Ahaan Rungta – 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

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

@Ahaan Rungta – 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.

@Josh Silverman – I am e-Mailing you later today!

@Ahaan Rungta – it's an anonymous disposable email lol

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.

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

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

Roland Fong - 7 years, 4 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!

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

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)

Arturo Vial Arqueros - 7 years, 4 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.

Lokesh Sharma - 7 years, 4 months ago

can i submit solution more than once ?

Shubham Agarwal - 7 years, 4 months ago

When are you going to release the results?

Mehdi Kazemi - 7 years, 4 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.

Adam Buck - 7 years, 4 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:

Petko Petkov - 7 years, 4 months ago

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

tehmap tehmap

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

Cheng Sun - 7 years, 4 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 :).

@Petko Petkov – 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.

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

Ivan Stošić - 7 years, 4 months ago

@Ivan Stošić – Cost of the minimum spanning tree?

@Cheng Sun – 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.

@Cheng Sun – 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 :)

@Petko Petkov – 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.

@Ivan Stošić – 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).

@Petko Petkov – 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

@Cheng Sun – Oh gosh, your tour is zero-indexed!

@Ivan Stošić – Ah, whoops. Thanks for catching that. I think I fixed that when I submitted.

@Cheng Sun – 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.

@Petko Petkov – 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.

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.

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

Soham Dibyachintan - 7 years, 4 months ago

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

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

Aditya Pappula - 7 years, 4 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!

I get 1978459 km for that tour.

Ross Dempsey - 7 years, 4 months ago

1978459.5589

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++?

@Roland Fong – 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

did you remember to return to the original city?

@Josh Silverman – I did forget, actually... thanks for pointing that out

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

Ammar Fathin Sabili - 7 years, 4 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. :)

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.

Matt Mundy - 7 years, 4 months ago

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

Jeffrey Milloy - 7 years, 4 months ago

i like it.

Aljon Altavano - 7 years, 4 months ago

great i will try to achieve target

Irfan Ali - 7 years, 4 months ago

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

Bhavya Niravbhai Shah - 7 years, 4 months ago

Should the submission be zero- or one-indexed?

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)

Sundar R - 7 years, 4 months ago

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

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

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>

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

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

Mine is 258891.567 km.

Well done! I got 261930.

260228 here

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

Cody Johnson - 7 years, 4 months ago

I got 261930.

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.

thats cool i will try my best.

javeria raja - 7 years, 4 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.

Lokesh,

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

put an encoding hint at the beginning of the file (like this: # coding=utf-8 )
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!

Arron Kau Staff - 7 years, 4 months ago

Thanks, I got it worked in a different manner.

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

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.

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

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").

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.

An ordinary TSP problem?

Forretrio Wong - 7 years, 4 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.

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

Juan José D'Ambrosio - 7 years, 4 months ago

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

Roel Baars - 7 years, 4 months ago

how do i get a link on my profile

Shubham Chaudhary - 7 years, 4 months ago

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

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.

Quang Minh Bùi - 7 years, 4 months ago

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

It is stated that it has to be closed.

Calvin Lin Staff - 7 years, 4 months ago

Sorry about even asking this, I should have read the statement carefully. Thanks anyway!

How many cities we have to include?

Atul Kumar - 7 years, 4 months ago

There is a cities file in the OP!

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

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

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

Snehal Shekatkar - 7 years, 4 months ago

lol

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

Math	Appears 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}$