Let’s combine linear optimization in Julia with Google Maps to create a route for a bar crawl, gallery tour, or pizza delivery with the least amount of wandering around. In this article, we’ll develop a route optimizer, quickly and without difficult math, using a Julia package called JuMP and turn it into an interactive web application using Google Maps and Forio Epicenter.

You may be have heard about the Traveling Salesman Problem (TSP) used for finding the shortest distance for many waypoints or for mapping circuits on circuit boards and transistors on chips. Today we’ll use this technique to find the quickest path through a town using real-time traffic data. Feel free to check out a complete demo or view the source code.

As a data scientist, I love linear programming. You provide a clearly stated goal and a set of constraints and the algorithm returns the optimum answer. Linear programming’s simplex algorithm has been cited as one of the top ten algorithms of the twentieth century and is one of the central techniques in operations research. The Julia JuMP authors have created a package that lets you create your own solver, defining goals and constraints with simple algebraic formulas. You can dive right in without an operations research background or mathematics PhD.

Most solutions to route optimization focus on minimizing distances but, by using real-time traffic data available as an API service, we can optimize routes based on duration instead.

1. Choose your Stops

We need a list of locations to visit. Initially, we just want a set of latitudes and longitudes for our waypoints. The list can either be a predefined JSON object or created by the end user using the Google Maps API.

{
 {"name": "Forio", "latitude": 37.776861, "longitude": -122.410573 },
 {"name": "Golden Gate Bridge", "latitude": 37.819844, "longitude": -122.478553 },
 {"name": "Palace of Fine Arts", "latitude":37.801981, "longitude": -122.449284 },
 {"name": "Lombard Street", "latitude": 37.802224, "longitude": -122.418708 },
 {"name": "Pier 39", "latitude": 37.808665, "longitude": -122.409821 },
 {"name": "Cliff House", "latitude": 37.778513, "longitude": -122.513993 },
 {"name": "Coit Tower", "latitude":37.802338, "longitude": -122.405810 },
 {"name": "Painted Ladies", "latitude":  37.776297, "longitude": -122.432788 },
 {"name": "The Exploratorium", "latitude": 37.802020, "longitude": -122.397095 }
}

2. Determine Durations between Stops

The solver needs a matrix of trip segment durations to calculate the optimum route. Fortunately, Google’s Distance Matrix service computes travel distance and journey duration between multiple origins and destinations using a given mode of travel.

The response from the Distance Matrix service returns our desired durations, but also a lot of stuff we don’t need. We can clean it up and turn it into the duration matrix we need using the function distanceMatrixToArray. This creates a two dimensional array that shows the time in seconds it takes to get from one location to another based on current traffic conditions.

Because of one way streets and traffic, the time to get from one location to another is usually not the same as the time to get back. For example, in the table above, it takes 330 seconds (5 minutes, 30 seconds) to get from Forio’s headquarters in San Francisco to the Alexander Book Company but only 261 seconds (4 minutes, 21 seconds) to return. This is called an asymmetric TSP and is a bit harder to solve than a symmetric TSP.

3. Define your Goals and Constraints

In addition to the data provided in the matrix, we need to set up the problem for the solver to analyze. JuMP makes it easy to define the objective function, the decision variables, the constraints, and the callbacks.

First, we create a model object and select a solver for that object. Julia JuMP supports several different solvers.

m = Model(solver=GLPKSolverMIP())

Next, we define the decision variables, which is just a column array.

@defVar(m, x[1:n,1:n], Bin)

Next, we set the objective function, which in this case is just minimizing the duration of the tour.

@setObjective(m, Min, sum{dur[i,j]*x[i,j], i=1:n,j=1:n})

Finally, we set the constraints. One constraint is that we do not allow self-arcs.

for i = 1:n
    @addConstraint(m, x[i,i] == 0)
end

Another constraint is that we must enter and leave each location once and only once.

for i = 1:n
	@addConstraint(m, sum{x[i,j], j=1:n} == 1)
	@addConstraint(m, sum{x[j,i], j=1:n} == 1)
 end

4. Solve your Model

After you define your goals and constraints, you can run your model by passing in the duration matrix:

function solveTSP(m)
	status = solve(m)
	n = int(sqrt(m.numCols))
	tour = extractTour(n, getValue(m.dictList[1]))
	return tour
end  

And this returns an optimized list of indices.

[1, 3, 6, 2, 5, 8, 7, 9, 4, 1]

We send this to Google Maps to plot the best route!

5. Call your Solver on the Server

Thanks to Forio Epicenter, we have a Julia server available as the backend for making this solver calculation into an interactive web application. In Epicenter, you expose the Julia function to the user interface by exporting the function, and then calling the function in JavaScript:

getOptimizedValues: function (durationMatrix) {
  	return operationsService.do('solve', durationMatrix);
}

Try It Out!

Find the most efficient routes for a sight seeing tour, a book tour, or create and save your own map.

What’s Next?

Because optimization with Julia JuMP is so easy, you can try lots of ideas quickly. You can use linear programming for price optimization, production scheduling, or airline routing.

Fork the code!