廣州熱線

近日,在第12屆 DIMACS算法挑戰(zhàn)賽12th Implementation Challenge on Vehicle Routing Problems中,華為云瑤光調(diào)度算法團(tuán)隊聯(lián)合華中科技大學(xué)團(tuán)隊參賽,最終斬獲兩項冠軍、一項亞軍、兩項季軍,是所有參賽隊伍中唯一獲得多個冠軍的團(tuán)隊,也是獲得前三名最多的團(tuán)隊,同時,也是中國團(tuán)隊首次在DIMACS比賽中獲得冠軍。這是該團(tuán)隊在獲得GECCO2020 OCPamp;USCP比賽雙賽道冠軍,以及刷新50多項PDPTW榜單世界最好記錄之后,再次斬獲的國際重量級大賽冠軍。

DIMACS算法挑戰(zhàn)賽始于1990年,由美國離散數(shù)學(xué)和理論計算機(jī)科學(xué)中心Center for Discrete Mathematics and Theoretical Computer Science, DIMACS發(fā)起并主辦,致力于推動重大應(yīng)用問題的算法研究,是計算機(jī)領(lǐng)域歷史最悠久、最專業(yè)的國際算法競賽之一。歷屆賽題包括旅行商問題,圖分割問題,網(wǎng)絡(luò)流問題,最短路徑問題,半正定規(guī)劃等,都是計算復(fù)雜性理論和運籌優(yōu)化領(lǐng)域中最困難、最富挑戰(zhàn)的課題。鑒于比賽在業(yè)內(nèi)的權(quán)威性以及賽題的巨大研究和應(yīng)用價值,本次挑戰(zhàn)賽吸引了領(lǐng)域內(nèi)全球最頂尖的50多支研究團(tuán)隊參賽,來自包括,業(yè)內(nèi)全球眾多知名公司和高校,以及法國、加拿大等國家級研究機(jī)構(gòu),其中也不乏多位該領(lǐng)域的國際著名學(xué)者及院士組隊參賽,使得本次比賽競爭尤其激烈。

本屆DIMACS算法挑戰(zhàn)賽主題是廣義的VRP問題Vehicle Routing Problem。?VRP問題屬于典型的NP-難問題,已被學(xué)術(shù)界和工業(yè)界持續(xù)研究超過半個世紀(jì)。和歷屆賽題一樣,該問題是領(lǐng)域內(nèi)極富挑戰(zhàn)的課題,求解難度非常大,也是典型的同時在理論上和實踐中都有巨大研究價值的課題,至今也仍然是研究和應(yīng)用的熱點領(lǐng)域。

VRP問題核心是在圖網(wǎng)絡(luò)中尋找滿足一系列約束情況下最優(yōu)路徑,其中最優(yōu)化的目標(biāo)可以包括,最少時間、最小成本等,更一般化地,在有限的資源和特定的約束條件下,求解一個或者多個最優(yōu)目標(biāo)。VRP問題廣泛應(yīng)用于資源調(diào)度、物流配送、航路規(guī)劃等眾多領(lǐng)域。在云場景下,同樣面臨著多種此類復(fù)雜的約束優(yōu)化問題。一個典型的場景,比如,如何在滿足各種約束比如,容量、拓?fù)浣Y(jié)構(gòu)、功率的前提下,最優(yōu)化云資源的利用率和最大程度地保障租戶的服務(wù)質(zhì)量。這是關(guān)乎云平臺的運營能力和客戶服務(wù)質(zhì)量的關(guān)鍵問題,也是云平臺的核心競爭力之一。以公有云的規(guī)模,在保障用戶服務(wù)質(zhì)量的前提下,每提升1的資源利用率,可能意味著上千萬的成本節(jié)省。華為云一直在相關(guān)優(yōu)化算法研究領(lǐng)域重兵投入,同時也積累了深厚的經(jīng)驗,這也是團(tuán)隊參加本次比賽的底氣之一。

華為云瑤光調(diào)度算法團(tuán)隊由“天才少年”和“博士軍團(tuán)”領(lǐng)銜,并與華中科技大學(xué)呂志鵬教授團(tuán)隊就調(diào)度優(yōu)化領(lǐng)域展開了深入合作,致力于解決華為云調(diào)度場景下面臨的多種復(fù)雜的優(yōu)化問題?，幑庹{(diào)度算團(tuán)隊中的“天才少年”都是頂尖的算法高手,對算法的設(shè)計和實現(xiàn)有極其豐富的經(jīng)驗,此前在ACM競賽中獲獎無數(shù);呂志鵬教授團(tuán)隊也在優(yōu)化算法領(lǐng)域經(jīng)驗豐富,曾多次獲得優(yōu)化領(lǐng)域重量級大賽的冠軍。瑤光調(diào)度算法團(tuán)隊基于華為云瑤光智慧云腦構(gòu)建了“面向云場景的智能決策優(yōu)化求解引擎框架”,以及基于該框架的靈活可擴(kuò)展的算法策略庫,以適應(yīng)云上多變的場景和求解需求,尤其是大規(guī)模、復(fù)雜約束的優(yōu)化問題的求解。本次比賽,團(tuán)隊基于此求解引擎框架和算法策略庫,設(shè)計了針對該問題的全新鄰域搜索算子和擾動機(jī)制,并通過懶加載的緩存機(jī)制極大程度地提高了鄰域搜索的效率。從結(jié)果上看,團(tuán)隊獲得冠軍的算法在總分上平均領(lǐng)先第二名5以上,在部分算例上,結(jié)果甚至比其他最好結(jié)果好10以上,在這樣一個競技平臺上以及對于一個已經(jīng)被研究超過50年的問題而言,這是一個極為難得的結(jié)果。

未來,華為云將持續(xù)優(yōu)化瑤光智慧云腦的決策優(yōu)化求解能力,在全域調(diào)度、容量管理、SLA保障以及更多的場景下持續(xù)發(fā)揮價值,釋放更多技術(shù)紅利,為各行各業(yè)提供極致性能、極致穩(wěn)定、多樣性算力、云邊端協(xié)同的云基礎(chǔ)設(shè)施。同時,華為云將持續(xù)發(fā)揮全棧技術(shù)創(chuàng)新能力,繼續(xù)探索分布式云形態(tài)下全域調(diào)度、軟硬協(xié)同等技術(shù),為企業(yè)提供極優(yōu)極簡的云上體驗。