SWAT Mobility Tops Yet Another Li & Lim Benchmark

written by:
SWAT Mobility Team
Published on:
Sep 15, 2020
Our MFS team was credited with the best known result for instance lr2_4_8 under 400 tasks category on 24 Aug 2020.

SWAT Mobility clinches another PDPTW record on the world-renowned Li & Lim Benchmark with our proprietary algorithm developed in-house.

On 24 August 2020, our MFS team [1] was credited with the best known result for the instance lr2_4_8, under the 400 tasks instances category of Li & Lim's PDPTW benchmark problems. The submitted solution was generated with the objective of minimising the number of vehicles and total distance.

Currently, SWAT Mobility holds 2 other records in the 1000 tasks category. The results obtained in the 1000 category were achieved much earlier when we worked on intensive fleet minimisation algorithms with a focus on larger instances. 

Competing in and maintaining these benchmarks require significant resources, and even though it does not directly impact our core business, our team is eager to continue contributing to scientific achievements in the vehicle routing problem space and improve our algorithm.

Optimising for the passenger experience

In our business, we our use algorithm to help companies and fleet operators figure out the best solution to maximise the usage of their available vehicles. We have accumulated much experience in strengthening our algorithm to cope with both “fleet minimisation” and “passenger convenience” optimisation.

As we work with companies to improve the overall employee commuting experience, we had to tailor our algorithm to better cater to the needs of our passengers. These include considering factors like walking distances, the convenience of bus stops and “human-oriented” route geometry in our calculations. These criteria are usually not included in regular logistics-oriented VRP benchmarking.

About the Benchmark

Each task is either a pickup or a delivery, and has a sibling (a delivery or a pickup). The results reported has a hierarchical objective: 1) Minimize number of vehicles 2) Minimize total distance. Distance and time should be calculated with double precision, total distance results are rounded to two decimals. Exact methods typically use a total distance objective and use integral or low precision distance and time calculations. Hence, results are not directly comparable. [1]

[1] https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/400-customers/