機(jī)器之心
機(jī)器之心發(fā)布
機(jī)器之心編輯部
疫情期間，紹興物流 ，道路受阻、貨車資源有限等問題影響著快遞網(wǎng)的正常運(yùn)行，但快遞網(wǎng)算法的優(yōu)化卻可以幫我們省出一些時(shí)間。在今年 AAAI 的接收論文中，來自菜鳥人工智能部大快遞算法團(tuán)隊(duì)的一篇論文設(shè)計(jì)實(shí)現(xiàn)了深度學(xué)習(xí)驅(qū)動(dòng)的 MIP 求解加速方法，在 8 類經(jīng)典運(yùn)籌問題上將 SCIP 可行解獲取帶來平均意義下 10 倍以上的計(jì)算加速，且有較好的泛化能力。

在本次疫情中，快遞物流在新冠抗疫物資運(yùn)輸中起了非常關(guān)鍵的作用。面對受到影響的運(yùn)輸網(wǎng)絡(luò)，如何規(guī)劃路由與車線，利用有限的貨車資源盡快將積壓的包裹送達(dá)目的地，這是物流領(lǐng)域典型的組合優(yōu)化問題，該問題可建模為混合整數(shù)規(guī)劃問題 (Mixed Integer Programing, MIP)，并利用求解器進(jìn)行求解。
然而，快遞網(wǎng)絡(luò)規(guī)劃問題通常規(guī)模很大，包含的決策變量和約束條件非常多，求解非常耗時(shí)，很難在短時(shí)間內(nèi)求解完并應(yīng)用到線上。而且，快遞網(wǎng)絡(luò)每天都在運(yùn)轉(zhuǎn)，而相似的組合優(yōu)化問題也需要反復(fù)求解。當(dāng)前學(xué)術(shù)圈與工業(yè)界尚無處理相似 MIP 問題求解的通用方法，每天計(jì)算時(shí)通常將其視為全新的求解任務(wù)，從而導(dǎo)致歷史求解的過程數(shù)據(jù)損失其價(jià)值。如果能從歷史求解過程中，采用機(jī)器學(xué)習(xí)的方法學(xué)習(xí)到相似 MIP 問題的結(jié)構(gòu)特點(diǎn)，則有望大幅提速求解效率。
基于這一觀察，菜鳥人工智能部大快遞算法團(tuán)隊(duì)基于其在運(yùn)籌優(yōu)化、機(jī)器學(xué)習(xí)以及物流行業(yè)的積累，設(shè)計(jì)實(shí)現(xiàn)了深度學(xué)習(xí)驅(qū)動(dòng)的 MIP 求解加速方法：MIP-OSP，最新研究成果論文《Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction》發(fā)表在人工智能頂級會(huì)議 AAAI-2020 上，并受邀做口頭報(bào)告。本文將對這一運(yùn)籌優(yōu)化與機(jī)器學(xué)習(xí)學(xué)科的交叉應(yīng)用論文進(jìn)行深入解讀，并介紹該方法在菜鳥快遞網(wǎng)絡(luò)路由優(yōu)化問題中的實(shí)際應(yīng)用。

論文地址：https://arxiv.org/abs/1906.09575
應(yīng)用場景
混合整數(shù)線性規(guī)劃 (MIP) 是求解組合優(yōu)化問題最為常見的建模與優(yōu)化手段，在菜鳥網(wǎng)絡(luò)的很多運(yùn)籌優(yōu)化相關(guān)應(yīng)用中 (例如快遞網(wǎng)絡(luò)、車輛排線、人員排班、庫存管理、服務(wù)器分配等) 都可以采用 MIP 方法進(jìn)行建模求解。MIP 模型中的整數(shù)變量為其賦予了描述現(xiàn)實(shí)世界中離散決策的能力。以 0-1 整數(shù)決策變量為例，我們可以用它來描述生產(chǎn)調(diào)度問題中某個(gè)工件是否在某個(gè)機(jī)器上加工的決策問題、車輛路徑規(guī)劃問題中某兩個(gè)門店是否進(jìn)行串線運(yùn)輸?shù)臎Q策問題等等。在大量實(shí)際應(yīng)用中（例如圖 1 所示），相似的 MIP 被會(huì)被反復(fù)求解，且求解時(shí)長隨著問題規(guī)模的增大呈指數(shù)增長。本文提出的 MIP-OSP 算法希望從這類相似 MIP 問題的歷史求解過程中「學(xué)習(xí)經(jīng)驗(yàn)」，不斷加速新問題的求解。

圖 1. 應(yīng)用場景示例。場景描述：在分撥中心到站點(diǎn)的傳站車輛調(diào)度問題中，智能調(diào)度引擎每天制定車輛的運(yùn)輸計(jì)劃，決策車貨匹配關(guān)系并優(yōu)化車輛路徑。此問題可以建模為 MIP 模型進(jìn)行求解，由于運(yùn)輸計(jì)劃基于每天不同的訂單進(jìn)行更新，系統(tǒng)中每天都要對相似的 MIP 模型進(jìn)行求解。
方法簡介
MIP 模型可以統(tǒng)一表述為標(biāo)準(zhǔn)形式：
， 其中
為包含整數(shù)的決策變量，A，b，c為模型的輸入?yún)?shù)。針對不同場景的實(shí)際優(yōu)化問題，MIP 模型的基本數(shù)學(xué)結(jié)構(gòu)保持不變，但模型參數(shù) A，b，c 以及決策變量定義域
會(huì)有不同的具體表征。如果能針對這類通用的數(shù)學(xué)模型挖掘出問題特征并與最優(yōu)解進(jìn)行關(guān)聯(lián)，將大幅提升該思路的通用化能力，有著巨大的應(yīng)用前景。研究者所設(shè)計(jì)的 MIP-OSP 方法基于 MIP 模型的抽象參數(shù) A，b，c 建立圖模型，進(jìn)而通過預(yù)測 MIP 問題的最優(yōu)解實(shí)現(xiàn)求解加速，其整體框架如圖 2 所示。

圖 2. MIP-OSP 方法流程
圖 2 中左半部分為最優(yōu)解預(yù)測模型的訓(xùn)練過程，右半部分為模型的應(yīng)用過程。仍以傳站車輛調(diào)度問題為例，假設(shè)調(diào)度引擎已經(jīng)完成了連續(xù) n-1 天的模型求解，并將計(jì)算過程與計(jì)算結(jié)果存儲(chǔ)到數(shù)據(jù)庫中。該方法首先基于這 n-1 天的 MIP 模型基本信息以及求解過程數(shù)據(jù)訓(xùn)練出最優(yōu)解預(yù)測的模型，并將其用于第 n 天 MIP 問題的最優(yōu)解預(yù)測。令
表示基于模型對第 n 天最優(yōu)解的預(yù)測，基于這一預(yù)測結(jié)果可以將 MIP 問題的搜索空間大幅減小，從而加速第 n 天 MIP 問題的計(jì)算。顯然，隨著系統(tǒng)運(yùn)行時(shí)間增加，模型訓(xùn)練的數(shù)據(jù)逐步累積，使得最優(yōu)解預(yù)測的準(zhǔn)確率越來越高，求解新的 MIP 問題時(shí)速度也越來越快。
整體算法框架
研究者提出了一類基于圖卷積神經(jīng)網(wǎng)絡(luò) (GCN) 的最優(yōu)解預(yù)測算法 (MIP-OSP)，通過收集 MIP 的結(jié)構(gòu)特征以及根節(jié)點(diǎn)線性松弛特征，預(yù)測 MIP 模型中 0-1 整數(shù)變量在最優(yōu)解中的取值。整體流程如下：
首先針對通用 MIP 模型設(shè)計(jì)了一類三部圖的表征方式；
而后基于該三部圖設(shè)計(jì) Attention GCN 預(yù)測模型進(jìn)行變量取值預(yù)測；
最后根據(jù)模型預(yù)測結(jié)果，生成 local branching 形式的約束加入到原模型中，加速 MIP 求解。
考慮如下通用的 MIP 模型：