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

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:

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in`\(`

...`\)`

or`\[`

...`\]`

to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

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

Log in to reply

Any update on this?

Log in to reply

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

Log in to reply

hello can u please change my name to asdfgh rfvcm

Log 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!

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)

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

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

Log in to reply

Log in to reply

Log in to reply

Log in to reply

$300!$ is (something like $306057512216440636......\leftarrow$ not the full value)

My TI-89 just informed me what the value ofLog in to reply

Log in to reply

10000! is only 10000!

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

$t > T$, where $T$ is the time the contest is open.

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 timeP.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.Log in to reply

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

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

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

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

Log in to reply

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

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

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

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)

Log in to reply

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.

Log in to reply

can i submit solution more than once ?

Log in to reply

When are you going to release the results?

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.

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:

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

http://pastebin.com/dvrz6XPr

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

Log in to reply

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.

Log in to reply

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.

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log 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!

Log in to reply

I get 1978459 km for that tour.

Log in to reply

1978459.5589

Log in to reply

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?

Log in to reply

Log in to reply

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

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

Log in to reply

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

Log in to reply

i like it.

Log in to reply

great i will try to achieve target

Log in to reply

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

Log in to reply

Should the submission be zero- or one-indexed?

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)

Log in to reply

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

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.

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>

Log in to reply

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

Log in to reply

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

Mine is 258891.567 km.

Log in to reply

Well done! I got 261930.

Log in to reply

260228 here

Log in to reply

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

Log in to reply

I got 261930.

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.

Log in to reply

thats cool i will try my best.

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

Log in to reply

Lokesh,

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!

Log in to reply

Thanks, I got it worked in a different manner.

Log in to reply

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

Log in to reply

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

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

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

Log in to reply

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

An ordinary TSP problem?

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.

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

Log in to reply

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

Log in to reply

how do i get a link on my profile

Log in to reply

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

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.

Log in to reply

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

Log in to reply

It is stated that it has to be closed.

Log in to reply

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

Log in to reply

How many cities we have to include?

Log in to reply

There is a cities file in the OP!

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. :(((((((((((((

Log in to reply

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

Log in to reply

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

Log in to reply

lol

Log in to reply

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

## lolfail

Log in to reply