SINTEF PDPTW榜單紀(jì)錄舉例
�。ㄆ渲蠬W指代華為云擎天架構(gòu)調(diào)度算法團(tuán)隊(duì)）
挑戰(zhàn)：如何離理論最優(yōu)解再近一步
科技工業(yè)研究院（SINTEF）是歐洲最大的獨(dú)立研究機(jī)構(gòu)之一，其在1999年發(fā)起并管理的PDPTW Benchmark，被認(rèn)為是VRP（Vehicle Routing Problem）問(wèn)題領(lǐng)域最權(quán)威的算法榜單之一，吸引了來(lái)自全球頂尖學(xué)者，及Emapa、DELMIA Quintiq、Terasoft等知名廠商參與。
VRP問(wèn)題作為經(jīng)典的NP-hard問(wèn)題，已被學(xué)術(shù)界研究超過(guò)五十年，算法核心是在圖網(wǎng)絡(luò)中尋找滿足一系列約束情況下的最優(yōu)路徑，工業(yè)上被廣泛應(yīng)用于分布式云資源調(diào)度、航線規(guī)劃、物流配送等領(lǐng)域。
而更復(fù)雜的約束條件、榜單上幾近理論最優(yōu)值的結(jié)果，使得刷新最好記錄的難度大幅增加。
VRP問(wèn)題示意圖
突破：云上實(shí)踐與算法理論的絕佳融合
云上的約束優(yōu)化問(wèn)題往往規(guī)模更大、約束更多，作為擎天架構(gòu)的管控面，華為云瑤光智慧云腦通過(guò)元啟發(fā)式及機(jī)器學(xué)習(xí)等算法，構(gòu)建了“面向云場(chǎng)景的智能決策優(yōu)化求解引擎框架”，以解決全域資源調(diào)度、智能資源碎片整理、邊緣站點(diǎn)選址等復(fù)雜多目標(biāo)決策優(yōu)化問(wèn)題。其中的關(guān)鍵算法也運(yùn)用到了本次打榜當(dāng)中。
來(lái)自華為云擎天架構(gòu)調(diào)度算法團(tuán)隊(duì)的天才少年、博士軍團(tuán)，聯(lián)合華中科技大學(xué)呂志鵬教授團(tuán)隊(duì)，通過(guò)整合自適應(yīng)大規(guī)模鄰域搜索、禁忌搜索、引導(dǎo)式局部搜索等傳統(tǒng)啟發(fā)式優(yōu)化算法，輔以創(chuàng)新的種群管理方法和基于統(tǒng)計(jì)模型的禁忌表策略，實(shí)現(xiàn)僅靠PC級(jí)別的計(jì)算資源，刷新SINTEF PDPTW榜單中的多項(xiàng)已知最好解紀(jì)錄，其中一部分實(shí)例的優(yōu)化幅度甚至超過(guò)了5%，實(shí)現(xiàn)云上實(shí)踐賦能算法理論的進(jìn)一步突破。
運(yùn)用：極致彈性與智能感知的幕后黑科技
華為云擎天架構(gòu)調(diào)度算法團(tuán)隊(duì)通過(guò)持續(xù)技術(shù)創(chuàng)新，除了在決策優(yōu)化領(lǐng)域，還在實(shí)時(shí)分布式資源調(diào)度，多NUMA容量實(shí)時(shí)測(cè)算、容量預(yù)測(cè)與擴(kuò)容管理、亞健康或與故障預(yù)測(cè)等領(lǐng)域取得了算法突破，最大限度滿足用戶(hù)對(duì)資源穩(wěn)定與彈性的需求。
此外，華為云依托瑤光智慧云腦資源畫(huà)像與預(yù)測(cè)能力，實(shí)現(xiàn)算力的智能推薦，讓?xiě)?yīng)用負(fù)載運(yùn)行在最合適的算力之上。更可智能識(shí)別優(yōu)質(zhì)資源，針對(duì)任務(wù)型、可容錯(cuò)的算力密集型場(chǎng)景，提供超高性?xún)r(jià)比的競(jìng)享實(shí)例，在保證使用時(shí)長(zhǎng)的情況下還可節(jié)省85%的使用成本。
華為云基于擎天架構(gòu)釋放更多技術(shù)紅利，為各行各業(yè)提供極致性能、極致穩(wěn)定、多樣性算力、云邊端協(xié)同的云基礎(chǔ)設(shè)施。
未來(lái)，華為云將持續(xù)發(fā)揮全棧技術(shù)創(chuàng)新能力，繼續(xù)探索分布式云形態(tài)下全域調(diào)度、軟硬協(xié)同等技術(shù)，為企業(yè)提供極優(yōu)極簡(jiǎn)的云上體驗(yàn)。
[1]:數(shù)據(jù)取自科技工業(yè)研究院（SINTEF）PDPTW榜單，統(tǒng)計(jì)截止至2020年12月5日。
https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/
