Long Term Routing

Long Term Routing is a VRP for multiple days. When planning for multiple days, the optimisation gets even more complicated.

Input

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

  • period
  • locations
  • orders
  • vehicles

Planning period

An extra property explaining the period for which we can solve the problem should be used.

Parameter

Description

Type

start

Start date of planning period

string

end

End date of planning period (non inclusive)

string

{
  "period": {
      "start": "2018-01-01",
      "end": "2018-01-31"
  },
  // ...
}

Locations

Define the list of locations.

Property

Description

name
(string)

Unique identifier for location name

latitude
(number)

Latitude in WSG84

longitude
(number)

Longitude in WSG84

Orders

Property

Description

Type

name

The unique name of the order

string

location

The name of the location where this order is located. (refers to location list)

string

duration

Duration of the service (in minutes)

integer

type

Type restriction. Only vehicles with the same type string can perform the orders for which this type is present.

string

dateWindows

Date windows that restrict the time and date at which this order is scheduled.

array of DateWindow

plannedDate

Date at which this order was already planned to and to which it must adhere.

string

plannedVehicle

Vehicle at which this order was already planned to and to which it must adhere.

string

priority

Priority allows you to make certain visits a priority over others. In some cases you have more visits than you can serve, resulting in a few unserved. But if you want to make sure your high priority visits take precedence, use this parameter and set it to 100.

integer >0

hard

In the case of overconstrained planning, this indicates whether this order should be integrated into the planning or not.

boolean

allowedVehicles

List of vehicle id's that are allowed to process this order.

array of string

disallowedVehicles

List of vehicle id's that are NOT allowed to process this order.

array of string

DateWindow

The date windows are a list of start/end and date-time combinations that describes the time availability of an order.
It has a starttime and endtime, a start date and an end date. You can indicate whether this availability is either hard, which means that it must be accounted for in the schedule. Optionally, you can define the weight on this availability constraint.

Property

Description

Type

starttime

Start time of a date window. (0-1440)

integer

endtime

End time of a date window. (0-1440)

integer

start

Start date of date window.

string

end

End date of date window.

string

hard

Evaluates this date window constraint as a hard one or a soft one.

Boolean

weight

Weighting on the date window. The higher, the more important this constraint is.

integer

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.

Property

Description

Type

name

Unique identifier for vehicle name

string

startlocation

The name of the location where the vehicle starts

string

endlocation

The name of the location where the vehicle ends

string

shiftstart

Starting time of the shift in minutes (0-1439)

integer

shiftend

End time of the shift in minutes (0-1439)

integer

capacity

Capacity available in the vehicle.

integer

type

Type restrictions. These should match with the type requirements of an Order.

array of string

overtime

Checks whether this vehicle can go into overtime.

boolean

breaks

Break definitions

Break 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).

Parameter

Description

Type

breakstart

Earliest starting time of a break

integer

breakend

Latest ending time of a break

integer

breakduration

Duration of a break

integer

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

Linked orders

Orders that require to be executed at the same time are called Linked orders. A typical use case is that you would need 2 people to execute a job.

"linked_orders": [
  {
    "order1": "o1",
    "order2": "o2"
  }
]

Precedence relations

In PVRP, a time dependency (or precedence constraint) can be modelled for two orders. order1 is the name of the left order (must be executed first), referenced by the name provided in orders. order2 is the name of the right order (must be executed after order 1). min is the minimum time in days between order2 and order1 and max is the maximum time in days between order2 and order1.

"precedence_constraints": [
    {
      "order1" : "o1",
      "order2": "o2",
      "min": 1,
      "max": 5
    }
]

Options

Specific options can be added to guide the solving process.

Property

Description

Type

traffic

Traffic modifier. Default at 1.0. All travel times get multiplied with the traffic parameter.

double

overconstrained

Indicates to not plan all orders, but only the feasible ones.

boolean

minimize_driver_wait_time

Wait time should be minimized.

boolean

minimize_vehicle_use

The least number of vehicles should be used.

boolean

capacitySpread

Create a fair workload for every vehicle.

boolean

force_type_constraints

If yes, then the type constraints violations are not allowed. Only do this when you are sure about type definitions.

boolean

traffic

Modifier for traffic. Default at 1.0, at 1.1 it enforces you to be 10% more conservative when it comes to travel timie

double

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

Property

Description

Type

location

The location name of the visit

string

order

The order name of the visit.

string

arrival

The arrival time of that visit in minutes starting from midnight.

integer

finish

The finish time of that visit in minutes starting from midnight. >= arrival

integer

wait

The waiting time at that visit, if applicable in minutes.

integer

drive

The driving / travel time from this visit to the next visit in minutes

integer

distance

The 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",
            "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
        }
    ]
}