Routing models

Routing models involve determining the sequence in which things should be done by different resources. The simplest case of a routing model is the TSP, where a single resource (the travelling salesman) has to visit all locations provided in the cheapest possible way. This is the key focus of routing models, finding good sequences of activities which minimise the cost. Routing models grow more complicated and involve many side constraints. Typical examples of this are models such as the CVRP, which is tasked with still finding a cost efficient sequence of activities, but also needs to ensure that each vehicle is only assigned orders which cumulatively fit on the vehicle.

In the Icepack modelling world, concepts such as distance, time, or capacity are simply dimension which are measured along. So it’s possible to add more constraint dimensions as required, an example of this would be two capacity dimensions such as weight and volume. Time windows are simply constraints on the time dimension but one could also add windows on mass dimensions if required, which is a nice trick to help the optimiser product results which are often closer to real-world operations.

The last generalisation of the VRPs includes pickup and dropoff situations. In the classic academic CVRP problems, there’s an assumption that the vehicle makes one “trip” per day. This means that the vehicle does not return to the depot during the course of the day - which is often not the case in reality. The way this is modelled is by creating two tasks for each job, the first which specifies the pickup location, and the second the dropoff location. This means that we don’t require the concept of a depot, rather just the details of the job.

The last tier of complexity comes in the form of compartment modelling. This is often useful when modelling line haul vehicles which have mass constraints over axels and it’s important where on the vehicle different jobs are placed, in addition to how the vehicle is sequenced.

All classes of routing models support pulling through a detailed road network used in the optimisation process. If you’re looking to play around with the API and get a sense of the modelling style and constraints, we suggest starting off with the academic problems before tackling the IVR7/IVR8 models. If you’re looking to use the API in a production environment, we recommend the IVR7/IVR8 class of routing models and they provide the most modelling flexibility.