GMPRO docs: Driver load balancing with soft constraints
If your drivers are paid per trip, as is common for many third-party logistics (3PL) companies, it's important to distribute stops fairly so that each driver earns a similar income. In this blog post, I'll show you how to take advantage of the GMP Route Optimization API 's load and capacities feature to balance stops evenly across routes.
I'll present two approaches. The first uses hard constraints that limit the number of stops each driver can do per route to prevent overloading any single driver with too many deliveries. The second employs soft capacities to balance routes while allowing some flexibility in overall driving distance to achieve an even distribution of work.
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
Part 4: Fleet routing app - free Google Maps 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 (this article)
Why do some routes have more stops than others?
This happens because it's often the most cost-effective way to plan the route. As I explained in my last post on route clustering, route optimization algorithms focus on minimizing the total cost or travel time for the fleet as a whole. They are not designed to account for fairness, workload balance, or equity among drivers.
👨💻
Screenshots in this blog post were taken with GMPRO-viewer , using data imported via GMPRO-json-converter. Both tools are free to use.
Consider this example: What is the lowest cost way to assign vehicles to stops to this route plan with 6 shipments and 2 vehicles? Assume that the fleet operates on a unit (1 km x 1 km) grid.
After some trial and error, you'll find that the most efficient way to solve this VRP is for the orange driver to do stops C, D, E and F and for the blue driver to do stops A and B for a total cost of 2 + 2 + 4 + 1 (orange) + 2 + 2 (blue) = 13.
Other solutions are possible, but they require either the blue or orange drivers to travel an additional 3 units to reach the other side. Here’s a real-world example of this in action:
Input
{
"model": {
"shipments": [
{
"deliveries": [
{
"arrivalLocation": {
"latitude": 49.2923352,
"longitude": -123.1317422
},
"duration": "600s",
"timeWindows": [
{
"startTime": "2024-07-08T16:00:00Z",
"endTime": "2024-07-08T18:00:00Z"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"label": "yvr321"
}
],
"vehicles": [
{
"startLocation": {
"latitude": 49.2808457,
"longitude": -123.0827831
},
"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
},
"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
}
Output
{
"routes": [
{
"vehicleLabel": "mark-yvr",
"vehicleStartTime": "2024-07-08T16:00:00Z",
"vehicleEndTime": "2024-07-08T17:07:32Z",
"visits": [
{
"startTime": "2024-07-08T16:14:28Z",
"detour": "0s",
"shipmentLabel": "yvr123"
},
{
"shipmentIndex": 1,
"startTime": "2024-07-08T16:57:32Z",
"detour": "1821s",
"shipmentLabel": "yvr456"
}
],
"transitions": [
{
"travelDuration": "868s",
"travelDistanceMeters": 4872,
"waitDuration": "0s",
"totalDuration": "868s",
"startTime": "2024-07-08T16:00:00Z"
},
{
"travelDuration": "1984s",
"travelDistanceMeters": 16505,
"waitDuration": "0s",
"totalDuration": "1984s",
"startTime": "2024-07-08T16:24:28Z"
},
{
"travelDuration": "0s",
"waitDuration": "0s",
"totalDuration": "0s",
"startTime": "2024-07-08T17:07:32Z"
}
],
"routePolyline": {
"points": "_dxkHnrfnV?`@HAN??f@Ar@@^@TDPFRBP@F?@@P?^?^?X?BAp@Z@|@@xADjA@N@hA@L@|ABtA?R@fA?zAFj@@j@@?l@EbK?LAX?XApB?t@At@?@?FC|C?t@ArBAv@AlBAlBCzEAv@AlBElKApAA\\A\\OhBC\\GZEZGXABGVGXIf@Kb@G`@Gd@E`@EZAT?RCjB?Z?T?N?N?B?F?XAlBA\\?VAb@?x@?~B?\\AP?P?LC|AEnBA`@Ah@Eb@Av@Al@Cv@Ad@Eh@GdAC`@OdBCLGb@GXWtAS~@Qn@IVGRA@CFWt@a@~@IV]l@[f@c@|@[h@IPMRUb@INIRIJGHIJc@t@CFA@AH_@p@i@|@s@nA_BjCINS^OXKPININMPCFMTINKPWd@_A`Bg@z@Wd@}@dBIJa@v@GJGLcAbBCFa@t@MRKRw@tACDUb@m@`Aa@t@]j@m@bAOXUb@i@|@IP{@zAc@z@M\\GREPCLAJEZGp@CXKrACTETERA@GVEJEHMVYl@_@n@INOVILYd@q@nAYd@?@Wd@gAhBIRCFyAfCaAfBCDQXGHEFE@C@A?EAECECKOc@zB?@Mn@A@[`BOr@I^APGV{AdHI`@Kl@EN_@hBCLCJEf@ELINIPUa@CEIMS[]m@EGGMMUEEYg@ACWa@u@rA{ArCCFAFAN@DHVFLXf@BFBF@D@L?@?BAFCHEJGLWd@Y`@?@?AXa@Ve@FMDKBI@G?C?AAMAECGCGYg@GMIWAE@O@GBGzAsCt@sAV`@@BXf@DDLTFLDF\\l@RZHLBDT`@HQHODMd@s@LSJSp@gALYXg@FKPYf@}@`@u@Xg@JOz@}ApA}BXg@`DyFh@aAjAuBXe@nDmG`GqKdAmBz@_BR[d@{@FIh@_ARa@bAbBNVDHHLDHLTHLZh@j@~@NXHJt@tAPVLTDJPZZh@Xf@p@fAVd@FJDHR\\dBxCl@fAjArBdCfEpE|HfCjEJT|@|Ad@v@d@v@@BVb@Z`@NRFJJLBBBBDBBBDBFDNDPDB@JBHBJDJBJDjCz@B@TJ@@NL@@PJLJDFJNXb@t@nALT\\l@j@~@bAhBFJXf@j@bALPFLPXp@dALRz@zANTd@v@f@z@LN\\l@\\n@Xb@@BJNHPb@t@NXr@nAl@dADDV\\VZRT`@^LJBBNJNJTPTLPHZLTHJB^FRBF?b@Bh@@fA?jADP?B?H?T?J?fBBPGBC?AT@p@?fA@lDDjA@^?f@@R?P@z@?|B?tDDnDDP@hA@jBBvDDvDF`@@@?`@?rBBZ@b@?P@j@@nDDpDDT?^@dCDvB@vEHX?l@@b@@~ABd@?X@\\?lABbCFJ?H?L?bEF|CBH?P?vDBnEDj@@nCDhDDlDBbBDtAB`EB|DDzDD~DFxBB|@DhDDtB@z@@tA@h@Dd@Bb@@N?l@@|@Bb@?pBChB@P@X?X?bAB^?V@Z?vA@n@@N@T?xABT?f@@J?`BBrAB~A?pA@rCDb@?~CF~CDH?xABZ@\\@bB@lBDnBBfA@tDF|@@f@@hABP@`DDlBBlDDT?zCDT@D?H?N?RiAPcAP}@?UFYj@mCf@mCb@aCf@cCf@qCf@iCd@gCd@eCh@kCd@gCP{@TkALq@X}AF[ZaBlEDtABdEDfDDrABzA@h@@~GF`@?vBDP@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@g@?Av@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@?bBAb@?T?rB?pAA`@@`LAzEAN?|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": "2852s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "1200s",
"totalDuration": "4052s",
"travelDistanceMeters": 21377
},
"routeCosts": {
"model.vehicles.cost_per_kilometer": 21.377
},
"routeTotalCost": 21.377
},
{
"vehicleIndex": 1,
"vehicleLabel": "will-yvr",
"vehicleStartTime": "2024-07-08T16:00:00Z",
"vehicleEndTime": "2024-07-08T17:24:19Z",
"visits": [
{
"shipmentIndex": 2,
"startTime": "2024-07-08T16:12:24Z",
"detour": "0s",
"shipmentLabel": "yvr789"
},
{
"shipmentIndex": 3,
"startTime": "2024-07-08T16:31:36Z",
"detour": "923s",
"shipmentLabel": "yvr987"
},
{
"shipmentIndex": 4,
"startTime": "2024-07-08T16:51:15Z",
"detour": "1921s",
"shipmentLabel": "yvr654"
},
{
"shipmentIndex": 5,
"startTime": "2024-07-08T17:14:19Z",
"detour": "2879s",
"shipmentLabel": "yvr321"
}
],
"transitions": [
{
"travelDuration": "744s",
"travelDistanceMeters": 7933,
"waitDuration": "0s",
"totalDuration": "744s",
"startTime": "2024-07-08T16:00:00Z"
},
{
"travelDuration": "552s",
"travelDistanceMeters": 6170,
"waitDuration": "0s",
"totalDuration": "552s",
"startTime": "2024-07-08T16:22:24Z"
},
{
"travelDuration": "579s",
"travelDistanceMeters": 6408,
"waitDuration": "0s",
"totalDuration": "579s",
"startTime": "2024-07-08T16:41:36Z"
},
{
"travelDuration": "784s",
"travelDistanceMeters": 12161,
"waitDuration": "0s",
"totalDuration": "784s",
"startTime": "2024-07-08T17:01:15Z"
},
{
"travelDuration": "0s",
"waitDuration": "0s",
"totalDuration": "0s",
"startTime": "2024-07-08T17:24:19Z"
}
],
"routePolyline": {
"points": "ks_lHbfmmV?l@s@??l@?LAp@L?F?rA@~@@x@A~AGJ?dAFdB?j@Az@AzAC?\\At@?v@?rAAlB@p@AdF?lB?b@CpC?lB?lBAv@?dD?zC?T?jB?\\?PA|@?fB?D?B?r@An@ArC?hA?t@?v@?t@AjIAvB?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`@zAj@|ATp@L\\?@L\\HVVr@t@xBL^JXNb@n@bBHTLTZl@bArBZj@pA~BnAxBTb@Vb@p@tAh@`A`@r@r@lANZr@bBTp@Np@TlAHdABl@@n@CbACh@ALGd@EZGh@G\\Mv@Kp@Kj@AFCP?DE`@Ej@?BEn@AZ?N?T?R?Z?NBj@@^@T@B@TH`ALlABVFv@JdA@HFt@Hz@Dd@@HFr@?@Db@B\\@^@\\?\\?B?@AVA\\CXCPMj@?DI\\GPCFGN]t@CFCDs@rAi@fAm@jAO\\M\\GLCFIVENENKd@W~AE^CXEh@Eh@?BEfA?@Ah@?f@AjAAd@?N?T?l@?l@?`@BjA@RFtADv@BdA?BD`@B\\DTNv@Lj@DNFVFVLd@Nn@FZFT?BDTFf@?p@?ZALAJCTEPITELGLEFEFGHEFABABABAD?De@TMFMFWNKLGLKPEJGPM\\IRQn@Md@CNITA@ETEJAHANAZA^Ih@El@?X?B?hA?D?X@|@A^?b@@lBAlAArC?X?JCbKAzAAPEr@?BAr@?@?J?j@?N?X?bA?d@Ab@ArBAvA?v@?t@?~@?p@?lECbA?lA?N@HBJ?v@?X?^Av@AfBAbCAjDA`ACtD?nBAhB?ZApAAnB?v@A~@MWKSJRLV?hB?lAAdD?v@?~@AlB?vAAh@AbBAt@Av@?t@Af@M@c@AoCC]?a@AkBCG?s@C]?oC@c@?kBCc@AA?}@@kA?cAAS?m@A{CCq@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?@CXCPC`@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?tA@~@@t@?P?P?H@t@@fA?x@?R@R?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@?L?XA^?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@@pAEfAEP?PAh@?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?rA?tB?j@@H?J?H@HDh@B^@D?F?D?|@?F?p@?|@?n@?jA?lB?lB?lBAv@?lB?t@AlD?n@xA?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@L@L@\\@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@AHAbAAH?@Ap@?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@FfA@ZB`@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^ANCNAFEXIf@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@?\\?H?b@?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@UdA?@CJUz@Qj@KXCJA?O^U^CBGHILONOLIBIDSFg@LC?E@YFGBMBo@JI@m@J{@De@D]A[Gw@MaBYsAYa@IOCSGSGMGWOGGg@i@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": "2659s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "2400s",
"totalDuration": "5059s",
"travelDistanceMeters": 32672
},
"routeCosts": {
"model.vehicles.cost_per_kilometer": 32.672
},
"routeTotalCost": 32.672
}
],
"metrics": {
"aggregatedRouteMetrics": {
"performedShipmentCount": 6,
"travelDuration": "5511s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "3600s",
"totalDuration": "9111s",
"travelDistanceMeters": 54049
},
"usedVehicleCount": 2,
"earliestVehicleStartTime": "2024-07-08T16:00:00Z",
"latestVehicleEndTime": "2024-07-08T17:24:19Z",
"totalCost": 54.048999999999992,
"costs": {
"model.vehicles.cost_per_kilometer": 54.048999999999992
}
}
}Balance routes with hard constraints
So how can we balance this route? The most straightforward way to do this is to apply a route balancing policy where we introduce additional constraints to prevent any single route from being significantly longer than others. In the example above, we have 6 shipments and 2 vehicles, so we can set a target load per vehicle of 6 / 2 = 3 deliveries each.
To do this, we first set a loadLimit of 3 in the vehicle object within the GMPRO request payload, as shown below:
{
"loadLimits": {
"stopCount": {
"maxLoad": 3
}
}
}And include the corresponding loadDemands on each shipment object.
{
"loadDemands": {
"stopCount": {
"amount": "1"
}
}
}This will instruct the GMPRO solver to allocate a maximum of 3 shipments to each vehicle. Since route optimization algorithms aim to serve all shipments without leaving any unassigned, each vehicle will end up with exactly 3 shipments each.
GMPRO driver load balancing example with hard constraints
Here's what the route plan looks like with load constraints added:
And here's the accompanying JSON:
Input
{
"model": {
"shipments": [
{
"deliveries": [
{
"arrivalLocation": {
"latitude": 49.2923352,
"longitude": -123.1317422
},
"duration": "600s",
"timeWindows": [
{
"startTime": "2024-07-08T16:00:00Z",
"endTime": "2024-07-08T18:00:00Z"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"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"
}
]
}
],
"label": "yvr321"
}
],
"vehicles": [
{
"startLocation": {
"latitude": 49.2808457,
"longitude": -123.0827831
},
"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
},
"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
}
Output
{
"routes": [
{
"vehicleLabel": "mark-yvr",
"vehicleStartTime": "2024-07-08T16:00:00Z",
"vehicleEndTime": "2024-07-08T17:37:08Z",
"visits": [
{
"startTime": "2024-07-08T16:14:28Z",
"detour": "0s",
"shipmentLabel": "yvr123",
"loadDemands": {
"stopCount": {
"amount": "-1"
}
}
},
{
"shipmentIndex": 4,
"startTime": "2024-07-08T16:34:42Z",
"detour": "800s",
"shipmentLabel": "yvr654",
"loadDemands": {
"stopCount": {
"amount": "-1"
}
}
},
{
"shipmentIndex": 1,
"startTime": "2024-07-08T17:27:08Z",
"detour": "3597s",
"shipmentLabel": "yvr456",
"loadDemands": {
"stopCount": {
"amount": "-1"
}
}
}
],
"transitions": [
{
"travelDuration": "868s",
"travelDistanceMeters": 4872,
"waitDuration": "0s",
"totalDuration": "868s",
"startTime": "2024-07-08T16:00:00Z",
"vehicleLoads": {
"stopCount": {
"amount": "3"
}
}
},
{
"travelDuration": "614s",
"travelDistanceMeters": 7187,
"waitDuration": "0s",
"totalDuration": "614s",
"startTime": "2024-07-08T16:24:28Z",
"vehicleLoads": {
"stopCount": {
"amount": "2"
}
}
},
{
"travelDuration": "2546s",
"travelDistanceMeters": 22936,
"waitDuration": "0s",
"totalDuration": "2546s",
"startTime": "2024-07-08T16:44:42Z",
"vehicleLoads": {
"stopCount": {
"amount": "1"
}
}
},
{
"travelDuration": "0s",
"waitDuration": "0s",
"totalDuration": "0s",
"startTime": "2024-07-08T17:37:08Z",
"vehicleLoads": {
"stopCount": {}
}
}
],
"routePolyline": {
"points": "_dxkHnrfnV?`@HAN??f@Ar@@^@TDPFRBP@F?@@P?^?^?X?BAp@Z@|@@xADjA@N@hA@L@|ABtA?R@fA?zAFj@@j@@?l@EbK?LAX?XApB?t@At@?@?FC|C?t@ArBAv@AlBAlBCzEAv@AlBElKApAA\\A\\OhBC\\GZEZGXABGVGXIf@Kb@G`@Gd@E`@EZAT?RCjB?Z?T?N?N?B?F?XAlBA\\?VAb@?x@?~B?\\AP?P?LC|AEnBA`@Ah@Eb@Av@Al@Cv@Ad@Eh@GdAC`@OdBCLGb@GXWtAS~@Qn@IVGRA@CFWt@a@~@IV]l@[f@c@|@[h@IPMRUb@INIRIJGHIJc@t@CFA@AH_@p@i@|@s@nA_BjCINS^OXKPININMPCFMTINKPWd@_A`Bg@z@Wd@}@dBIJa@v@GJGLcAbBCFa@t@MRKRw@tACDUb@m@`Aa@t@]j@m@bAOXUb@i@|@IP{@zAc@z@M\\GREPCLAJEZGp@CXKrACTETERA@GVEJEHMVYl@_@n@INOVILYd@q@nAYd@?@Wd@gAhBIRCFyAfCaAfBCDQXGHEFE@C@A?EAECECKOc@zB?@Mn@A@[`BOr@I^APGV{AdHI`@Kl@EN_@hBCLCJEf@ELINIPUa@CEIMS[]m@EGGMMUEEYg@ACWa@u@rA{ArCCFAFAN@DHVFLXf@BFBF@D@L?@?BAFCHEJGLWd@Y`@?@CBYb@kAtBu@tA`A~A@BVb@cBvCU`@ADYd@Wf@EHS\\KPc@x@IDEBS\\a@n@MRQXEFABQVQNGDIFQFKBK@I@I?A?GAI?EAIAKESKSKOGMG]QUMUIa@MQAQ?Q@QBMBQDKBKBKDKDKDGDIDKF]VA@GDGDWX]`@CBABABMZCDCFGHGLCFCDEJA?INCFCFKVCFAFCDK\\GXYjAEJADADGVCLMd@Oh@GVABOd@IZGROd@M\\GPITELQb@EJA@ELCFMZS`@KTKPS`@CD?@ILEJGLW`@Q\\e@t@QXORORQTa@f@c@f@cAjAo@l@C@_@Z?@GDURIFSPQJOJo@`@q@^a@RGB_@P[JC@]J_@JC@c@HIBIBG@C?[FI@I@G@O@G@A?YBE?[@A?I@W?A?qA?W?i@A_@AGA[AQA[C[CEAYCE?a@Gg@Iq@K_@GQEKC_@IYGCA]I]K[IA?IESGA?MEME[M]M[MAAWMIEQIYQc@S[S]QOIIGg@YoAcAe@a@UUq@o@QOQQCCIG}@y@y@q@ECWWk@i@MKAAOMgA_AGGIGgAaASQGEOM][_@[_@[SQII_@[}@w@SQII_@[QOAAII_@[][SQKIOOMKSQKISQII][_@[KKQO_@]][[WCC}@w@SQII]]gA_AMKMMOM[Y_@]][][_@[UUg@c@oAiAi@g@_@[IIIIWUGEc@c@yFgFEEGEIIUUCCEC][e@c@k@g@gAcA][y@u@eAaAEEGEIGCEGECCCCCEMKCCCEIGAA][MKWUEEGEGGECAAQKc@[UQEM?AAAKKq@k@_Aw@IGUQEE]W]U]SOGIGKGKE[QIEMIIGKGCACCGGAACEEGEGEIEKCKAICQAI?I?A?G?K?M@G@MBKBMDKBIFGDIFEFEFEFCFAHAJ@J@JDHFHHHLBBDHBJBHBNBR@RAR?RARK|AGVSbAGZOv@Or@CXEZKr@WbBCTGb@YlBm@pEQrACVANCX?B?f@?h@?hAIRAR?JAFAD?BABABABABABA@C@A@A@CBE@KDKJ]?g@?G@WFi@@mA?gAAU?S@U?c@@]?K@[@a@?_@?a@?aA@KAKA?dA?V?@AD?LAL?@?J?T?^?J?B?b@?L@PAB?@A??@?@?@?@?@?@?@?@?@?@?@@@?@?@@@?@?B?D?D?D@HAzHAt@?v@@PDn@@NDp@@D@HLlA@JHt@Fj@F`@BZN|@BX@D?@BRBL?BDX@D@`@?n@?r@?B?r@?@?v@?t@?B?v@?r@CjIAv@?t@y@?o@?_B?kBAyAAwBA}A?mB?cB?{AAyA??u@?o@?n@?t@xA?zA@bB?lB?|A?vB@xA@jB@~A?n@?x@??u@@w@BkI?s@?w@?C?u@?w@?A?s@?C?s@?o@Aa@AEEY?CCMCS?AAECYO}@C[Ga@Gk@Iu@AKMmAAIAEEq@AOEo@AQ?w@@u@@{HBE?ABG@I@?@?@?@A@??A@??A@??A?A@??A?A?A@??A?A?A?A?A?A?A?A?A?AAA?A?AA??A?AA??AA??AA??AA?A??AA?A?AI?GAI?W?A?q@?EA]?EAKAK?E?A?W?eAJ@J@`AA`@?^?`@?ZAJA\\?b@AT?RAT?fA@lA?h@ALPBB@@L?V?R?d@Az@AXA?[AcCAaA?g@?]@K?K@O@QDe@Jq@Fe@RyAr@uED[F]Dc@@C?A@QRo@BIBKFMHONQ@A?ARSJIFCJCFABANAR?F?@@B?B@@?DBNFXNf@\\B@B@B?@@@?D?NAB@JJ@?@@B?@@N@TPb@ZPJ@@DBFFFDDDVTLJ\\Z@@HFBDBBLJBDBBBBFDBDHFFDDDdA`Ax@t@\\ZfAbAj@f@d@b@\\ZDBBBTTHHFDDDxFfFb@b@FDVTHHHH^Zh@f@nAhAf@b@TT^Z\\Z\\Z^\\ZXNLLLLJfA~@\\\\HHRP|@v@BBZV\\Z^\\PNJJ^Z\\ZHHRPJHRPLJNNJHRP\\Z^ZHH@@PN^ZHHRP|@v@^ZHHRP^Z^Z\\ZNLFDRPfA`AHFFFfA~@NL@@LJj@h@VVDBx@p@|@x@HFBBPPPNp@n@TTd@`@nAbAf@XHFNH\\PZRb@RXPPHHDVL@@ZL\\LZLLDLD@?RFHD@?ZH\\J\\HB@XF^HJBPD^Fp@Jf@H`@FD?XBD@ZBZBP@Z@F@^@h@@V?pA?@?V?HA@?ZAD?XC@?FANAFAHAHAZGB?FAHCHCb@IBA^K\\KBAZK^QFC`@Sp@_@n@a@NKPKRQHGTSFE?A^[BAn@m@bAkAb@g@`@g@PUNSNSPYd@u@P]Va@FMDKHM?ABERa@JQJURa@L[BGDM@ADKPc@DMHUFQL]Ne@FSH[Ne@@CFWNi@Le@BMFW@E@EDKXkAFYJ]BE@GBGJWBGBGHO@?DKBEBGFMFIBGBERKBABCDC@A\\c@PQDEHGDCHINI@?PIJGJGPENELCJEHAHAHA@?B?@?DAD?FAD@D?H?\\JPFPHLF^RTJHDFDFBB@FBHBFBF@L@N@H?F?JCHAFADAHEFCFEJIHIJMJOFKFKHOJQ^q@Ta@FUb@y@JQR]DIVg@Xe@@ETa@bBwCf@aATa@`CgEHMp@mAd@y@d@y@lA{BHQHODMd@s@LSJSp@gALYXg@FKPYf@}@`@u@Xg@JOz@}ApA}BXg@`DyFh@aAjAuBXe@nDmG`GqKdAmBz@_BR[d@{@FIh@_ARa@bAbBNVDHHLDHLTHLZh@j@~@NXHJt@tAPVLTDJPZZh@Xf@p@fAVd@FJDHR\\dBxCl@fAjArBdCfEpE|HfCjEJT|@|Ad@v@d@v@@BVb@Z`@NRFJJLBBBBDBBBDBFDNDPDB@JBHBJDJBJDjCz@B@TJ@@NL@@PJLJDFJNXb@t@nALT\\l@j@~@bAhBFJXf@j@bALPFLPXp@dALRz@zANTd@v@f@z@LN\\l@\\n@Xb@@BJNHPb@t@NXr@nAl@dADDV\\VZRT`@^LJBBNJNJTPTLPHZLTHJB^FRBF?b@Bh@@fA?jADP?B?H?T?J?fBBPGBC?AT@p@?fA@lDDjA@^?f@@R?P@z@?|B?tDDnDDP@hA@jBBvDDvDF`@@@?`@?rBBZ@b@?P@j@@nDDpDDT?^@dCDvB@vEHX?l@@b@@~ABd@?X@\\?lABbCFJ?H?L?bEF|CBH?P?vDBnEDj@@nCDhDDlDBbBDtAB`EB|DDzDD~DFxBB|@DhDDtB@z@@tA@h@Dd@Bb@@N?l@@|@Bb@?pBChB@P@X?X?bAB^?V@Z?vA@n@@N@T?xABT?f@@J?`BBrAB~A?pA@rCDb@?~CF~CDH?xABZ@\\@bB@lBDnBBfA@tDF|@@f@@hABP@`DDlBBlDDT?zCDT@D?H?N?RiAPcAP}@?UFYj@mCf@mCb@aCf@cCf@qCf@iCd@gCd@eCh@kCd@gCP{@TkALq@X}AF[ZaBlEDtABdEDfDDrABzA@h@@~GF`@?vBDP@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@g@?Av@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@?bBAb@?T?rB?pAA`@@`LAzEAN?|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": 3,
"travelDuration": "4028s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "1800s",
"totalDuration": "5828s",
"travelDistanceMeters": 34995,
"maxLoads": {
"stopCount": {
"amount": "3"
}
}
},
"routeCosts": {
"model.vehicles.cost_per_kilometer": 34.995
},
"routeTotalCost": 34.995
},
{
"vehicleIndex": 1,
"vehicleLabel": "will-yvr",
"vehicleStartTime": "2024-07-08T16:00:00Z",
"vehicleEndTime": "2024-07-08T17:08:22Z",
"visits": [
{
"shipmentIndex": 2,
"startTime": "2024-07-08T16:12:24Z",
"detour": "0s",
"shipmentLabel": "yvr789",
"loadDemands": {
"stopCount": {
"amount": "-1"
}
}
},
{
"shipmentIndex": 3,
"startTime": "2024-07-08T16:31:36Z",
"detour": "923s",
"shipmentLabel": "yvr987",
"loadDemands": {
"stopCount": {
"amount": "-1"
}
}
},
{
"shipmentIndex": 5,
"startTime": "2024-07-08T16:58:22Z",
"detour": "1922s",
"shipmentLabel": "yvr321",
"loadDemands": {
"stopCount": {
"amount": "-1"
}
}
}
],
"transitions": [
{
"travelDuration": "744s",
"travelDistanceMeters": 7933,
"waitDuration": "0s",
"totalDuration": "744s",
"startTime": "2024-07-08T16:00:00Z",
"vehicleLoads": {
"stopCount": {
"amount": "3"
}
}
},
{
"travelDuration": "552s",
"travelDistanceMeters": 6170,
"waitDuration": "0s",
"totalDuration": "552s",
"startTime": "2024-07-08T16:22:24Z",
"vehicleLoads": {
"stopCount": {
"amount": "2"
}
}
},
{
"travelDuration": "1006s",
"travelDistanceMeters": 16891,
"waitDuration": "0s",
"totalDuration": "1006s",
"startTime": "2024-07-08T16:41:36Z",
"vehicleLoads": {
"stopCount": {
"amount": "1"
}
}
},
{
"travelDuration": "0s",
"waitDuration": "0s",
"totalDuration": "0s",
"startTime": "2024-07-08T17:08:22Z",
"vehicleLoads": {
"stopCount": {}
}
}
],
"routePolyline": {
"points": "ks_lHbfmmV?l@s@??l@?LAp@L?F?rA@~@@x@A~AGJ?dAFdB?j@Az@AzAC?\\At@?v@?rAAlB@p@AdF?lB?b@CpC?lB?lBAv@?dD?zC?T?jB?\\?PA|@?fB?D?B?r@An@ArC?hA?t@?v@?t@AjIAvB?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`@zAj@|ATp@L\\?@L\\HVVr@t@xBL^JXNb@n@bBHTLTZl@bArBZj@pA~BnAxBTb@Vb@p@tAh@`A`@r@r@lANZr@bBTp@Np@TlAHdABl@@n@CbACh@ALGd@EZGh@G\\Mv@Kp@Kj@AFCP?DE`@Ej@?BEn@AZ?N?T?R?Z?NBj@@^@T@B@TH`ALlABVFv@JdA@HFt@Hz@Dd@@HFr@?@Db@B\\@^@\\?\\?B?@AVA\\CXCPMj@?DI\\GPCFGN]t@CFCDs@rAi@fAm@jAO\\M\\GLCFIVENENKd@W~AE^CXEh@Eh@?BEfA?@Ah@?f@AjAAd@?N?T?l@?l@?`@BjA@RFtADv@BdA?BD`@B\\DTNv@Lj@DNFVFVLd@Nn@FZFT?BDTFf@?p@?ZALAJCTEPITELGLEFEFGHEFABABABAD?De@TMFMFWNKLGLKPEJGPM\\IRQn@Md@CNITA@ETEJAHANAZA^Ih@El@?X?B?hA?D?X@|@A^?b@@lBAlAArC?X?JCbKAzAAPEr@?BAr@?@?J?j@?N?X?bA?d@Ab@ArBAvA?v@?t@?~@?p@?lECbA?lA?N@HBJ?v@?X?^Av@AfBAbCAjDA`ACtD?nBAhB?ZApAAnB?v@A~@MWKSJRLV?hB?lAAdD?v@?~@AlB?vAAh@AbBAt@Av@?t@Af@M@c@AoCC]?a@AkBCG?s@C]?oC@c@?kBCc@AA?}@@kA?cAAS?m@A{CCq@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?@CXCPC`@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?tA@~@@t@?P?P?H@t@@fA?x@?R@R?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@?L?XA^?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@EFMZOVO\\Q\\O\\MVO\\[p@Q\\M\\CBKVM\\ADKVKZM^AFITK^I\\?BK`@G\\Ib@I^G`@E`@CNCRC\\AF?DCZC\\AJA\\C^AP?RA\\?HA`@?^Ad@?`@?f@?V?J?b@?`@Ad@?b@?b@?jAAfA?h@At@Af@?`@AL?XAb@A`@AXAh@GpB?DE`AEjA?@EbBEdA?HA\\Ch@C|@EdACdAABC`ACj@AZAf@E`A?JA\\ARAd@Cb@Ad@A^Cd@ExAAVCx@EjAAb@?BA\\AZARAN?PAPA`@APCp@Ab@?BC`@AX?@Cl@G|@C\\Eh@Ef@CTIj@G`@G\\ERAHGXMd@K\\KZIXABM\\MZMVO\\A@KPMXOXOVSZ]l@a@p@OVOXU\\KRa@p@OTa@r@OXOT]l@CD?BMRINc@`AKRGLA@GPIRCFIPEJKVM^MZIXM\\K\\M`@K\\IZIXCLGPI`@IXKd@CNENG^Kf@EXG\\CJETAHCTCHGb@E`@EXEb@CJCZIh@ALANC`@G`AAFC`@A^Cd@G`AGhAE~@Cd@Ch@GfAAPCf@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@L@L@\\@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@AHAbAAH?@Ap@?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@FfA@ZB`@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^ANCNAFEXIf@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@?\\?H?b@?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@UdA?@CJUz@Qj@KXCJA?O^U^CBGHILONOLIBIDSFg@LC?E@YFGBMBo@JI@m@J{@De@D]A[Gw@MaBYsAYa@IOCSGSGMGWOGGg@i@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": 3,
"travelDuration": "2302s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "1800s",
"totalDuration": "4102s",
"travelDistanceMeters": 30994,
"maxLoads": {
"stopCount": {
"amount": "3"
}
}
},
"routeCosts": {
"model.vehicles.cost_per_kilometer": 30.994
},
"routeTotalCost": 30.994
}
],
"metrics": {
"aggregatedRouteMetrics": {
"performedShipmentCount": 6,
"travelDuration": "6330s",
"waitDuration": "0s",
"delayDuration": "0s",
"breakDuration": "0s",
"visitDuration": "3600s",
"totalDuration": "9930s",
"travelDistanceMeters": 65989,
"maxLoads": {
"stopCount": {
"amount": "3"
}
}
},
"usedVehicleCount": 2,
"earliestVehicleStartTime": "2024-07-08T16:00:00Z",
"latestVehicleEndTime": "2024-07-08T17:37:08Z",
"totalCost": 65.989,
"costs": {
"model.vehicles.cost_per_kilometer": 65.989
}
}
}Generally, if you have n shipments and k vehicles, setting each vehicle's loadLimit to n/k rounded up can help distribute stops evenly across your fleet. This type of rebalancing policy is known as a hard constraint because the route optimization solver will make sure that a vehicle's load never exceeds its capacity, even if it means leaving some stops unassigned.
Balance routes with soft constraints
A more effective approach to setting up a route balancing policy is to use soft constraints, which allow you to trade off route efficiency for route equality. For example, consider the scenario we looked at earlier with 6 shipments and 2 vehicles, with each driver having a maximum capacity of 3.
The total cost now is 2 + 2 + 4 + 1 (orange) + 2 + 2 +3 (blue) = 16, or 3 more than the route optimal solution we saw in the first instance (Example A). The difference in cost can be entirely attributed to the detour of 3 units that driver blue had to make in going from B to D to keep the route balanced.
If we want the GMPRO solver to ignore the capacity constraint if it means that one or more vehicles have to make large detours to maintain it, we can add a small penalty for each stop above a vehicle's target capacity. In the example above, we could add a penalty of 2.5 units (which is less than the detour value of 3 units) for each stop above a vehicle's target capacity like so:
{
"loadLimits": {
"stopCount": {
"softMaxLoad": 3,
"costPerUnitAboveSoftMax": 2.5
}
}
}The total cost of an unbalanced 4 stop (orange) + 2 stop (blue) route solution is now 2 + 2 + 4 + 1 + 2.5 (penalty) for orange and 2 + 2 for blue = 15.5. This is less than the total cost of 16 in the perfectly balanced route given in Example B, so the unbalanced solution is preferred.
If the detour was smaller because the stops were closer together as shown in Example D:
The total cost is now 2 + 2 + 4 + 1 (orange) + 2 + 2 + 2 (blue) = 15, which is less than the 15.5 total cost for the unbalanced route in Example C. This means that the 3 stop per driver balanced solution is preferred.
GMPRO driver load balancing example with soft constraints
Let's test out soft constraints in our real world, 6 shipment 2 vehicle example. If we compare the total mileage from the optimal, unbalanced route solution with the suboptimal balanced one, we get a difference of 65,989m (balanced) - 54,049m (unbalanced) = 11,940m. This is effectively the length of the round trip detour from blue stop 1 to blue stop 2. Since we've set "costPerKilometer": 1 for both drivers, the effective cost of this detour is 11.94.
Let's set "softMaxLoad": 3 and "costPerUnitAboveSoftMax": 12. This configuration tells GMPRO that if any vehicle exceeds a load of 3, a penalty of 12 units will be added to the route solution, which makes it more cost-effective to balance routes by allowing the blue driver to take a detour of up to 11,940 meters.
Input ("softMaxLoad":3 and "costPerUnitAboveSoftMax": 12)
Output
Result (balanced route)
As expected, the soft constraints gave us a balanced route of 2 vehicles with 3 shipments each.
Next, let's change the value of costPerUnitAboveSoftMax to something small like 5. Such a small penalty means that unbalanced routes will generally be preferred, unless the detour cost is less than 5 units.
Input ("softMaxLoad":3 and "costPerUnitAboveSoftMax": 5)
Output
Result (unbalanced route)
Since the penalty of 5 units is too small to matter, we get an unbalanced (but optimal) route with a 4 shipment / 2 vehicle split.
Conclusion
In this blog post, I showed how to balance routes produced by the Google Maps Platform Route Optimization API using two methods. The first method divides the total number of stops by the number of drivers, rounds up, and sets this as the maximum number of stops per vehicle. The second uses soft constraints to achieve a balance between route efficiency and fairness, favoring a balanced solution only when the additional cost is below a specified threshold. Both methods have their place, and as route planners it is your job to decide which one best balances (haha) driver satisfaction with operational efficiency.
👋 As always, if you have any questions or suggestions for me, please reach out or say hello on LinkedIn.