Travelling Blimp Salesman
The Traveling Blimp Salesman challenge was one of the more complex challenges on the hackathon. There are many potential approaches to such a challenge, so one needs to try out different approaches and see what works. There are many different heuristics one could use when solving a standard traveling salesman problem, and these can be modified to work with this challenge. A simple approach is to always just visit the nearest city and continue until all the cites have been visited. This could be modified for this challenge to compare the cost of traveling directly to the next city vs. going back to headquarters first to pick up more blimps.
Many of the top scorers used modifications of this basic approach. Alexander tried many different approaches to the problem, but the more complex ones often ran into the time limit. He ended up using a dual-approach: His algorithm would visit a city and then check if other cities were worth visiting or if it was better to return to headquarters. Once time was running low, his code switched to an algorithm that just visited the cities one-at-a-time in order of the most revenue, until no more cities were worth visiting. This simple approach was good enough to score in 6th-place on the back-to-school hackathon. You can view Alexander’s code on Github.
Neal Wu used a similar approach to score in first place on the challenge. He started with a randomized greedy algorithm that, after visiting a city, would check for nearby neighbors to visit. It would look at which city would provide the most profit for the next visit and whether that city was worth visiting directly. Since there could be up to 100,000 cities, Neal just checked a random subset of cities each time. After determining what order to visit, the cities, the next step was to figure out the best times to actually return to headquarters. Neal used dynamic programming to do perform these checks, which managed to boost his score into first place.
Some people tried more complex algorithms to solve this problem, but those didn’t end up doing well. Since there was such a large number of cities in the high-scoring test-cases, any overly-complex approach would run out of time trying to solve them. In addition, due to the distribution of cities and the costs of transporting blimps, it was often only worth visiting a small number of cities at a time (sometimes even one city was enough). In future challenges, we will probably use smaller test cases (and good distributions) so more sophisticated algorithms can work well. Approximate challenges can be both practical and highly competitive, so stay tuned for more of them in the future.