## 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.

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!

## Comments

Sort by:

TopNewestHi 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 · 2 years, 11 months ago

Log in to reply

– Quimey Vivas · 2 years, 11 months ago

Any update on this?Log in to reply

here. – Peter Taylor Staff · 2 years, 11 months ago

Sorry about the delay,I have posted the results rightLog in to reply

– Kaustubh Miglani · 1 year, 6 months ago

hello can u please change my name to asdfgh rfvcmLog in to reply

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 · 2 years, 12 months ago

Log in to reply

"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 · 2 years, 12 months ago

Log in to reply

– Josh Silverman Staff · 2 years, 11 months ago

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

– Taehyung Kim · 2 years, 11 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.Log in to reply

– Josh Silverman Staff · 2 years, 11 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!Log in to reply

– Priyatam Roy · 2 years, 11 months ago

Try sorting them first and then go on to make a cycleLog in to reply

– Ahaan Rungta · 2 years, 11 months ago

False. I thought of a brute-force algorithm right away when I saw this.Log in to reply

– Ryan Soedjak · 2 years, 11 months ago

good luck trying to check most of 300! possibilitiesLog in to reply

– Nicky Sun · 2 years, 11 months ago

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

– Carl Denton · 2 years, 11 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! :)Log in to reply

– Michael Diao · 2 years, 11 months ago

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

– Carl Denton · 2 years, 11 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.Log in to reply

10000! is only 10000! – Josh Silverman Staff · 2 years, 11 months ago

Log in to reply

– Carl Denton · 2 years, 11 months ago

Nice. What did you use to create that?Log in to reply

– Josh Silverman Staff · 2 years, 11 months ago

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

– Carl Denton · 2 years, 11 months ago

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

– Ryan Soedjak · 2 years, 11 months ago

hmm I thought he was better than that... probably trolling.Log in to reply

– Josh Silverman Staff · 2 years, 11 months ago

How long did it take to finish?Log in to reply

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 · 2 years, 11 months agoLog in to reply

Sure, send me a message at: josh_ahaan@hmamail.com – Josh Silverman Staff · 2 years, 11 months ago

Log in to reply

– Ahaan Rungta · 2 years, 11 months ago

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

– Ryan Soedjak · 2 years, 11 months ago

it's an anonymous disposable email lolLog in to reply

– Josh Silverman Staff · 2 years, 11 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.Log in to reply

– Ahaan Rungta · 2 years, 11 months ago

I am e-Mailing you later today!Log in to reply

– Roland Fong · 2 years, 11 months ago

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

– Taehyung Kim · 2 years, 12 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.Log in to reply

– Nicky Sun · 2 years, 12 months ago

Also, you could do the problem beforehand and just print the answer.Log in to reply

– Ahaan Rungta · 2 years, 11 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!Log in to reply

– Nicky Sun · 2 years, 11 months ago

There's also a very large chance that someone's already won.Log in to reply

can i submit solution more than once ? – Shubham Agarwal · 2 years, 12 months ago

Log in to reply

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 · 2 years, 12 months ago

Log in to reply

Thanks a lot and good luck. – Lokesh Sharma · 2 years, 12 months ago

Log in to reply

When are you going to release the results? – Mehdi Kazemi · 2 years, 11 months ago

Log in to reply

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 · 2 years, 11 months ago

Log in to reply

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. – Josh Silverman Staff · 2 years, 11 months ago

Log in to reply

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 · 2 years, 11 months agoLog in to reply

tehmap

If anyone else wants to plot their routes, check out this handy Google Maps API example code – Cheng Sun · 2 years, 11 months ago

Log in to reply

– Petko Petkov · 2 years, 11 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 :).Log in to reply

– Cheng Sun · 2 years, 11 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.Log in to reply

– Petko Petkov · 2 years, 11 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 :)Log in to reply

– Ivan Stošić · 2 years, 11 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.Log in to reply

– Petko Petkov · 2 years, 11 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).Log in to reply

– Ivan Stošić · 2 years, 11 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.Log in to reply

http://pastebin.com/dvrz6XPr – Cheng Sun · 2 years, 11 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:Log in to reply

– Ivan Stošić · 2 years, 11 months ago

Oh gosh, your tour is zero-indexed!Log in to reply

– Cheng Sun · 2 years, 11 months ago

Ah, whoops. Thanks for catching that. I think I fixed that when I submitted.Log in to reply

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 · 2 years, 11 months ago

Log in to reply

– Ivan Stošić · 2 years, 11 months ago

I've managed to prove that the optimal tour is at least 189858.4 km longLog in to reply

– Cheng Sun · 2 years, 11 months ago

Cost of the minimum spanning tree?Log in to reply

– Ivan Stošić · 2 years, 11 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.Log in to reply

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 · 2 years, 11 months ago

Log in to reply

– Jeffrey Milloy · 2 years, 11 months ago

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

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. :) – Ahaan Rungta · 2 years, 11 months agoLog in to reply

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! – Lokesh Sharma · 2 years, 12 months ago

Log in to reply

– Ross Dempsey · 2 years, 12 months ago

I get 1978459 km for that tour.Log in to reply

– Josh Silverman Staff · 2 years, 12 months ago

1978459.5589Log in to reply

– Roland Fong · 2 years, 11 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++?Log in to reply

http://pastebin.com/yus6TChg

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:did you remember to return to the original city? – Josh Silverman Staff · 2 years, 11 months ago

Log in to reply

– Roland Fong · 2 years, 11 months ago

I did forget, actually... thanks for pointing that outLog in to reply

– Ammar Fathin Sabili · 2 years, 12 months ago

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

Awesome!! This sounds so cool! Will try to go for the kill :D – Aditya Pappula · 2 years, 12 months ago

Log in to reply

Good Luck to everyone who is participating as I am a highly stupid and dismal programmer. – Soham Dibyachintan · 2 years, 12 months ago

Log in to reply

– Ahaan Rungta · 2 years, 11 months ago

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

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.

– Jeffrey Milloy · 2 years, 11 months agoLog in to reply

Alright! Post your scores! I got 653,000. – Cody Johnson · 2 years, 11 months ago

Log in to reply

– Lokesh Sharma · 2 years, 11 months ago

I got 261930.Log in to reply

Out of interest, how is everyone doing so far? Best I've done is 249603 km – Matt Mundy · 2 years, 11 months ago

Log in to reply

Mine is 258891.567 km. – Ammar Fathin Sabili · 2 years, 11 months ago

Log in to reply

– Arturo Vial Arqueros · 2 years, 11 months ago

260228 hereLog in to reply

– Lokesh Sharma · 2 years, 11 months ago

Well done! I got 261930.Log in to reply

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> – Matt Mundy · 2 years, 11 months ago

Log in to reply

I did a little research on the travelling salesman problem. I think this problem is a little harder than I had originally anticipated. – Roland Fong · 2 years, 11 months ago

Log in to reply

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 · 2 years, 12 months ago

Log in to reply

– Ahaan Rungta · 2 years, 11 months ago

Remember, this is a competition! So just submit your code. ;)Log in to reply

Should the submission be zero- or one-indexed? – Ross Dempsey · 2 years, 12 months ago

Log in to reply

i like challenges ... and i feel happy achieving them... i will surely participate ...... – Bhavya Niravbhai Shah · 2 years, 12 months ago

Log in to reply

great i will try to achieve target – Irfan Ali · 2 years, 12 months ago

Log in to reply

i like it. – Aljon Altavano · 2 years, 12 months ago

Log in to reply

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 · 2 years, 11 months ago

Log in to reply

how do i get a link on my profile – Shubham Chaudhary · 2 years, 11 months ago

Log in to reply

– Lokesh Sharma · 2 years, 11 months ago

https://brilliant.org/profile/shubham-41uopo/Log in to reply

FYI: There is a duplicate entry in the list of cities: apparently we have to visit Kinshasa twice. – Roel Baars · 2 years, 11 months ago

Log in to reply

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 · 2 years, 12 months ago

Log in to reply

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. – Quimey Vivas · 2 years, 12 months ago

Log in to reply

An ordinary TSP problem? – Forretrio Wong · 2 years, 12 months ago

Log in to reply

Sorry, can we manipulate the

formatof 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"). – Ammar Fathin Sabili · 2 years, 12 months ago

Log in to reply

– Arron Kau Staff · 2 years, 12 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.Log in to reply

I would take this problem seriously, but I have an SAT to take on Saturday :( – Roland Fong · 2 years, 12 months ago

Log in to reply

– Peter Taylor Staff · 2 years, 12 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.Log in to reply

– Ahaan Rungta · 2 years, 11 months ago

I just took the SAT this morning. Tried to do exactly this. :PLog in to reply

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 Sharma · 2 years, 12 months ago

Log in to reply

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

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 · 2 years, 12 months ago

Log in to reply

– Lokesh Sharma · 2 years, 12 months ago

Thanks, I got it worked in a different manner.Log in to reply

thats cool i will try my best. – Javeria Raja · 2 years, 12 months ago

Log in to reply

Solving the same in C++ was quite tedious.I had to input each of the 340 values as there is no copy-paste option. :((((((((((((( – Priyatam Roy · 2 years, 11 months ago

Log in to reply

How many cities we have to include? – Atul Kumar · 2 years, 12 months ago

Log in to reply

– Ahaan Rungta · 2 years, 11 months ago

There is a cities file in the OP!Log in to reply

Should the tour be closed (a cycle) or open (a path)? – Ivan Stošić · 2 years, 12 months ago

Log in to reply

– Calvin Lin Staff · 2 years, 12 months ago

It is stated that it has to be closed.Log in to reply

– Ivan Stošić · 2 years, 12 months ago

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

Good luck to everybody who participated! I won't have time for this unfortunately. :( – Ahaan Rungta · 2 years, 12 months ago

Log in to reply

My city Pune is not included though it is bigger and more important than Nagpur.. :( – Snehal Shekatkar · 2 years, 12 months ago

Log in to reply

– Lokesh Sharma · 2 years, 12 months ago

lolLog in to reply

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

## lolfail

– Thomas Luo · 2 years, 12 months agoLog in to reply