来源:华中科技大学
还记得他们吗？
计算机学院吕志鹏教授团队
4月9日
他们再次拿下
DIMACS算法挑战赛全球冠军
参赛选手线上交流
4月9日结束的第12届美国离散数学和理论计算机科学中心（Center for Discrete Mathematics and Theoretical Computer Science）DIMACS算法挑战赛中，吕志鹏团队与华为云瑶光调度算法团队组成的联合参赛团队，首次参赛即在四个赛道中斩获两项冠军、一项亚军以及两项季军，是所有参赛队伍中唯一获得多项冠军和前三名的队伍。
据悉，其他三个赛道获得冠军的团队分别来自美国、德国和挪威，获得前三名的国家还有法国、加拿大、巴西和丹麦。这是中国团队在DIMACS算法挑战赛中首次夺冠，同时中国也是此次竞赛中获得冠军和前三名最多的国家。
在顶级赛事和全球算法高手过招
团队讨论
DIMACS算法挑战赛于1990年发起，致力于推动重大应用问题的算法研究，是计算机领域历史最悠久、最专业的国际专业算法竞赛之一，至今已有32年的历史。大赛主办方为美国离散数学和理论计算机科学中心，是国际学术界的权威机构，本届大赛由其联合亚马逊公司共同举办。
“这是一个学界和业界深度融合的赛事，是最权威的算法比赛之一。历届赛题既包含困扰业界和学术界多年的‘硬骨头’难题，也有最前沿的应用难题，非常具有挑战性。”吕志鹏介绍。
此次DIMACS算法挑战赛的主题为车辆路由问题（Vehicle Routing Problem，VRP）。该问题广泛应用于物流运输、供应链优化、后勤保障、先进制造、智慧城市等诸多工业应用领域，在提出至今的60余年时间里，被国际学术界和工业界持续深入研究。
如此具有挑战性的赛事自然汇聚了来自各国的高手。本次竞赛共吸引了来自19个国家和地区的59支顶尖算法研究团队参赛，包括卡耐基梅隆大学、康奈尔大学、多伦多大学、都柏林大学、蒙特利尔大学、谷歌、沃尔玛、大和运输等著名高校与公司，以及欧洲最大的独立研究机构SINTEF、加拿大交通运输研究中心CIRRELT、法国国家信息与自动化研究所INRIA等国际著名研究机构。
此外，多位该领域的国际著名学者及院士，如Jean-François Cordeau、Daniele Vigo、Jin-Kao Hao、Matteo Fischetti、Keld Helsgaun等人的参赛，也使得本次竞赛的竞争尤为激烈。“参赛选手大多是该领域的高手，有些选手就是某些经典算法的提出者，或者是在该领域研究了30年以上的学者。我们会有一些压力，但是在这个领域我们也积累了很多学术研究和工业落地的经验，大家都比较有信心。”吕志鹏说道。
吕志鹏所在实验室自成立至今的40余年来，一直聚焦于复杂问题的求解算法与工业应用研究，曾多次获得国际算法竞赛全球冠军。例如，在GECCO 2020国际会议中，吕志鹏教授团队与华为云瑶光调度算法团队合作获得最优相机布局算法竞赛两项分赛道的冠军以及总冠军。吕志鹏教授团队2021年获得国际计算机辅助设计会议（ICCAD 2021）EDA国际算法竞赛的冠军，以及2017年获得SAT国际算法竞赛的冠军。
算法不断迭代代码达2万余行
此次竞赛共包含五个赛道，本团队参加了四个赛道的比赛，分别是带容量约束的车辆路由问题赛道（CVRP）、可分载的车辆路由问题赛道（SDVRP）、带时间窗的车辆路由问题赛道（VRPTW）、库存路由问题（IRP）赛道。他们是为数不多的参加多个赛道的队伍。“有很多队伍只参加一个赛道的比赛，就像体育比赛一样。我们同时参加多个赛道的比赛，是因为我们在不同赛道对应的学术研究和工业应用方面有比较多的前期积累。”吕志鹏说。
团队成员丁俊文老师介绍，车辆路由问题可以描述为如何为多个车辆合理规划访问客户的顺序，要求各车辆从仓库出发并最终返回仓库，在满足容量约束的条件下使得总的行驶时间或路程最短，“当考虑更多实际应用中的需求后可以延伸出各种变种的车辆路由问题，如考虑客户的配送时间窗、客户的产品销量和库存容量、订单可拆分等实际应用中的因素，各个赛道的问题便由此而来。”丁俊文说，这些问题看似简单，但是找到最优方案却十分困难，已经困扰业界和学界多年。
2021年12月，赛事启动。参赛前两个月团队成员几乎每天都待在实验室，“从第一版算法到我们提交的最后一版算法已经修改了不知多少次，最后核心代码写了有2万行左右。”团队成员硕士二年级学生李云皓说。这是团队备赛的常态，该队硕士三年级学生黄施豪说，备赛时他们经常是白天修改代码，晚上进行测试，第二天早上看结果，接着再改。“就是这样一个不断优化的过程，赛题都非常具有挑战性。比如库存路由问题，我们既要规划路径，又要决定各客户的配送量，还要考虑客户的库存管理问题”黄施豪说。
如图是一个满足时间窗约束的配送方案
4月9日，赛事成绩公布，团队首战告捷，并取得大满贯，带容量约束的车辆路由问题赛道（CVRP）和可分载的车辆路由问题赛道（SDVRP）获得冠军；带时间窗的车辆路由问题赛道（VRPTW）获得亚军和季军；库存路由问题（IRP）赛道获得季军。
团队所设计的启发式优化算法，在边组装交叉算子、路径加权引导的局部搜索、邻域评估近似筛选策略、多层多阶段搜索框架等多项关键技术上实现了突破。
年轻团队继续出发
团队成员李云皓和黄施豪做研究
除了斩获全球大奖，还有一个喜人的消息，吕志鹏透露，团队的相关研究已落地应用。例如，在先进制造行业，芯片代工厂中的物料传送系统的核心问题就是本次竞赛的车辆路由问题，需要考虑时间窗、订单优先级、库存容量、轨道独占性等一系列复杂的实际因素。
吕志鹏团队除了吕志鹏和丁俊文老师，学生们都是90后，年轻人给团队带来了诸多青春活力。李云皓说，同学们都十分拼搏，“大家都比较‘卷’，不只是我们参赛的几个人，整个实验室的同学们都很拼，大家经常参加国际国内各类比赛，赛场上比本领。”
吕志鹏介绍，实验室的研究氛围比较自由，前期会给学生们安排一些基础的算法训练，之后就直接带他们做一些前沿的算法研究或者参加一些国际算法比赛。“以赛代炼，他们可以将平时训炼的技能灵活运用，能力自然就能得到不断的提升。”吕志鹏说。4月11日，黄施豪又投入到了日常的科研工作中，实验室的师生都在忙于自己的工作，他们朝着科研方向继续前行探索，期待在用科研服务工业应用道路上再获佳绩。
喜看后浪起
助力复兴潮
华中大人
冲呀！
