Shortest route between all LDS temples in the 48 states?

I’ve become interested in linear programming¬†recently as a tool to solve quantitative problems at work. In an effort to evaluate the various solution methods, I created an interesting toy problem. The problem is this: what is the shortest route to drive between all 89 announced temples of The Church of Jesus Christ of Latter-Day Saints in the lower 48 states?

To solve this problem, I found the lat-lon coordinates of each of the announced temples, which is available from the church. Next, I used the time-distance matrix API service from openrouteservice.org to calculate the distance between each pair of temples. Armed with this distance matrix, I used the python pulp library to calculate the shortest route between the temples. This is not a trivial calculation: for just these 89 sites, it took approximately 11 days to calculate the solution using CBC on my Macbook Pro laptop. I would have preferred to use CPLEX, which would have been much faster, but it’s not free and it’s expensive. The CBC solution is guaranteed to be the shortest path for the given distance data.

I then created a google map of the locations and street directions for the optimal route between the temples. It looks like this:

us-temple-routes

There are a few caveats. Some of the temples do not have exact street addresses yet (e.g., Taylorsville Utah). For those locations, the google map directions show directions to the town itself. Also, the distances from the google map may not match exactly the distances given by the Matrix API from openrouteservice.org. Nevertheless, I think it’s pretty cool.

The total distance is, by openrouteservice.org data, about 15,240 miles. The shortest leg? Between Provo Utah and Provo City Center (about 3 miles). The longest leg? 512 miles between Fort Collins, CO and Billings MT.

If you want the detailed data (exact route from temple to temple with distances), leave me a comment, and I’ll arrange a way to get it to you.