Veeroute optimizer showcased the best known results on public benchmarks designed to be close to reality.
In the decision table for 300 tasks proposed by cssartori, Veeroute has taken 214 rows. These are the best known solutions, which were obtained using the Veeroute optimizer.
What does it mean? Let's have a look.
How do benchmarking competitions work?
In March 2019, Carlo S. Sartori posted in the cssartori public repository a set of benchmarks for the pickup and delivery problem, with time windows based on open data.
Each benchmark is related to a transportation problem that does not have a ready-made solution; there is only the current best known result. While it’s impossible to check whether this result is optimal, anybody can try to improve it.
The first competitor who provides a more effective solution to a particular problem will be entered into the final table. The table shows the current best known results and the dates they were received. If several participants provided the same results, then the table indicates the one who provided the solution first.
The benchmarking competition does not rank competitors or declare winners. However, it’s typically possible to clearly determine the leader in terms of their current contribution. The more times a participant is listed on the table, the more solutions they managed to improve.
Competitions of this kind are also held by large organizations like SINTEF , which is an influential Norwegian independent research organization that registers the best known solutions of academic benchmarks.
Does a successful result in the benchmarking competition prove the product's effectiveness?
Although benchmarks are often used to compare software products, they rarely provide results close to reality. We talked about it in detail in our article that compares the optimizers.
The competitions mainly use academic benchmarks, which are abstract and unrealistic. They are greatly simplified in comparison to everyday business problems and use fixed data sets, so fulfilling those benchmarks doesn't guarantee that the scheduler can solve actual problems efficiently.
As an example, the standard benchmarks, including those whose solutions are collected by SINTEF, use the Euclidean distance. This means the path from A to B is always calculated along a straight line. Since such conditions are rare in the real world, the results obtained on standard benchmarks will not give you a clear picture of the optimizer's operation quality.
Benchmarks made to be close to reality
Unlike the benchmarks offered by popular repositories, the instances created by Carlo S. Sartori were based on real-world data. For example, the distances between points were calculated considering existing roads rather than in a straight line.
The instances were generated using real-world data for addresses and travel times. The tool Open Source Vehicle Routing Instance Generator was developed specifically for the purpose of generating these instances. Travel times are computed using the Open Source Routing Machine, which takes as input OpenStreetMap data. Addresses were obtained from the OpenAdresses project and the Donovan and Work (2016) dataset.
— cssartori, Carlo S. Sartori
Thus, Carlo S. Sartori managed to bring the benchmarks closer to reality. Unequal segments are considered in the instances: the path from A to B differs from the path from B to A — for instance, this would be the case for one-way roads. This simultaneously makes the route planning more complex and gets benchmarks closer to real world conditions.
The proximity to real conditions is the reason why Veeroute’s team paid attention to the benchmarks created by Carlo S. Sartori: they showcase the Veeroute combinatorial optimizer's capabilities better than standard academic benchmarks.
Veeroute’s results
Carlo S. Sartori’s repository presented instances of different sizes: from 100 to 5000 locations. Each size group has exactly 25 instances. Veeroute has found the best known solution for all instances of over 1500 locations.
All instances received an improved solution by Veeroute, except for the group of the smallest size of 100 locations, which is easily explainable. It is relatively simple to achieve a better result for small problems; most competitors managed to surpass the benchmark, but only the first one to do so was listed on the table.
In total, Veeroute earned the first recorded best known solution for 214 out of 300 instances.