3 Basic vehicle routing model
At the simplest level, ODL Live solves a vehicle routing problem which has been extended for real-time scenarios. In the vehicle routing problem, vehicles visit stops in their planned routes. A stop is a location and a vehicle really refers to the combination of vehicle+driver, so a ‘vehicle’ could in fact mean a repair person or engineer. Many different types of costs and constraints can be applied to this routing problem, and you can also define your own costs and constraints with user functions. The following section gives a short overview of the larger concepts in the routing model.
3.1 Jobs and stops
Job objects contain stops, and ODL Live supports various different types of job objects, as shown in the following image:
See the section on types of jobs and stops for more details. Stops have a duration in milliseconds, which is the amount of time needed to serve them (e.g. park the car, unload the delivery, fix the broken machine etc). Stops have a location in latitude and longitude and one or more time windows.
3.2 Real-time planning objects
When the model is extended to real-time we include several other types of objects such as GPS traces and stop arrival and completion events. These new objects allow ODL Live to estimate the state of the vehicles (e.g. their positions, which stops they have pending, are about to complete or have completed, etc). We also have a new type of object called a dispatch which lets you lock down the short-term plan for the vehicle - see realtime planning section for more details.
3.3 Open, late and close times
Time windows on stops are supported - so a stop can have a start time, which is the earliest time the vehicle can start serving a stop, and an end time, which is the latest time a vehicle can start serving a stop. If the vehicle arrives at the stop before the stop’s start time, the vehicle is assumed to wait until the stop opens.
A stop can have a late time defined which should be earlier than its close time. By default the system will try to prevent stops being served after their late time, but still allow service if lateness is unavoidable. You should monitor for the plan starting to run significantly late for one or more stops and then manually intervene as needed, e.g. by arranging an alternative time with a customer.
Vehicles also have open times (when they leave the depot), late times (when they should return to the depot by), and close times (when they absolutely have to return to the depot by). See section on vehicle start and end times for more details.
Lateness modelling should always be enabled for real-time planning - i.e. you should always have a late time defined on both your stop and vehicle and this should be earlier than the close time by a decent safety margin. If you attempted to use only a hard end time window (so close time only, no late time) for real-time planning, you would find that small delays such as traffic jams would cause stops to become unloaded when the vehicle cannot arrive at the stop before its close time, even if the vehicle was only going to be one second late. We recommend a large safety margin - for example a day - so you effectively turn off the close time by setting it to the late time + 24 hours, and use only late time.
If you need more control over the time windows - for example you want to set multiple time windows for a job or you want to customise the cost penalties incurred if a delivery is late, we also support a more advanced interface to setup time windows.
See the section on Time windows and custom lateness penalties for more details on how to configure time windows and lateness penalties.
3.4 Skills
Skills are used to restrict which vehicles can serve which jobs. Skills could refer to the vehicle (e.g. refrigerated, fork-lift), or the person driving the vehicle (e.g. has licence A, licence B, qualification C). You can also use skills to lock a specific job to a specific vehicle, e.g. a vehicle could have a skill which is the same as its id, and then a job could have that as its required skill. You can also set prohibited skills - i.e. skills which the vehicle should not have. See the section on skills for more details. Also the section vehicle value-dependent cost functions for details of how to prohibit or allow a vehicle-job combination based on a vehicle’s numeric value (e.g. length, width).
Job-vehicle user functions can also be used to define custom rules on what combinations of vehicles and jobs are allowed, as well as defining costs for each combination.
3.5 Quantities and capacities
If you’re modelling freight or food deliveries, you may have to worry about the vehicle not having enough capacity to hold the deliveries - for example they may weight too much or take up too much space. To model this, you define one or more capacity dimensions on the vehicle (e.g. weight, volume) and corresponding quantities on the jobs. See quantities section for more details.
Incompatible quantities can prevent different types of quantities being on-board together - for example prevent food and chemicals being on-board at-once ( sequence based state user functions can also used to do this, if you need more control).
Soft capacities can also be used to allow but penalise capacity violation.
3.6 Cost model and penalties
ODL Live minimises the total cost of a routing plan, subject to loading as many jobs as it can and obeying other constraints like skills, capacities etc. The total cost is the sum of several different types of cost, these are some of the main cost types:
Basic vehicle costs. Costs for using a vehicle, for driving, for serving a stop etc. See basic vehicle costs section for details.
Fullness penalty. Cost which is applied to a vehicle based on how full it is, to help spread work between vehicles, thereby encouraging workload balancing. See workload balancing section.
Interstop costs. Costs or additional time applied between different types of stops. See interstop costs section.
Lateness. Cost associated with serving a stop late or a vehicle returning late. Defined on the model record. Normally lateness is setup as a non-linear penalty function, for example as the square of late time, to help spread lateness out between different stops.
Maximum separation. Set a maximum separation between stops on the same route or penalties based on the max separation, to keep routes within small areas. See max separation section.
On-board time penalty. A penalty cost based on how long items are on-board for pickup-delivery problems, see this section for details.
Route centering penalty. Cost which is applied to minimise the travel distance or time between the most central stop on a route and all other stops on the route. You can use this cost to force routes to form tighter clusters, instead of the typical ‘petal’ shaped routes that arise naturally from a central depot. See route centering penalty section.
Service radius penalty. A penalty applied if a vehicle serves stops outside of its defined service radius. This can also be set as a hard constraint (i.e. no assignments outside of service radius / polygon).
Total travel hours, km or work hours Set penalties and hard limits on the total travel hours, kilometres or worktime on a route. See sections total travel hours and total work time limit for details.
User function costs. With user functions you can define your own custom costs.
3.7 Traffic estimation
By default, ODL Live does its travel time calculations internally on road network data built from OpenStreetMap. There’s no need to use a 3rd party service to generate a travel time matrix or to setup your own dedicated OSRM server.
ODL Live has several modes for traffic and rush hour modelling:
Standard car speeds and standard truck speeds. A set of speeds available out the box (i.e. without any tuning or requiring any data to learn from), which adjust road speeds based on (a) type of road, (b) urban density (as you get more traffic in cities) and (c) hour of the day, using different profiles for weekday and weekend. Standard car speeds is our recommended solution, although if you need more fine-grained control you could use the other methods available. You can specify different dimensions of your truck (e.g. height, width, weight) when you build a truck road network graph.
Traffic learner. ODL Live includes a Traffic Learner module that can learn traffic patterns from historic journey data using machine learning. The Traffic Learner is the recommended solution to use providing you can construct a suitable dataset of historic journeys. Traffic Learner can learn subtle patterns - e.g. that traffic will be slower going one way in the morning and the other at night.
Manual tuning. Using ODL Live you can also customise rush hour periods based on your team’s knowledge. Set rush hour start and end times, define intermediary periods (e.g. ‘early rush hour’), different speed profiles for night-time etc.
External matrix. You can pass ODL Live an external matrix of travel times and distances (for all day or multiple times of the day). Generate a matrix from your favourite 3rd party service if you wish to, and use it in ODL Live.
ODL Live uses time-dependent travel times in every step of the algorithm (i.e. not just as a post-optimisation process), so routes are structured around rush hours. For example, the optimiser will favour doing stops that are close together during rush hours and further-apart stops outside of rush hours.
You can also use ODL Live to generate travel time and distance matrices to use in other applications - see command line matrix generation.
3.8 Selected other model features
The following list is a selection of the more important model features:
Alternative jobs. ODL Live can decide which job is best to do out of a set of possible jobs - see section on alternative jobs.
Breaks. Work breaks can be defined on a vehicle. See the chapter on breaks for more details.
Delay optimisation to minimise waiting time. ODL Live can calculate delayed leave times which get added to your routes to minimise waiting times at stop, on-board time for items etc.
Delivery locking. Stops already collected at a depot can be locked on-board for realtime problems.
Open or closed routes. Vehicles can start and end at defined locations, or at their first and last stop - see this ection.
Park and walking loops. With park-and-loop route optimisation, a driver can park their truck and deliver parcels on-foot in a loop.
Replenishment routing. With replenishment routing you can define that a vehicle uses a numeric value which needs to be replenished by visiting special stops. This is useful for electric vehicle routing where the vehicle needs to charge on route, and for various other types of routing problem.
User functions. Define your own costs and constraints with user functions.
The table of contents for the jobs and and vehicles chapters gives a more comprehensive list of modelling features.