Professor Lv Zhipeng’s team and the Huawei Alkaid scheduling algorithm team participated together in the 12th DIMACS Implementation Challenge and won two championships, one runner-up, and two third places in the four tracks, marking them the only team to win multiple titles in the top three places.

Since 1990, the DIMACS Implementation Challenges have been dedicated to assessing the practical performance of algorithms for major problems. It is one of the longest established and most professional international algorithm competitions.

The focus of the 12th Implementation Challenge is the study of Vehicle Routing problems. The subject has been studied for 60 years, and the results are widely used in transportation, supply chain optimization, logistics, advanced manufacturing, and smart city applications.

The Challenge attracted 59 teams from 19 countries and regions, including Jean-François Cordeau, Daniele Vigo, and Jin-Kao Hao. The participation of such renowned scholars and academicians made the competition especially fierce.

For four decades, Lv's laboratory has been studying algorithmic applications for complex problems and has won a myriad of international algorithm championships. His team, along with the Huawei Alkaid team, ranked first in the two categories of GECCO 2020 and received 1st place in the overall ranking. The team also won the first prize in the 2017 SAT international algorithm competition and the 2021 EDA international algorithm competition.

The team iterated over 20,000 lines of code 

Lv’s team addressed four out of the Challenge’s five variants, including Capacitated VRP (CVRP), VRP with Split Deliveries (VRPSD), VRP with Time Windows (VRPTW), and Inventory Routing Problem (IRP). They are one of the few teams that addressed multiple variants.

The team members spent practically every day in the laboratory for two months before the Challenge. "The code has been revised so many times from the first to the latest version that we submitted, and the final core code is over 20,000 lines." Li Yunhao, one of the team members, a second-year master's student, said. This is usual for the teams when preparing for competitions. Huang Shihao, a third-year master's student on the team, said that their daily routine is to modify the code during the day, test it at night, check the results the next morning, and then modify it again. "It is such a continuous optimization process, and the problems are very challenging. Take the inventory routing problem for example, not only do we need to design the route, plan the distribution volume for each customer, but also consider the customer's inventory management." He said.

On April 9, the event’s results were announced. The team won the championship in CVRP and VRPSD, and the second and third place in VRPTW and IRP respectively.

The heuristic optimization algorithm designed by the team has revolutionized many key technologies such as edge assembly intersection operator, local search guided by path weighting, approximate screening strategy for neighborhood evaluation, and multi-layer and multi-stage search framework.

Aside from the championship, there is another gratifying news. According to Professor Lv, their research results have been put into practice, for example, in the material transfer system in chip foundries.

Written by: Huang Bochuan, Gao Yifei

Edited by: Ye Jingyi，Jiang Jing