Pickup and Delivery Routing

A special case of the classical Vehicle Routing Problem is the Pickup and Delivery Problem. Each order has a pickup location and a drop-off location that are mutually dependent. An item can only be dropped off after it has been picked up by the same driver.

The Solvice solver will find the optimal routes to do all your orders, so it may often occur that you pick up multiple orders before you drop them off. If you specify capacity constraints, it will ensure that your vehicles won't try to carry more than they can hold.

Some example use-cases:

  • same-day courier
  • taxi services
  • moving companies
  • transportation services
  • third-party restaurant delivery
  • garbage pickups
  • etc...

First off, but most importantly, you should define that the problem is a PDP, by setting the solver property to "PDP" in the payload.

Usage of Pickup and Delivery API is mostly identical with the normal Vehicle Routing API, with only one difference: the way we define pickup and delivery orders. If an item has to reach a certain location, you have to pick it up first (i.e. create a pickup order with activity : "pickup") and then drop it of in another location (i.e. create a dropoff order with activity : "dropoff").

In the example on the right, you can see one order (order0) which has a pickup requirement in the centre of Ghent and a delivery requirement (see the next tab) in the city of Antwerp. It takes 10 minutes to pickup and 10 minutes to deliver and it accounts for 3 units of the load in a vehicle. Mind that the property ride alerts the solver that its about the same ride!

Input

An input for a solve request for a PDP problem requires several data:

  • locations
  • orders
  • vehicles

Locations

Define the list of locations.

PropertyDescription
name
(string)
Unique identifier for location name
latitude
(number)
Latitude in WSG84
longitude
(number)
Longitude in WSG84

Orders

PropertyDescriptionType
nameThe unique name of the orderstring
locationThe name of the location where this order is located. (refers to location list)string
rideThe name of the ride of a pickup or a dropoff.string
activityThe activity of the order. "pickup" or "dropoff".string
durationDuration of the service (in minutes)integer
typeType restriction. Only vehicles with the same type string can perform the orders for which this type is present.string
demandDemand for capacity type 1. Can be in volumetric measures.integer
windowsTime windows that restrict the time at which this order is scheduled.array of Window
allowedVehiclesList of vehicle id's that are allowed to process this order.array of string
disallowedVehiclesList of vehicle id's that are NOT allowed to process this order.array of string

Fleet

The fleet consists of your vehicles, that you want to allocate the orders to. Each vehicle is defined by a starting and ending location (referencing a location on the network), and the shift start and end times.

PropertyDescriptionType
nameUnique identifier for vehicle namestring
startlocationThe name of the location where the vehicle startsstring
endlocationThe name of the location where the vehicle endsstring
shiftstartStarting time of the shift in minutes (0-1439)integer
shiftendEnd time of the shift in minutes (0-1439)integer
capacityCapacity available in the vehicle.integer
typeType restrictions. These should match with the type requirements of an Order.array of string
overtimeChecks whether this vehicle can go into overtime.boolean
breaksBreak definitionsBreak object

The end location is optional and may be omitted. This may be useful in cases when you care less about total distance traveled, and instead would like to prioritize your visits closeby to be done as soon as possible. The reason why this works is because Solvice OnRoute minimizes total travel time, and may leave closeby visits for on the way back.

Optionally, you may define the capacity of the vehicle (using the same unit as the "weight" for your orders). The algorithm will make sure that this capacity will not be exceeded. You can define 2 types of capacity: e.g. one for weight (in pounds, kilos, tons) and one for volume (square meters, cube meters)

If you are using type restrictions on your visits, make sure you also define the same types for your vehicles in the type parameter. This value is an array of strings for multiple types. Vehicles without any type will still be able to serve the visits that have no type restrictions. Examples of type restrictions: "Technician", "Maintenance", ...

If a vehicle can do overtime, then the shift end constraint is not seen as hard and then it is possible that some orders are scheduled after shift end. overtime_end determines the maximum of overtime.

Breaks

A break can be scheduled between a certain break interval (breakstart and breakend) and can take a pre-defined amount of time (breakduration).

ParameterDescriptionType
breakstartEarliest starting time of a breakinteger
breakendLatest ending time of a breakinteger
breakdurationDuration of a breakinteger

Introducing breaks will require more computation time, as they are seen as visits in the solution.

Options

Specific options can be added to guide the solving process.

PropertyDescriptionType
trafficTraffic modifier. Default at 1.0. All travel times get multiplied with the traffic parameter.double
overconstrainedIndicates to not plan all orders, but only the feasible ones.boolean
minimize_driver_wait_timeWait time should be minimized.boolean
minimize_vehicle_useThe least number of vehicles should be used.boolean

Output

After checking that the status is solved, you can fetch the solution in the solution endpoint. The solution endpoint will return a list of visits per vehicle. Additionally, the score function will be presented as well as the unresolved constraints.

Score

Scoring an optimisation solution is done by dividing between soft and hard constraints.
Hard constraints are required constraints, while soft constraints force the solution in a certain direction as objective functions. For more information, see the section on What is Optimisation?

In the following example, the score is given for a simple optimisation question where you can see that there is no hard constraint violation (resulting in a hard score of 0) and the soft score results in 59 score points while aiming to reach to zero. This means that the solution is feasible according to the constraints.

{
    "score": {
        "hardScore": 0,
        "softScore": -59,
        "feasible": true
    }
}

Unresolved constraints

Some constraints cannot be resolved and are left violated. In the unresolved section in the solution, we show the constraints that are violated in a list with their respective score value.

"unresolved": [
    {
      "name": "Vehicle Capacity",
      "value": -4,
      "level": "HARD"
    }
  ]

Solution

The actual solution is a map of a list of visits to the vehicle name.

{
  "solution ": {
    "driver1": [
      {
        "location ": "loc0 ",
        "order ": null,
        "arrival ": 510,
        "finish ": 510,
        "wait ": 0,
        "drive ": 0,
        "distance ": 0
      },
      {
        "location ": "loc1 ",
        "order ": "order1 ",
        "arrival ": 504,
        "finish ": 534,
        "wait ": 0,
        "drive ": 24,
        "distance ": 24
      }
    ]
  }
}

Visit object

PropertyDescriptionType
locationThe location name of the visitstring
orderThe order name of the visit.string
arrivalThe arrival time of that visit in minutes starting from midnight.integer
finishThe finish time of that visit in minutes starting from midnight. >= arrivalinteger
waitThe waiting time at that visit, if applicable in minutes.integer
driveThe driving / travel time from this visit to the next visit in minutesinteger
distanceThe travel distance from this visit to the next visit in minutes.integer

Example

{
    "solver": "VRP",
    "options": {
        "capacitySpread": true
    },
    "locations": [
        {
            "name": "loc0",
            "latitude": 51.12317420299715,
            "longitude": 5.281797793554478
        },
        {
            "name": "loc1",
            "latitude": 50.65329310557439,
            "longitude": 4.517600740757033
        },
        {
            "name": "loc2",
            "latitude": 51.20586951408341,
            "longitude": 5.050825570502835
        },
        {
            "name": "loc3",
            "latitude": 51.116048511299724,
            "longitude": 3.4438340449873435
        }
    ],
    "fleet": [
        {
            "name": "drive John",
            "startlocation": "loc0",
            "shiftstart": 500,
            "shiftend": 1439,
            "type": [
                "Technician"
            ]
        },
        {
            "name": "driver Joe",
            "startlocation": "loc2",
            "endlocation": "loc1",
            "shiftstart": 500,
            "shiftend": 900,
            "type": [
                "Maintenance"
            ]
        }
    ],
    "orders": [
        {
            "name": "order0 pickup",
            "location": "loc2",
            "windows": [
                {
                    "starttime": 480,
                    "endtime": 720,
                    "hard": true
                },
                {
                    "starttime": 780,
                    "endtime": 1020,
                    "hard": true
                }
            ],
            "duration": 30,
            "type": [
                "Technician"
            ]
        },
        {
            "name": "order1",
            "location": "loc1",
            "duration": 30
        },
        {
            "name": "order2",
            "location": "loc0",
            "demand": 2,
            "duration": 30
        },
        {
            "name": "order3",
            "location": "loc1",
            "demand": 2,
            "duration": 5
        }
    ]
}