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 :py:data:`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 .. code-block:: python 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 :py:data:`Job`. **Examples** .. code-block:: json :caption: A Job that must be delivered by 2pm :emphasize-lines: 4 { "uid": "uid1", "duration": 2, "leave_by": 14, "location": {"lat": -33.849489, "lon": 151.127482} } .. code-block:: json :caption: A Job that you have agreed to perform between 9am and 10am :emphasize-lines: 4,5 { "uid": "uid1", "duration": 2, "arrive_after": 9, "leave_by": 10, "location": {"lat": -33.849489, "lon": 151.127482} } .. code-block:: json :caption: A Job where the customer has informed you they are only home after 6pm :emphasize-lines: 4 { "uid": "uid1", "duration": 2, "arrive_after": 18, "location": {"lat": -33.849489, "lon": 151.127482} } .. code-block:: json :caption: A Job where the customer is open from 9am to 3pm :emphasize-lines: 4,5 { "uid": "uid1", "duration": 2, "arrive_after": 9, "leave_by": 15, "location": {"lat": -33.849489, "lon": 151.127482} } .. code-block:: json :caption: A Job where the customer is available all day, but doesn't want to receive deliveries midday to 2pm because they close for lunch :emphasize-lines: 4,5 { "uid": "uid1", "duration": 2, "exclude_period_start": 12, "exclude_period_end": 14, "location": {"lat": -33.849489, "lon": 151.127482} } .. code-block:: json :caption: A Job where the customer is open from 9am to 3pm, but doesn't want to receive deliveries from 10am-11am because they're busy :emphasize-lines: 4,5,6,7 { "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 :py:data:`Driver` and the ``size`` on a :py:data:`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 :ref:`Dimension `. volume is another :ref:`Dimension `. number of passengers is yet another :ref:`Dimension `. Simple Capacity ^^^^^^^^^^^^^^^ If you only use one :ref:`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** .. code-block:: json :caption: A RoutingProblem where the driver will not be able to serve all 3 jobs. One will be unserved because the Driver does not have sufficient capacity. :emphasize-lines: 8,16,22,28 { "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 :ref:`Dimension `, for example: * weight AND volume, or * seated passengers AND wheelchair passengers then you should use :ref:`Multi-Dimension Capacity`. Multi-Dimension Capacity is expressed in a DSL (Domain Specific Language): * Each :ref:`Dimension ` name preceeds its value, separated by ``:`` * :ref:`Dimensions` are separated using ``&`` for example: ``weight:7&volume:1300&pallets:26``. To use :ref:`Multi-Dimension Capacity`, you should #. Set the ``capacity`` on all Drivers for all :ref:`Dimensions`. A driver that can take up to 8 boxes and up to 3 pallets would have capacity ``boxes:8&pallets:3`` #. Set the ``size`` of each Job. A Job that is comprised of 1 box and no pallets would have size ``boxes:1&pallets:0`` If a :ref:`Dimension ` is omitted on a Driver, it is assumed that this Driver has 0 capacity for that :ref:`Dimension `. Likewise, if a :ref:`Dimension ` is omitted on a Job, it is assumed that this Job takes 0 size for that :ref:`Dimension `. So ``boxes:1&pallets:0`` is equivalent to ``boxes:1``. **Example** .. code-block:: json :caption: A RoutingProblem where the Driver can serve all 3 Jobs, since the total pallets doesn't exceed 9 and the total boxes doesn't exceed 10 :emphasize-lines: 8,16,22,28 { "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 :ref:`Dimensions`, and the capacity limit in each :ref:`Dimension ` depends on other :ref:`Dimensions`, then you should use Logical Capacity Logical capacity is expressed using the same DSL as :ref:`Multi-Dimension Capacity`, with a few extensions: * Each :ref:`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:0`` * If there are no boxes, the truck can hold 10 bikes. ``bikes:10&boxes:0`` * If 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 :ref:`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 :ref:`Territories`. You can use this constraint by setting the ``spec_type`` on :py:data:`Jobs ` and :py:data:`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** .. code-block:: json :caption: A RoutingProblem where the driver will be able to serve job_1 and job_3, but not job_2. :emphasize-lines: 8,16,22,28 { "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: * ``cert1`` * ``cert2`` * ``cert1,cert2`` * ``cert1,cert8`` * ``plumber,cert2,cert8`` but it **cannot** be served by a driver with any of the following types: * (blank) * ``cert8`` * ``cert8,cert9`` * ``plumber`` * ``plumber,cert8`` **Examples** .. code-block:: json :caption: A RoutingProblem where the driver will be able to serve job_1, job_2 and job_3, but not job_4. :emphasize-lines: 8,16,22,28,34 { "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 :ref:`Multiple Types` or :ref:`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: * ``internal`` * ``internal,plumber`` * ``subcontractor,cert3`` * ``subcontractor,cert1,cert2,cert3,cert4`` but **cannot** be served by a Driver with one of the following types: * (blank) * ``subcontractor`` * ``cert3`` * ``subcontractor,cert1,cert2,cert4`` **Examples** .. code-block:: json :caption: A RoutingProblem where driver_1 and driver_3 are able to serve the Job, but driver_2 cannot. :emphasize-lines: 8,15,22,30 { "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 :ref:`Types`, so you'll notice the syntax is the same as :ref:`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 :ref:`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 :py:data:`Settings` object called ``min_time_aboard`` .. code-block:: json { "settings": { "min_time_aboard": true } } Pickup Delivery with Capacity ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ If you wish to use the :ref:`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** .. code-block:: json :caption: Two Jobs represening a Pickup Delivery pair. The Driver must go to ``job_1-pickup`` and then subsequently go to ``job_2-delivery`` :emphasize-lines: 3,11 [ { "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" } ] .. code-block:: json :caption: Pickup Delivery Jobs with Simple Capacity :emphasize-lines: 3,6,12,13 [ { "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 } ] .. code-block:: json :caption: Pickup Delivery Jobs with Multi-Dimension Capacity or Logical Capacity :emphasize-lines: 3,6,12,13 [ { "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 ``"end_location": {"lat": -33.1, "lon": 151.0}`` At the last job (anywhere) Set the Driver's ``"end_anywhere": true`` =========================== ================================================================= .. Warning:: ``end_location`` is ignored if you set ``"end_anywhere": true``. See the :py:data:`Driver Reference ` for details. | | | Fairness -------- Fairness is a :py:data:`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_threshold`` is the **driving** time below which Jobs are considered walkable. - ``30`` seconds 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_threshold``\ s (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 :py:data:`Driver ` attributes which determine times during their shift that a Driver cannot serve Jobs. You need to consider whether they should be :ref:`Fixed Breaks` at a certain time, or :ref:`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.5`` - ``driver.lunch_duration = 45`` - ``driver.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 = 10`` - ``driver.lunch_duration = 30`` - ``driver.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 .. Indices and tables .. ================== .. * :ref:`genindex` .. * :ref:`modindex` .. * :ref:`search`