Connecting Google Maps and Google Sheets to Solve the Traveling-Salesman Problem

Connecting Google Maps and Google Sheets can help us solve important and difficult problems. A typical problem is when we have a list of addresses in a Google spreadsheet, and we want to find the shortest possible route that visits each place exactly once. Finding the shortest route visiting a list of addresses is known as the Traveling-Salesman Problem.
How can we solve this problem without coding a complex algorithm? Keep reading!

We know that Google Maps is capable of calculating a solution to this classical optimization problem. The key question is how to use Google Maps and Google Sheets to solve the Traveling-Salesperson Problem? Google Sheets doesn’t offer any predefined function callable from a cell to compute the solution. The only option available is to go to the Google Script Editor, write our own Javascript function, and call it from the spreadsheet. Luckily, the Javascript version used by Google Sheets already includes a reference to the Google Maps object, so our task will be relatively simple. We will not need to dig into Google Maps API.

Let’s start and see how we can start calling Google Maps from a Google Sheets!

Preparing the Google Spreadsheet

First, we create a spreadsheet with a list of addresses we want to visit visit. I suggest placing the stops in a column. For our example, let’s use column B, cells B1-B16. I randomly selected 15 addresses from Google Maps. I don’t know who lives at these addresses if it’s a house, a gas station, or an empty lot. For the purpose of this example doesn’t matter.

Starting the Google Script Editor IDE

Our goal is to find the sequence of stops that minimizes the length of the route. We switch to the Google Script Editor to write a function that computes that route.

We can access the Script Editor from Google Sheets, by selecting the menu “Tools” and then “Script Editor.”

The browser will open a new tab displaying a simple editor, IDE, we will use to write our Javascript function.

The programming language used by Google is called Google Apps Script, a subset of Javascript. The main difference, is that Google Apps Script already includes a set of predefined objects to make it easy for coders to access all the leading Google Apps, like Gmail, Documents, Slides, Maps, etc.

Connecting Google Maps and Google Sheets to find the optimal route

Our plan is to write a function that will take 3 parameters:

1. a list of addresses to visit,
2. the route starting point (address),
3. the route end point (final address).

We want to call the function using, as first argument, a range of cells containing the list of addresses. We expect, as a result, a list of values telling us in which order visit each stop. We want the result to be formatted to be expandable vertically on a column of the spreadsheet. We will like to be able to place the results on column A next to column B with the addresses.

Here is the Javascript code of the function I wrote, called optimalRoute(). We will use it to calculate the optimal route:

function optimalRoute(stops, startAddress, endAddress) {

    // 1. Access the Maps object
    var df = Maps.newDirectionFinder();

    // 2. Set the starting and ending addresses
    df.setOrigin(String(startAddress));
    df.setDestination(String(endAddress));

    // 3. More settings...
    df.setMode(Maps.DirectionFinder.Mode.DRIVING);
    df.setOptimizeWaypoints(true);

    // 4. Adding addresses to the route
    for(var i=0; i < stops.length; i++) {
        var addr = stops[i][0];     
        if(addr.length>0) {
            df.addWaypoint(addr);     
        }
    }

    // 5. Compute optimal route   
    var directions = df.getDirections();   
    var stops_order = directions.routes[0].waypoint_order;

    // 6. Assign the stop position to each address
    var stop_sequence = [["Stop #"]];
    for (j = 0; j < stops_order.length; j++) {
        var stop = stops_order.indexOf(j) + 1;
        stop_sequence.push([stop]);   
    }

    // 7. Return the result   
    return stop_sequence; 
} 

Explanation of the optimal-route algorithm, step by step

1. A single line of code is all we need to access the newDirectionFinder object of Google Maps.
2. Assuming that startAddress and endAddress are strings or references to single cells, we use them to set the corresponding settings of the NewDirectionFinder object.
3. We need tell Google Maps we are looking for a route optimized for driving (not for walking or riding a bike).
4. We add all the addresses to the route. just in case, we are skipping empty values that could have been included by mistake.
5. The computation of the optimal route is one single call. We are now ready to extract and process the optimized sequence of stops.
6. Our goal is to identify the stop number for each address (our route will start at stop #1, them stop #2, and so on). In this way we will be able to reorder our addresses using the result of the function as sorting key. This is important because we might have have additional information, like email, name, and phone number, associated to each address sitting on columns C, D, etc. And having a sorting key for each row (record) in my list will allow us to manually sort the rows.
   We can’t directly use the sequence returned by Google Maps stops_order. The list returned by Google Maps is a lists of positions (numbers) telling us what address to visit first, then second, end so on. We can easily map the stops_order array assigning a sequence order to each address. We finally insert the results in an array of arrays, in a way that it will be displayed by the spreadsheet as a vertical sequence of cells (side by side with our addresses).
7. We finally return the value to the caller.

Calling the optimalRoute() function from the Spreadsheet

Calling the function we just wrote from the spreadsheet is very easy. We select cell A1, and we enter the simple formula shown below. For the purpose of this example, We are going to select two random addresses as starting and ending point for the route. We can also pass the addresses to our function as a link (like A4) to a cell containing the address.

= optimalRoute(
    B2:B16,
    "3045 Ashby Ave, Berkeley CA",
    "414 Clipper St, San Francisco CA"   
  )

The Optimal Route

The optimal route is now ready on our spreadsheet.

Sorting the addresses

We might want to sort the result to have the addresses listed by the order we will visit them. For that, we select the range of cells A1-B16. We go to the menu data, select the entry “Sort Range.” On the dialog box, we check “Data has header row” and confirm with the [Sort] button.

This will sort the addresses based on the values in column A. We might notice that this also triggers a new recalculation of the route. The new route will confirm the existing sequence of already sorted addresses.

Conclusions

In this article, I presented a simple way to calculate the optimal route for a list of addresses. Currently, Google Maps has a limit of 25 maximum addresses. The limit can be extended if you own a G Suite subscription and are available to pay for the extra computations.

If you find this post useful, please leave a comment and share it on your social media channels. Thank you!

Related Articles

A better use of lookup(), vlookup(), and hlookup() with examples for Google Sheets

There is a better way to use Google Sheets lookup() functions With a few simple examples you will learn how to hide your data (hash tables) and use the functions in a more advanced yet simple way.

Referring Columns By Name in Google Sheets Query()

This article shows a better way to import and link CSV files into a Google spreadsheet. By using a simple technique you can protect your spreadsheet and safely query data from an external CSV even when the structure of the CSV files changes.