The Traveling Santa
Challenge
It’s the holiday season and at MongoDB, we got to thinking about how efficiently Santa could deliver presents around the world. Visiting every Christmas-celebrating house in one night seems like a challenge, but none too big for an engineer.
We presented the below challenge in our MongoDB
Advocacy Hub
on the classic
Traveling Salesperson problem
. Given a set of geo coordinates, one for each of the 10 most populous urban areas on the planet, how would you find the shortest path the salesperson (or in this case, Santa) could use to reach each city? (To participate in our next our next challenge
register for the Advocate Hub
!)
We provided the following JSON dataset containing the 10 most populous cities, including the North Pole:
{"_id":"Beijing","population":1.952e+07,"location":{"type":"Point","coordinates":[116.383333,39.916667]}}
{"_id":"Delhi","population":2.4953e+07,"location":{"type":"Point","coordinates":[77.23,28.61]}}
{"_id":"Guangzhou","population":2.0597e+07,"location":{"type":"Point","coordinates":[113.266667,23.133333]}}
{"_id":"Mexico City","population":2.0843e+07,"location":{"type":"Point","coordinates":[-99.133333,19.433333]}}
{"_id":"Mumbai","population":2.0741e+07,"location":{"type":"Point","coordinates":[72.825833,18.975]}}
{"_id":"New York","population":1.8591e+07,"location":{"type":"Point","coordinates":[-74.0059,40.7127]}}
{"_id":"North Pole","population":1.0,"location":{"type":"Point","coordinates":[0.0,90.0]}}
{"_id":"Osaka","population":2.0123e+07,"location":{"type":"Point","coordinates":[135.502222, 34.693889]}}
{"_id":"Shanghai","population":2.2991e+07,"location":{"type":"Point","coordinates":[121.5,31.2]}}
{"_id":"São Paulo","population":2.0831e+07,"location":{"type":"Point","coordinates":[-46.633333,-23.55]}}
{"_id":"Tokyo","population":3.7833e+07,"location":{"type":"Point","coordinates":[139.683333,35.683333]}}
Solution
Congratulations to Dror Asaf for solving the traveling Santa challenge. Dror determined the correct path for Santa to take to reach the 10 most populous cities in the least distance required.
The order of cities visited is:
North Pole
New York
Mexico City
São Paulo
Mumbai
Delhi
Guangzhou
Shanghai
Beijing
Osaka
Tokyo
North Pole
Dror’s methodology was pretty straightforward. Starting at the North Pole, Dror used MongoDB’s geospatial indexing and queries to select the next city to visit at each stage of the journey. Dror’s strategy finds the closest city to Santa’s current position and sets that city to visit next in Santa’s world tour.
You may notice that while this works for the set of cities in the challenge, a next-nearest-destination isn’t a general solution to the traveling Santa problem. I’ve described a general solution below. But before we get there I need to admit a mistake.
In the original data set I mistakenly assigned a negative latitude for the city of Osaka, Japan. Here’s the erroneous document:
{"_id":"Osaka","population":2.0123e+07,"location":{"type":"Point","coordinates":[135.502222,-34.693889]}}
Which would put Osaka at a location adjacent to Port Lincoln, Australia. Last time I checked, Osaka doesn’t go there. The correct latitude is 34.693889. Now, let’s take a closer look at the Traveling Santa problem to find a general solution.
How far from here to there?
The starting dataset I provided only included the the geo-coordinates of the cities. You, the participant, need to calculate the distances between the cities before you can actually solve the problem at hand. I included this additional twist in the problem to focus attention on a common snag when calculating distance between two points on a globe.
For example, let’s say I wish to fly from Honolulu to Tokyo. Tokyo is west of Honolulu, so it would make sense to fly west to reach it. However, not all maps get this right. Check out what happens when I ask this web-based mapping service for a path from Honolulu to Tokyo.
The wrong way to go from Honolulu to Tokyo
This mapping service pointed me in the wrong direction, going the long way around the planet. It did this because it models the Earth as a 2 dimensional surface with edges, just like a flat piece of paper. Its surprisingly common for databases that claim to support geospatial indexes to only expose 2D planes. In this model, the Earth is simply a flat plain over which we’ve imposed a coordinate system centered at latitude 0, longitude 0. Here’s a visualization of this 2D way of thinking, where the origin of the coordinate system is marked with the red dot and the edges of the Earth are marked with red lines. The edges of this model is the anti-meridian.
The Anti-Meridian
The Earth is of course not a flat plane but a 3 dimensional surface. So, we’ll need a way to calculate the distance between two points on a globe. This is called a
haversine
formula, and with this function we can derive the shortest distance between Honolulu and Tokyo.
The right way to Tokyo
At this point I’ve chosen to calculate the distance between each city and write it to MongoDB for use later. I have chosen to represent the distance between two cities as an “edge” document with the following format
{
"_id" : ObjectId("5676f18a66414e88e89a09c3"),
"from" : "Delhi",
"dest" : "Beijing",
"dist" : 3776477.26147437
}
At this point I am ready to find the shortest path between the cities. I am going to use a recursive function to traverse each path and find the shortest among them. First I need an object to represent the path I am currently building / traversing. In JavaScript this object takes the following form:
function Path(){
this.distance = 0;
this.visited = [];
this.clone = function() {
var newPath = new Path();
newPath.distance = this.distance;
for ( i in this.visited )
newPath.visited.push ( this.visited[i] );
return newPath;
};
}
To find the shortest path, starting at the North Pole, I initialize the Path object by plugging in the North Pole as the first city I have visited and then pass this initialized object to the recursive function ‘visit’.
function visit ( path ) {
// get last city visited
var city = path.visited[ path.visited.length - 1 ];
var paths = [];
db.edges.find( { from: city } ).forEach (
function( edge ) {
// avoid cities I've already visited
if ( path.visited.indexOf( edge.dest ) == -1 ) {
// branch out a new path
var newPath = path.clone();
//print( "Adding the next edge "+edge.dest );
newPath.visited.push( edge.dest );
newPath.distance += edge.dist;
//recurse
paths.push( visit ( newPath ) );
}
}
);
if( paths.length == 0 ) {
// if no new paths the tour is complete. Now go home!
var lastEdge = db.edges.findOne(
{ from: path.visited[ path.visited.length -1 ],
dest: path.visited[0]
}
);
path.visited.push( path.visited[0] );
path.distance += lastEdge.dist;
print( "Path complete "+path.visited );
paths.push( path );
}
paths.sort( compare );
return paths[0];
}
The complete code solution is available here
, and once complete I can assert that Santa’s best route to reach all 10 cities in the shortest time.
"distance" : 45344411.211476855,
"path" : [
"North Pole",
"Tokyo",
"Osaka",
"Beijing",
"Shanghai",
"Guangzhou",
"Delhi",
"Mumbai",
"São Paulo",
"Mexico City",
"New York",
"North Pole"
],
"route" : {
"type" : "LineString",
"coordinates" : [
[
0,
90
],
[
139.683333,
35.683333
],
is:
[
135.502222,
34.693889
],
[
116.383333,
39.916667
],
[
121.5,
31.2
],
[
113.266667,
23.133333
],
[
77.23,
28.61
],
[
72.825833,
18.975
],
[
-46.633333,
-23.55
],
[
-99.133333,
19.433333
],
[
-74.0059,
40.7127
],
[
0,
90
]
]
}
}
Very astute readers will see that that this is the same path as Dror’s solution, just traversed in reverse order. The “route” field in the document is a geojson formatted LineString I’ve added to the result document which was used to render the paths you see in the maps above.
Now, you may notice this is an exhaustive and brute force approach to solving a problem which is known to be more difficult to solve the more points you need to visit. This is why I limited the number of cities Santa would be visiting to 10. However, I can certainly think or a couple of optimizations which could be added to make my code even faster. I’d encourage you to take a look at the solution and make some suggestions in the comments below. Better yet, register in our
Advocacy Hub
, take part in the challenge with a gist of your own solution!
Want to learn more about geospatial capabilities in MongoDB? Check out my
presentation on geo-spatial queries
or read our recent blog post on the geospatial performance improvements now live in MongoDB 3.2.
Geospatial performance improvements in 3.2
About the Author - Bryan Reinero
Bryan Reinero is US Developer Advocate at MongoDB fostering understanding and engagement in the community. Previously Bryan was a Senior Consulting Engineer at MongoDB, helping users optimize MongoDB for scale and performance and a contributor to the Java Driver for MongoDB.
Earlier, Bryan was Software Engineering Manager at Valueclick, building and managing large scale marketing applications for advertising, retargeting, real-time bidding and campaign optimization. Earlier still, Bryan specialized in software for embedded systems at Ricoh Corporation and developed data analysis and signal processing software at the Experimental Physics Branch of Ames Research Center.
December 23, 2015