The Itinero project originally started as a logistical optimization project for newspaper delivery. We built a new and improved version on top of the current routing core. In this first version we support routes for one vehicle at time, check out the Travelling Salesman Problem (TSP) for more information. We use a combination of Genetic Algorithms, local search and Guided Neighbourhood Search to get good results very fast.
At the moment we support the following problem types:
An example solution, from a sequence of points to a solution route:
A fastest route along a sequence of points.
Another thing we did is add support for U-turn prevention. While this is something we already have in the Itinero routing engine itself, there is also a need to implement this at the level of the optimization code.
We ask the question: Is it allowed or a good idea to make U-turns at the points we are travelling along. Sometimes it will be, if for example we have to make longer stops at each point or when using a bicycle, but most of the time, for example for newspaper delivery or waste collection it’s best to avoid U-turns. This is especially true when travelling with big trucks.
So we implemented U-turn prevention in all of the supported optimization problems, an example is shown here for the TSP. This is the same sequence of points except with a cost given to U-turns:
A fastest route along a sequence of points, taking into account the cost of U-turns.
Support for multiple vehicles
This is ideal for simple logistics problems, or shortest routes along several POI’s, but we are planning to expand to routing calls with multiple vehicles soon.