Constraints
Contents
Constraints#
Tarot Routing - Route Optimisation API
Duration#
The duration of a Job is the amount of time which a Driver will spend not driving at that Job. It is often referred to as the service time.
During the optimisation the duration is used to calculate the Estimated Time of Departure (ETD) from a Job.
Specifically:
job.etd = job.eta + duration
Time Windows#
Time Windows restrict the time which the Driver is allowed to visit a given Job.
This is often used for:
Service Levels agreed with the customer
Appointments agreed with the customer
Deliver windows promised to the customer
Opening hours of the customer
Restricting access to a customer at a certain time of day (e.g. because of traffic, school zones, lunch, vehicle restrictions etc)
You can set Time Windows using the arrive_after and leave_by attributes on each Job.
You can set both values, one of the values, or neither.
If it is not possible to serve a Job within its Time Window, the Job will be unserved.
Note
arrive_after constrains the ETA (Estimated Time of Arrival) of a Job
leave_by constrains the ETD (Estimated Time of Departure) of a Job.
So, if you want to force a job to be served at an exact time, you should set
job.arrive_after = time_to_arrive_at_the_job
job.leave_by = time_to_arrive_at_the_job + job.duration
Negative Time Windows
Sometimes, customers are closed during certain times (e.g. if they have lunch) or don’t want to receive deliveries at certain times (e.g. a busy period)
This can be communicated using the exclude_period_start and exclude_period_end attributed of a Job.
Examples
{
"uid": "uid1",
"duration": 2,
"leave_by": 14,
"location": {"lat": -33.849489, "lon": 151.127482}
}
{
"uid": "uid1",
"duration": 2,
"arrive_after": 9,
"leave_by": 10,
"location": {"lat": -33.849489, "lon": 151.127482}
}
{
"uid": "uid1",
"duration": 2,
"arrive_after": 18,
"location": {"lat": -33.849489, "lon": 151.127482}
}
{
"uid": "uid1",
"duration": 2,
"arrive_after": 9,
"leave_by": 15,
"location": {"lat": -33.849489, "lon": 151.127482}
}
{
"uid": "uid1",
"duration": 2,
"exclude_period_start": 12,
"exclude_period_end": 14,
"location": {"lat": -33.849489, "lon": 151.127482}
}
{
"uid": "uid1",
"duration": 2,
"arrive_after": 9,
"leave_by": 15,
"exclude_period_start": 10,
"exclude_period_end": 11,
"location": {"lat": -33.849489, "lon": 151.127482}
}
Capacity#
You can restrict how much a vehicle can hold using Size and Capacity
This is often used for:
Setting a total weight limit (in KGs, Tonnes, LBs, etc) for items in a vehicle
Setting a total size limit (in m3, litres, etc) for items in a vehicle
Restricting the number of items (pallets, trolleys, boxes, crates) in a vehicle
Restricting the number of passengers in a vehicle
Restricting the total number of stops a Driver can do
Combining several of the above constraints
You can use this constraint by setting the capacity on a Driver and the size on a Job
If any Job has a size, then all Drivers must have a capacity
Dimensions#
We use the word Dimension to refer to each type of thing that you want to constrain.
For example: weight is a Dimension. volume is another Dimension. number of passengers is yet another Dimension.
Simple Capacity#
If you only use one Dimension, you can use simple capacity. e.g. you want to constrain weight or volume, but not weight AND volume.
To use Simple Capacity, you should set the Job size s and Driver capacity s to integers.
The optimiser is not aware of units (kilograms, grams, metres cubed, litres, etc). So you must use the same units for all values
Example
{
"drivers": [
{
"uid": "driver_1",
"shift_start": 8,
"shift_end": 17,
"location": {"lat": -33.867798, "lon": 151.166256},
"capacity": 10
}
],
"jobs": [
{
"uid": "job_1",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"size": 3
},
{
"uid": "job_2",
"duration": 2,
"location": {"lat": -33.880661, "lon": 151.183096},
"size": 4
},
{
"uid": "job_3",
"duration": 2,
"location": {"lat": -33.913168, "lon": 151.262267},
"size": 6
}
],
"settings": {}
}
Multi-Dimension Capacity#
If you want to constrain more than one Dimension, for example:
weight AND volume, or
seated passengers AND wheelchair passengers
then you should use Multi-Dimension Capacity.
Multi-Dimension Capacity is expressed in a DSL (Domain Specific Language):
Each Dimension name preceeds its value, separated by
:Dimensions are separated using
&
for example: weight:7&volume:1300&pallets:26.
To use Multi-Dimension Capacity, you should
Set the
capacityon all Drivers for all Dimensions. A driver that can take up to 8 boxes and up to 3 pallets would have capacityboxes:8&pallets:3Set the
sizeof each Job. A Job that is comprised of 1 box and no pallets would have sizeboxes:1&pallets:0
If a Dimension is omitted on a Driver, it is assumed that this Driver has 0 capacity for that Dimension.
Likewise, if a Dimension is omitted on a Job, it is assumed that this Job takes 0 size for that Dimension.
So boxes:1&pallets:0 is equivalent to boxes:1.
Example
{
"drivers": [
{
"uid": "driver_1",
"shift_start": 8,
"shift_end": 17,
"location": {"lat": -33.867798, "lon": 151.166256},
"capacity": "pallets:9&boxes:10"
}
],
"jobs": [
{
"uid": "job_1",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"size": "pallets:1"
},
{
"uid": "job_2",
"duration": 2,
"location": {"lat": -33.880661, "lon": 151.183096},
"size": "pallets:3&boxes:5"
},
{
"uid": "job_3",
"duration": 2,
"location": {"lat": -33.913168, "lon": 151.262267},
"size": "pallets:5&boxes:2"
}
],
"settings": {}
}
Logical Capacity#
If you want to constrain multiple Dimensions, and the capacity limit in each Dimension depends on other Dimensions, then you should use Logical Capacity
Logical capacity is expressed using the same DSL as Multi-Dimension Capacity, with a few extensions:
Each Dimension name preceeds its value, separated by
:AND constraints (all of which must be true) are expressed using
&OR constraints (one of which must be true) are expressed using
|Parentheses are used to
(group logical sections)
Imagine a truck which carries both boxes and bikes. The more bikes in the truck, the less space there is left for boxes, and vice versa.
If there are no bikes, the truck can hold 25 boxes.
boxes:25&bikes:0If there are no boxes, the truck can hold 10 bikes.
bikes:10&boxes:0If there are 5 bikes, the truck can hold 16 boxes.
bikes:5&boxes:16
We can express this to the optimiser using Logical Capacity by setting the Driver capacity to
(boxes:25&bikes:0)|(bikes:10&boxes:0)|(bikes:5&boxes:17)
Note: Logical capacity can only be applied to the Driver. Job size s must be described using Multi-Dimension Capacity mentioned above (|, (, and ) are not allowed).
Types#
Types restrict which Drivers are allowed to do which Jobs
This is often used for:
Ensuring certain deliveries are performed by refrigerated vehicles
Ensuring that the driver has the right qualifications to perfom a service (e.g. she is a level 2 qualified electrician)
Ensuring that large parcels are delivered by large enough vehicles, or vehicles with a tail lift
Forcing a Job to be performed by a specfic Driver(because the customer requested her, for example)
Ensuring only certain vehicle types (e.g. small trucks, bicycles, electric vehicles) perform deliveries in city areas
If you are looking to create “Territories” or “Delivery Zones”, please use Territories.
You can use this constraint by setting the spec_type on Jobs and Drivers.
A Job with spec_type=null can be served by any Driver.
Note
We refer to this constraint as Types, yet in the code this is called spec_type, an abbreviation of Specialisation Type.
type is a reserved word in most programming languages, so we didn’t want to use it.
Simple Types#
If a Job has one or more types, it may only be served by a Driver who has the same type.
For example a Job with type electrician cannot be served by a driver without a type, or a driver with type plumber. However, it can be served by a Driver with type electrician.
Examples
{
"drivers": [
{
"uid": "driver_1",
"shift_start": 8,
"shift_end": 17,
"location": {"lat": -33.867798, "lon": 151.166256},
"spec_type": "plumber"
}
],
"jobs": [
{
"uid": "job_1",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"spec_type": "plumber"
},
{
"uid": "job_2",
"duration": 2,
"location": {"lat": -33.880661, "lon": 151.183096},
"spec_type": "electrician"
},
{
"uid": "job_3",
"duration": 2,
"location": {"lat": -33.913168, "lon": 151.262267},
"spec_type": null
}
],
"settings": {}
}
Multiple Types#
Multiple types should be separated by commas ,.
A Job with type cert1,cert2 could be served by a Driver with any of the following types:
cert1cert2cert1,cert2cert1,cert8plumber,cert2,cert8
but it cannot be served by a driver with any of the following types:
(blank)
cert8cert8,cert9plumberplumber,cert8
Examples
{
"drivers": [
{
"uid": "driver_1",
"shift_start": 8,
"shift_end": 17,
"location": {"lat": -33.867798, "lon": 151.166256},
"spec_type": "plumber,cert2,cert3"
}
],
"jobs": [
{
"uid": "job_1",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"spec_type": "cert2"
},
{
"uid": "job_2",
"duration": 2,
"location": {"lat": -33.880661, "lon": 151.183096},
"spec_type": "plumber"
},
{
"uid": "job_3",
"duration": 2,
"location": {"lat": -33.913168, "lon": 151.262267},
"spec_type": "electrician,cert3"
},
{
"uid": "job_4",
"duration": 2,
"location": {"lat": -33.913168, "lon": 151.262267},
"spec_type": "electrician,cert4"
},
],
"settings": {}
}
Logical Types#
If you need to be more specific about who can do what, use logical types
Logical types can only be applied to Jobs. The Driver spec_type must be expressed using Multiple Types or Simple Types as above.
Logical types are expressed in our DSL:
AND constraints (all of which must be true) are expressed using
&OR constraints (one of which must be true) are expressed using
|Parentheses are used to
(group logical sections)
For example, imagine all of your internal Drivers are qualified to do all Jobs. But sometimes you use subcontracted drivers, and it is important to ensure they have the appropriate qualification for each Job.
A Job with spec_type internal|(subcontractor&cert3) could be served by any Driver with one of the following types:
internalinternal,plumbersubcontractor,cert3subcontractor,cert1,cert2,cert3,cert4
but cannot be served by a Driver with one of the following types:
(blank)
subcontractorcert3subcontractor,cert1,cert2,cert4
Examples
{
"drivers": [
{
"uid": "driver_1",
"shift_start": 8,
"shift_end": 17,
"location": {"lat": -33.867798, "lon": 151.166256},
"spec_type": "internal"
},
{
"uid": "driver_2",
"shift_start": 8,
"shift_end": 17,
"location": {"lat": -33.867798, "lon": 151.166256},
"spec_type": "subcontractor,cert4"
},
{
"uid": "driver_3",
"shift_start": 8,
"shift_end": 17,
"location": {"lat": -33.867798, "lon": 151.166256},
"spec_type": "subcontractor,cert3,cert4"
},
],
"jobs": [
{
"uid": "job_1",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"spec_type": "internal|(subcontractor&cert3)"
}
],
"settings": {}
}
Territories#
Many Delivery and Field Services companies divide their servicable area into “zones” or “territories”.
Companies often adopt this approach because:
Each Driver gets to know their geographic area well
You immediately know which Route a new Job falls into based on its location
Warehouses can prepare shipments on the dock before the last order is made, before the optimisation is run.
Warning
Routes planned with Territories are usually 10% to 35% longer (KMs and hours) than without.
However, we know that many companies cannot afford to make the trade-offs required to receive that benefit.
Internally, Territories are implemented using Types, so you’ll notice the syntax is the same as Multiple Types.
A Driver with driver.territories = 'North,East' can serve Jobs with:
job.territories = 'North'job.territories = 'East'job.territories = 'North,East'job.territories = ''job.territories = null
but cannot serve Jobs with:
job.territories = 'East'job.territories = 'NorthEast'
Jobs Outside Territories#
Sometimes you will have a job that is not in any territory.
By default any Driver can serve this Job.
However, you may desire all Jobs outside of your predefined Territories to be unserved.
To put this in place, simply set the job.territories = 'JOB_OUTSIDE_TERRITORIES'
This effectively creates an extra Territory which no driver can serve.
It doesn’t matter what you call it. It just needs a territory name that no Drivers have.
Pickup Delivery#
Pickup and Delivery refers to a situation where a Driver should pickup a parcel and subsequently deliver it in the same run. There may be other Jobs served between the Pickup and the Delivery.
A Pickup and Delivery must be represented as two Jobs in Tarot Routing: A Pickup Job and a Delivery Job.
Just like all Jobs, the Pickup Job and the Delivery Job can each have their own constraints.
For example, using Time Windows you could ensure that the pickup is performed after 10am pickup_job.arrive_after = 10 and the Delivery Job is performed before 2:30pm delivery_job.leave_by = 14.5
Pickup Delivery constraints can be expressed to the optimiser by setting the value of the pickup_from on the Delivery Job to the uid of the Pickup Job:
delivery_job.pickup_from = pickup_job.uid
Pickup Delivery Interval#
If you wish to constrain the maximum time between the pickup and the delivery, you can use delivery_job.pd_interval_max.
Its value is the maximum time in minutes between the pickup_job.eta and the delivery_job.eta
Minimise Time Aboard#
Sometimes, the things you’re picking up and delivering are humans, or hot/cold food.
Hot food gets cold. Cold food gets hot. Humans complain.
As a result, it may be desirable to minimise the time that these “things” spend in the vehicle.
You can do this using a parameter in the Settings object called min_time_aboard
{
"settings": {
"min_time_aboard": true
}
}
Pickup Delivery with Capacity#
If you wish to use the Capacity constraint with Pickup Delivery Jobs, you should set:
size = 10 # for example
pickup_job.size = size
delivery_job.size = -size
The delivery_job.size is negative to reflect the fact that this delivery is no longer consuming space (or weight, places, etc) in the vehicle.
Examples
job_1-pickup and then subsequently go to job_2-delivery# [
{
"uid": "job_1-pickup",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482}
},
{
"uid": "job_2-delivery",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"pickup_from": "job_1-pickup"
}
]
[
{
"uid": "job_1-pickup",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"size": 10
},
{
"uid": "job_2-delivery",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"pickup_from": "job_1-pickup",
"size": -10
}
]
[
{
"uid": "job_1-pickup",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"size": "boxes:3&bikes:2"
},
{
"uid": "job_2-delivery",
"duration": 2,
"location": {"lat": -33.849489, "lon": 151.127482},
"pickup_from": "job_1-pickup",
"size": "boxes:-3&bikes:-2"
}
]
Pickup Delivery and Unserved Jobs#
If any job in a Pickup Delivery pair/chain cannot be served, then none of those jobs will be served.
Driver End Location#
By default, Drivers end where they started.
However, you can change this.
If the driver ends: |
You should: |
|---|---|
Where they started |
Do nothing. This is the default behaviour. |
At a fixed location |
Set the Driver’s |
At the last job (anywhere) |
Set the Driver’s |
Warning
end_location is ignored if you set "end_anywhere": true.
See the Driver Reference for details.
Fairness#
Fairness is a Setting which changes the way the optimiser works.
When allocate_fairly=true, the algorithm tries to give each driver roughly the same volume of work, measured by the total time they spend driving + performing jobs.
In general, we recommend using this constraint only if you have to because:
Being fair also means being less optimal - your drivers will drive more in total
Using this constraint substantially complicates the RoutingProblem, and so the algorithm takes longer to reach a good solution.
Walkable Jobs#
settings["walkable_threshold"] allows you to bias the optimiser towards visiting neighbouring jobs consecutively.
Note
In most cases, the optimiser would serve them consecutively anyway.
However:
Under certain circumstances, the optimiser can plan to visit neighbouring Jobs separately.
This only happens if the optimal route involves driving past those jobs more than once.
The optimiser considers visiting them consecutively to be equivalent to visiting them at different times, because it has to drive past them twice anyway.
To enable this Walkable Jobs Bias, set settings["walkable_threshold"]
The
walkable_thresholdis the driving time below which Jobs are considered walkable.30seconds is a reasonably good value for most use cases.
The optimiser will then prefer to visit those Jobs consecutively instead of separately.
Warning
Using higher walkable_thresholds (200+ seconds) may result in slightly less optimial routes (more time spent driving).
In our testing 90% of cases didn’t result in any loss.
When there was, the loss of optimality was rarely more than two minutes over the entire scenario.
You probably don’t want your driver walking between stops that are 200+ driving seconds apart anyway.
Breaks#
Breaks are a set of Driver attributes which determine times during their shift that a Driver cannot serve Jobs.
You need to consider whether they should be Fixed breaks at a certain time, or Floating Breaks so the optimiser can decide when it should occur within a given time period.
Fixed breaks#
Fixed Breaks must be served exactly at the prescribed time.
You can set a 45min Fixed Break at 1:30pm using:
driver.lunch_start = 13.5driver.lunch_duration = 45driver.lunch_latest_start = null
Floating Breaks#
Floating Breaks have a predetermined duration, but the Optimiser can decide when the optimal moment is for the Driver to take the Break within a given time period.
You can set a 30 minute break sometime between 10am and 11:30am using:
driver.lunch_start = 10driver.lunch_duration = 30driver.lunch_latest_start = 11
Note
The lunch_start and lunch_latest_start constrain the start time of the break.
So, in the example above, the break can occur between 10am and 11:30am, which implies that the break must be started between 10am and 11am