1、什么是運籌優(yōu)化

運籌學（Operations Research）作為數學、計算機科學、管理學的交叉學科，最早起源于一戰(zhàn)中的防空作戰(zhàn)系統(tǒng)，由錢學森先生引入中國，最開始的用途是優(yōu)化航空／軍工等領域。如今廣泛應用在企業(yè)的生產、運營、物流環(huán)節(jié)，通過算法指導和輔助人類管理者進行決策。在本博客中，我們將運籌優(yōu)化概括為，通過求解一個最優(yōu)化問題，在滿足約束的條件下，最小化完成某件事所花費的成本。最優(yōu)化問題常描述為一個數學規(guī)劃問題，根據決策變量是連續(xù)或離散，可以分為兩類：連續(xù)最優(yōu)化問題與組合優(yōu)化。

連續(xù)最優(yōu)化問題的標準形式是：

這里x是決策變量，f(x)是目標函數，g(x)是不等式約束條件，h(x)是等式約束條件，且有m=p=0。若有m=p=0，則問題轉化為無約束優(yōu)化問題。函數f,g,h可以是線性或非線性，經典的求解算法有：牛頓法、梯度下降法、共軛法等等。

而當決策變量取值是（或部分是）整數，則是離散優(yōu)化問題，常稱為組合優(yōu)化（Combinatorial Optimization），是運籌優(yōu)化的一個重要分支，其標準形式是：

而當決策變量取值是（或部分是）整數，則是離散優(yōu)化問題，常稱為組合優(yōu)化（Combinatorial Optimization），是運籌優(yōu)化的一個重要分支，其標準形式是：

一般描述為混合整數規(guī)劃（mixed integer programming，MIP），所有的參數(cj,dk,aij,gik,bi)取值是任意實數，只考慮線性表達式。$$m$$是約束條件的數量，$$n$$是連續(xù)變量數，$$p$$是整數變量數。若n=0則上述MIP轉化為純整數規(guī)劃，若$$p=0$$則上述MIP轉化為線性規(guī)劃；特別的，若yk∈{0，1}，全稱量詞k，則轉化為二元（binary）規(guī)劃問題。組合優(yōu)化問題（如資源調度、生產排產、路徑優(yōu)化、運營排班等）是企業(yè)經營決策所面臨的最常見的優(yōu)化問題類型，覆蓋商業(yè)決策優(yōu)化的大部分流程，因此也是運籌學的主要研究對象之一。從航班和工廠的調度、金融資產配置、倉庫貨物存儲到運輸路線的設計，很多都可以建模成組合優(yōu)化問題。本文討論的對象是組合優(yōu)化問題。

2、常見的組合優(yōu)化問題及其求解方法

組合優(yōu)化問題的離散特性為問題求解引入了特別的挑戰(zhàn)，因為求解空間是隨問題規(guī)模呈指數級增長的，其中有不少是NP-complete的。也就是說目前還找不到多項式時間復雜度的算法。NP-complete問題有很多，如經典的satisfiability（SAT）問題，minimum vertex cover（MVC）問題，max cut（MC）問題等等。它們之間可以在多項式復雜度內相互歸約，也就是說其中一個被證明有多項式復雜度解法的話，所有的都有多項式復雜度解法。

2.1 常見的組合優(yōu)化問題

NP-complete問題中最經典的問題之一要屬旅行商問題（Traveling Salesman Problem，TSP），它是車輛路徑問題（Vehicle Routing Problem, VRP）的一個特例。其迷人之處可能就在于看似描述很簡單，日常生活中可能還常用到，但想要找到通用的高效解法卻發(fā)現非常難。其可行解是所有點的全排列，隨著點數的增加，會產生組合爆炸，暴力求解的復雜度O(n!)。問題描述為由n個城市組成的完全圖，兩個城市間有整數代價；有一個旅行商要走遍所有城市，每個城市只走一次且最后回到原點（即Hamilton回路），求所有城市的訪問路徑的順序，且該路徑的代價和最小。

很多時候對于中大規(guī)模TSP，尚無找到最優(yōu)解的有效算法，其能找到的最好解與真正最優(yōu)解的距離稱為optimality gap。這也是評估很多TSP算法的重要指標，用來說明它的解接近最優(yōu)的程度。自被提出后的幾十年里，該問題在組合優(yōu)化領域被反復地研究，從而衍生出基于精確算法、近似算法、啟發(fā)式算法幾大類成熟的方法。TSP問題在交通運輸、電路板線路設計、物流配送等場景有著廣泛的應用。

組合優(yōu)化中的另一經典問題是車輛路徑規(guī)劃問題（Vehicle Routing Problem, VRP），描述為一定數量的客戶，各自有不同數量的貨物需求，從倉庫向客戶提供貨物，由一個車隊負責分送。需要組織適當的分配方案和行車路線，目標是使得客戶的需求得到滿足，并在一定的約束（時間窗、裝載率）下，達到諸如路程最短、成本最小、耗費時間最少等目標。一個簡單的有著16個客戶（編號為1-16）、1個倉庫（編號為0）的示意圖如下所示，共需要4輛車完成配送（以不同顏色標識），每輛車服務4個客戶，所有車均從倉庫出發(fā)，服務完所有的客戶之后，再返回倉庫。

根據不同的問題特征，可以附加各種約束，得到不同的VRP問題變形，如下圖所示。TSP是VRP的特例，即不考慮車輛的約束，用一輛車服務完所有的客戶。而若車輛有容量（裝載量上限），就構成了CVRP，再考慮時間窗（Time Window）就是VRPTW；若為同時取送貨（Pickup and Delivery），則構成了VRPPD。一般的城市配送問題都可以描述為CVRP，一般的預約安裝類問題都可以抽象為VRPTW，而外賣配送、打車等O2O范圍類的問題都可以用VRPPD來描述。因此，VRP在物流配送中有著廣泛的應用場景，在過去50年來是研究熱點。傳統(tǒng)的優(yōu)化方法（啟發(fā)式、精確算法等）專注于研究各種各樣的問題變形，甚至拓展到了uncertainty、robust、stochastic、two-echelon等場景，而深度強化學習類的方法則主要專注于求解TSP、CVRP等簡單情形，并常用優(yōu)化方法得到的解作為比較對象。下文將詳細介紹。

2.2 組合優(yōu)化問題的常見求解方法

2.2.1 近似算法

這類算法找的不是最優(yōu)解，而是次優(yōu)（sub-optimal）解，或者說近優(yōu)（near-optimal）解，其優(yōu)點是會有某種程度上的最優(yōu)性保證。具體地，它能保證最壞情況下給出的解不次于最優(yōu)解的一定倍數，這個倍數稱為近似比（approximation ratio）。對于NP完全問題，雖然求最優(yōu)解沒有多項式復雜度的算法，但求近優(yōu)解卻存在不少多項式復雜度的算法。這類方法包含如貪心算法、原始-對偶法、動態(tài)規(guī)劃法等。

對于一個最小化的組合優(yōu)化問題，假設全局最優(yōu)解的目標函數為100，那么近似比為2的近似算法收斂求得的解一定在[100，200]，最壞情況是200。對于TSP問題，在滿足三角不等式（triangle inequality）時，Christofides algorithm 通過計算最小生成樹和最小權完全匹配來求解，其時間復雜度為O(n3)，近似比為1.5。

2.2.2 啟發(fā)式算法

啟發(fā)式算法是指通過對經驗的歸納推理以及實驗分析來解決問題的方法，即借助于某種直觀判斷或試探的方法。其本質上也是找一個近似解，但與上面的近似算法相比，差別在于啟發(fā)式算法沒有最優(yōu)性的理論保證，即不能保證解的質量。但一般來說，它比上面的近似算法能找到更好的解。可以分為以下兩類。

一類是可以根據問題相關的heuristic構造解，如最近鄰，或者最小生成樹；另一種是local search，即根據heuristic來對中間解進行局部修改，以迭代的方式在解空間中進行搜索。這類算法通常是以問題為導向的即Problem Specific，沒有一個通用的框架，每個不同的問題通常設計一個不同的啟發(fā)式算法，更多是快速尋求局部最優(yōu)。

還有一類是應用元啟發(fā)式搜索框架，耳熟能詳的有禁忌搜索算法、模擬退火算法、遺傳算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法、人工魚群算法、人工蜂群算法等；它們以生物的行為方式或者物質的運動形態(tài)為背景，對社會性昆蟲的群體行為的研究基礎上，群居性生物通過協(xié)作表現出的宏觀智能行為特征，又稱群智能優(yōu)化算法。元啟發(fā)式算法可以針對普遍的問題，即Problem Independent，可以作為一個black box操作，適用性廣，但還是要根據問題特點來調節(jié)算法的各種參數；有隨機優(yōu)化的機制，適合于尋求全局最優(yōu)。

對于TSP問題，這類方法中的SOTA算法為Lin-Kernighan-Helsgaun (LKH)，可解決的規(guī)?？梢赃_到上萬級別。對于VRP問題，根據求解過程，可分為 construction heuristic 和 improvement heuristic 兩類。construction heuristic 用于構造一個初始可行解，常用的方法包括 Solomon I1 以及 saving heuristic （節(jié)約算法），后者的示意圖如下所示?；舅枷胧菍⒏骺蛻酎c均與depot相連，構成若干條只含有一個配送點的線路；然后通過貪心規(guī)則，計算將點 i和點 j 連接在一條線路上距離的節(jié)約值；重復這個步驟，對線路進行合并。

improvement heuristic用于對初始解進行改進提升，常用的方法如下圖所示。基本思想是通過交換點、邊的位置或順序，常作為元啟發(fā)式算法中構造鄰域解的中間算子，再嵌套迭代不斷優(yōu)化求解效果。

2.2.3 精確算法

精確算法是指能夠求出問題最優(yōu)解的算法。對于難解的組合優(yōu)化問題，當問題的規(guī)模較小時，精確算法能夠在可接受的時間內找到最優(yōu)解；當問題的規(guī)模較大時，精確算法一方面可以提供問題的可行解，另一方面可以為啟發(fā)式方法提供初始解，以便能搜索到更好的解。精確算法主要包括分支定界法、割平面法、列生成算法、動態(tài)規(guī)劃法等。

精確算法，顧名思義，就是搜索整個解空間，能夠保證找到最優(yōu)解。當然由于搜索空間太大，實際當中會通過剪枝等方法來減小搜索空間。常見的做法是建模成整數規(guī)劃（Integer programming，IP）或混合整數規(guī)劃問題（Mixed-integer programming，MIP），然后通過對偶理論，尋找問題的下界和上界（對于最小化問題，就是可行解），然后不斷逼近。

經典的VRPTW的數學規(guī)劃模型如下所示：

該模型是典型的MIP，決策變量x{ijk}是二元變量，取值為 0 或 1；s{ik}是連續(xù)變量，代表車輛k到達客戶 i的時間。原問題的下界，可以很容易地通過求解其線性松弛來得到，但是往往非常弱，因此常通過添加割平面來提升下界的值；給定的source和sink，會存在很多條滿足資源約束的最短路徑，因此常通過列生成法，先通過少數可行路徑構造一個主問題，再求解一個定價子問題，逐步加入能使目標得到改進的新變量（列）；而為了保證得到可行解，還需要對分數變量進行分支。

具體的，分支定界（Branch and Bound）本質上就是將搜索空間構造成樹的形式，通過不斷地選取和分裂節(jié)點，配合剪枝來有效地找尋最優(yōu)整數解。至于如何挑選節(jié)點和如何對其賦值對于找到解的速度有很大影響，是門很大的學問，因此衍生出不少啟發(fā)式（Heuristic）策略。割平面法（Cutting Plane）從松弛問題的一個非整數的最優(yōu)解出發(fā)，序貫地添加一個新的線性不等式（其對應線性方程所代表的超平面即稱為割平面），求解新的松弛問題的算法。列生成算法（Column Generation）運用分解的思想和單純形法的特點，不是直接同時處理所有的候選方案，而是基于當前生成列的子集，通過限制主問題進行優(yōu)化求解；其余的候選方案（變量）可以改善限制主問題當前最優(yōu)解時，才會進入該子集。

在實際MIP的求解中，這些方法往往是進行組合，構成 branch and cut、branch and price、branch and cut and price （BCP）方法等，而BCP方法就是求解TSP和VRP的最有效的精確算法。

3、數學規(guī)劃求解器

求解器是用來實現在可行域中找到最優(yōu)解的工具，其本質上是一個專業(yè)的數學/計算軟件，用于實現復雜的數學算法。目前市面上主要分商用求解器、開源求解器兩類。商用求解器主要有IBM CPLEX、GUROBI、FICO XPRESS等；開源求解器主要有SCIP、COIN-OR、Google OR-Tools等。商用求解器的效率一般是開源求解器的5-7倍。以VRPTW benchmark C101為例，上述模型通過Gurobi在3s內即可得到最優(yōu)解。正因為有了優(yōu)化求解器的存在，只需將以上整數規(guī)劃模型的系數矩陣輸入到優(yōu)化求解器中，它就能夠快速求出最優(yōu)解或可行解（除了分支定界法還集成了各種啟發(fā)式和割平面算法）。

如前所述，混合整數規(guī)劃在工業(yè)、經濟、國防、醫(yī)療等各行各業(yè)應用十分廣泛。目前，僅有少數幾個發(fā)達國家擁有自己的整數規(guī)劃求解器，如美國有GUROBI、CPLEX、SAS、MATLAB、CBC、SYMPHONY，德國有SCIP，俄羅斯有MIPCL和GLPK，英國有XPRESS（后被美國FICO公司收購），芬蘭有LPSOLVE。商業(yè)求解器三大廠 CPLEX、GUROBI 與 XPRESS 憑借豐富的商業(yè)開發(fā)經驗，以及較好的性能，在國際市場上占了超過90%的份額。目前號稱SOTA的數學規(guī)劃求解器是Gurobi Optimization，由 Zonghao Gu、Ed Rothberg和Robert Bixby 于 2008 年創(chuàng)立， 自 2009 年首次發(fā)布以來，Gurobi 一直在求解器性能（通過實現平均每年 60% 的速度提高）和適用性（通過將其應用擴展到 40 多個不同行業(yè)的 2,400 多家公司）方面不斷設定新標準。

求解器在工業(yè)發(fā)展中的意義非凡。例如，我國戰(zhàn)略布局上面臨的難題 EDA （電子設計自動化）需要用到SAT求解器進行快速驗證，而制造、物流與供應鏈優(yōu)化等則需要用到整數規(guī)劃求解器（尤其是線性規(guī)劃求解器）。在幾年前，凡是需要用到求解器的企業(yè)，都是直接購買美國的 CPLEX、GUROBI 與 XPRESS。好消息是，近年來，國內一些有著領先科技能力的新銳公司和互聯網大廠，也開始研發(fā)自己的優(yōu)化求解器，布局相關研究。首款“國產”求解器于2018年發(fā)布，雖然處在起步階段，但也實現了從0到1的突破。

3.1 國內數學規(guī)劃求解器

3.1.1 中科院CMIP混合整數規(guī)劃求解器

中科院數學與系統(tǒng)科學院戴彧虹研究員帶領CMIP團隊從2015年開始，歷經30個月，自主研發(fā)了我國第一個具有國際水平的整數規(guī)劃求解器CMIP，并于2018年3月確定版本為CMIP 1.0版本。CMIP代碼總量已經超過五萬行，涵蓋國際現有求解器預處理、啟發(fā)式、割平面、分支、節(jié)點選擇、域傳播等各種功能模塊，并已經較好地具備了求解大規(guī)模整數規(guī)劃的能力。

3.1.2 LEAVES優(yōu)化求解器和COPT

LEAVES優(yōu)化求解器是上海財經大學與杉數科技聯合建設的一個運籌學與人工智能基礎算法平臺，也是第一個成規(guī)模的華人運籌學優(yōu)化算法求解器。LEAVES求解器可以解決線性規(guī)劃、半正定規(guī)劃、幾何規(guī)劃、線性約束凸規(guī)劃等常見的大規(guī)模優(yōu)化問題，現已在社區(qū)開源。

杉數科技開發(fā)的商業(yè)求解器COPT，同時具備大規(guī)?；旌险麛狄?guī)劃、線性規(guī)劃（單純形法和內點法）、二階錐規(guī)劃、半定規(guī)劃以及凸二次規(guī)劃和凸二次約束規(guī)劃問題求解能力的綜合性能數學規(guī)劃求解器。其1.0版本于2019年5月發(fā)布，現迭代更新到6.5版。據2022年6月19日Mittlemann測試榜單（http://plato.asu.edu/bench.html，亞利桑那州立大學Hans Mittelmann教授負責維護的數學規(guī)劃求解器測試平臺，是目前世界上公認的最知名的、具有權威性和代表性的獨立第三方測試平臺）數據，COPT在線性規(guī)劃的單純形法、內點法、凸二次規(guī)劃、半定規(guī)劃均排名第一。

3.1.3 達摩院Mind-Opt

Mind-Opt出自阿里達摩院決策智能實驗室，是求解優(yōu)化問題的專業(yè)計算軟件?？蓮V泛應用于云計算、零售、金融、制造、交通、能源等領域，號稱每年在彈性計算資源調度優(yōu)化場景里為阿里云節(jié)省數億成本。過去兩年，杉數、阿里與Gurobi在線性規(guī)劃權威榜單 Mittlemann 測試上競爭激烈。據2023年3月24日數據，MindOpt和COPT在Mittelmann測試集的LPopt榜單（http://plato.asu.edu/ftp/lpopt.html）上均居榜首。

3.1.4 華為天籌

華為云天籌（OptVerse）AI求解器將運籌學和AI相結合，突破業(yè)界運籌優(yōu)化極限，支持求解混合整數線性規(guī)劃問題和線性規(guī)劃問題，尋求最優(yōu)解。其特點是AI賦能求解，基于歷史數據和問題特征自適應選擇最優(yōu)參數，支持基于拓撲感知的分布式并行加速，充分利用華為云分布式并行能力。據2023年3月24日數據，天籌AI求解器在Mittelmann測試集的大規(guī)模網絡線性規(guī)劃榜單（http://plato.asu.edu/ftp/network.html）中位列TOP1

4、深度強化學習和組合的交叉研究

如今深度學習在自然語言處理、視覺、語音、推薦等領域的應用已經非常廣泛；在深度學習任務中，我們會為模型定義一個損失函數，稱作優(yōu)化問題的目標函數，損失函數表征的是預測值和實際值之間的差距，再通過一定的優(yōu)化算法（如SGD）減小這個差距。多數情況下，損失函數十分復雜，很難得到確定、唯一的解析解，而是一般通過優(yōu)化迭代的方法去逼近一個數值解。機器學習算法和經典的運籌優(yōu)化算法的對比如下：

結合兩者的優(yōu)點，這兩大類算法的交叉融合也逐漸成為一個研究熱點，相結合的方式主要有以下兩種：（此處借鑒大佬Yoshua Bengio論文中的圖示，分別見Fig 7 和Fig 9）

• 以end-to-end的方式用機器學習直接根據給定問題輸出解（輔以相應的后處理）
• 將機器學習與傳統(tǒng)的算法相結合，比如使用機器學習幫助選取參數或者啟發(fā)式策略

下文將以路徑規(guī)劃問題（TSP、VRP）為例，從這兩方面來介紹近年來的一些交叉研究。以基于機器學習的組合優(yōu)化為主線，前后引入了RNN、注意力機制、Transformer、GNN等，從而發(fā)展成今天的眾多分支。這個方向正隨著機器學習的蓬勃發(fā)展而快速演進，隨著更多的想法被吸收和融入到組合優(yōu)化中，會成為傳統(tǒng)算法的有力補充。

4.1 End-to-End 方法

4.1.1 早期研究

用機器學習來求解組合優(yōu)化問題，在早些年就已有嘗試和萌芽。1985年，Hopfield和Tank的論文《"Neural" computation of decisions in optimization problems》嘗試用Hopfield-network來求解小型的TSP實例，其缺點是對超參和參數初始化敏感；1995年，Zhang和Dietterich在論文《A Reinforcement Learning Approach to Job-Shop Scheduling》中將強化學習應用到NP-hard的車間調度問題；1999年，論文《Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research》綜述了早期神經網絡用于組合優(yōu)化問題的研究。鑒于當時數據、算力等的局限，這些嘗試大多都只限于研究探索，沒有展現出比傳統(tǒng)算法更優(yōu)異的效果。

4.1.2 Pointer Network-開端

2014年提出的sequence-to-sequence（Seq2Seq）模型、注意力機制（Attention mechanism）以及后來的Transformer，已被廣泛用于翻譯、聊天機器人、文本生成等序列數據的任務處理上，取得了不錯的效果。但是，傳統(tǒng)的 Seq2Seq 模型無法解決輸出序列的詞匯表會隨著輸入序列長度的改變而改變的問題，因為其decoder 輸出的目標數量是固定的，例如翻譯時輸出的向量長度往往等于字典的大小，且忽略了輸出只能從輸入中選擇這個先驗信息。這導致 Seq2Seq 不能用于一些組合優(yōu)化的問題，例如凸包問題、TSP 等。這些問題的特征是輸出往往是輸入集合的子集（輸出嚴重依賴于輸入），而這個長度是變化的。如TSP的輸出是輸入的全排列，對于每個問題實例而言，其輸入的數量，即城市的數量是不一樣的。

2015年Google和UC Berkeley的《Pointer Networks》將深度神經網絡應用到了組合優(yōu)化領域，Ptr-Net 可以解決輸出字典大小可變的問題并修改了 Attention 的方法，根據 Attention 的值從 Encoder 的輸入中選擇一個作為 Decoder 的輸出。

Ptr-Net 的點睛之筆是改動了注意力機制。傳統(tǒng)的帶有注意力機制的seq2seq模型中，先使用encoder部分對輸入序列進行編碼，然后對編碼后的向量做attention，最后使用decoder部分對attention后的向量進行解碼從而得到預測結果。但在Ptr-Net中，得到預測結果的方式便是輸出一個概率分布，邏輯上就像一個指針指向輸入中的某個節(jié)點，也即所謂的指針。即傳統(tǒng)帶有注意力機制的seq2seq模型輸出的是針對輸出詞匯表的一個概率分布，而Ptr-Net 輸出的則是針對輸入文本序列的概率分布。

4.1.2 引入強化學習

前面提到的主要是監(jiān)督學習的方法，這成為了一個比較大的局限，因為對于監(jiān)督學習來說算法質量很大程度上取決于訓練集的質量。這意味著要訓練這個網絡，需要先求解出訓練集中問題的高質量解。在計算機視覺中的物體檢測、圖片分類，肉眼即可打標。但如果訓練集中每個樣本是TSP這樣的NP完全問題，那么求其最優(yōu)解或高質量的可行解，復雜度太高。為了克服監(jiān)督學習的局限，引入了強化學習。因為強化學習不需要顯式的帶標簽的數據集，而是通過與環(huán)境不斷交互中得到的反饋來學習。

2018年 Lehigh University 的論文《Reinforcement Learning for Solving the Vehicle Routing Problem》將 Ptr-Net拓展到求解VRP。相較于TSP，VRP的難點在于，問題輸入是動態(tài)變化的。如當一個客戶訪問后，其需求可能就會被清零（或減少，對于split delivery）。而Ptr-Net結構存在的問題在于，當輸入序列中的動態(tài)元素發(fā)生變化時，要對整個encoder進行更新才能進行下一個節(jié)點的預測，增加了計算量。

這篇文章指出，輸入集合中元素之間的順序，如單詞之間的相對關系，在文本翻譯等場景很重要；而在組合優(yōu)化問題如TSP、VRP中，輸入是客戶的位置和他們的需求量，其相互順序并沒有意義。因此去掉了encoder部分，只保留了decoder部分。具體的，在Embedding layer，直接把靜態(tài)元素（坐標）映射為一個$$D$$維的向量空間，不同時刻的輸入共享同一個輸入結構；在 Attention layer，RNN的輸出和動態(tài)元素（需求量）輸入給attention機制，然后形成下一個可行決策點的概率分布。

模型訓練采用了經典的policy gradient方法。另外，為了加速訓練和產生可行解，它用了masking scheme會將不可行解的log prob設為負無窮。有兩種后處理方式：Greedy與Beam search。對于新的問題實例，只要它是來自于同一問題實例分布，則無需重新訓練。在中等規(guī)模VRP（50，100個客戶）中，該方法在解的質量上相較經典heuristic方法（Clarke-Wright savings heuristic，Sweep heuristic）以及Google OR Tools有一定優(yōu)勢。在結合beam search后，對比OR Tools有60%以上的勝率。

4.1.3 Transformer結構

2017年Google的論文《Attention Is All You Need》引起了業(yè)界的巨大反響，這篇文章提出了Transformer模型，使用了（多頭）注意力機制；該模型準確率更高，而且易并行，訓練也更快。其網絡結構也被借鑒到求解路徑優(yōu)化問題上。如2019年阿姆斯特丹大學的論文《Attention: Learn to solve routing problems!》，與原Transformer模型相比，encoder部分中沒有使用位置編碼，這樣便使node embedding與輸入順序無關；之后節(jié)點的embedding通過N個堆疊的注意力層來更新，每層包括多頭注意力層(Multi-Head Attention, MHA)、全連接前饋層(Feed Forward, FF)、跳躍鏈接（ship connection）和批量歸一化層（Batch Normalization，BN）。多頭注意力機制允許節(jié)點從不同的鄰居接收不同類型的消息，前饋子層使用512維的隱藏層和ReLU激活函數。

decoder采用了經典的自回歸模式，按順序執(zhí)行，在時間步t∈{1，...,n}時，根據來自encoder的embedding和decoder在時間步t之前的輸出Πt'，t'輸出節(jié)點Πt。在解碼過程中，用一個特殊的context node（c）來表征解碼上下文。這個context node加上其它的embedding信息通過MHA層（與encoder中的MHA相比，這里為了高效沒有skip-connection, BN和FF子層）得到輸出向量。最后，decoder結構有一個single attention head（即M=1的MHA），通過softmax輸出即為當前步的輸出。

訓練采用基于policy-based的強化學習方法，baseline function通過基于當前最好的策略模型進行deterministic greedy rollout得到。實驗部分主要考慮了多種路徑問題，如TSP和VRP的多種變體，在部分case中，與構造類heuristic（Nearest、Random and Farthest Insertion和Nearest Neighbor），OR Tools等方法相比能得到更優(yōu)的解。其實驗數據是在單位正方形內隨機均勻采樣得到。

4.1.4 Graph Embedding與GNN

對于組合優(yōu)化問題，一個困境是對于同樣類型，但數據不同的問題，我們常常需要一遍遍地重新去求解。那么給定一個圖優(yōu)化問題和一個問題實例的分布，有沒有辦法可以讓heuristic泛化到那些不曾見過的問題實例？引入機器學習的期望之一就是提高其泛化能力，即訓練完的模型可以有效地應用于未曾見過的問題實例。為了提高泛化能力，對于圖這種非歐幾里得數據來說，通過圖嵌入（Graph embedding）來抽取數據中的有效特征，通過低維的向量來表征圖的節(jié)點及拓撲結構等信息，再作為后面機器學習算法的輸入。而圖神經網絡（Graph neural network，GNN）是將深度神經網絡模型應用于解決圖相關任務的方法，其中重要的一種是結合了卷積的圖卷積網絡（Graph Convolutional Network，GCN）。

2020年菜鳥網絡在KDD上的一篇論文《Efficiently solving the practical vehicle routing problem: A novel joint learning approach》提出了基于點序列預測和邊分類的圖卷積網絡GCN-NPEC。模型遵循的是經典的encoder-decoder框架。在encoder部分，采用GCN網絡生成圖中點和邊的representation。采用的GCN編碼器同時考慮點和邊兩種輸入，將實際路網的交通可達性作為edge embedding。

在decoder階段，共有兩個decoder：點序列預測解碼器和邊分類解碼器。Π其中，點序列預測解碼器以點特征作為輸入，生成VRP的解序列，邊分類模型以邊特征作為輸入，輸出一個代表邊是否存在的概率矩陣。邊分類解碼器需要標簽來指導分類訓練，但由于精確算法很難在合理的時間內生成VRP的精確解，尤其當問題規(guī)模很大（如大于100）時。作為一種折中，論文中將點序列預測解碼器得到的Π作為邊概率矩陣的ground-truth（label）。在訓練過程中，采用結合強化學習（點序列預測解碼器）和監(jiān)督學習（邊分類解碼器）的聯合學習策略。

在實驗分析階段，論文選取了真實的配送數據和實際路網矩陣，對比實驗證明了邊緣特征的重要性，聯合學習策略可以加速訓練的融合并最終提高解的質量。

4.1.5 RLHF

在VRP中，優(yōu)化目標常是最小化總運輸成本、行駛時間/距離、所需車輛數、時間窗違反量等等。這些目標有清晰、可量化的計算公式，而在工業(yè)實際中，常常需要車輛的行駛軌跡（路線）看起來 visual attractiveness，如路線之間沒有覆蓋或者交集（not overlapping、not crossing）。如下圖，就分別示例了考慮 visual attractiveness（左圖）、將總成本（右圖）作為最小化目標的兩個解決方案。顯然，當考慮 visual attractiveness時，線路之間的交叉較少，看起來更加優(yōu)美，更加易于算法方案的落地。在這種情況下，每個司機都集中在一個小區(qū)域內進行服務，意味著更高的操作效率，因為司機會更加熟悉片區(qū)內的交通、停車點、商戶營業(yè)時間等。

但是，路線看起來優(yōu)美、沒有交叉，只是主觀、定性的描述，很難定義明確的計算公式。誠然，可以通過計算幾何的方法，先計算每個route的最小外接圓、外接凸多邊形，然后最小化這些多邊形之間的重疊區(qū)域或交叉點，但和visual attractiveness也不直接等價。這樣的方案在落地時，仍然會受到調度員（生產實際中，由調度員手動調車和排路線）的挑戰(zhàn)。另一種方案是，通過統(tǒng)計學的方法，挖掘調度員的經驗，可在一定程度上，學習到“司機對片區(qū)熟悉”這一信息。

幸運的是，TMS中沉淀的調度員派車方案、車輛行駛軌跡，可以用來指導算法的尋優(yōu)。這一點和LLM的進步軌跡很類似。LLM可以生成多樣性的文本內容，然而對生成結果的評估是主觀和依賴上下文的。通過預測下一個單詞的方式和簡單的損失函數（如交叉熵）來建模，沒有顯示地引入人的偏好和主觀意見。而RLHF通過使用強化學習的方式來直接優(yōu)化帶有人類反饋的語言模型，用生成文本的人工反饋作為衡量標準，再進一步用該反饋作為損失來優(yōu)化模型，使得ChatGPT類的模型大放異彩。RLHF 使得在一般文本數據語料庫上訓練的語言模型能和復雜的人類價值觀對齊。

再回到路徑規(guī)劃的落地應用上，一開始使用監(jiān)督學習進行訓練，基于TMS中積累的調度員派車方案（visual beautiful solutions），通過調度員（人類訓練者）提供正確的標記示例，模型學習根據輸入預測正確的動作或輸出；在RM（Reword Model）訓練獎勵值方面，需要調度員對模型生成的回答進行排名，比較多個輸出并構建更好的規(guī)范數據集，從而創(chuàng)建強化學習的獎勵信號。

總之，利用RLHF將人類專家的知識和經驗融入到智能體的學習過程中，可以提高學習的效率和性能，通過人類經驗，加速visual beautiful solutions 這類難以量化方案的落地，是一個值得探索的方向。

4.2 搜索與后處理

如前所述，基于深度學習的方法已經在組合優(yōu)化問題中取得還不錯的成績。另一方面，我們也可以看到，這些方法大多數還需要結合一些后處理操作，可分為如下幾類。

在不少工作中，對于機器學習模型表示概率的輸出，需要經過一些后處理算法得到最終的解。包括 1）Greedy：每次選取輸出概率最高的節(jié)點。2）Beam search：本質上是寬度受限的廣度優(yōu)先搜索。3）Sampling：采樣一定數量的解，取最優(yōu)。

機器學習部分已經得到了一個完整的解，再結合一些局部搜索方法（如2-OPT、3-OPT等操作）對這個解進行修改來試圖進行提升。2019年蒙特利爾綜合理工學院等機構的論文《How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem》通過實驗說明了搜索過程對于機器學習方法的影響巨大，一些基于機器學習的方法得到的解在經過如2-OPT，3-OPT和LK等方法refine后其optimality gap能夠顯著降低。

融合樹搜索或蒙特卡洛樹搜索（MCTS）的思想，如基于GCN輸出節(jié)點屬于最優(yōu)解的概率，用來在樹搜索中以迭代的方式構造解。這個概率分布可能是多峰的，這樣就可以生成很多候選解，有利于后面樹搜索中更好的探索。在訓練和推理中都加入MCTS，在訓練中可以促進探索，增強泛化能力；在推理時可以改進效果，增強穩(wěn)定性。

4.3 與傳統(tǒng)方法的結合

將機器學習引入用于解決組合優(yōu)化問題，上面提到的方法主要是end-to-end的方式，而另一種重要的方式是與傳統(tǒng)的OR方法相結合。

如前所述，解決組合優(yōu)化的傳統(tǒng)方法中比較經典的就是建模成混合整數規(guī)劃問題，在精確求解器如Gurobi、SCIP等中，規(guī)劃算法的實現涉及到大量超參數，如開源MIP求解器中性能最為強勁的SCIP求解器提供了2617個超參數，其中超過2000個超參數與求解過程中的決策強相關。通常，這些超參數由求解器開發(fā)者依據人工經驗整定，面向通用問題提供一套適用性最為廣泛的參數作為默認值。但面向細分行業(yè)特定場景，首先，默認參數難以發(fā)揮求解器的最佳性能。第二，求解器使用門檻相對較高，要求用戶對組合優(yōu)化、數學規(guī)劃算法和場景問題本身有較為深入的理解。第三，即使是行業(yè)領域的專家，在求解器的海量參數組合中為特定場景問題選擇最佳參數的過程中，也存在著人工調參耗時耗力的挑戰(zhàn)。

這里需要提及的是NeurlPS 的ML4CO（The Machine Learning for Combinatorial Optimization）基于機器學習的組合優(yōu)化比賽。2021年的比賽由加拿大蒙特利爾理工大學和蒙特利爾大學機器學習研究所 (Mila) 主辦。Mila是全球領先的深度學習研究中心，由Yoshua Bengio教授創(chuàng)立。本次挑戰(zhàn)賽的重點是通過機器學習方法替代現有組合優(yōu)化求解器（開源求解器 SCIP 和它的Python封裝 Ecole）中的啟發(fā)式組件，針對混合整數線性規(guī)劃問題（MILP）進行優(yōu)化，探索機器學習在求解器參數整定、參數推薦上的應用，來達到提升現有的組合優(yōu)化求解器求解性能的目的。主辦方提供了三個 MILP 數據集，它們來自完全不同的現實問題，如 Dual Task 賽道研究如何更快收緊 MILP 問題的約束邊界，征集SCIP求解器的最佳參數推薦方案，從而幫助提升通用求解器在細分行業(yè)特定場景問題上的性能。

具體的，求解器內置有分支定界、割平面、列生成等算法的求解框架，涉及一些決策過程，如分支變量的選擇、樹搜索時的節(jié)點選取策略和節(jié)點裁剪策略、有效不等式的選擇、非負列進基的選擇等等，求解器內部常是一些啟發(fā)式選擇策略。引入機器學習，就是從大量的數據中自主學習啟發(fā)式規(guī)則，對決策進行引導。如分支定界方法會將解空間遞歸地切分，形成搜索樹，期間會計算bound并裁剪掉肯定不包含最優(yōu)值的子樹。He et al. (2014 ) 以監(jiān)督學習的方式得到自適應的節(jié)點搜索策略，Liberto et al. (2016) 提出DASH方法，針對搜索過程中的子問題動態(tài)切換并選取最合適的啟發(fā)算法，Gasse et al. (2019) 結合了模仿學習和GCN來學習變量選擇策略等等。此外，Tang et al. (2020)使用強化學習用于自適應地選擇割平面，也證明了對于分支切割算法的價值；Ding et al. (2020) 使用三部圖來預測初始二元變量的取值，用于構造 local branching cut。這些都是采用深度學習算法來輔助決策傳統(tǒng)OR方法中啟發(fā)式選擇策略的有力嘗試。

5、結論與建議

應用深度強化學習來求解傳統(tǒng)的組合優(yōu)化問題，隨著機器學習的蓬勃發(fā)展而快速演進，學術上掀起了一波熱潮，但在業(yè)界的推廣使用，還有一段距離。

學術研究上的問題都是有著明確清晰定義的標準問題，而在真實的業(yè)務場景中，問題定義常是模糊的，需要通過trial and error來確定約束條件和目標函數。再以路徑優(yōu)化為例，業(yè)務關心的目標可能是距離最短、每輛車的服務區(qū)域盡量集中，考慮的約束可能有車輛的載重、容積上限、每趟服務的點數上限等等，特別是在POC的場景。機器學習類算法在問題定義改變（如新增/刪減某個約束條件），需要重新訓練模型，存在很大的試錯成本；而數學規(guī)劃類的方法，能真正做到開箱即用。

另一方面，學術研究上的實驗數據（包括倉庫位置、客戶節(jié)點位置、需求量等）基本都是在一個區(qū)間內隨機均勻采樣得到的，所以機器學習類的算法依據同樣的生成規(guī)則，可以得到大量的訓練數據。而在真實場景上，客戶分布、下單頻率，往往沒有明顯的數學統(tǒng)計特征。這樣就造成了機器學習類的算法在按照某種分布生成的數據集上表現較好，但是在實際算例上表現欠佳。

如某供應鏈企業(yè)中AI部門所承接的算法問題，各業(yè)務線、各行業(yè)線，都有大量的決策優(yōu)化、深度學習的場景。在干支線路由、傳站、城配、末端攬派，都存在上文所述的路徑規(guī)劃問題。在決策優(yōu)化的場景，目前普遍使用的還是傳統(tǒng)的優(yōu)化方法，機器學習類方法僅作為上游的銷量預測、體積預測環(huán)節(jié)，二者互為補充。目前尚在探索使用機器學習類算法端到端支撐某個優(yōu)化決策類場景。但是在機器視覺（CV）和自然語言處理（NLP）的場景，則大不相同。在CV和NLP領域，深度學習已較為成熟，出現了許多開源的代碼和框架，在業(yè)界應用也較為廣泛。

相信隨著研究的深入，隨著大模型在各行各業(yè)的落地實踐，深度強化學習和組合優(yōu)化方法的交叉融合，一定會帶來更為卓越的成果和應用；再借助分布式算力、海量數據的優(yōu)勢，在業(yè)界真正落地，產生價值。

參考文獻

Di Liberto, Giovanni, et al. "Dash: Dynamic approach for switching heuristics." European Journal of Operational Research 248.3 (2016): 943-953.

He, He, Hal Daume III, and Jason M. Eisner. "Learning to search in branch and bound algorithms." Advances in neural information processing systems 27 (2014).

Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." Advances in Neural Information Processing Systems 32 (2019).

Tang, Yunhao, Shipra Agrawal, and Yuri Faenza. "Reinforcement learning for integer programming: Learning to cut." International conference on machine learning. PMLR, 2020.

Ding, Jian-Ya, et al. "Accelerating primal solution findings for mixed integer programs based on solution prediction." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 02. 2020.

Hopfield, John J., and David W. Tank. "“Neural” computation of decisions in optimization problems." Biological cybernetics 52.3 (1985): 141-152.

Zhang, Wei, and Thomas G. Dietterich. "A reinforcement learning approach to job-shop scheduling." IJCAI. Vol. 95. 1995.

Smith, Kate A. "Neural networks for combinatorial optimization: a review of more than a decade of research." Informs journal on Computing 11.1 (1999): 15-34.

Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. "Pointer networks." Advances in neural information processing systems 28 (2015).

Nazari, Mohammadreza, et al. "Reinforcement learning for solving the vehicle routing problem." Advances in neural information processing systems 31 (2018).

Kool, Wouter, Herke Van Hoof, and Max Welling. "Attention, learn to solve routing problems!." arXiv preprint arXiv:1803.08475 (2018).

Duan, Lu, et al. "Efficiently solving the practical vehicle routing problem: A novel joint learning approach." Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.

Bengio, Y. ,  A. Lodi , and  A. Prouvost . "Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon." (2018).

Rossit, Diego Gabriel, Daniele Vigo, Fernando Tohmé, and Mariano Frutos. "Visual attractiveness in routing problems: A review." Computers & Operations Research 103 (2019): 13-34.

https://www.ecole.ai/2021/ml4co-competition/