Waste less time on Facebook — follow Brilliant.
×

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:

  1. A link to your brilliant profile page.
  2. Your email address.
  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
3 years, 9 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 - 3 years, 8 months ago

Log in to reply

Any update on this?

Quimey Vivas - 3 years, 8 months ago

Log in to reply

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

Peter Taylor Staff - 3 years, 8 months ago

Log in to reply

hello can u please change my name to asdfgh rfvcm

Kaustubh Miglani - 2 years, 3 months ago

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!

Daniel Liu - 3 years, 9 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 - 3 years, 8 months ago

Log in to reply

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

Josh Silverman Staff - 3 years, 8 months ago

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.

Taehyung Kim - 3 years, 8 months ago

Log in to reply

@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 Staff - 3 years, 8 months ago

Log in to reply

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

Priyatam Roy - 3 years, 8 months ago

Log in to reply

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

Ahaan Rungta - 3 years, 8 months ago

Log in to reply

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

Ryan Soedjak - 3 years, 8 months ago

Log in to reply

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

Nicky Sun - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

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

Michael Diao - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

@Carl Denton 300! is only 306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000

10000! is only 10000!

Josh Silverman Staff - 3 years, 8 months ago

Log in to reply

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

Carl Denton - 3 years, 8 months ago

Log in to reply

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

Josh Silverman Staff - 3 years, 8 months ago

Log in to reply

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

Carl Denton - 3 years, 8 months ago

Log in to reply

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

Ryan Soedjak - 3 years, 8 months ago

Log in to reply

@Ahaan Rungta How long did it take to finish?

Josh Silverman Staff - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

@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 Staff - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

@Ahaan Rungta it's an anonymous disposable email lol

Ryan Soedjak - 3 years, 8 months ago

Log in to reply

@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 Staff - 3 years, 8 months ago

Log in to reply

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

Ahaan Rungta - 3 years, 8 months ago

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

Roland Fong - 3 years, 8 months ago

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.

Taehyung Kim - 3 years, 8 months ago

Log in to reply

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

Nicky Sun - 3 years, 8 months ago

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!

Ahaan Rungta - 3 years, 8 months ago

Log in to reply

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

Nicky Sun - 3 years, 8 months ago

Log in to reply

can i submit solution more than once ?

Shubham Agarwal - 3 years, 8 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 - 3 years, 8 months ago

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.

Lokesh Sharma - 3 years, 8 months ago

Log in to reply

When are you going to release the results?

Mehdi Kazemi - 3 years, 8 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 - 3 years, 8 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 - 3 years, 8 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 - 3 years, 8 months ago

Log in to reply

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 - 3 years, 8 months ago

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

Petko Petkov - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

@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ć - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

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

Ivan Stošić - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

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

Ivan Stošić - 3 years, 8 months ago

Log in to reply

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

Cheng Sun - 3 years, 8 months ago

Log in to reply

@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 - 3 years, 8 months ago

Log in to reply

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

Ivan Stošić - 3 years, 8 months ago

Log in to reply

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

Cheng Sun - 3 years, 8 months ago

Log in to reply

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

Ivan Stošić - 3 years, 8 months ago

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 - 3 years, 8 months ago

Log in to reply

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

Jeffrey Milloy - 3 years, 8 months ago

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 - 3 years, 8 months ago

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!

Lokesh Sharma - 3 years, 8 months ago

Log in to reply

I get 1978459 km for that tour.

Ross Dempsey - 3 years, 8 months ago

Log in to reply

1978459.5589

Josh Silverman Staff - 3 years, 8 months ago

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

Roland Fong - 3 years, 8 months ago

Log in to reply

@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 Staff - 3 years, 8 months ago

Log in to reply

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

Roland Fong - 3 years, 8 months ago

Log in to reply

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

Ammar Fathin Sabili - 3 years, 8 months ago

Log in to reply

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

Aditya Pappula - 3 years, 9 months ago

Log in to reply

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

Soham Dibyachintan - 3 years, 9 months ago

Log in to reply

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

Ahaan Rungta - 3 years, 8 months ago

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.

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()

Jeffrey Milloy - 3 years, 8 months ago

Log in to reply

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

Cody Johnson - 3 years, 8 months ago

Log in to reply

I got 261930.

Lokesh Sharma - 3 years, 8 months ago

Log in to reply

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

Matt Mundy - 3 years, 8 months ago

Log in to reply

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

Mine is 258891.567 km.

Ammar Fathin Sabili - 3 years, 8 months ago

Log in to reply

260228 here

Arturo Vial Arqueros - 3 years, 8 months ago

Log in to reply

Well done! I got 261930.

Lokesh Sharma - 3 years, 8 months ago

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 - 3 years, 8 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 - 3 years, 8 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 - 3 years, 8 months ago

Log in to reply

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

Ahaan Rungta - 3 years, 8 months ago

Log in to reply

Should the submission be zero- or one-indexed?

Ross Dempsey - 3 years, 9 months ago

Log in to reply

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

Bhavya Niravbhai Shah - 3 years, 9 months ago

Log in to reply

great i will try to achieve target

Irfan Ali - 3 years, 9 months ago

Log in to reply

i like it.

Aljon Altavano - 3 years, 9 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 - 3 years, 8 months ago

Log in to reply

how do i get a link on my profile

Shubham Chaudhary - 3 years, 8 months ago

Log in to reply

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

Lokesh Sharma - 3 years, 8 months ago

Log in to reply

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

Roel Baars - 3 years, 8 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 - 3 years, 8 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 - 3 years, 8 months ago

Log in to reply

An ordinary TSP problem?

Forretrio Wong - 3 years, 8 months ago

Log in to reply

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

Ammar Fathin Sabili - 3 years, 9 months ago

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.

Arron Kau Staff - 3 years, 9 months ago

Log in to reply

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

Roland Fong - 3 years, 9 months ago

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.

Peter Taylor Staff - 3 years, 9 months ago

Log in to reply

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

Ahaan Rungta - 3 years, 8 months ago

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.

Lokesh Sharma - 3 years, 9 months ago

Log in to reply

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!

Arron Kau Staff - 3 years, 9 months ago

Log in to reply

Thanks, I got it worked in a different manner.

Lokesh Sharma - 3 years, 8 months ago

Log in to reply

thats cool i will try my best.

Javeria Raja - 3 years, 9 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 - 3 years, 8 months ago

Log in to reply

How many cities we have to include?

Atul Kumar - 3 years, 8 months ago

Log in to reply

There is a cities file in the OP!

Ahaan Rungta - 3 years, 8 months ago

Log in to reply

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

Ivan Stošić - 3 years, 9 months ago

Log in to reply

It is stated that it has to be closed.

Calvin Lin Staff - 3 years, 9 months ago

Log in to reply

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

Ivan Stošić - 3 years, 9 months ago

Log in to reply

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

Ahaan Rungta - 3 years, 9 months ago

Log in to reply

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

Snehal Shekatkar - 3 years, 8 months ago

Log in to reply

lol

Lokesh Sharma - 3 years, 8 months ago

Log in to reply

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

lolfail

Thomas Luo - 3 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...