A Deep Dive on Speed, Clustering and Optimality

Three years have passed since the launch of our LogisticsOS vehicle routing API. During this time, we have dedicated ourselves to enhancing our algorithms, assisting numerous enterprise customers in optimizing their last-mile deliveries. The primary concerns for customers utilizing a Vehicle Routing Problem (VRP) solver typically revolve around three key aspects: fast computational time, visually appealing clustered routes, and optimization for cost efficiency. Striking a balance among these factors is often challenging.

Customers place a high premium on swift computational time, as it allows them to conduct multiple iterations with various parameters to explore every conceivable scenario. Simultaneously, they are discerning about the visual appeal of clustered routes, as dispatchers and drivers have specific preferences in this regard. Furthermore, cost-driven enterprises prioritize the optimality of route plans, creating a dynamic where these three crucial aspects frequently clash.

It becomes evident that providing the solver with more time for optimization yields better route plans, translating to lower costs. Additionally, achieving high-quality clustering necessitates investing time in optimizations. Consequently, there is a common trade-off, requiring a compromise on the optimality of route plans to achieve visually appealing clusters.

Speed and Optimality

In the LogisticsOS VRP API, users have the flexibility to adjust the search_level parameter of the algorithm engine, a choice that significantly influences the time taken by the solver to generate a route plan. The search_level parameter offers varying degrees of optimization, allowing users to tailor their experience based on specific needs.

When the search_level is set to 0, the VRP engine constructs a feasible solution and then employs Large Neighborhood Search (LNS) to enhance the solution before presenting it to the user. At search_level 1, the VRP engine takes a more comprehensive approach by applying both LNS and Iterative Ruin and Recreate (IRC) before returning the optimized route plan. For the highest level of optimization at search_level 2, the VRP engine utilizes a sequential application of LNS, IRC, and Guided Search (GS) to the initial route plan before delivering the solution to the end user.

To validate the effectiveness of our approach, we conducted tests on various VRP instances sourced from the VRPLIB (http://vrp.galgos.inf.puc-rio.br/index.php/en/). The results demonstrate the versatility and performance of our VRP API across different scenarios and complexities.

Instance name	Num customers	Best known cost	LogisticsOS level 0		LogisticsOS level 1		LogisticsOS level 2
			Cost	Time	Cost	Time	Cost	Time
Antwerp1	6000	477277	482211	63s	480456	147s	479779	210s
Antwerp2	7000	291350	301239	93s	300135	177s	297513	254s
Brussels1	15000	501719	510288	230s	507119	410s	505901	734s
Ghent1	10000	469531	483988	144s	480332	277s	479119	423s
Leuven1	3000	192848	195170	47s	194377	66s	192848	134s
Leuven2	4000	111391	116387	76s	114749	155s	112815	212s

As evident from the computational results presented above, setting the search_level to 0 in the LogisticsOS VRP engine yields solutions that are approximately 2% to 4% away from optimality. However, by increasing the search_level, users can achieve further cost reductions ranging from 0.5% to 2%. This enhanced optimization comes at the trade-off of a significant increase in computational time, potentially doubling or even quadrupling the processing duration. Users can fine-tune the search_level based on their priorities, balancing the need for cost efficiency against the computational resources available.

Clustering and Optimality

Interestingly, customers often prioritize a sub-optimal vehicle routing solution with clustered routes over obtaining the most optimal numerical solution. Dispatchers and drivers typically find solutions with visually clustered routes more favorable. The key consideration revolves around understanding the extent of optimality sacrificed when generating these clustered routes.

To address this, we conducted tests by setting high_quality_cluster to true and resolving benchmark instances. This approach aimed to provide insights into the trade-off between route optimality and the visual appeal of clustered routes, helping us strike the right balance for our users' preferences.

Instance name	Num customers	Best known cost	LogisticsOS level 0		LogisticsOS level 1		LogisticsOS level 2
			high_quality_cluster		high_quality_cluster		high_quality_cluster
			False	True	False	True	False	True
Antwerp1	6000	477277	482211	503484	480456	500355	479779	490136
Antwerp2	7000	291350	301239	307341	300135	304467	297513	302245
Brussels1	15000	501719	510288	520233	507119	518349	505901	517385
Ghent1	10000	469531	483988	487396	480332	486231	479119	486117
Leuven1	3000	192848	195170	120952	194377	120890	192848	197291
Leuven2	4000	111391	116387	117831	114749	117031	112815	115868

Based on the experiments conducted above, a premature conclusion may suggest that improving cluster quality could result in a cost increase ranging from 1% to 4%. However, it's essential to note that these percentage increases do not fully reflect the reality. Feedback from dispatchers and drivers has highlighted a crucial aspect: when delivery routes are concentrated in a specific geographic zone, the increase in cost is not a direct representation of the operational reality.

Dispatchers and drivers emphasize that having delivery routes concentrated in a geographical zone reduces volatilities in their operations. Stable traffic conditions contribute to more accurate Estimated Time of Arrivals (ETAs). Moreover, the ability to assign drivers familiar with the area to clustered route zones enhances delivery efficiency. Therefore, the cost increase observed in the experiments may not uniformly translate to real-world scenarios, as the benefits of improved cluster quality extend beyond mere numerical considerations.

Brussels1 (high_quality_cluster false)

Brussels1 (high_quality_cluster true)

I strongly encourage you to experience the capabilities of the LogisticsOS VRP API firsthand. By trying it out, you can witness the potential improvements it offers over your existing route optimization solution. Our solution comes equipped with global map and traffic data coverage, powered by TomTom technology. Whether you're grappling with route optimization challenges or considering a resell partnership, please don't hesitate to reach out. We are here to assist and collaborate, providing tailored solutions to meet your specific needs.

About LogisticsOS

LogisticsOS is the most powerful route optimization system on the market. Our flexible, hosted route optimization and planning/replanning APIs require no knowledge of optimization techniques. High-quality results are returned within seconds— even at scale. From time reduction and vehicle capacity to depot automation and cost customization, our feature-rich software can create the efficiency and cost-savings that you need. Contact us today for a free product demo.