Balanced Pickup and Unloading

In this example, we have a fictitious company that picks up various sizes of boxes and can unload them at a central facility when the vehicle is full. We have a fleet of heterogeneous vehicles that pick up the three item types as seen in the items array below

{
    "items": [
        {
            "weight": 1.33,
            "item_type": "box",
            "volume": 1
        },
        {
            "weight": 2.5,
            "item_type": "big box",
            "volume": 2
        },
        {
            "weight": 5.5,
            "item_type": "heavy box",
            "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

{
    "max_weight_carried": 30,
    "vehicle_id": "Vehicle1",
    "type": "car",
    "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": "box"
        },
        {
            "quantity": 13,
            "item_type": "big box"
        },
        {
            "quantity": 9,
            "item_type": "heavy box"
        }
    ]
}

Similar to delivery problems , we express the amount to be picked up at each order with pickup_item_quantities. In problems involving pickups, the vehicle may become full during the shift and be therefore unable to service any more orders. By specifying certain orders to have the ability to receive unloaded items, we can extend the shift since the vehicle can empty its contents at these orders. An example of such an order is below. Note that the amount that can be unloaded must be set – typically this should be a very large value to allow essentially unlimited unloading.

{
    "order_id": "Unload at trash facility",
    "location_id": "Trash facility",
    "unloading_capacity_by_item": [
        {
            "quantity": 1000,
            "item_type": "box"
        },
        {
            "quantity": 1000,
            "item_type": "big box"
        },
        {
            "quantity": 1000,
            "item_type": "heavy box"
        }
    ],
    "duration": 1800,
    "max_visits": 10
}

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

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

img

All orders are visited and the routes are very balanced in terms of number of stops (either 10 or 11 orders serviced in each route). The unloading facility (boxed in red) is visited a total of 8 times to allow the vehicles to empty their contents and continue the route.

In the routes returned in the API response, any stop where items are picked up will have details of what is picked up, and how much of each item is in the vehicle at that time

{
    "items_picked_up": [
        {
            "cumulative_quantity": 5,
            "item_type": "box",
            "quantity": 2
        },
        {
            "cumulative_quantity": 3,
            "item_type": "big box",
            "quantity": 0
        },
        {
            "cumulative_quantity": 1,
            "item_type": "heavy box",
            "quantity": 1
        }
    ]
}

In the API response, the orders array contains the details of all the visits to the order. Of interest is the Unload at trash facility order:

{
    "num_visits": 10,
    "order_id": "Unload at trash facility",
    "min_visits": 0,
    "latitude": 33.918164,
    "max_visits": 100,
    "abs_arrival_times": [
        1503577584,
        1503583818,
        1503584573,
        1503584877,
        1503587446,
        1503589861,
        1503590397,
        1503590913,
        1503592867,
        1503593959
    ],
    "visit_gap_days": [
        0.07215277777777777,
        0.008738425925925926,
        0.0035185185185185185,
        0.029733796296296296,
        0.02795138888888889,
        0.0062037037037037035,
        0.0059722222222222225,
        0.022615740740740742,
        0.012638888888888889
    ],
    "priority": 0,
    "arrival_times": [
        "2017-08-24T11:59:57-04:00",
        "2017-08-24T12:59:19-04:00",
        "2017-08-24T08:26:24-04:00",
        "2017-08-24T10:27:57-04:00",
        "2017-08-24T11:51:01-04:00",
        "2017-08-24T10:22:53-04:00",
        "2017-08-24T11:10:46-04:00",
        "2017-08-24T12:41:07-04:00",
        "2017-08-24T10:10:18-04:00",
        "2017-08-24T12:08:33-04:00"
    ],
    "longitude": -84.274783,
    "location_id": "Trash facility",
    "visit_gap": [
        6234,
        755,
        304,
        2569,
        2415,
        536,
        516,
        1954,
        1092
    ]
}

Additionally, for every stop at the unloading facility, an items_unloaded array is included to describe the activity at the stop.

{
    "items_unloaded": [
        {
            "item_type": "box",
            "quantity": 3
        },
        {
            "item_type": "big box",
            "quantity": 0
        },
        {
            "item_type": "heavy box",
            "quantity": 3
        }
    ]
}

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 unloading stops are strategically inserted by the algorithm in order to satisfy as many orders as possible while still respecting the vehicle capacities.