Google Maps route optimization: multi vehicle
How to solve the Vehicle Routing Problem with GMPRO, the new Google Maps route optimization API.
![Google Maps route optimization: multi vehicle](/content/images/size/w2000/2024/07/gg-io-icon.png)
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](https://blog.afi.io/content/images/2024/07/Screen-Shot-2024-07-05-at-12.47.26-PM.png)
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
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](https://blog.afi.io/content/images/2024/07/Routes.jpg)
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).
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.
"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.
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](https://blog.afi.io/content/images/2024/07/Screen-Shot-2024-07-11-at-8.17.50-AM.png)
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](https://blog.afi.io/content/images/2024/07/Screen-Shot-2024-07-12-at-3.25.30-PM.png)
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.
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