Google Maps route optimization: multi vehicle

Afian Anwar -

In my last blog post, I explained how to use the Google Maps Platform Route Optimization (GMPRO) API to solve the single-vehicle Travelling Salesman Problem. In this post, I'll demonstrate how GMPRO can also be used to tackle the multi-vehicle Vehicle Routing Problem. We will utilize GMPRO to model the operations of a last-mile delivery company, incorporating factors such as time windows, vehicle capacities, and driver shift times. At the end, I'll discuss GMPRO pricing in detail and compare it to other route optimization providers.

A pickup and dropoff route created using Google Maps route optimization

Part 1: GMPRO: Google Maps Platform route optimization API
Part 2: GMPRO TSP solver: Google Maps with more than 25 waypoints
Part 3: Google Maps route optimization: multi vehicle (this article)
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

What is the Vehicle Routing Problem?

The Vehicle Routing Problem (VRP) is a complex combinatorial optimization problem that aims to determine the most efficient routes for a fleet of vehicles to deliver goods or services to a set of customers. The primary objective is to minimize the total transportation cost, which may include factors such as distance, time, and fuel consumption. The VRP is a fundamental problem in the fields of logistics, transportation, and supply chain management.

Google Maps route optimization to solve the Vehicle Routing Problem

Software tools or algorithms that solve the VRP are called VRP solvers. The Google Maps route optimization API, GMPRO, is one such solver.

There are two main inputs into the VRP - shipments and vehicles.

shipments represent the deliveries that need to be made. 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).

vehicles are the drivers doing the deliveries. Each vehicle needs a startLocation and (optional) endLocation that sets where the vehicle starts and ends his route.

Both shipments and vehicles are part of the model object, which contains the settings and constraints for the entire optimization request.

The output of the VRP is a route plan - a set of routes for each vehicle, including the sequence of stops and estimated times of arrival (ETAs).

👨‍💻
Screenshots in this blog post were taken with GMPRO-viewer , using data imported via GMPRO-json-converter. Both tools are free to use.

GMPRO delivery route optimization example

To solve the Vehicle Routing Problem (VRP) using GMPRO, we first need to model our delivery operations as a VRP. Imagine you are the operations manager at a logistics company and have several deliveries to manage. Each delivery weighs 1 kg.

pkg_id delivery_address duration load time windows
yvr123 198 W 18th Ave, Vancouver
(49.2545595, -123.1096174)		 10 min 1 09:00 - 11:00
yvr456 9500 Alberta Rd, Richmond
(49.1654802, -123.1187887)		 10 min 1 09:00 - 11:00
yvr789 766 Calverhall St, North Vancouver
(49.313724, -123.0514561)		 10 min 1 09:00 - 11:00
yvr987 3711 Delbrook Ave, North Vancouver
(49.343481, -123.0863414)		 10 min 1 09:00 - 11:00
yvr654 1074 Jefferson Ave, West Vancouver
(49.3352081, -123.1453979)		 10 min 1 09:00 - 11:00
yvr321 5491 Greenleaf Rd, West Vancouver
(49.3513846, -123.2631103)		 10 min 1 09:00 - 11:00

You also have two drivers Mark and Will who work as independent contractors. They drive their own delivery vans and start work from their own homes. Their vans are quite old, so they can only carry up to 5 kg of packages.

veh_id start_address capacity shift time
mark-yvr 1132 E Hastings St, Vancouver
(49.2808457, -123.0827831)		 5 08:00 - 12:00
will-yvr Deep Cove, North Vancouver
(49.3191441, -122.9522224)		 5 08:00 - 12:00

How do we model this last mile delivery route optimization scenario as a GMPRO API call?

Shipments

First, we are going to map each field in the delivery manifest as a shipment. Taking the first package yvr123 as an example:

Package ID

"label": "yvr123" indicates that this particular shipment belongs to a package with id yvr123.

Delivery Address

To set the delivery address for each shipment, we use the arrivalLocation object. In the example below, driver mark-yvr has to "arrive" at coordinates (49.2808457, -123.0827831) corresponding to the delivery address 198 W 18th Ave, Vancouver. If you don't have the coordinates on have you'll have to geocode them beforehand using the Geocoding API or similar.

"arrivalLocation": {
        "latitude": 49.2808457, 
        "longitude": -123.0827831
    }

Duration

Also known as service time, "duration": "600s" means that when the driver arrives, he will spend 10 minutes (60 sec x 10 min = 600 sec) making the delivery. This includes the time spent looking for parking, calling the customer and making sure that the package arrives safely at the customer's doorstep.

Load

loadDemands on the shipments object is used together with loadLimits on the vehicles object to determine how many deliveries each driver can do without exceeding the capacity of his vehicle. For example, if his vehicle can safely carry 5 kg of packages and each package weighs 1 kg on average, GMPRO will use this information to ensure that the driver will never be assigned more than 5 deliveries. 

"loadDemands": {
        "weight": {
            "amount": "1"
        }
    }

Time Windows

timeWindows (array) is an array with a single object that stores the startTime (string) and endTime (string) of the delivery time window in ISO8601 format. For example, if you are delivering a package to a business based in London, UK, and want to make sure your driver only arrives there during business hours, you could use "startTime": "2024-07-08T09:00:00Z" , "endTime": "2024-07-08T17:00:00Z" to guarantee that the route optimization algorithm schedules this visit between 9 am and 5 pm.

💡
In GMPRO, timestamps must be provided in RFC3339 UTC "Zulu" format. This means you need to convert your local delivery time to UTC. For example, 09:00 in Vancouver, BC is 16:00 UTC on 8 July 2024 (taking into account Daylight Savings Time).
"timeWindows": [
        {
            "endTime": "2024-07-08T16:00:00Z",
            "startTime": "2024-07-08T18:00:00Z"
        }
    ]

Putting everything together, here's what the shipment object for the single package package yvr123 looks like:

{
    "shipments": [
        {
            "deliveries": [
                {
                    "arrivalLocation": {
                        "latitude": 49.2545595,
                        "longitude": -123.1096174
                    },
                    "duration": "600s",
                    "timeWindows": [
                        {
                            "startTime": "2024-07-08T16:00:00Z",
                            "endTime": "2024-07-08T18:00:00Z"
                        }
                    ]
                }
            ],
            "loadDemands": {
                "weight": {
                    "amount": "1"
                }
            }
        }
        "label": "yvr123"
    ]
}

Vehicles

Second, we need to model our drivers as vehicles.

Vehicle ID

"label": "mark-yvr" lets you specify that this vehicle object corresponds to the driver Mark (mark-yvr).

Start Address

startLocation and endLocation are objects that let you specify the (required) start location and (optional) end location of your drivers. These two parameters influence which deliveries are assigned to a driver because ideally, they'd be given jobs that are "on the way". In our example, both Mark and Will operate as independent contractors, so they both start from home.

"startLocation": {
        "latitude": 49.2545595, 
        "longitude": -123.1096174
    }

Capacity

loadLimits  tells you what the maximum capacity of the vehicle is. It's used together with loadDemands on the shipment object to ensure that packages assigned to a driver's route never exceeds the vehicle's carrying capacity. For example, to set a vehicle capacity of 5 kg, you would set weight to have a "maxLoad":5.

{
    "loadLimits": {
        "weight": {
            "maxLoad": 5
        }
    }
}

Shift Time

StartTimeWindows and endTimeWindows let you set when the driver starts and ends his route. For example, setting startTime to "08:00" and endTime to "12:00" means that the driver will leave his startLocation at exactly 08:00 and arrive at his endLocation by 12:00. If no endLocation is specified, it means that his last delivery will be completed before 12:00.

"startTimeWindows": [
        {
            "startTime": "2024-07-08T08:00:00Z"
        }
    ],
    "endTimeWindows": [
        {
            "endTime": "2024-07-08T12:00:00Z"
        }
    ]

Costs

"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, so you need to tell GMPRO what these costs are in order for it to calculate an efficient route.

⚠️
If you don't specify a costPerKilometer in the vehicle object, then anything goes and the route solution returned will be garbage.

Additional Options

I have also included an additional field, populatePolylines: true. This field returns an encoded polyline string in the response, representing the route taken by each vehicle to complete its assigned shipments.

Here is the complete JSON representation of a single vehicle object:

{
    "vehicles": [
        {
            "startLocation": {
                "latitude": 49.2545595,
                "longitude": -123.1096174
            },
            "loadLimits": {
                "weight": {
                    "maxLoad": 5
                }
            },
            "startTimeWindows": [
                {
                    "startTime": "2024-07-08T08:00:00Z"
                }
            ],
            "endTimeWindows": [
                {
                    "endTime": "2024-07-08T12:00:00Z"
                }
            ],
            "label": "mark-yvr"
        }
    ]
}

Input

And here's what the complete Google Maps route optimization request for our 4 shipment 2 vehicle example looks like:

curl -X POST 'https://routeoptimization.googleapis.com/v1/{project_id}' \
-H "Content-Type: application/json" \
-H "Authorization: Bearer $(gcloud auth application-default print-access-token)" \
--data-binary @- << EOM
{
    "model": {
        "shipments": [
            {
                "deliveries": [
                    {
                        "arrivalLocation": {
                            "latitude": 49.2545595,
                            "longitude": -123.1096174
                        },
                        "duration": "600s",
                        "timeWindows": [
                            {
                                "startTime": "2024-07-08T16:00:00Z",
                                "endTime": "2024-07-08T18:00:00Z"
                                
                            }
                        ]
                    }
                ],
                "loadDemands": {
                    "weight": {
                        "amount": "1"
                    }
                },
                "label": "yvr123"
            },
            {
                "deliveries": [
                    {
                        "arrivalLocation": {
                            "latitude": 49.1654802,
                            "longitude": -123.1187887
                        },
                        "duration": "600s",
                        "timeWindows": [
                            {
                                "startTime": "2024-07-08T16:00:00Z",
                                "endTime": "2024-07-08T18:00:00Z"
                            }
                        ]
                    }
                ],
                "loadDemands": {
                    "weight": {
                        "amount": "1"
                    }
                },
                "label": "yvr456"
            },
            {
                "deliveries": [
                    {
                        "arrivalLocation": {
                            "latitude": 49.313724,
                            "longitude": -123.0514561
                        },
                        "duration": "600s",
                        "timeWindows": [
                            {
                                "startTime": "2024-07-08T16:00:00Z",
                                "endTime": "2024-07-08T18:00:00Z"
                            }
                        ]
                    }
                ],
                "loadDemands": {
                    "weight": {
                        "amount": "1"
                    }
                },
                "label": "yvr789"
            },
            {
                "deliveries": [
                    {
                        "arrivalLocation": {
                            "latitude": 49.343481,
                            "longitude": -123.0863414
                        },
                        "duration": "600s",
                        "timeWindows": [
                            {
                                "startTime": "2024-07-08T16:00:00Z",
                                "endTime": "2024-07-08T18:00:00Z"
                            }
                        ]
                    }
                ],
                "loadDemands": {
                    "weight": {
                        "amount": "1"
                    }
                },
                "label": "yvr987"
            },
            {
                "deliveries": [
                    {
                        "arrivalLocation": {
                            "latitude": 49.3352081,
                            "longitude": -123.1453979
                        },
                        "duration": "600s",
                        "timeWindows": [
                            {
                                "startTime": "2024-07-08T16:00:00Z",
                                "endTime": "2024-07-08T18:00:00Z"
                            }
                        ]
                    }
                ],
                "loadDemands": {
                    "weight": {
                        "amount": "1"
                    }
                },
                "label": "yvr654"
            },
            {
                "deliveries": [
                    {
                        "arrivalLocation": {
                            "latitude": 49.3513846,
                            "longitude": -123.2631103
                        },
                        "duration": "600s",
                        "timeWindows": [
                            {
                                "startTime": "2024-07-08T16:00:00Z",
                                "endTime": "2024-07-08T18:00:00Z"
                            }
                        ]
                    }
                ],
                "loadDemands": {
                    "weight": {
                        "amount": "1"
                    }
                },
                "label": "yvr321"
            }
        ],
        "vehicles": [
            {
                "startLocation": {
                    "latitude": 49.2808457,
                    "longitude": -123.0827831
                },
                "loadLimits": {
                    "weight": {
                        "maxLoad": 5
                    }
                },
                "startTimeWindows": [
                    {
                        "startTime": "2024-07-08T16:00:00Z"
                    }
                ],
                "endTimeWindows": [
                    {
                        "endTime": "2024-07-08T18:00:00Z"
                    }
                ],
                "label": "mark-yvr",
                "costPerKilometer": 1
            },
            {
                "startLocation": {
                    "latitude": 49.3191441,
                    "longitude": -122.9522224
                },
                "loadLimits": {
                    "weight": {
                        "maxLoad": 5
                    }
                },
                "startTimeWindows": [
                    {
                        "startTime": "2024-07-08T16:00:00Z"
                    }
                ],
                "endTimeWindows": [
                    {
                        "endTime": "2024-07-08T18:00:00Z"
                    }
                ],
                "label": "will-yvr",
                "costPerKilometer": 1
            }
        ],
        "globalStartTime": "2024-07-08T07:00:00Z",
        "globalEndTime": "2024-07-09T06:59:00Z"
    },
    "populatePolylines": true
}
EOM

Run the code above in the Google Cloud CLI (instructions can be found in our last post) and wait a few seconds for the response.

Output

{
  "routes": [
    {
      "vehicleLabel": "mark-yvr",
      "vehicleStartTime": "2024-07-08T16:00:00Z",
      "vehicleEndTime": "2024-07-08T16:55:21Z",
      "visits": [
        {
          "startTime": "2024-07-08T16:14:53Z",
          "detour": "0s",
          "shipmentLabel": "yvr123",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        },
        {
          "shipmentIndex": 1,
          "startTime": "2024-07-08T16:45:21Z",
          "detour": "1101s",
          "shipmentLabel": "yvr456",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        }
      ],
      "transitions": [
        {
          "travelDuration": "893s",
          "travelDistanceMeters": 4995,
          "waitDuration": "0s",
          "totalDuration": "893s",
          "startTime": "2024-07-08T16:00:00Z",
          "vehicleLoads": {
            "weight": {
              "amount": "2"
            }
          }
        },
        {
          "travelDuration": "1228s",
          "travelDistanceMeters": 11934,
          "waitDuration": "0s",
          "totalDuration": "1228s",
          "startTime": "2024-07-08T16:24:53Z",
          "vehicleLoads": {
            "weight": {
              "amount": "1"
            }
          }
        },
        {
          "travelDuration": "0s",
          "waitDuration": "0s",
          "totalDuration": "0s",
          "startTime": "2024-07-08T16:55:21Z",
          "vehicleLoads": {
            "weight": {}
          }
        }
      ],
      "routePolyline": {
        "points": "_dxkHnrfnV?`@HAN??f@Ar@@^@TDPFRBP@F?@@P?^?^?X?BAp@Z@|@@xADjA@N@hA@L@|ABtA?zA@xAHHCpA@GbMAX?XApBAlB?FC|C?t@ArBAv@AlBAlBCzEAv@AlBElKApAA\\A\\OhBc@Be@DK@c@D[DK@EvE?XCrC?Z?ZAdBAb@J?J@f@?rBFF?D@bCBhCDlA@T@jCFtA@dDD^Bf@?R@l@@L@P@JBH@?@t@VRHLDl@Xh@TXHF@HDL@L@X@X@H?XALAP?D?`@@l@?j@@t@BZ?v@@jBBrA?D?FADCJG~@BlCBDF@@?@@@@?@@Z@b@@Z@j@?NBR?`@B\\?fAB~@@L@R@tA@hADzCHnA@\\?hAB~AB`A?T?d@@dAB~@@L?jDF\\AP?R?H?N@d@?B?V@T?NKxABr@@D?L?rCDb@@ApA?fA?LCfFAzDAvCAl@CxCEtE?V?RGvFGrFdBFxADD?|ABF@bBBh@@l@@|A@~ABhBBxABtA@vABzAB`@?b@@b@@fBBhBBdAF^B?d@?pAApA?bBCvB?bA?x@CzAAlA?`@AnD?h@AlA?R?XCpBAhC?ZATAlB?@AjB?HAl@?f@AhB?NClE?N?L?FAF?RA~B?d@?N?v@AnBEbE?@EnGC`CEpDAtA?F?t@C|A?`@N@PA^@V@~@BhA@fA@P?@?NEP?`ABR?l@@N?`B@zAARHDBF?|@@v@@lB@`@@lBB|@@PIfA@jCDzDDRAt@@h@?`A?pBBz@@f@?fA@L@T?hBHr@B`ABF?L@H?dA@@?jBB`HDXJJB|@@bA?N?fA@T@H?fDDn@?X?PA@AJEjA?fB@T@zFFN?~ADdA@vDDl@@tABDDBBD@\\@lA@h@@d@@R@P@\\?j@A\\?L?l@@rABF?VK~@B`CDN?ZDjB@rBB|FFd@?nA?r@B`@@f@?vA?b@@D?T@T?n@BZ@RBVB^DB?^FTDVFPDZHZHZHTH@@XJXJXLZLPJVJXLB@RF@@RFDBVH`@J\\JXFf@Jb@FZDZD^DVBT@F?Z@@?\\@R@lEDtABdEDfDDvABvA@hIHb@?tBDP@T?d@@V?d@J\\@P?zAGl@E`@AB?B?XC@?D?^CtASPETE^MLENERG\\Sf@UTKNKTMd@]^Y@CZWPOZYRQf@e@bA_ApAkAv@q@l@k@x@u@TSrBmBDCtAqAd@_@\\[pAmAlAiAdDyCPMj@i@v@s@`CyBrAkAdB_BPONOBCPQdB{Af@e@dAaAj@e@HIJK~CqCJKr@o@BCz@w@NONMJIJI~@{@|@y@ROp@k@p@o@h@m@`@g@BCLSNUV_@j@aADGNWhAgBZe@d@w@h@{@l@cAPYDGt@qAj@}@FST?NGLEJAHANAX?T@H@N@tAB^@fA?bA@nC@JEFAF?|ECjA?zAAhB@lC?|C?X?lG?J@xA?jA@PAxA?T@x@?~@@Z@jB?R?Z?l@?bBAx@?rB?pAA`@@|RCN?|C?ZAx@Al@?P@ZDn@@n@?h@AJ?N?~B?`H@pB?X?D?zB?RA?rA?R?nB?rBAzB?\\?T@dA?x@?`C?lBAh@?f@d@B"
      },
      "metrics": {
        "performedShipmentCount": 2,
        "travelDuration": "2121s",
        "waitDuration": "0s",
        "delayDuration": "0s",
        "breakDuration": "0s",
        "visitDuration": "1200s",
        "totalDuration": "3321s",
        "travelDistanceMeters": 16929,
        "maxLoads": {
          "weight": {
            "amount": "2"
          }
        }
      },
      "routeCosts": {
        "model.vehicles.cost_per_kilometer": 16.929
      },
      "routeTotalCost": 16.929
    },
    {
      "vehicleIndex": 1,
      "vehicleLabel": "will-yvr",
      "vehicleStartTime": "2024-07-08T16:00:00Z",
      "vehicleEndTime": "2024-07-08T17:24:15Z",
      "visits": [
        {
          "shipmentIndex": 2,
          "startTime": "2024-07-08T16:12:22Z",
          "detour": "0s",
          "shipmentLabel": "yvr789",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        },
        {
          "shipmentIndex": 3,
          "startTime": "2024-07-08T16:31:33Z",
          "detour": "918s",
          "shipmentLabel": "yvr987",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        },
        {
          "shipmentIndex": 4,
          "startTime": "2024-07-08T16:51:04Z",
          "detour": "1904s",
          "shipmentLabel": "yvr654",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        },
        {
          "shipmentIndex": 5,
          "startTime": "2024-07-08T17:14:15Z",
          "detour": "2882s",
          "shipmentLabel": "yvr321",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        }
      ],
      "transitions": [
        {
          "travelDuration": "742s",
          "travelDistanceMeters": 7934,
          "waitDuration": "0s",
          "totalDuration": "742s",
          "startTime": "2024-07-08T16:00:00Z",
          "vehicleLoads": {
            "weight": {
              "amount": "4"
            }
          }
        },
        {
          "travelDuration": "551s",
          "travelDistanceMeters": 6170,
          "waitDuration": "0s",
          "totalDuration": "551s",
          "startTime": "2024-07-08T16:22:22Z",
          "vehicleLoads": {
            "weight": {
              "amount": "3"
            }
          }
        },
        {
          "travelDuration": "571s",
          "travelDistanceMeters": 6406,
          "waitDuration": "0s",
          "totalDuration": "571s",
          "startTime": "2024-07-08T16:41:33Z",
          "vehicleLoads": {
            "weight": {
              "amount": "2"
            }
          }
        },
        {
          "travelDuration": "791s",
          "travelDistanceMeters": 12159,
          "waitDuration": "0s",
          "totalDuration": "791s",
          "startTime": "2024-07-08T17:01:04Z",
          "vehicleLoads": {
            "weight": {
              "amount": "1"
            }
          }
        },
        {
          "travelDuration": "0s",
          "waitDuration": "0s",
          "totalDuration": "0s",
          "startTime": "2024-07-08T17:24:15Z",
          "vehicleLoads": {
            "weight": {}
          }
        }
      ],
      "routePolyline": {
        "points": "eq_lHldmmVBADCB@^BAB@D@DBBB@BABCHGH?D?BC\\[JM`@c@R@H@TBAFAHAL?|@?v@A`AAt@dAFdB?fBCzAC?\\At@?v@?rAAlB@p@AdF?lB?b@CpC?lB?lBAv@?dD?zC?T?hC?PAdD?HAbBArC?hA?t@?v@A`KAvB?f@Av@?fA?~@Gb@?^?N?pB@x@?XBjB@Z?h@@t@@lA@vA@v@BxBL|HH|H?LBlB@lBD~ED~E@n@@jAAnD?lB?r@?z@AdC?t@Av@?v@?lBAt@?nBCjBAnB?t@?vAAdBAtBC|EAdDAbDAtCChB?nA?|BAjBAzE?\\AdDAdB?p@AhBAtB?BAt@?v@?hB?B?j@?D?P?T@V@VDp@Ff@D^Ff@F\\BJF\\H\\FRDR`@zA`AnCL\\?@L\\`@jAt@xBL^JXNb@n@bBHTLTZl@bArBZj@pA~BdB|CVb@p@tAh@`A`@r@r@lANZr@bBTp@Np@TlAHdABl@@n@CbACh@ALGd@EZGh@G\\Mv@Kp@Kj@AFCVE`@Ej@?BEn@AZ?N?T?R?Z?NBj@@^@T@B@TH`ALlABVFv@JdA@HFt@Hz@Dd@@HFr@Dd@B\\@^@\\?\\?BAXA\\CXCPMj@?DI\\GPCFGN]t@CFCDs@rAi@fAm@jAO\\M\\KTIVENENKd@W~AE^CXEh@Eh@?BEhAAh@?f@AjAAd@?N?T?l@?l@?`@BjA@RFtADv@BhAD`@B\\DTNv@Lj@DNFVFVLd@Nn@FZFT?BDTFf@?p@?ZALAJCTEPITELGLEFEFGHEFABABABAD?De@TMFMFWNKLGLKPEJGPM\\IRQn@Md@CNITA@ETEJAHANAZA^Ih@El@?X?B?hA?D?X@|@A^?b@@lBC`F?X?JCbKAzAAPEr@?BAr@?@?J?j@?h@?bA?d@Ab@ArBAvA?v@?t@?~@?p@?lECbA?lA?N@HBJ?v@?X?^Av@AfBAbCAjD?`AEhE?zAAhBAZ?pAAlB?v@A`AMWMULTLV?hB?lAAdD?v@?~@AlB?vAClCAt@Av@?t@Af@M@c@AoCC]?a@AkBCG?s@C]?oC@c@?kBCc@AA?}@AoC@aA@{CGq@AoE?qBE}AEoCCc@A[?eCAO@K?O?OAMCoEEeCAkAA]C[E_@ESGOC]Im@U{@g@][GCe@i@IKOQAIAGMSS]q@oAe@iAa@}@Wo@M[GMSc@U?OLYTY^[`@MNm@x@i@|@EFKPWh@KTGJCDKTUb@Yj@A@C^O\\INWh@ABM\\M\\O`@ELITGTGNQl@K`@K`@K`@G^I`@EPCPO~@CTGb@ANCL?@Gj@C`@CPAPEh@A\\ATAZ?^?DA\\?`@@d@?b@@d@?^@L?X@~@BlA@bA@R@v@@jABhA?N?T@^@h@?`@@d@@`@?x@?d@?b@?r@?~@?^?n@AD?v@?l@?d@?zAAvA?F?z@@fA?j@?dA@bBAbA?lAAzA?r@?n@?R?H?h@?@A`A?l@?bA?j@A\\?V?n@?|@?l@AjA?j@?\\ArD?fA?p@?TAfA?hBCnBAlAAnAAz@AdAApAAp@?B?l@?^?fA?h@@X@tC@t@?P?P?H@t@@fA?x@@f@?p@OZA@?BExB?DCtACx@?@?n@A\\?B?X?nA?B@l@?p@?j@?XATA|@Ox@CLCDCDEHQTi@?cCDQPkA@wBCeAAA?iACO?w@?iB?_BCeACA?cBCS?A?wC@U?wAAq@Be@@]AMAIAICGCIEICGEGEIGiCcBuDcCcBkAkAu@gAo@qAy@On@It@Iz@INCHBIHOH{@Hu@No@pAx@fAn@jAt@bBjAtDbChCbBHFFDFDHBHDFBHBH@L@\\@d@Ap@CvA@T?vCA@?R?bBB@?dAB~ABhB?v@?N?hAB@?dA@vBBjAAPFjBB\\@lA@@l@?N?f@?F?F@d@?h@@T@\\@`@Bh@?BD|@@j@Bf@HzC?B?@HPAxA?vAAt@?x@A~A?TA`@?J?`@AR?p@ChBA^CpBAf@C~@An@A~@?XAd@?f@A^?p@A~@Al@Ab@?ZAv@?LAf@?@Ab@Ad@Aj@Al@?PChACnAAX?`@Aj@A@A~@Ab@Ab@Af@?h@CdAA`AAp@A`@Ad@?^Af@C`BAh@AxAAvB?`A?r@?f@A|A?rA?\\?R?|E?f@?L?d@?z@?b@?j@?h@?|@?l@?Z?lA?~@?`AAlC?N?dC?rB?fB?nA?`@?hA?v@?hA?z@?~A?pA?|@?\\?h@?|@?j@?Z?^?d@?N?T?b@A`@?h@AZAFA`@Eb@?FEXG`@GZADI^K\\M\\EHIPM\\MTOZa@t@k@hACBOVQ\\]n@S`@U`@GL]n@QZOXQZOXOXQ\\O\\MVOXIPEJOZEFIP]r@MVMVKTEHWh@EFMZOVUNA@EHINa@r@i@`AQZKROZ]v@Qb@CFEJUp@Od@[dAM`@Mj@Mv@Gj@SxACZA^Cj@Ch@ClAChA?JCz@A|@AZ?`@AN?`AChBAr@CzCA`A^?r@@T@f@@pAEfAEb@Ah@?LA@?XIvB@H?|@@l@@z@@@x@?z@Az@?NAf@?J?h@A`@?FAD?DCDADE@C@C@Q?S@O?_@@I?[@S?O@G@S@G@UFSHURA?EHEDOPEHIJGLENG^I\\CTCRCTAXA^Af@?@?P?hE?j@@H?J?H@HB^Fh@?F?F?`A?dD?lA?lB?lB?lBAdD?t@A|ExA?zA??u@?o@?n@?t@{A?yA?}ACwA?_BC[@U?c@?@PAb@?l@?`B?T?vAAdE?J?F?xA?R?xAArB?t@?t@?@?L?X?N?L?h@@r@Al@?z@?pA?nA?Z?j@?^?^?h@?B?Z?`AAlA@H?H?~@?D?r@Aj@?P?n@?bB?J?lBS?gAAe@?s@?cA?U?cA?EAQAwA?{A?w@?c@?k@?q@?OAKAIAGAECGCIAICIEKEIGQOKKKKIMKOKOGMWw@AEKa@IWK_@CUAEEUEYAYM?E?C@A?EBA@A@A@A@CDCFADAD?@AB?D?HAN?H?`@?T?f@?F?n@?X?D?t@?VA`@?R@`@?v@AH?^?\\?|@?^ATAb@?VAH?@?BFXGfAAPCf@C`@Ch@C^Ch@APAHC`@A^Ch@Cb@AHARCf@AZEh@Cb@A\\?@Cd@CZ?F?BC\\Cf@Cb@AP?@AJA`@C\\Cd@Cd@C^Cf@A^Cd@ATEh@A^A`@?BAXCl@?XAh@Ab@Af@?\\Ah@?h@?X@`@?b@@^?J@\\@d@@b@?L@LBj@@d@Bd@@X?@FnABz@Bd@FdB@X@l@?@B`ABhA@b@@fA@f@?X?b@?^?H?Z?h@?^?@Af@?`@A`@?TAl@Af@A^A^Ch@A\\Ad@CV?DCd@Ab@Cb@C^IdAGbAGbAIhAGbACh@AXCf@A^AVCl@Aj@AXAb@Af@A\\A`@Aj@CdAAt@Ad@A\\C`BChAAn@Cp@Az@AHClAAr@?FAVAZ?@Cb@A\\ALATCb@Eb@?FCXGd@EXEXGb@I\\I^Mf@GVOd@O`@M^O^Q^MXS\\KT]p@S^Q\\Yj@S^CFEJO\\MVO\\MZKZM^GREPK\\I^CNCLK`@In@Kr@C`@E^Cb@Cf@Cb@A`@A`@Cb@Ad@?^Ab@?JEhCCjB?@?d@AbAAbA?B?|A?fB?B?n@?`@@h@?`@?`@@fA@b@?b@?B@^@hAB~@?JBz@@f@@b@@T@j@B`@B`ABd@@d@DhAB`@HhB@b@Dl@Bv@?FF|@@f@?@Bb@Bf@@ZFdA@b@FfAD|@Bn@DdAFdABz@@FD~@D|@Bz@@BB|@FpAD`A@DBn@ZvGD`A?H@L@Z@L?LBd@Bh@@b@@^?DB^@b@@bA@fA@`@?N?N@h@?l@?T?d@A`@?d@?h@Ab@?JAX?^Ad@Ah@C`AAf@AZCx@?HCpAE~BAd@Cd@Av@Av@EhBGnBA^Ab@C`@A`@Cd@C^Cd@C\\?BE^APAPGx@Gh@KfAE\\Ed@ABE\\E\\Gd@E\\G`@G^EVCHE\\GXAFIb@EVAFG^ShAG`@I`@G^G\\G\\G^Ib@Kh@G`@Ib@Ib@AFCJCPG`@I`@G^G^ANCNG`@If@AFE\\Gd@CTCNGd@K`AG`@Ed@E^C`@Gb@Eb@Ed@C`@C^Ed@C\\Cb@Eb@C`@GhACb@A^Ef@Ab@Cb@A`@A^Cd@Ab@Aj@AZ?FAh@Ah@Af@Ad@?f@?d@Aj@?b@?f@?p@?\\?l@?h@BlC?Z?l@@x@?X?L?b@@`@?b@?`@@b@?b@?d@@b@?`@?f@@`@?`@?f@@`A?f@A`@?b@AZAd@Ad@C`@Cb@Eb@E\\G`@G`@?BGXCLCRCHGTI`@IZM^ITOJA??BEJ]|@Qb@g@pA?@gApCMb@Qj@[fA[nA[bBCJO|@G`@ENGJCDCBCBE@G@C@C?I?ME?VKtCEnB?NSjDC\\Gn@ABKr@a@|CMt@Ib@UdACLUz@Qj@Od@A?O^U^KLILONOLSHSFk@LE@a@JMBy@Lm@J{@De@D]A[Gw@MaBYsAYa@IOCSGSGMGWOo@q@kAyAYa@A?m@w@i@c@YUECi@]s@SG?iAGgAFcAXE@m@b@_@n@Ud@M`@E\\CTAZ?JDbAB\\Fp@?BF^PtAF|@@bAARC|@CrA@f@B`@Dt@@L@V@N@DBZ?D?L@p@?DA`@?BANANCXOv@If@G`@Gd@ANATIpA?BEh@AJIh@CHQh@M\\CJAFAD?J?LBFFJFHJHHDPDP@RARKNKHSLa@Hm@Hc@HQDIPOPMRGFATCD?d@A^Cx@Bb@@R@N@b@@b@@X@H@D@JHJJHNRv@FT@DLRJHVNRPJB^LZNFD^Td@f@Z`@TXJPJN\\ZXVNJB@\\J@?ZBh@?XYR]VeANi@Pm@DKLc@@ARi@J]@?h@mALUFKNSBAVSFALCR?TD`@LVLLFHJHSHKFCL?LBD@PHn@`@Z^RPHJVXt@z@HJVb@@@Rl@Rl@@DNr@Dj@D^?V@t@@rA?X@v@?x@@j@"
      },
      "metrics": {
        "performedShipmentCount": 4,
        "travelDuration": "2655s",
        "waitDuration": "0s",
        "delayDuration": "0s",
        "breakDuration": "0s",
        "visitDuration": "2400s",
        "totalDuration": "5055s",
        "travelDistanceMeters": 32669,
        "maxLoads": {
          "weight": {
            "amount": "4"
          }
        }
      },
      "routeCosts": {
        "model.vehicles.cost_per_kilometer": 32.669
      },
      "routeTotalCost": 32.669
    }
  ],
  "metrics": {
    "aggregatedRouteMetrics": {
      "performedShipmentCount": 6,
      "travelDuration": "4776s",
      "waitDuration": "0s",
      "delayDuration": "0s",
      "breakDuration": "0s",
      "visitDuration": "3600s",
      "totalDuration": "8376s",
      "travelDistanceMeters": 49598,
      "maxLoads": {
        "weight": {
          "amount": "4"
        }
      }
    },
    "usedVehicleCount": 2,
    "earliestVehicleStartTime": "2024-07-08T16:00:00Z",
    "latestVehicleEndTime": "2024-07-08T17:24:15Z",
    "totalCost": 49.598,
    "costs": {
      "model.vehicles.cost_per_kilometer": 49.598
    }
  }
}

A quick look at the returned route solution shows that all six vehicles shipments were assigned:

"aggregatedRouteMetrics": {
      "performedShipmentCount": 6
}

2 shipments were assigned to mark-yvr and 4 to will-yvr, as indicated by the visits array in the routes object. For example, visits in mark-yvr's route contains two objects, yvr123 and yvr456, which he is scheduled to deliver at 16:14 UTC and 16:45 UTC respectively.

"visits": [
        {
          "startTime": "2024-07-08T16:14:53Z",
          "detour": "0s",
          "shipmentLabel": "yvr123",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        },
        {
          "shipmentIndex": 1,
          "startTime": "2024-07-08T16:45:21Z",
          "detour": "1101s",
          "shipmentLabel": "yvr456",
          "loadDemands": {
            "weight": {
              "amount": "-1"
            }
          }
        }
      ]

When displayed on a map, the route solution is neatly divided into two parts: north (pink / will-yvr) and south (purple / mark-yvr). This division was done automatically by GMPRO in seeking the lowest cost solution, without any explicit instructions from us.

6 visit / 2 vehicle route solution from the Google route optimization API

If you change the input slightly e.g. by changing the capacity of will-yvr to 3 from 5, you get a slightly different route solution. Now, mark-yvr picks up an extra delivery by crossing over to North Vancouver to "help out" with will-yvr's route.

Effect of load and capacity constraints on the Google route optimization solution

GMPRO pricing (multi vehicle VRP)

Pricing for GMPRO's multi vehicle route optimization API is tiered, and starts at $30 per 1,000 visits, or $0.03 per visit (a visit is defined as a latitude longitude pair included in the shipment object). At higher volumes, the per visit cost can go as low as $0.0021 (0.2 cents) per visit, which is crazy good considering that you get real time traffic baked into the optimization. When comparing route optimization providers, it's important to note that some companies charge based on "unique visits" defined by latitude and longitude optimized within a 24-hour period. These companies do not charge for sending the same visit in different API calls within this period. However, GMPRO charges for each API call, even if it involves the same visit.

Here's what GMPRO's full pricing table for multi vehicle route optimization looks like:

0 - 100k 100k - 500k 500k - 1M 1M - 5M 5M - 10M 10M - 20M 20M +
$30.00 $14.00 $6.00 $2.40 $2.10 $2.10 $2.10

The first two tiers (0 - 100k and 100k - 500k) are available to the public. You just need to set up a GCP billing account with your credit card and every month and you'll be charged automatically based on volume. The higher tiers (500k and up) are only available if you work with a Google Maps Partner.

💡
If you'd like to see a demo of GMPRO to find out if its a good fit for your business, email me at afian.anwar@hkmci.com.

Closing thoughts

There's a lot to like about GMPRO. It has a decent set of features (especially real time traffic) and the price is good (very good in fact, considering that it starts at $0.03 per visit when some competitors charge $0.15). The immediate effect of GMPRO is that it will probably suck the oxygen out of the route optimization market and make it hard for GMPRO's smaller competitors to raise venture capital. Potential customers would immediately ask why they should invest time and energy integrating their systems with a boutique route optimization provider when Google Maps offers basically the same thing for less money. Investors will ask why they are betting against Google.

The longer term problem for the route optimization API industry is that Google Cloud sales reps are allowed to sell GMPRO, so you now have tens of thousands (when you include Cloud and Maps resellers) sales reps competing with you to sell route optimization to a relatively small pool of customers.

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

But this doesn't automatically mean that Google Maps will win. Google might be surprised to find the route optimization market is smaller, and harder to sell to than initially thought.

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

Next: Part 4: GMPRO fleet routing app - free route planner for multiple stops