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

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

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

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

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