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

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

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

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

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