|
在近日结束的第12届美国DIMACS算法挑战赛中，由华中科技大学教授吕志鹏团队与华为云瑶光调度算法团队组成的联合参赛团队，在4个赛道中斩获两项冠军、一项亚军及两项季军。这是中国团队在DIMACS算法挑战赛中首次夺冠，同时中国也是此次竞赛中获得冠军和前三名最多的国家。
DIMACS算法挑战赛于1990年发起，是计算机领域历史最悠久、最专业的国际专业算法竞赛之一。大赛主办方为美国离散数学和理论计算机科学中心。
本届竞赛的主题为车辆路由问题，共吸引了来自19个国家和地区的59支顶尖算法研究团队参赛。此次竞赛共包含5个赛道，华中科大团队参加了带容量约束的车辆路由问题赛道、可分载的车辆路由问题赛道、带时间窗的车辆路由问题赛道、库存路由问题赛道等赛道。
团队成员、华中科大讲师丁俊文介绍，车辆路由问题可以描述为如何为多个车辆合理规划访问客户的顺序，要求各车辆从仓库出发并最终返回仓库，在满足容量约束的条件下使得总行驶时间或路程最短。
“当考虑更多实际应用中的需求后，可以延伸出各种变种的车辆路由问题，如考虑客户的配送时间窗、客户的产品销量和库存容量、订单可拆分等实际应用中的因素，各个赛道的问题便由此而来。”丁俊文说，这些问题看似简单，但是找到最优方案却十分困难。
在赛事启动的前两个月，团队成员几乎每天都在实验室写代码。“从第一版算法到提交的最后一版已经修改了不知多少次，最后核心代码写了有2万行左右。”团队成员硕士生李云皓说，团队设计的启发式优化算法，在边组装交叉算子、路径加权引导的局部搜索、邻域评估近似筛选策略、多层多阶段搜索框架等多项关键技术上实现了突破。
|