◎ Science and Technology Daily reporter Wu Chunxin correspondent Zhao Na Wang Xiaoxiao
On April 11, the reporter learned from Huazhong University of Science and Technology that in the 12th AMERICAN Discrete Mathematical and Theoretical Computer Science Center DIMCS Algorithm Challenge that just ended on the 9th, the joint team of Professor Lu Zhipeng from Huazhong University of Science and Technology, who just won the EDA Algorithm (ICCAD 2021) International Competition Championship last year, and huawei Cloud Yaoguang scheduling algorithm team, won two championships, one runner-up and two third places in four tracks for the first time.
This is the first time that the Chinese team has won the title in the DIMACS Algorithm Challenge, and China is also the country that has won the most championships and the top three in this competition.
The top tournament in the algorithmic world
Launched in 1990, the DIMACS Algorithm Challenge is committed to promoting the study of algorithms for major application problems, and is one of the oldest and most professional international professional algorithm competitions in the field of computing, with a history of 32 years.
The competition is hosted by the Center for Discrete Mathematics and Theoretical Computer Science in the United States, which is co-organized with Amazon.
"This is a deeply integrated competition between academia and industry, and one of the most authoritative algorithm competitions. The previous competition topics include both the 'hard bones' problems that have plagued the industry and academia for many years, as well as the most cutting-edge application problems, which are very challenging. Lu Zhipeng introduced.
The theme of the DIMACS Algorithm Challenge is the Vehicle Routing Problem (VRP). This problem is widely used in logistics and transportation, supply chain optimization, logistics support, advanced manufacturing, smart city and many other industrial applications, and has been continuously studied in depth by the international academic and industrial circles in the more than 60 years since it was proposed.
It is reported that the competition attracted a total of 59 top algorithm research teams from 19 countries and regions.
The algorithm continuously iterates over the code to more than 20,000 lines
The competition consisted of five tracks, with the Chinese team participating in four track races, namely the Vehicle Routing Problem Track (CVRP) with capacity constraints, the Vehicle Routing Problem Track (SDVRP) with load-bearing, the Vehicle Routing Problem Track with Time Window (VRPTW), and the Inventory Routing Problem (IRP) track.
"There are a lot of teams that only compete on one track, just like sports. We participate in multiple track races at the same time, because we have a lot of early accumulation in academic research and industrial applications corresponding to different tracks. Lu Zhipeng said.
Team member Ding Junwen introduced that the vehicle routing problem can be described as how to reasonably plan the order of visiting customers for multiple vehicles, requiring each vehicle to start from the warehouse and eventually return to the warehouse, so that the total driving time or distance is the shortest under the condition of meeting the capacity constraints. These problems seem simple, but finding the best solution is very difficult, which has plagued the industry and academia for many years.
In December 2021, the event was launched. For the first two months of the competition, the team members stayed in the lab almost every day. "From the first version of the algorithm to the last version of the algorithm we submitted, it has been modified an unknown number of times, and the final core code has written about 20,000 lines." Team member Li Yunhao, a second-year master's student, said.
This is the norm for team preparation, the team's master's third-year student Huang Shihao introduced, when preparing for the game, they often modify the code during the day, test at night, see the results the next morning, and then change again.
On April 9, the results of the race were announced, and the team's record was outstanding: vehicle routing problem track with capacity constraint (CVRP) and loadable vehicle routing problem track (SDVRP) won the championship; vehicle routing problem track with time window (VRPTW) won the second and third place; and inventory routing problem (IRP) track won the third place.
The algorithm system has been applied
In addition to winning the global awards, there is also good news. Lu Zhipeng said that the vehicle routing problem involved in this competition is actually the core problem of the material delivery system in the chip foundry, and the relevant research done by the team in the competition has been applied.
The team members are very young, Professor Lui Zhipeng's team in addition to Lui Zhipeng and Ding Junwen, the students are "post-90s", young people to the team to bring a lot of youth vitality. Li Yunhao said that the students are very hard, "not only a few of us participating in the competition, the entire laboratory students are fighting, everyone often participates in various international and domestic competitions, and the competition is better than skill." ”
Lu Zhipeng said that the laboratory research atmosphere is relatively free, and some basic algorithm training will be arranged for students in the early stage, and then they will directly take them to do some cutting-edge algorithm research or participate in some international algorithm competitions.
"By practicing instead of racing, you can flexibly apply the skills you usually train, and your ability can naturally be continuously improved." Lu Zhipeng said. At present, Huang Shihao is engaged in daily scientific research work, and the teachers and students of the laboratory continue to explore in the direction of scientific research, looking forward to achieving further good results on the road of industrial application of scientific research services.
Source: Science and Technology Daily The pictures in this article are provided by Huazhong University of Science and Technology
Editor: Wang Yu
Review: Julie
Final Judgement: Wang Yu