MOIA’s Algorithm Team Develops Hackathon Solver for the Li-Lim Benchmark
Written by: Christopher Weyand
MOIA’s pooling algorithm deals with a myriad of complex situations and handles competing objectives like customer experience (delays, perceived detours, walking distance …) and operational concerns (battery charging, route stability, driver breaks …). It must operate with limited, incomplete information in a dynamic environment.
A new trip is booked, a traffic jam appears, or a vehicle cannot be reached while it drives through a tunnel. The algorithm considers all these real-time updates and comes up with the most efficient schedule for each vehicle. Often, a single newly booked trip requires multiple vehicles to change their plans.
Using the knowledge, concepts and learnings from MOIA’s pooling algorithm, our experts took on a new challenge and tested their skills on an existing algorithm benchmark. They developed a solver for the Li-Lim benchmark as a two-week hackathon project.
The Li-Lim benchmark [1] is a publicly available dataset of scenarios, where vehicles must pick up and drop off passengers [2]. The primary goal is to minimize the number of vehicles to serve all passengers. The research institute Sintef collects the best-known solutions since 2003, which allows researchers across the globe to compare their algorithms.
The figure below shows how closely our solvers’ vehicle usage matches the best solutions after 60s computation time on instances with a short planning horizon. If it needs more vehicles than the best-known solution, the gap is shown in red. Instances where the solver finds the best-known solution are marked in green. The solver matches the best-known solution in 67 out of 179 instances and achieves a median gap of 5.26% more vehicles.
In the past, significant research effort and resources went into finding the current best solutions [3]. For example, NVIDIA built a GPU-accelerated algorithm that was able to find record-breaking solutions with 200 minutes computation budget on specialized hardware. Our 1-minute solutions show the efficiency of our solver in a practical setting. E.g., NVIDIAs record-breaking solution on the instance lr1_0800_02 consists of 59 vehicles to serve 400 passengers while our hackathon solver needs 60 vehicles.
While the solver did not achieve any world records, the results are surprisingly good given the two weeks of development time versus the decades of existing research. To work on an algorithm under lab conditions — metaphorically speaking — was a pleasure for the team and a refreshing experience.
References
[1] Haibing Li and Andrew Lim. 2003. A Metaheuristic for the Pickup and Delivery Problem with Time Windows. https://doi.org/10.1142/s0218213003001186
[2] Yvan Dumas, Jacques Desrosiers, François Soumis. 1991. The pickup and delivery problem with time windows. https://doi.org/10.1016/0377-2217(91)90319-Q
[3] Carlo S. Sartori, Luciana S. Buriol. 2020. A study on the pickup and delivery problem with time windows: Matheuristics and new instances. https://doi.org/10.1016/j.cor.2020.105065
