We continually work to improve the algorithms of our API for route optimization so that we can provide quality solutions with enhanced efficiency. The matter at hand: the speed with which we interact with business-specific tools and the ability to rapidly solve problems of increasing size. Let’s have a look under the hood of the most recent version of VROOM, the open source software that we have developed.
Ever Better, Ever Faster
The above graph depicts, for 56 problems, the improvement in solution finding that was achieved through various trade-offs between solution quality and calculation times based on the Solomon benchmark, which is one of the standards in the field. The smallest gap to optimal solution costs, which on the average was already at a very low 1.81%, has now been further lowered to 1.63%. Not an easy task, given that the calculation time has been nearly halved: on the average, barely 360 milliseconds for problems that each involve 100 delivery points.
In the field, we noted that calculation times for the problems of one of our clients were reduced by 42%.
Improved Solutions
The combinatorial complexity of vehicle routing problems is so great as to make an exhaustive search for optimal solutions unrealistic. That is why we have adopted a local search strategy that allows us to limit our focus. The search process has to be at once sufficiently thorough to generate the best solutions and limited enough to maintain ultrafast calculation times. A newly added local search operator now allows us to reach even better solutions, and which are experienced as such in the field, for vehicles travel through neighboring locations far less frequently.
Setting Records for Problem Solving Speeds
To sharply reduce local search calculation times, we cut off some of the “branches” at the outset. Calculating and storing previously untapped data allows us to identify more quickly these inoperable solutions that fail to respect time and/or capacity constraints, and even constraints that are not necessarily explicit, such as the maximum number of jobs a given vehicle can perform, which may be limited by other constraints. The end result yields solutions in as little as half the time without having unduly limited the search for valid solutions and thereby overall quality.
Contact us if you would like to measure the impact of these improvements on your use-case.
