Santa's Stolen Sleigh
a project by T.J. Gaffney and Dan Smith.
Introduction
This was a Kaggle project, listed here.
The problem statement is that we have a bunch of houses around the globe, given by latitude and longitude, and some presents to give to each house, with a given weight. We must try to minimize the total distance that Santa travels. However, there is a weight limit for his sleigh. He can only load his sleigh up with that many toys, and must return to the north pole to get more presents.
Some partial code is linked through-out. This is rough code; it isn't very readable and may be missing dependencies.
Approach
This problem is both a travelling salesman problem and a knapsack problem. Run-time was a limiting factor. There were 100,000 homes which needed to be spread out over hundreds of trips.
Our approach was to essentially ignore the optimal-packing problem, opting for a greedy solution. We reasoned (correctly, I think) that a single sleigh-load should be a cluster. So we ran a clustering algorithm to get clusters contained to the weight-restriction. Then we tried to find good solutions to the TSP within each cluster. [There were still enough points for this to be complex.] We knew that we'd never be able to get a perfect solution for these, but we could improve clusters piece-wise by brute forcing computing power or by trying different algorithm. As we found new best paths, we recorded them to that cluster. It appeared that we could save a lot of distance by optimizing the clusters, whereas slightly-more efficient packing would save maybe a trip to the north pole.
Clusters - Modified k-Means
We used a k-means, but modified it to make sure that we didn't exceed the weight in any one cluster.
We followed basically this pseudo-code:
We ended up needing to coerce Antartica to all belong to one cluster. There were a few points down there that, if split up, added too much distance.
TSP - Insertion Model
As a baseline for each cluster, we ran a basic insertion model. This means, that we started with a random point, and went to the closest point in the cluster next, and repeated until we had all the clusters done.
Some code for this is here.
TSP - 2-Opt Algorithm
We explored a lot of algorithms for working with TSP. We narrowed in on the Lin-Kernighan heuristic, a generalization of a 2-opt algorithm. We had a lot of success with this approach. We wanted to try related algorithms on different clusters and see what worked best on each, even if just coincidentally. We don't have to worry about over-fitting for this problem, because we can take the best path we generate for each cluster, regardless of how it's found.
TSP - Genetic Algorithm
A genetic algorithm with a cross-over breeding approach can be used to solve the TSP. This seemed to not perform as well as the annealing scheme in the same amount of time, but it did have the property that it seemed to keep improving the more we let it run, so it was useful for brute forcing a better solution.
Some code for this is here. We did standard breeding and mutations for the TSP problem.
Result
This project has a sad ending. We both misread Kaggle's timeline, and missed the deadline for first entry. [There's a last date that you can make your first submission, and we thought there was just a single deadline.] After we realized that we couldn't enter, we didn't continue the project. We think our methodology is sound.