基于參數分析的物流網絡優化問題研究

（武漢理工大學 物流工程學院，湖北 武漢 430063）

1 前言

對于求解復雜問題的優化算法，目前已經出現了大量的研究。精確算法在解決小規模問題方面表現出了較強的優越性，但是隨著問題的復雜化以及工業應用程度的加深，在大規模算例中精確式算法求解時間較長，效率緩慢，已經無法滿足人們的需求。因此有研究者開始針對不同的問題開發了大量的啟發式算法，盡管啟發式算法不能像精確式算法一樣保證解的最優性，但是在求解大規模算例以及組合優化問題中，啟發式算法具有高效性。

啟發式算法是一種基于直觀或經驗構造的算法，在給定的計算時間內能夠給出待解決組合優化問題的較優解，但是不一定能保證所得解的可行性和最優性，甚至在多數情況下，無法闡述所得解同最優解之間的近似程度。元啟發式算法的優化機理不過分依賴待解問題的結構信息，可以應用于不同類別的組合優化問題中，不論是啟發式還是元啟發式算法，在應用于求解實際問題的過程中，都需要進行合理的參數設置才能有效的解決問題。優良的參數設置將會給最終的求解質量以及算法的性能帶來巨大的提升。實踐表明，開發（元）啟發式算法應用于解決問題的過程中僅有10%的時間是用于算法的設計編寫，而90%的時間用于算法內部參數的調整[1]。因此選擇一種合適的方法進行參數分析就顯得尤為重要。

針對參數分析問題，Birattari等給出了比較正式的定義[2]。近年來也出現了一大批關于算法參數分析的研究，主要的幾種參數分析的方法如下：第一種是借助于人力，采用“試錯法”或設計不同的仿真實驗，對不同的參數設置進行嘗試性實驗，這一過程中會浪費大量的人力和時間，同時所能分析的參數的數量和類型較少；第二種是通過設計不同的算法框架，對需要分析的啟發式算法的參數進行分析，這一過程需要研究者有較強的算法設計能力，適用度不高，操作難度較大；第三種是借助已有的參數分析工具，ParamILS（Iterated Local search in Parameter Configuration Space）[3],SMAC（Sequential Model-based Algorithm Configuration）[4]以及 irace（iterated racing）[2]等。早期以“試錯法”為主的參數分析方法逐漸被實驗設計方法所取代，實驗設計的方法主要是通過運用統計學的知識進行參數分析，陳一招[5]等、劉偉[6]等分別通過統計學的實驗方法和仿真實驗的方法最終確定了蟻群算法中關鍵參數的取值范圍，Grefenstette[7]等首次將遺傳算法應用于分析遺傳算法中的參數，進而有研究者在算法分析參數的基礎上開發出了更多的參數分析工具。

煤炭物流是我國物流網絡中的重要一環，而從實際的港口煤炭物流網絡中抽象出來的帶邊中斷動態網絡最大流問題[9]是一個綜合了最大流問題和調度問題的組合優化問題，該問題是給定一個弧容量已知的網絡，每條邊都分配到一組待執行的中斷任務；每個中斷任務有一個持續時間及任務的開始執行時間窗口；研究如何調度邊上的中斷任務使得在規劃時間跨度內通過網絡的流量最大化。Boland等證明該問題在單一路徑問題上的強NP難（Strong Non-Deterministic Polynomial-time Hardness）特性，對該問題的求解目前已經出現了多種方法，其中精確式算法有benders分解[10-11]，（元）啟發式的算法有貪婪算法[9]、貪婪隨機自適應搜索算法[9]、混合禁忌搜索算法[12]等。在使用精確式算法求解該問題的過程中，其求解結果能夠保證解的最優性，但應用于求解大規模算例時算法耗時過長，不便于快速求解。而對于（元）啟發式算法，它可以在規定的時間內找到問題的較優解，應用于求解實際的應用問題時更加高效。但兩種方法都存在一個問題，精確式算法從問題建模到最后求解對求解器的依賴程度較高，而求解器在求解過程中需要設置大量的參數來保證解的精確性，雖然目前比較先進的求解器都有參數內部自調整過程，但是求解器自身的參數設置問題依舊是一個難題。而（元）啟發式算法在求解過程中需要設置大量的參數來確保最后所得解的質量，但由于其參數的設定沒有統一的標準，現有的研究對于參數的設定問題沒有定論，因此存在著參數設置的不確定性問題。而本文主要對在求解帶邊中斷動態網絡最大流問題的過程中，所運用的（元）啟發式算法進行研究，利用相關的參數分析工具對算法進行分析，最終實現對算法性能的提升。本文將采用irace來分析在求解帶邊中斷動態網絡最大流問題中使用的貪婪隨機自適應搜索算法中關鍵參數的問題。這也是首次將irace應用于分析貪婪隨機自適應搜索算法在帶邊中斷動態網絡最大流問題中的應用問題。

2 帶邊中斷動態網絡最大流問題及模型

帶邊中斷動態網絡最大流問題（Maximum Total Flow with Flexible Arc Outages，MaxTFFAO）由澳大利亞學者Boland等提出[9]，下文均用MaxTFFAO表示。該問題是針對某大型煤炭碼頭供應鏈上下游之間如何安排設備檢修問題，通過抽象數學建模，最終得到的一個綜合了運籌學中基礎的最大流問題和調度規劃問題中的數學難題。同時他們已經通過復雜的三階段理論證明了帶邊中斷動態網絡最大流問題是一個NP難問題。

為合理描述MaxTFFAO問題的數學形式，保持全文數學符號的連貫性，特給出規定。集合符號[m,n]={m,m+1,...,n},[m]={1,2,...,m},m,n∈Z+。本文將時間刻度離散化，時間t表示為第t個單位時段，設置網絡總時間跨度為T，則[T]={1,2,...,T}。G=(V,A,s,s′,U)表示一個網絡，節點集合[V]，路徑弧集合[A] ，源點s，終點s′,容量集合為 [U]，μa∈[U](μa∈N,a∈[A])表示弧a的容量。

每一個需要停機維護設備定義為一個維護作業，用符號j表示，[J]表示網絡中所有維護作業的集合,[Ja]表示網絡中所有與弧a相關的維護作業的集合。每一項維護作業j都存在一個特定的維護時間窗口 (rj,dj)，其中rj∈[T]表示維護作業j的最早開始處理時間點，dj∈[T]表示維護作業j的終止處理時間點；同時，每一項維護作業j都有一個連續的維護過程，時間長度定義為pj∈[T]。維護作業開始時間為sj∈[rj,dj-pj+1]，其中[rj,dj-pj+1]為維護作業的開始時間窗口，當 j∈[Ja]時，t∈[sj,sj+pj-1]時弧a中斷，其弧上的流量為0。

為更好地使用數學術語描述煤炭供應鏈設備維護問題，本文提出如下三個假設：

假設1 任意一條路徑弧a上存在數量不等的多個維護作業；

假設2 路徑弧上的不同維護作業的維護時間窗口不重疊，即對于同一條弧a上的任意兩個維護作業j和j′，都有；

假設3 維護作業一旦開始，在其處理時間段內不可提前中斷。

為了準確地表達該問題的數學模型，將在模型中使用到的變量設置如下：a表示網絡中的任意一條弧;t表示時間跨度T內任意一個時間點；表示流進節點υ的路徑弧的集合；表示流出節點υ的路徑弧的集合。變量φat∈R+表示在時間點t內流經弧a的流量；xat=1表示弧a在時間點t內閉合，否則就斷開；yjt=1表示維護作業j開始于時間t，否則就為0。因此該問題的數學模型表示如下：

會計制度是行政事業單位進行會計管理和核算的重要依據， 2019年1月1日起行政事業單位將全面實行政府會計制度，該如何做好新舊會計制度的銜接呢？本文就新舊會計制度銜接的難點進行分析，并以此提出新舊會計制度銜接的具體措施，希望能夠對行政事業單位的會計工作有所幫助。

目標函數式（1）是將跨度時間T內每一時間點所對應的網絡最大流的加和最大化。式（2）表示流量平衡約束；式（3）限制了每一個時間點內網絡中各弧上流量不超過弧的容量；式（4）要求每一項維護作業j在其可選起始處理時間窗口[rj,dj-pj+1]內恰好被執行一次；式（5）表示網絡弧a在時間t內的開閉情況由維護作業j所選的時間點t′決定，即當時，網絡弧a在時間點t內為中斷狀態。

3 求解MaxTFFAO問題的算法

3.1 貪婪隨機自適應搜索算法

在給定的初始的維護作業計劃中，首先將總的時間跨度設定為T=1 000，同時按照劃分時間片段，在劃分出的M個時間片段中，觀察發現每個時間片段內的網絡結構是不變的，因此在求解T時間跨度內的最大流問題時，可以先計算時間片段內單位時間的最大流再乘上對應的時間片段的長度，就可以求出該時間片段所對應的最大流。將M個時間片段的最大流值求和就是初始的目標值函數，整個計算過程可以用Gurobi優化求解器來實現。但是隨著問題規模的不斷擴大，Gurobi優化求解器在給定的時間不能獲得最優解。

因此Boland等提出采用貪婪隨機自適應搜索算法（Greedy Randomized Adaptive Search Procedure-GRASP）對該問題進行求解，下文均使用GRASP表示該算法。在時間跨度1 000內，將每個單位時間作為一個靜態的最大流問題進行處理，這樣便劃分出1 000個靜態網絡來求解一個可行解的目標值，但是其計算的時間成本仍會很大。在本問題中可以依據給定的初始可行解設計相對應的時間片段，在同一時間片段內的每一時刻，可行解的網絡結構是相同的，因此求解某個時間片段的最大流時，只需要求一個靜態網絡的最大流問題的解值，再乘上這個時間片段的長度就可以得到初始可行解的值。之后通過任意改變一個維護作業的開始處理時間點，形成一系列新的可行解，通過記錄目標函數值的增加量或者減少量，來選擇下一個候選解，這是貪婪算法的基本原型。而在GRASP算法中，選擇候選解的方式是通過控制隨機性的參數來實現。

3.2 irace介紹

irace（iterated racing）是一個自動化的參數分析工具，其內部實現的是iterated F-race算法。Iteated F-race算法執行初期會從給定的需要分析的算法參數中，根據參數的類別選擇對應的分布模型，隨機的從參數組中選取候選參數組。在race過程中，每一次的迭代中均使用racing策略以及non-Parametric Friedman測試挑選出最佳參數組。在執行racing策略的過程中，將選出的所有參數組在每一個訓練算例中逐個地執行求解算法，直到在統計結果上發現有參數組的求解結果性能劣于其他的參數組，此時將該參數組剔除。在race結束后，所選出的最佳參數組會進入取樣模型中并更新模型，下一次迭代開始時會從這一模型中隨機的挑選新的參數組，racing策略會將上一次迭代中的最佳參數組和新挑選出的參數組一起用于新的迭代中去，這一策略會重復的執行，直到最后分析成本耗盡為止。其具體的racing策略執行過程如圖1所示。

在實際的分析過程中，首先在參數分析的過程中會準備三個文件：參數定義的文件（里面規定了參數的名字、參數的類型以及參數的取值范圍）、指導參數分析的文件以及指定問題的數據集文件。在準備好三個文件之后，在irace進行參數分析的過程中，根據指導參數分析文件中的規定來進行整個搜索過程，參數定義文件以及數據集文件作為irace的輸入，irace內部會通過在不同的算例文件上執行算法，從參數定義空間挑選性能較好的參數組，具體的參數分析流程如圖2所示。

圖1 irace內部racing策略執行過程

圖2 參數分析過程

3.3 基于irace的算法改進

在本文所使用的GRASP算法中，通過隨機的方式選擇候選解，使用k值來指導隨機過程，即將數對按照凈目標值函數非減的順序進行排序，并隨機的選取列表中第k個數對，k的取值取決于整個數對列表的長度K以及k1和k2，同時k和K之間的關系可以用來表示，其中k1和k2為確定最終該算法的兩個關鍵參數，其取值范圍為：k1∈N,k2∈{k ∈R:0≤k≤1}，其中N表示自然數，R表示實數。

由于參數k1和k2取值的不確定性，使得算法在求解過程中存在一定的不確定因素的影響，因此在這里使用irace對求解MaxTFFAO的算法進行參數分析。irace是一個自動化的參數分析工具，其內部實現的是Iterated F-race算法，irace分析主要步驟包括三個方面，首先是將需要分析的參數按照其給定的參數范圍隨機的組成候選參數組，然后，根據參數類型所對應的參數分布模型來選取候選參數，最后irace通過race分析選出最佳的參數組。這是實現參數分析主要的三個步驟。

此次irace主要分析的GRASP算法中的關鍵參數為控制算法隨機性的兩個參數，其中參數的初始默認值見表1。

表1 參數默認初始值

在實際分析過程中，irace分析結束后產生的最佳參數組會在同一問題的不可見算例中測試其性能，即irace分析方法會在訓練算例中產生最佳的參數組，并在測試算例（testing instances）中測試所找到的最佳參數組，因此首先將實驗數據分為訓練數據（training instances）和測試數據（testing instances）。其中訓練算例的數據用于完成分析過程，測試算例的數據用于完成對比和分析參數。本文中所用的算例均來源于Boland等所采用的標準測試數據，數據主要包含兩個方面，一是抽象化的網絡結構，二是與此網絡結構相對應的維護作業的相關信息。不同規模的數據做實驗，形成對比，能夠說明算法性能的優劣。在實驗過程中，為了方便irace分析，采取先將網絡結構固定，將維護作業的數據作為輸入數據的方法。在本次實驗中，分析GRASP算法所用的分析成本為1 200。

用irace進行參數分析時，首先將小規模數據中的80組數據作為訓練算例，找出最佳的參數組合，并在大規模數據的80組算例中進行測試，最終確定最佳的參數組合。irace分析結束之后的算法內部參數的改進結果見表2。

表2 基于irace的算法改進結果

4 實驗設計與分析

4.1 實驗設計

本實驗中GRASP算法所用的編碼均是采用python2.7的版本進行編寫，在對比實驗中分別使用包含默認參數組的GRASP算法以及由irace分析出來的新的參數組組成的GRASP算法對問題進行求解，前后兩個算法分別用GRASP_old和GRASP_new表示。其中GRASP算法包含了控制隨機性的參數k1和k2。所有計算實驗都在CPU為酷睿：i7-4710（八線程 2.5 GHz），12GB內存的戴爾一體機（型號：Dell Inspiron One 2350）上完成，運行環境為64位ubuntu16.04LTS操作系統。數學優化求解器Gurobi8.0.0運用整數規劃方法計算靜態網絡最大流問題。其中參數分析工具使用irace2.4版本。網絡結構數據均使用DIMACS格式，而維護作業列表信息也要統一格式，以方便數據讀取與計算。

本實驗中所采用的數據均來自于文獻[9]。實驗數據主要包含兩個方面：一是抽象化的網絡結構，二是與此網絡結構相對應的維護作業的相關信息。每一組數據包含8組不同的網絡結構,每個網絡結構中包含10組與之對應的維護作業信息，總共兩組數據，一組小規模的數據，一組大規模的數據，總共160組算例。有關數據的相關信息見表3。

表3 數據集內部的網絡數據信息

在算法實驗中，新參數組和舊參數組構成的GRASP算法的初始解都設定為每個維護作業時間窗口的中間時間點，即。而對于所有的實例，都設置300s和1 800s兩種運行時間限制，目的是在同一實驗環境設置條件下，對比結果，進行分析。

4.2 實驗分析

對結果的評價指標有兩種：一是比較兩種算法在求解每一個網絡的10個算例時，記錄得到的最優解更好的算例的個數，并用符號#bestsol表示；二是以各個算法得到的最優解值與直接使用Gurobi數學優化求解器求解的上界的間隔（gap）的大小作為比較，即，其中z′表示Gurobi數學優化求解器求解的上界，z表示各個算法得到的最優解值。選取求解每一個網絡的10個算例的最大間隔及平均間隔作為評價標準。

表4-表7四組表格分別表示維護作業列表的可選時間窗口為小規模γ∈[1,35]及大規模γ∈[25,35]，運行時間分別為300s與1800s的結果。

表4 維護作業列表的可選時間窗口為小規模γ∈[1,35]運行300s的結果

表5 維護作業列表的可選時間窗口為小規模γ∈[1,35]運行1800s的結果

表6 維護作業列表的可選時間窗口為大規模γ∈[25,35]運行300s的結果

表7 維護作業列表的可選時間窗口為大規模γ∈[25,35]運行1800s的結果

在文獻[9]中，Gurobi不論是在小網絡小規模算例中還是在大網絡大規模算例中，其算法的求解性能均比其他的算法要好，而且GRASP算法的求解性能主要體現在求解大網絡結構的算例上，因此在對比實驗中，主要對比GRASP_old和GRASP_new兩組算法在求解大網絡小規模算例和大網絡大規模算例上的性能表現：

在大網絡小規模算例和大網絡大規模算例中，GRASP_new無論是在運行300s還是1 800s時，能給出更好解的個數都要比GRASP_old多。

本文還設定了一個比較算法的性能指標，就是分析單個算法求解單個算例的結果與在所有算法中求得該算例最好的結果之間的相對差距。如果一個實例I公認的最好解的值是zbest，當前算法求得實例I的解值為z0，那么，使用ρ(I)表示該性能指標：。本文考慮該性能指標的累積效果，總體比較幾種算法的實際性能。每一組測試中的每一個算法對應著n個這樣的性能指標，其形成的集合采用P(ρ)表示。本文考慮其累積效果，取集合P(ρ)中最大的一個值，設置為單位刻度，其中n為每組實驗數據的個數，即n=80。設m∈[n]，即m=1,2,...,n，對任一種算法，其實際性能累積效果為，其中要求實例I滿足ρ(I) ≤m?τ。

圖3-圖6表示在每一組實例數據中，每一種算法所對應的該性能指標的累積效果，縱坐標為實際性能累積效果，橫坐標為隨m值增大的性能指標刻度值。

根據圖3-圖6累計效果圖可以看出，圖形曲線上升越快，縱坐標越快達到上限，說明此實例中，算法表現最好。綜合四圖分析如下：

（1）上述四圖得到的結果和四張表格的結果互為佐證；

（2）上述四種圖的結果證明，GRASP算法在新的參數下要比之前默認參數中的表現要好很多，也證明了irace分析出來的參數要比之前默認的參數在算法中的表現更優。

5 總結與展望

本文采用最新的參數分析工具irace，應用于分析求解帶邊中斷動態網絡最大流問題的GRASP算法中的參數，在對比了默認參數值下的運行結果和irace分析所得最佳參數組的運行結果之后發現，無論是從最后求得的最優解的個數還是最終的累積性能效果圖來看，最終運行的結果都比算法默認參數下的要好。這一結果首先說明irace在參數分析的基礎上得出的結果要比在默認參數下求得的結果更好，其次可以根據irace分析出的結果及時更改原來GRASP算法中的默認參數，使得最終結果更接近最優解。

圖3 第一個實例組γ∈[1,35]，計算時間限制為300s的性能概況

圖4 第一個實例組γ∈[1,35]，計算時間限制為1 800s的性能概況

圖5 第二個實例組γ∈[25,35]，計算時間限制為300s的性能概況

圖6 第二個實例組γ∈[25,35]，計算時間限制為1 800s的性能概況

求解MaxTFFAO問題的過程中，除了GRASP算法之外還有其他對該問題求解的啟發式算法，在之后的研究當中可以完善更多的求解該問題的（元）啟發式算法，同時也可以進一步設計不同的（元）啟發式算法對該問題進行求解。在設計算法的過程中，可以運用irace對算法中的參數進行分析或者進行最佳的參數設置，從而提升算法的性能，減輕人為調參的負擔。