Ctrl+K

Concepts

Concepts#

Tarot Routing - Route Optimisation API

Drivers, Vehicles, and Theoretical Runs#

The Driver is a very flexible concept in Tarot Routing.

It can be used to represent:

  • an actual (human, for now) Driver, or

  • a vehicle, or

  • a predetermined theoretical run, or

  • several of the above at the same time.

It is used to represent the Human Driver when:

  1. the Driver owns their vehicle, and comes to work in it

  2. the Driver has restrictions on the hours they can work, or pauses they must take

It is used to represent a Vehicle when

  1. the Capacity of the vehicle is important

  2. the Type of the vehicle is important

  3. different Drivers drive the same vehicle

It is used to represent a Theoretical Run when:

  1. Jobs are pre-allocated to delivery zones

  2. you will decide later which human driver will drive this Run



ETA, ETD, and Duration#

ETA: Estimated Time of Arrival at a Job

ETD: Estimated Time of Departure after completing a Job

Duration: The time the Driver expects to spend performing a Job. Often called the service time. It includes time spent parking, walking to/from the vehicle, and time actually perfoming the job.

The job.duration is set by you, and taken into account by the optimisation algorithm.

The algorithm the sets the job.eta during the optimisation, based on the optimised route it calculates.

The job.etd is calculated very simply as job.etd = job.eta + duration



Optimisation Time#

How long does an optimisation run for?

It Depends

Every optimisation is stopped by one of the following Stopping Criteria:

  1. The max_opt_time is reached.

    It’s just a time limit on how long the algorithm can optimise for.

  2. The improvement_threshold_per_second is reached.

    This is a very common way to determine when an algorithm should stop calculating. Concretely, we’re talking about improvements in the Objective Function, which is a function that represents how good (or bad) each possible solution is.

    When the improvement every second drops below a certain threshold, we stop the optimisation.

    It is based on the premise that algorithms make large improvements when they first begin running, and those improvements get smaller and smaller as the algorithm gets closer to the optimal solution. In general this is true, but in cases where there are a lot of constraints (i.e. the Objective Function is less smooth), it’s not uncommon to see no improvement for a long time, followed by a large improvement.

  3. The optimiser has found a local minimum (only applicable if quick_opt=true)

    With quick_opt=true, the algorithm stops as soon as it reaches a local minimum. i.e. It is not using a metaheuristic jump out of a local minimum to continue the search.

    If you’re not sure what this means you can learn here or just trust me that quick_opt finds a good-but-not-great solution very quickly, then stops.

What determines the amount of time until I reach a local minimum or hit the improvement threshold?

There are two main factors:

  1. The number of Nodes (roughly the number of Drivers + number of Jobs)

    The more Nodes there are, the more possible solutions the algorithm needs to consider. Therefore, it takes longer.

  2. The number and complexity of constraints

    This is a very interesting one, because not all constraints are created equally.

    Certain constraints actually make a RoutingProblem easier to solve, beacuse they reduce the number of possible solutions to consider. (e.g. the algorithm doesn’t need to consider any solutions where the Job Type doesn’t match the Driver Type)

    Other constraints make it harder to solve, beause they increase the time it takes to evaluate if a solution is valid or not. (e.g. when the algorithm considers different possibilities of Jobs for a Driver to visit at the start of the day, it needs to check every single time if the Job at the end of the day still respects its Time WIndow)

    Futhermore, interactions between constraints can have very surprising effects on the performance of the algorithm.

Note

Sometimes you will see that the Routing API responds in a little longer than the max_opt_time.

This is because:

  1. max_opt_time restricts the amount of time it spends optimising only.

  2. The first thing the algorithm does is retrieve a Distance Matrix. This can take a few seconds for large optimisations. This time is not counted towards the max_opt_time.

  3. It can take time to send large requests and responses over the network, which is also not counted towards the max_opt_time

Some Guidelines

In general we find that, for RoutingProblems with very basic constraints, we get pretty good solutions in the following timeframes:

nodes

time (s)

10

1

30

5

50

10

80

20

100

30

150

45

200

60

300

120

1000

600

As a general rule, we recommend setting

  • max_opt_time to the number of seconds in the table

  • improvement_threshold_per_second=0.00005 (the default)

  • quick_opt=false

{
   "max_opt_time": 450,
   "improvement_threshold_per_second": 0.00005,
   "quick_opt": false
}


Real Time Optimisation#

Real Time Optimisation refers to optimisations that happen when the Driver has already started their Run, and maybe already completed some Jobs.

This functionality is live in Tarot Routing. Documentation is coming soon.

Want to use it now? Let us know info@tarotanalytics.com



Asynchronous Polling Optimisation#

Asynchronous Optimisation is a way of using the optimiser which doesn’t require you to keep the HTTP connection open to wait for a solution. This means it is appropriate for larger optimisation problems - we recommend you use it whenever you’re optimising more than 200 Jobs.

Asynchronous Optimisation is made for larger problems.
You don’t need to keep the connection open to wait for a solution.

There are 3 basic requests to make:

  1. Start the optimisation

  2. Check the status in a loop until the optimisation has finished

  3. Get the solution.

Auth#

You need to include the header Authorization: Token <your_token> in every request you make to the Route Optimisation API

You should perform a login request at the beginning of each session, since tokens expire.

URL='https://api.route.optimiser.app/api/auth/token'
HEADERS='Content-Type: application/json'
BODY='{
        "email": "your_email_address",
        "password": "your_password"
}'

RESP=$(curl "$URL" -H "$HEADERS" --data "$BODY")

# jq is a command line utility for parsing JSON
# you can install it with `apt install jq` or equivalent.
# The idea is just to get the `access_token` from the JSON response.
TOKEN=$(echo $RESP | jq -r .access_token)

Full documentation for this request is in the Tarot Routing Swagger.

If you don’t have a Tarot Routing account already, send us an email and we’ll get you started: info@tarotanalytics.com

Optimisation Objective#

By default, the optimiser tries to minimise the total time taken to complete all Jobs.

You can also set the objective to distance or cost using settings.optimisation_objective = "distance" or settings.optimisation_objective = "cost"

If Settings.optimisation_objective = "cost" you must provide costs for every Driver.

Lean more:

Contents