Concepts ========================================================== *Tarot Routing - Route Optimisation API* Drivers, Vehicles, and Theoretical Runs --------------------------------------- The :py:data:`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: #. the Driver owns their vehicle, and comes to work in it #. the Driver has restrictions on the hours they can work, or pauses they must take It is used to represent a **Vehicle** when #. the Capacity of the vehicle is important #. the Type of the vehicle is important #. different Drivers drive the same vehicle It is used to represent a **Theoretical Run** when: #. Jobs are pre-allocated to delivery zones #. 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*: #. The ``max_opt_time`` is reached. It's just a time limit on how long the algorithm can optimise for. #. 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. #. 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: #. 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. #. 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: #. ``max_opt_time`` restricts the amount of time it spends *optimising* only. #. 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``. #. 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`` .. code-block:: json { "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. .. epigraph:: | 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. :ref:`Start the optimisation ` 2. :ref:`Check the status ` in a loop until the optimisation has finished 3. :ref:`Get the solution `. Auth ---- You need to include the header ``Authorization: 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. .. tabs:: .. tab:: bash .. literalinclude:: _static/auth_req.sh :language: bash .. tab:: python .. literalinclude:: _static/auth_req.py :language: python 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