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

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

連續(xù)最優(yōu)化問題的標(biāo)準(zhǔn)形式是：

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 近似算法

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

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

2.2.2 啟發(fā)式算法

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

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

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

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

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

2.2.3 精確算法

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

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

經(jīng)典的VRPTW的數(shù)學(xué)規(guī)劃模型如下所示：

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

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

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

3、數(shù)學(xué)規(guī)劃求解器

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

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

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

3.1 國內(nèi)數(shù)學(xué)規(guī)劃求解器

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

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

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

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

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

3.1.3 達(dá)摩院Mind-Opt

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

3.1.4 華為天籌

華為云天籌（OptVerse）AI求解器將運(yùn)籌學(xué)和AI相結(jié)合，突破業(yè)界運(yùn)籌優(yōu)化極限，支持求解混合整數(shù)線性規(guī)劃問題和線性規(guī)劃問題，尋求最優(yōu)解。其特點(diǎn)是AI賦能求解，基于歷史數(shù)據(jù)和問題特征自適應(yīng)選擇最優(yōu)參數(shù)，支持基于拓?fù)涓兄姆植际讲⑿屑铀?，充分利用華為云分布式并行能力。據(jù)2023年3月24日數(shù)據(jù)，天籌AI求解器在Mittelmann測試集的大規(guī)模網(wǎng)絡(luò)線性規(guī)劃榜單（http://plato.asu.edu/ftp/network.html）中位列TOP1

4、深度強(qiáng)化學(xué)習(xí)和組合的交叉研究

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

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

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

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

4.1 End-to-End 方法

4.1.1 早期研究

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

4.1.2 Pointer Network-開端

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

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

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

4.1.2 引入強(qiáng)化學(xué)習(xí)

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

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

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

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

4.1.3 Transformer結(jié)構(gòu)

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

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

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

4.1.4 Graph Embedding與GNN

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

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

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

在實(shí)驗(yàn)分析階段，論文選取了真實(shí)的配送數(shù)據(jù)和實(shí)際路網(wǎng)矩陣，對比實(shí)驗(yàn)證明了邊緣特征的重要性，聯(lián)合學(xué)習(xí)策略可以加速訓(xùn)練的融合并最終提高解的質(zhì)量。

4.1.5 RLHF

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

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

幸運(yùn)的是，TMS中沉淀的調(diào)度員派車方案、車輛行駛軌跡，可以用來指導(dǎo)算法的尋優(yōu)。這一點(diǎn)和LLM的進(jìn)步軌跡很類似。LLM可以生成多樣性的文本內(nèi)容，然而對生成結(jié)果的評估是主觀和依賴上下文的。通過預(yù)測下一個(gè)單詞的方式和簡單的損失函數(shù)（如交叉熵）來建模，沒有顯示地引入人的偏好和主觀意見。而RLHF通過使用強(qiáng)化學(xué)習(xí)的方式來直接優(yōu)化帶有人類反饋的語言模型，用生成文本的人工反饋?zhàn)鳛楹饬繕?biāo)準(zhǔn)，再進(jìn)一步用該反饋?zhàn)鳛閾p失來優(yōu)化模型，使得ChatGPT類的模型大放異彩。RLHF 使得在一般文本數(shù)據(jù)語料庫上訓(xùn)練的語言模型能和復(fù)雜的人類價(jià)值觀對齊。

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

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

4.2 搜索與后處理

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

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

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

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

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

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

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

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

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

5、結(jié)論與建議

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

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

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

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

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

參考文獻(xiàn)

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/