GMPRO TSP solver: Google Maps with more than 25 waypoints

In this blog post, I'll show you how to use GMPRO to solve the Travelling Salesman Problem (TSP) and optimize a route with more than 25 waypoints or stops. You'll learn how to enable GMPRO on Google Cloud, configure the necessary permissions and roles, and make your first API request to GMPRO. Think of this tutorial as a "Hello World" for GMPRO.

Part 1: GMPRO: Google Maps Platform route optimization API
Part 2: GMPRO TSP solver: Google Maps with more than 25 waypoints (this article)
Part 3: Google Maps route optimization: multi vehicle
Part 4: GMPRO fleet routing app - free route planner for multiple stops
Part 5: GMPRO docs: Fixed vehicle costs
Part 6: GMPRO docs: Territory optimization and route planning
Part 7: GMPRO docs: Solving the VRP with route clustering and soft constraints
Part 8: GMPRO docs: Driver load balancing with soft constraints
Part 9: GMPRO docs: Driver breaks

What is the Travelling Salesman Problem (TSP)?

The Traveling Salesman Problem (TSP) is a classic optimization problem in the field of operations research and computer science. It can be defined as follows:

A salesman must visit a set of cities exactly once and return to the starting city, with the goal of minimizing the total travel distance or cost. Formally, given a list of cities and the distances between each pair of cities, the task is to find the shortest possible route that visits each city once and returns to the origin city.

As mathematical problems go, it's surprisingly practical and something that many people encounter in their daily life. If you were a door-to-door salesman selling encyclopedias or vacuum cleaners that needed to travel from one house to another (a travelling salesman, if you will), the TSP is something you'd need to solve on a daily basis.

How do I plan a route on Google Maps to solve the TSP?

Several years after Google Maps was launched, it shipped with a feature that let you add waypoints to a route and connect them together to form a longer route. This was great! Our door-to-door salesman could now plan his day by adding stops to his route and have Google Maps string them together, complete with turn-by-turn driving directions and Estimated Arrival Times (ETAs).

However, the route given by Google Maps follows the order of waypoints as entered. It does not automatically optimize the order to minimize drive time, which is something any smart travelling salesman would want.

To solve the TSP, he could instead use the Google Directions API with the flag optimize:true to optimize the provided route by rearranging the waypoints in a more efficient order.

https://maps.googleapis.com/maps/api/directions/json?
origin={origin}
&destination={destination}
&waypoints=optimize:true|{first_waypoint}|{second_waypoint}|...|{last_waypoint}
&key=GOOGLE_API_KEY

Travel time is the primary factor which is optimized, but other factors such as distance, number of turns etc are taken into account when deciding which route is the most efficient. However, you are limited to optimizing just 25 waypoints.

What’s the big deal about optimizing more than 25 waypoints?

For more than ten years, the Directions API was stuck with this 25 waypoint limit. And what if you wanted to optimize stops for more than two or more salespeople? Or a fleet of delivery vehicles? The directions API definitely couldn’t do that, and in that time, a whole generation of startups such as Onfleet, Routific, Route4Me and dozens more popped up to solve this problem and fulfill the market need for multi-vehicle route optimization.

In fact, demand for software to overcome the single vehicle, 25 waypoint limit of the directions API was so high that almost every route optimization startup wrote content marketing posts explaining how their software was best positioned to help you do so:

1. How To Route With Multiple Stops On Google Maps (Routific)
2. How To Optimize Route On Google Maps: 4 Simple Ways (Route4Me)
3. Can Google Maps or Waze Optimize Delivery Routes? (Onfleet)

Can Google compete this late in the game? GMPRO is ten years late to the route optimization party, but the tech giant has some several things going for them:

1. Brand. The trusted, familiar Google Maps brand is the default choice for any software project with a mapping component.
2. Price. GMPRO's multi vehicle route optimization API starts at $0.03 per optimized visit - 5x less than the competition.
3. Real time traffic. Other route optimization providers need to integrate with a data provider such as HERE Maps, Tom Tom, or (no surprise) Google Maps. This adds costs and latency to the route optimization request.

My view is that Google can win, but they can also lose. Selling route optimization software is not easy. Sales cycles are long and you need a sales team that understands both the technical implementation ("here's how you implement soft time windows in a capacitated pickup and delivery problem") and business value ("do this to cut down your route planning process from two hours to two minutes a day"). The existing route optimization API providers have this capability in spades.

Getting ready to make your first GMPRO API request

OK, story time's over. Let's learn how to make a single vehicle route optimization request to GMPRO.

GMPRO setup and authentication

To set up GMPRO, the first thing you need to do is enable it in your Google Cloud console. First, create a new project from the console dashboard at https://console.cloud.google.com/ and name it gmpro-tutorial. Click [CREATE].

Next, enable the Route Optimization API by going to the APIs & Services page and selecting it on the left hand menu. Once there, choose [+ Enable APIs and Services] and search for the "Route Optimization API" (not the NextBillion.ai one). Press [ENABLE].

After this, we need to set up Identity Access Management (IAM) roles and permissions to allow you to use GMPRO (IAM roles and permissions for route optimization). On the search bar on the header, type in "IAM" and select the [IAM & Admin] option.

Search for the user you are logged in as (in most cases this will be the account owner) and click the pencil [Edit Principal] icon.

Assign that user with the role of [Route Optimization Editor], and click [Save].

Great! Just a few more steps and we are ready to make our first GMPRO API request.

Logging into the Google Cloud CLI

To make our first GMPRO request, you need to download and install the Google Cloud CLI (Command Line Interface). Open your favorite command line shell (typically Terminal on MacOS or PowerShell on Windows) then initialize the Google Cloud CLI by running the following command:

gcloud init

You'll be asked to choose a user to log in with. Select the one you gave Route Optimization Editor privileges to in the previous step.

Next, choose the GCP project gmpro-tutorial we enabled the Route Optimization API with. Once that is done, we are finally ready to make our first GMPRO request.

GMPRO Travelling Salesman Problem API example

We are going to make a route optimization API request for a single vehicle that needs to make one dropoff. This is a small-scale, single city instance of the classic Travelling Salesman Problem. This request will be sent to the /optimizeTours endpoint of GMPRO, which is a synchronous endpoint (this means the client sends the request and waits for the server to send the response once the optimization is complete).

curl -X POST 'https://routeoptimization.googleapis.com/v1/{project_id}:optimizeTours' \
-H "Content-Type: application/json" \
-H "Authorization: Bearer $(gcloud auth application-default print-access-token)" \
--data-binary @- << EOM
{
  "model": {
    "shipments": [
      {
        "deliveries": [
          {
            "arrivalLocation": {
              "latitude": 49.227107,
              "longitude": -123.1163085
            }
          }
        ],
        "label": "shipment-01"
      }
    ],
    "vehicles": [
      {
        "startLocation": {
          "latitude": 49.2553636,
          "longitude": -123.0873365
        },
        "endLocation": {
          "latitude": 49.2201308,
          "longitude": -123.1085687
        },
        "label": "vehicle-a",
        "costPerKilometer": 1
      }
    ],
    "globalStartTime": "2023-01-13T16:00:00-08:00",
    "globalEndTime": "2023-01-14T16:00:00-08:00"
  },
  "populatePolylines": true
}
EOM

Copy and paste the following code snippet onto the command line, swap out {project_id} with the name given to the project created in the previous section e.g. "gmpro-tutorial" and press enter:

Input

Model, Shipments and Vehicles

model captures settings and constraints for the entire request, which includes both shipments and vehicles. In the request above, I've added two constraints, globalStartTime and globalEndTime to model the earliest start time and latest end time of all routes included in the optimization.

I've also included an additional field, populatePolylines: true. This returns an encoded polyline string in the response which represents the route taken by each vehicle in completing the shipments assigned to it.

shipments represent tasks or actual shipments that includes a delivery. Each delivery can come with loads (how heavy a particular shipment is or how much space it takes up) and timeWindows (which specify when this shipment needs to be picked up and dropped off). Each delivery is defined by a latitude or longitude, so if you only have the address string, you'll have to geocode it first using the Geocoding API.

vehicles represent the drivers (or autonomous robo-taxis, whenever that future comes to pass) that will be physically doing the deliveries. Each vehicle comes with a startLocation and optional endLocation that sets where the vehicle starts and ends his route. Usually the startLocation would be the central warehouse or depot. If the driver operates his own vehicle, it could be his home address.

"costPerKilometer": 1 sets a baseline for your driving distance costs. GMPRO or any delivery route optimization package is going to try to route as many deliveries as possible for the smallest cost, and if you skip this field the route solution returned will not use the shortest route possible.

Output

The output of the GMPRO Route Optimization API is a route plan - a collection of optimized routes for each driver. Once the above request is sent over, you should get a response that looks similar to the following:

{
    "routes": [
        {
            "vehicleLabel": "vehicle-a",
            "vehicleStartTime": "2023-01-14T00:00:00Z",
            "vehicleEndTime": "2023-01-14T00:15:47Z",
            "visits": [
                {
                    "startTime": "2023-01-14T00:11:29Z",
                    "detour": "0s",
                    "shipmentLabel": "shipment-01"
                }
            ],
            "transitions": [
                {
                    "travelDuration": "689s",
                    "travelDistanceMeters": 5503,
                    "waitDuration": "0s",
                    "totalDuration": "689s",
                    "startTime": "2023-01-14T00:00:00Z"
                },
                {
                    "travelDuration": "258s",
                    "travelDistanceMeters": 1852,
                    "waitDuration": "0s",
                    "totalDuration": "258s",
                    "startTime": "2023-01-14T00:11:29Z"
                }
            ],
            "routePolyline": {
                "points": "_eskH`pgnVX?d@?xABEhE?zBAvCx@@xBDr@?d@@B?r@@N?P?jBBjA@rDDd@@b@@jB@b@@hB@d@@^?f@@\\?P?xABpB?bEF`CDlA@\\@fC@`@?lED|BDbABRAxC@fDB\\?J?dA?x@BfA@DBB?D@tA@Z?fA@b@@X?rBBdCBfB@fDBfA@pB@lD@XLHBrA?v@?N?CtFA|B?xA?\\@HD`@AbC?nBAnBCnFCxDC~ECNCJ?F?P?^Al@?JC`BAxAEvF?v@CbCAbC?nD@f@BHCnEA|BQlNEfEEbD?TC|AGn@IdGMxF?XK|GAzAErCAx@V?V@X@d@DrA@^?p@@jBBtBBV@h@?zABr@@N?TAl@@L?J@rA@`@@L?fA@~@@F?H@b@?T?~@@\\@t@@x@@R?FEDALCRCTC@?HAFCFCFGFIUAkACI?q@Aa@AO?A?O?e@?aBCoACkBA@u@@oB?ED_DD}CDwCzAAxA?zAExAExACz@?XAFuE@G?AFuD?Q?S?K?]B_A@{@ByADuD@W?y@BkC?SBaC?Q@_CZ?z@?H?nABN?bA@N@H?jABT?hA@J@xA@fDDL?jDD?@?@?@?@@??@@??@@??@@?@?@??A@?@??A?A@??A?A@??A?A?AdDF"
            },
            "metrics": {
                "performedShipmentCount": 1,
                "travelDuration": "947s",
                "waitDuration": "0s",
                "delayDuration": "0s",
                "breakDuration": "0s",
                "visitDuration": "0s",
                "totalDuration": "947s",
                "travelDistanceMeters": 7355
            }
        }
    ],
    "metrics": {
        "aggregatedRouteMetrics": {
            "performedShipmentCount": 1,
            "travelDuration": "947s",
            "waitDuration": "0s",
            "delayDuration": "0s",
            "breakDuration": "0s",
            "visitDuration": "0s",
            "totalDuration": "947s",
            "travelDistanceMeters": 7355
        },
        "usedVehicleCount": 1,
        "earliestVehicleStartTime": "2023-01-14T00:00:00Z",
        "latestVehicleEndTime": "2023-01-14T00:15:47Z"
    }
}

The key part of the returned JSON is the routes array, which contains route objects that describe the optimal route for each vehicle. In the example above, only a single route is returned because there is just one driver.

These objects provide all the information your drivers need to ensure on-time deliveries. Here’s a summary of what the route object (from the response above) looks like:

root
 ├── routes (array)
 │   ├── [0] (object)
 │   │   ├── vehicleLabel: "vehicle-a"
 │   │   ├── vehicleStartTime: "2023-01-14T00:00:00Z"
 │   │   ├── vehicleEndTime: "2023-01-14T00:15:47Z"
 │   │   ├── visits (array)
 │   │   │   ├── [0] (object)
 │   │   │   │   ├── startTime: "2023-01-14T00:11:29Z"
 │   │   │   │   ├── detour: "0s"
 │   │   │   │   ├── shipmentLabel: "shipment-01"
 │   │   ├── transitions (array)
 │   │   │   ├── [0] (object)
 │   │   │   │   ├── travelDuration: "689s"
 │   │   │   │   ├── travelDistanceMeters: 5503
 │   │   │   │   ├── waitDuration: "0s"
 │   │   │   │   ├── totalDuration: "689s"
 │   │   │   │   ├── startTime: "2023-01-14T00:00:00Z"
 │   │   │   ├── [1] (object)
 │   │   │   │   ├── travelDuration: "258s"
 │   │   │   │   ├── travelDistanceMeters: 1852
 │   │   │   │   ├── waitDuration: "0s"
 │   │   │   │   ├── totalDuration: "258s"
 │   │   │   │   ├── startTime: "2023-01-14T00:11:29Z"
 │   │   ├── routePolyline (object)
 │   │   │   ├── points: "_eskH`pgnVX?...@?J@rA@`@@L?fA@~@@F?H@b@?T?~@@\\@t@@x@@R?FEDALCRCTC@?HAFCFCFGFIUAkACI?q@Aa@AO?A?O?e@?aBCoACkBA@u@@oB?ED_DD}CDwCzAAxA?zAExAExACz@?XAFuE@G?AFuD?Q?S?K?]B_A@{@ByADuD@W?y@BkC?SBaC?Q@_CZ?z@?H?nABN?bA@N@H?jABT?hA@J@xA@fDDL?jDD?@?@?@?@@??@@??@@??@@?@?@??A@?@??A?A@??A?A@??A?A?AdDF"
 │   │   ├── metrics (object)
 │   │   │   ├── performedShipmentCount: 1
 │   │   │   ├── travelDuration: "947s"
 │   │   │   ├── waitDuration: "0s"
 │   │   │   ├── delayDuration: "0s"
 │   │   │   ├── breakDuration: "0s"
 │   │   │   ├── visitDuration: "0s"
 │   │   │   ├── totalDuration: "947s"
 │   │   │   ├── travelDistanceMeters: 7355
 ├── metrics (object)
 │   ├── aggregatedRouteMetrics (object)
 │   │   ├── performedShipmentCount: 1
 │   │   ├── travelDuration: "947s"
 │   │   ├── waitDuration: "0s"
 │   │   ├── delayDuration: "0s"
 │   │   ├── breakDuration: "0s"
 │   │   ├── visitDuration: "0s"
 │   │   ├── totalDuration: "947s"
 │   │   ├── travelDistanceMeters: 7355
 │   ├── usedVehicleCount: 1
 │   ├── earliestVehicleStartTime: "2023-01-14T00:00:00Z"
 │   ├── latestVehicleEndTime: "2023-01-14T00:15:47Z"

routes: contains visits (stops) and transitions (travel activity between visits) for each vehicle’s route, and vehicle/route level metrics such as travel time, wait time and distance travelled.

metrics: stores global aggregated metrics and statistics across all vehicles and shipments.

Visually, you can think of each route as a timeline, with visits listed in order and transitions leading to and from each visit.

Returning to the Travelling Salesman Problem

How is all this relevant to solving the Travelling Salesman Problem? A call to the Route Optimization API formally defines the parameters of the problem in code. Returning to the definition of the TSP:

A salesman must visit a set of cities exactly once and return to the starting city, with the goal of minimizing the total travel distance or cost. Formally, given a list of cities and the distances between each pair of cities, the task is to find the shortest possible route that visits each city once and returns to the origin city.

vehicles represents the travelling salesman (where he starts and ends) while shipments represents the locations of each city that he has to visit.

Try running the code below (gmpro_curl_text-25city-tsp.json) to run a route with more than 25 waypoints on GMPRO.

Our intrepid travelling salesman starts his day in Vancouver, BC and ends in Nelson BC after making a three day tour of most of British Columbia, the Canadian Rockies, and Calgary AB.

The cities he visited (in order) are: Vancouver, BC, Canada, Burnaby, BC, Canada, Port Moody, BC, Canada, Coquitlam, BC, Canada, Port Coquitlam, BC, Canada, Surrey, BC, Canada, Langley, BC, Canada, Abbotsford, BC, Canada, Mission, BC, Canada, Chilliwack, BC, Canada, Hope, BC, Canada, Meritt, BC, Canada, Princeton, BC, Canada, Keremeos, BC, Canada, Osoyoos, BC, Canada, Kelowna, BC, Canada, Revelstoke, BC, Canada, Golden, BC, Canada, Lake Louise, BC, Canada, Banff, AB, Canada, Canmore, BC, Canada, Calgary, AB, Canada, Fernie, BC, Canada, Cranbook, BC, Canada and Nelson, BC, Canada.

How much will this API call cost you? Each shipment in the input JSON for a single-vehicle optimization costs $0.01 ($10 per 1,000 visits - see the official pricing page for the Google Maps Platform), so this 25 shipment call will cost you $0.25.

Afi Labs can help you build your route optimization system on GMPRO or other Google Maps APIs. 👋 Say Hello! to start working together.

In this tutorial, you learned how to make a single vehicle (TSP) API request. In the next one, I'll show you how to use GMPRO to solve the multi-vehicle Vehicle Routing Problem (VRP), as well as how to apply more advanced constraints like time windows, visit durations, loads, capacities, and much more.

👋 As always, if you have any questions or suggestions for me, please reach out or say hello on LinkedIn.

Next: Part 3: Google Maps route optimization: multi vehicle