Balanced Delivery and Replenishment

In this example, we have a fictitious company that delivers various sizes of pallets to customer locations. The fleet is not large enough to carry all the pallets for the day in a single load, so the vehicles can return to various locations throughout the day to replenish their supply of pallets. The three types of pallets to be delivered are described in the items array below

{
    "items": [
        {
            "weight": 1.33,
            "item_type": "pallet",
            "volume": 1
        },
        {
            "weight": 2.5,
            "item_type": "big pallet",
            "volume": 2
        },
        {
            "weight": 5.5,
            "item_type": "heavy pallet",
            "volume": 1
        }
    ]
}

The vehicles are constrained in terms of how much of each item they can carry as well as by volume and weight. Each vehicle’s capacity is expressed separately as part of the vehicle object, and an example vehicle object now looks like this. Note that we are specifying the "type": "truck" so that the paths over the street network between stops are compliant with the dimensions of the truck.

{
    "max_weight_carried": 30,
    "vehicle_id": "Vehicle1",
    "type": "truck",
    "height": 3.5,
    "shifts": [
        {
            "shift_id": "v1shift",
            "shift_start": "2017-08-24T08:05:00-04:00",
            "shift_end": "2017-08-24T17:10:00-04:00",
            "start_location_id": "loc100",
            "end_location_id": "loc100"
        }
    ],
    "max_volume_carried": 20,
    "capacity_by_item": [
        {
            "quantity": 18,
            "item_type": "pallet"
        },
        {
            "quantity": 13,
            "item_type": "big pallet"
        },
        {
            "quantity": 9,
            "item_type": "heavy pallet"
        }
    ]
}

As in other delivery problems , we express the amount to be delivered to each order with delivery_item_quantities. In problems involving deliveries, the vehicle may become empty during the shift and be therefore unable to service any more orders. By specifying certain orders to have the ability to replenish the supply, we can extend the shift since the vehicle can refill an amount so that more orders can be serviced. An example of such a replenishment order is below. Note that the amount that can be replenished must be set – typically this should be a very large value if essentially limitless replenishment can occur at this stop. If the replenishment stop has a limited supply of items, then that can be specified as well, and the total amount of supply added to the vehicles at this stop will not exceed the amount specified. Additionally, a duration is specified for the replenishment, and a maximum number of visits (enforced by the visit_range constraint)

{
    "order_id": "Replenish pallets",
    "location_id": "Central Depot",
    "replenishment_capacity_by_item": [
        {
            "quantity": 1000,
            "item_type": "pallet"
        },
        {
            "quantity": 1000,
            "item_type": "big pallet"
        },
        {
            "quantity": 1000,
            "item_type": "heavy pallet"
        }
    ],
    "duration": 600,
    "max_visits": 100
}

A full request involving deliveries, replenishment events, and a num_stops constraint to balance the routes is given below.

{
    "orders": [
        {
            "duration": 600,
            "location_id": "Central Depot",
            "order_id": "Replenish pallets",
            "max_visits": 100,
            "replenishment_capacity_by_item": [
                {
                    "item_type": "pallet",
                    "quantity": 1000
                },
                {
                    "item_type": "big pallet",
                    "quantity": 1000
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1000
                }
            ]
        },
        {
            "order_id": "689105",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc3",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 2
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "692039",
            "duration": 1800,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc5",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 4
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 2
                }
            ]
        },
        {
            "order_id": "583368",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc6",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 3
                }
            ]
        },
        {
            "order_id": "677048",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc7",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 2
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "685086",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc8",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 3
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "690020",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc9",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 4
                }
            ]
        },
        {
            "order_id": "674660",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc11",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 2
                },
                {
                    "item_type": "pallet",
                    "quantity": 3
                }
            ]
        },
        {
            "order_id": "413170",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc13",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 6
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "685945",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc14",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "692592",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc15",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 1
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "678545",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc17",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                },
                {
                    "item_type": "pallet",
                    "quantity": 5
                }
            ]
        },
        {
            "order_id": "692829",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc18",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 3
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 2
                }
            ]
        },
        {
            "order_id": "695124",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc19",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "693192",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc21",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "649953",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc21",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "694498",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc23",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 1
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "693854",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc24",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "688899",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc25",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 3
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "617086",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc26",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "340637",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc27",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 2
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "693098",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc28",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 3
                }
            ]
        },
        {
            "order_id": "683931",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc29",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 3
                }
            ]
        },
        {
            "order_id": "685382",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc30",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 4
                }
            ]
        },
        {
            "order_id": "691449",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc31",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 1
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "509217",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc32",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "691287",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc33",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 5
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "640723",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc34",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "665537",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc35",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 1
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 3
                }
            ]
        },
        {
            "order_id": "693858",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc36",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 2
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "392888",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc37",
            "delivery_item_quantities": [
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "695743",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc39",
            "delivery_item_quantities": [
                {
                    "item_type": "pallet",
                    "quantity": 4
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        },
        {
            "order_id": "692431",
            "duration": 150,
            "max_visits": 1,
            "min_visits": 1,
            "location_id": "loc40",
            "delivery_item_quantities": [
                {
                    "item_type": "big pallet",
                    "quantity": 1
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 1
                }
            ]
        }
    ],
    "locations": [
        {
            "latitude": 33.918164,
            "location_id": "Central Depot",
            "longitude": -84.274783
        },
        {
            "latitude": 33.3300399,
            "location_id": "loc1",
            "longitude": -84.07639
        },
        {
            "latitude": 33.5179638,
            "location_id": "loc2",
            "longitude": -84.4153667
        },
        {
            "latitude": 34.07687,
            "location_id": "loc3",
            "longitude": -84.52763
        },
        {
            "latitude": 33.73872,
            "location_id": "loc4",
            "longitude": -85.15883
        },
        {
            "latitude": 34.02463,
            "location_id": "loc5",
            "longitude": -84.1256499
        },
        {
            "latitude": 33.78583,
            "location_id": "loc6",
            "longitude": -84.30268
        },
        {
            "latitude": 34.07687,
            "location_id": "loc7",
            "longitude": -84.5738499
        },
        {
            "latitude": 33.98557,
            "location_id": "loc8",
            "longitude": -83.7661399
        },
        {
            "latitude": 34.02403,
            "location_id": "loc9",
            "longitude": -84.69128
        },
        {
            "latitude": 33.57832,
            "location_id": "loc11",
            "longitude": -84.26431
        },
        {
            "latitude": 33.56882,
            "location_id": "loc12",
            "longitude": -84.51451
        },
        {
            "latitude": 33.8200999,
            "location_id": "loc13",
            "longitude": -84.30606
        },
        {
            "latitude": 33.98078,
            "location_id": "loc14",
            "longitude": -84.02126
        },
        {
            "latitude": 33.98596,
            "location_id": "loc15",
            "longitude": -84.20871
        },
        {
            "latitude": 34.098671,
            "location_id": "loc16",
            "longitude": -83.789905
        },
        {
            "latitude": 33.68959,
            "location_id": "loc17",
            "longitude": -84.3739
        },
        {
            "latitude": 33.8965699,
            "location_id": "loc18",
            "longitude": -84.08495
        },
        {
            "latitude": 34.0078,
            "location_id": "loc19",
            "longitude": -84.5491
        },
        {
            "latitude": 33.44852,
            "location_id": "loc20",
            "longitude": -84.78468
        },
        {
            "latitude": 33.45099,
            "location_id": "loc21",
            "longitude": -84.7372199
        },
        {
            "latitude": 33.7084199,
            "location_id": "loc22",
            "longitude": -84.44377
        },
        {
            "latitude": 34.0286,
            "location_id": "loc23",
            "longitude": -84.37416
        },
        {
            "latitude": 33.82054,
            "location_id": "loc24",
            "longitude": -84.23121
        },
        {
            "latitude": 33.83828,
            "location_id": "loc25",
            "longitude": -84.21402
        },
        {
            "latitude": 34.05614,
            "location_id": "loc26",
            "longitude": -84.31995
        },
        {
            "latitude": 33.7435386,
            "location_id": "loc27",
            "longitude": -84.6712
        },
        {
            "latitude": 33.99045,
            "location_id": "loc28",
            "longitude": -84.8082699
        },
        {
            "latitude": 33.84614,
            "location_id": "loc29",
            "longitude": -84.7469
        },
        {
            "latitude": 33.68736,
            "location_id": "loc30",
            "longitude": -84.23972
        },
        {
            "latitude": 33.7757999,
            "location_id": "loc31",
            "longitude": -84.3845599
        },
        {
            "latitude": 34.19941,
            "location_id": "loc32",
            "longitude": -84.1556
        },
        {
            "latitude": 33.75112,
            "location_id": "loc33",
            "longitude": -84.35911
        },
        {
            "latitude": 33.9854531,
            "location_id": "loc34",
            "longitude": -83.707189
        },
        {
            "latitude": 33.52079,
            "location_id": "loc35",
            "longitude": -84.36567
        },
        {
            "latitude": 34.104,
            "location_id": "loc36",
            "longitude": -84.2661811
        },
        {
            "latitude": 33.88826,
            "location_id": "loc37",
            "longitude": -84.20234
        },
        {
            "latitude": 33.4439,
            "location_id": "loc38",
            "longitude": -84.32034
        },
        {
            "latitude": 33.96681,
            "location_id": "loc39",
            "longitude": -84.23654
        },
        {
            "latitude": 34.1162,
            "location_id": "loc40",
            "longitude": -83.81919
        },
        {
            "latitude": 34.07697,
            "location_id": "loc99",
            "longitude": -85.0148499
        },
        {
            "latitude": 33.9157,
            "location_id": "loc100",
            "longitude": -84.52097
        }
    ],
    "constraints": [
        {
            "max_travel_time_seconds": 0,
            "violation_increment": 1,
            "penalty_per_violation": 1,
            "constraint_name": "Make travel efficient",
            "constraint_type": "Travel_Time"
        },
        {
            "violation_increment": 1,
            "penalty_per_violation": 100000,
            "constraint_name": "Visit as many orders as possible",
            "constraint_type": "Visit_Range"
        },
        {
            "min_stops": 7,
            "constraint_name": "Balance num stops on route - between 8 and 12 active stops",
            "max_stops": 13,
            "constraint_type": "Num_Stops",
            "violation_increment": 1,
            "penalty_per_violation": 10000
        }
    ],
    "add_stats": true,
    "vehicles": [
        {
            "vehicle_id": "Vehicle1",
            "max_volume_carried": 25,
            "max_weight_carried": 35,
            "shifts": [
                {
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "start_location_id": "Central Depot",
                    "shift_id": "v1shift",
                    "end_location_id": "Central Depot",
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ],
            "height": 3.5,
            "type": "truck",
            "capacity_by_item": [
                {
                    "item_type": "pallet",
                    "quantity": 18
                },
                {
                    "item_type": "big pallet",
                    "quantity": 13
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 9
                }
            ]
        },
        {
            "vehicle_id": "Vehicle2",
            "max_volume_carried": 17,
            "max_weight_carried": 25,
            "shifts": [
                {
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "start_location_id": "Central Depot",
                    "shift_id": "v2shift",
                    "end_location_id": "Central Depot",
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ],
            "height": 3.5,
            "type": "truck",
            "capacity_by_item": [
                {
                    "item_type": "pallet",
                    "quantity": 12
                },
                {
                    "item_type": "big pallet",
                    "quantity": 7
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 4
                }
            ]
        },
        {
            "vehicle_id": "Vehicle3",
            "max_volume_carried": 20,
            "max_weight_carried": 25,
            "shifts": [
                {
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "start_location_id": "Central Depot",
                    "shift_id": "v3shift",
                    "end_location_id": "Central Depot",
                    "shift_end": "2017-08-24T14:10:00-04:00"
                }
            ],
            "height": 3.5,
            "type": "truck",
            "capacity_by_item": [
                {
                    "item_type": "pallet",
                    "quantity": 14
                },
                {
                    "item_type": "big pallet",
                    "quantity": 7
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 4
                }
            ]
        },
        {
            "vehicle_id": "Vehicle4",
            "max_volume_carried": 14,
            "max_weight_carried": 19,
            "shifts": [
                {
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "start_location_id": "Central Depot",
                    "shift_id": "v4shift",
                    "end_location_id": "Central Depot",
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ],
            "height": 3.5,
            "type": "truck",
            "capacity_by_item": [
                {
                    "item_type": "pallet",
                    "quantity": 10
                },
                {
                    "item_type": "big pallet",
                    "quantity": 5
                },
                {
                    "item_type": "heavy pallet",
                    "quantity": 2
                }
            ]
        }
    ],
    "items": [
        {
            "weight": 1.33,
            "item_type": "pallet",
            "volume": 1
        },
        {
            "weight": 2.5,
            "item_type": "big pallet",
            "volume": 2
        },
        {
            "weight": 5.5,
            "item_type": "heavy pallet",
            "volume": 1
        }
    ]
}

img

All replenishments occur at the central depot (boxed in red). In the purple route, the vehicle visits stop 1 and stop 2, replenishes in stop 3, then services stops 4, 5, and 6 in the western portion and returns to replenish in stop 7. The route concludes by servicing stops 8 and 9 south of the depot before returning home. The output JSON contains the full details of the stops and specifies when the replenishments occur.

In the routes returned in the API response, any stop where items are delivered will have details of what is delivered, and how much of each item is in the vehicle at that time. An example is below:

{
    "items_delivered": [
        {
            "quantity": 0,
            "cumulative_quantity": 0,
            "item_type": "pallet"
        },
        {
            "quantity": 3,
            "cumulative_quantity": 3,
            "item_type": "big pallet"
        },
        {
            "quantity": 0,
            "cumulative_quantity": 0,
            "item_type": "heavy pallet"
        }
    ]
}

For every replenishment stop, an items_replenished array is included to describe the activity at the stop.

{
    "items_replenished": [
        {
            "quantity": 3,
            "item_type": "pallet"
        },
        {
            "quantity": 1,
            "item_type": "big pallet"
        },
        {
            "quantity": 1,
            "item_type": "heavy pallet"
        }
    ]
}

As with unloading problems, other features of the pickup/delivery aspects of the route are also included in the route object, such as max_volume_in_vehicle, max_num_items_in_vehicle, and max_weight_in_vehicle. Since vehicle capacity constraints are never violated, the optimization engine ensures that no vehicle will ever be carrying more than its capacity at any point during the route (in terms of weight/volume/number of items). The replenishment stops are strategically inserted by the algorithm in order to satisfy as many orders as possible while still respecting the vehicle capacities.