基于參數(shù)分析的物流網(wǎng)絡(luò)優(yōu)化問(wèn)題研究

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

1 前言

對(duì)于求解復(fù)雜問(wèn)題的優(yōu)化算法，目前已經(jīng)出現(xiàn)了大量的研究。精確算法在解決小規(guī)模問(wèn)題方面表現(xiàn)出了較強(qiáng)的優(yōu)越性，但是隨著問(wèn)題的復(fù)雜化以及工業(yè)應(yīng)用程度的加深，在大規(guī)模算例中精確式算法求解時(shí)間較長(zhǎng)，效率緩慢，已經(jīng)無(wú)法滿足人們的需求。因此有研究者開(kāi)始針對(duì)不同的問(wèn)題開(kāi)發(fā)了大量的啟發(fā)式算法，盡管啟發(fā)式算法不能像精確式算法一樣保證解的最優(yōu)性，但是在求解大規(guī)模算例以及組合優(yōu)化問(wèn)題中，啟發(fā)式算法具有高效性。

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

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

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

2 帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問(wèn)題及模型

帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問(wèn)題（Maximum Total Flow with Flexible Arc Outages，MaxTFFAO）由澳大利亞學(xué)者Boland等提出[9]，下文均用MaxTFFAO表示。該問(wèn)題是針對(duì)某大型煤炭碼頭供應(yīng)鏈上下游之間如何安排設(shè)備檢修問(wèn)題，通過(guò)抽象數(shù)學(xué)建模，最終得到的一個(gè)綜合了運(yùn)籌學(xué)中基礎(chǔ)的最大流問(wèn)題和調(diào)度規(guī)劃問(wèn)題中的數(shù)學(xué)難題。同時(shí)他們已經(jīng)通過(guò)復(fù)雜的三階段理論證明了帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問(wèn)題是一個(gè)NP難問(wèn)題。

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

每一個(gè)需要停機(jī)維護(hù)設(shè)備定義為一個(gè)維護(hù)作業(yè)，用符號(hào)j表示，[J]表示網(wǎng)絡(luò)中所有維護(hù)作業(yè)的集合,[Ja]表示網(wǎng)絡(luò)中所有與弧a相關(guān)的維護(hù)作業(yè)的集合。每一項(xiàng)維護(hù)作業(yè)j都存在一個(gè)特定的維護(hù)時(shí)間窗口 (rj,dj)，其中rj∈[T]表示維護(hù)作業(yè)j的最早開(kāi)始處理時(shí)間點(diǎn)，dj∈[T]表示維護(hù)作業(yè)j的終止處理時(shí)間點(diǎn)；同時(shí)，每一項(xiàng)維護(hù)作業(yè)j都有一個(gè)連續(xù)的維護(hù)過(guò)程，時(shí)間長(zhǎng)度定義為pj∈[T]。維護(hù)作業(yè)開(kāi)始時(shí)間為sj∈[rj,dj-pj+1]，其中[rj,dj-pj+1]為維護(hù)作業(yè)的開(kāi)始時(shí)間窗口，當(dāng) j∈[Ja]時(shí)，t∈[sj,sj+pj-1]時(shí)弧a中斷，其弧上的流量為0。

為更好地使用數(shù)學(xué)術(shù)語(yǔ)描述煤炭供應(yīng)鏈設(shè)備維護(hù)問(wèn)題，本文提出如下三個(gè)假設(shè)：

假設(shè)1 任意一條路徑弧a上存在數(shù)量不等的多個(gè)維護(hù)作業(yè)；

假設(shè)2 路徑弧上的不同維護(hù)作業(yè)的維護(hù)時(shí)間窗口不重疊，即對(duì)于同一條弧a上的任意兩個(gè)維護(hù)作業(yè)j和j′，都有；

假設(shè)3 維護(hù)作業(yè)一旦開(kāi)始，在其處理時(shí)間段內(nèi)不可提前中斷。

為了準(zhǔn)確地表達(dá)該問(wèn)題的數(shù)學(xué)模型，將在模型中使用到的變量設(shè)置如下：a表示網(wǎng)絡(luò)中的任意一條弧;t表示時(shí)間跨度T內(nèi)任意一個(gè)時(shí)間點(diǎn)；表示流進(jìn)節(jié)點(diǎn)υ的路徑弧的集合；表示流出節(jié)點(diǎn)υ的路徑弧的集合。變量φat∈R+表示在時(shí)間點(diǎn)t內(nèi)流經(jīng)弧a的流量；xat=1表示弧a在時(shí)間點(diǎn)t內(nèi)閉合，否則就斷開(kāi)；yjt=1表示維護(hù)作業(yè)j開(kāi)始于時(shí)間t，否則就為0。因此該問(wèn)題的數(shù)學(xué)模型表示如下：

會(huì)計(jì)制度是行政事業(yè)單位進(jìn)行會(huì)計(jì)管理和核算的重要依據(jù)， 2019年1月1日起行政事業(yè)單位將全面實(shí)行政府會(huì)計(jì)制度，該如何做好新舊會(huì)計(jì)制度的銜接呢？本文就新舊會(huì)計(jì)制度銜接的難點(diǎn)進(jìn)行分析，并以此提出新舊會(huì)計(jì)制度銜接的具體措施，希望能夠?qū)π姓聵I(yè)單位的會(huì)計(jì)工作有所幫助。

目標(biāo)函數(shù)式（1）是將跨度時(shí)間T內(nèi)每一時(shí)間點(diǎn)所對(duì)應(yīng)的網(wǎng)絡(luò)最大流的加和最大化。式（2）表示流量平衡約束；式（3）限制了每一個(gè)時(shí)間點(diǎn)內(nèi)網(wǎng)絡(luò)中各弧上流量不超過(guò)弧的容量；式（4）要求每一項(xiàng)維護(hù)作業(yè)j在其可選起始處理時(shí)間窗口[rj,dj-pj+1]內(nèi)恰好被執(zhí)行一次；式（5）表示網(wǎng)絡(luò)弧a在時(shí)間t內(nèi)的開(kāi)閉情況由維護(hù)作業(yè)j所選的時(shí)間點(diǎn)t′決定，即當(dāng)時(shí)，網(wǎng)絡(luò)弧a在時(shí)間點(diǎn)t內(nèi)為中斷狀態(tài)。

3 求解MaxTFFAO問(wèn)題的算法

3.1 貪婪隨機(jī)自適應(yīng)搜索算法

在給定的初始的維護(hù)作業(yè)計(jì)劃中，首先將總的時(shí)間跨度設(shè)定為T=1 000，同時(shí)按照劃分時(shí)間片段，在劃分出的M個(gè)時(shí)間片段中，觀察發(fā)現(xiàn)每個(gè)時(shí)間片段內(nèi)的網(wǎng)絡(luò)結(jié)構(gòu)是不變的，因此在求解T時(shí)間跨度內(nèi)的最大流問(wèn)題時(shí)，可以先計(jì)算時(shí)間片段內(nèi)單位時(shí)間的最大流再乘上對(duì)應(yīng)的時(shí)間片段的長(zhǎng)度，就可以求出該時(shí)間片段所對(duì)應(yīng)的最大流。將M個(gè)時(shí)間片段的最大流值求和就是初始的目標(biāo)值函數(shù)，整個(gè)計(jì)算過(guò)程可以用Gurobi優(yōu)化求解器來(lái)實(shí)現(xiàn)。但是隨著問(wèn)題規(guī)模的不斷擴(kuò)大，Gurobi優(yōu)化求解器在給定的時(shí)間不能獲得最優(yōu)解。

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

3.2 irace介紹

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

在實(shí)際的分析過(guò)程中，首先在參數(shù)分析的過(guò)程中會(huì)準(zhǔn)備三個(gè)文件：參數(shù)定義的文件（里面規(guī)定了參數(shù)的名字、參數(shù)的類型以及參數(shù)的取值范圍）、指導(dǎo)參數(shù)分析的文件以及指定問(wèn)題的數(shù)據(jù)集文件。在準(zhǔn)備好三個(gè)文件之后，在irace進(jìn)行參數(shù)分析的過(guò)程中，根據(jù)指導(dǎo)參數(shù)分析文件中的規(guī)定來(lái)進(jìn)行整個(gè)搜索過(guò)程，參數(shù)定義文件以及數(shù)據(jù)集文件作為irace的輸入，irace內(nèi)部會(huì)通過(guò)在不同的算例文件上執(zhí)行算法，從參數(shù)定義空間挑選性能較好的參數(shù)組，具體的參數(shù)分析流程如圖2所示。

圖1 irace內(nèi)部racing策略執(zhí)行過(guò)程

圖2 參數(shù)分析過(guò)程

3.3 基于irace的算法改進(jìn)

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

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

此次irace主要分析的GRASP算法中的關(guān)鍵參數(shù)為控制算法隨機(jī)性的兩個(gè)參數(shù)，其中參數(shù)的初始默認(rèn)值見(jiàn)表1。

表1 參數(shù)默認(rèn)初始值

在實(shí)際分析過(guò)程中，irace分析結(jié)束后產(chǎn)生的最佳參數(shù)組會(huì)在同一問(wèn)題的不可見(jiàn)算例中測(cè)試其性能，即irace分析方法會(huì)在訓(xùn)練算例中產(chǎn)生最佳的參數(shù)組，并在測(cè)試算例（testing instances）中測(cè)試所找到的最佳參數(shù)組，因此首先將實(shí)驗(yàn)數(shù)據(jù)分為訓(xùn)練數(shù)據(jù)（training instances）和測(cè)試數(shù)據(jù)（testing instances）。其中訓(xùn)練算例的數(shù)據(jù)用于完成分析過(guò)程，測(cè)試算例的數(shù)據(jù)用于完成對(duì)比和分析參數(shù)。本文中所用的算例均來(lái)源于Boland等所采用的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)，數(shù)據(jù)主要包含兩個(gè)方面，一是抽象化的網(wǎng)絡(luò)結(jié)構(gòu)，二是與此網(wǎng)絡(luò)結(jié)構(gòu)相對(duì)應(yīng)的維護(hù)作業(yè)的相關(guān)信息。不同規(guī)模的數(shù)據(jù)做實(shí)驗(yàn)，形成對(duì)比，能夠說(shuō)明算法性能的優(yōu)劣。在實(shí)驗(yàn)過(guò)程中，為了方便irace分析，采取先將網(wǎng)絡(luò)結(jié)構(gòu)固定，將維護(hù)作業(yè)的數(shù)據(jù)作為輸入數(shù)據(jù)的方法。在本次實(shí)驗(yàn)中，分析GRASP算法所用的分析成本為1 200。

用irace進(jìn)行參數(shù)分析時(shí)，首先將小規(guī)模數(shù)據(jù)中的80組數(shù)據(jù)作為訓(xùn)練算例，找出最佳的參數(shù)組合，并在大規(guī)模數(shù)據(jù)的80組算例中進(jìn)行測(cè)試，最終確定最佳的參數(shù)組合。irace分析結(jié)束之后的算法內(nèi)部參數(shù)的改進(jìn)結(jié)果見(jiàn)表2。

表2 基于irace的算法改進(jìn)結(jié)果

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

本實(shí)驗(yàn)中所采用的數(shù)據(jù)均來(lái)自于文獻(xiàn)[9]。實(shí)驗(yàn)數(shù)據(jù)主要包含兩個(gè)方面：一是抽象化的網(wǎng)絡(luò)結(jié)構(gòu)，二是與此網(wǎng)絡(luò)結(jié)構(gòu)相對(duì)應(yīng)的維護(hù)作業(yè)的相關(guān)信息。每一組數(shù)據(jù)包含8組不同的網(wǎng)絡(luò)結(jié)構(gòu),每個(gè)網(wǎng)絡(luò)結(jié)構(gòu)中包含10組與之對(duì)應(yīng)的維護(hù)作業(yè)信息，總共兩組數(shù)據(jù)，一組小規(guī)模的數(shù)據(jù)，一組大規(guī)模的數(shù)據(jù)，總共160組算例。有關(guān)數(shù)據(jù)的相關(guān)信息見(jiàn)表3。

表3 數(shù)據(jù)集內(nèi)部的網(wǎng)絡(luò)數(shù)據(jù)信息

在算法實(shí)驗(yàn)中，新參數(shù)組和舊參數(shù)組構(gòu)成的GRASP算法的初始解都設(shè)定為每個(gè)維護(hù)作業(yè)時(shí)間窗口的中間時(shí)間點(diǎn)，即。而對(duì)于所有的實(shí)例，都設(shè)置300s和1 800s兩種運(yùn)行時(shí)間限制，目的是在同一實(shí)驗(yàn)環(huán)境設(shè)置條件下，對(duì)比結(jié)果，進(jìn)行分析。

4.2 實(shí)驗(yàn)分析

對(duì)結(jié)果的評(píng)價(jià)指標(biāo)有兩種：一是比較兩種算法在求解每一個(gè)網(wǎng)絡(luò)的10個(gè)算例時(shí)，記錄得到的最優(yōu)解更好的算例的個(gè)數(shù)，并用符號(hào)#bestsol表示；二是以各個(gè)算法得到的最優(yōu)解值與直接使用Gurobi數(shù)學(xué)優(yōu)化求解器求解的上界的間隔（gap）的大小作為比較，即，其中z′表示Gurobi數(shù)學(xué)優(yōu)化求解器求解的上界，z表示各個(gè)算法得到的最優(yōu)解值。選取求解每一個(gè)網(wǎng)絡(luò)的10個(gè)算例的最大間隔及平均間隔作為評(píng)價(jià)標(biāo)準(zhǔn)。

表4-表7四組表格分別表示維護(hù)作業(yè)列表的可選時(shí)間窗口為小規(guī)模γ∈[1,35]及大規(guī)模γ∈[25,35]，運(yùn)行時(shí)間分別為300s與1800s的結(jié)果。

表4 維護(hù)作業(yè)列表的可選時(shí)間窗口為小規(guī)模γ∈[1,35]運(yùn)行300s的結(jié)果

表5 維護(hù)作業(yè)列表的可選時(shí)間窗口為小規(guī)模γ∈[1,35]運(yùn)行1800s的結(jié)果

表6 維護(hù)作業(yè)列表的可選時(shí)間窗口為大規(guī)模γ∈[25,35]運(yùn)行300s的結(jié)果

表7 維護(hù)作業(yè)列表的可選時(shí)間窗口為大規(guī)模γ∈[25,35]運(yùn)行1800s的結(jié)果

在文獻(xiàn)[9]中，Gurobi不論是在小網(wǎng)絡(luò)小規(guī)模算例中還是在大網(wǎng)絡(luò)大規(guī)模算例中，其算法的求解性能均比其他的算法要好，而且GRASP算法的求解性能主要體現(xiàn)在求解大網(wǎng)絡(luò)結(jié)構(gòu)的算例上，因此在對(duì)比實(shí)驗(yàn)中，主要對(duì)比GRASP_old和GRASP_new兩組算法在求解大網(wǎng)絡(luò)小規(guī)模算例和大網(wǎng)絡(luò)大規(guī)模算例上的性能表現(xiàn)：

在大網(wǎng)絡(luò)小規(guī)模算例和大網(wǎng)絡(luò)大規(guī)模算例中，GRASP_new無(wú)論是在運(yùn)行300s還是1 800s時(shí)，能給出更好解的個(gè)數(shù)都要比GRASP_old多。

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

圖3-圖6表示在每一組實(shí)例數(shù)據(jù)中，每一種算法所對(duì)應(yīng)的該性能指標(biāo)的累積效果，縱坐標(biāo)為實(shí)際性能累積效果，橫坐標(biāo)為隨m值增大的性能指標(biāo)刻度值。

根據(jù)圖3-圖6累計(jì)效果圖可以看出，圖形曲線上升越快，縱坐標(biāo)越快達(dá)到上限，說(shuō)明此實(shí)例中，算法表現(xiàn)最好。綜合四圖分析如下：

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

（2）上述四種圖的結(jié)果證明，GRASP算法在新的參數(shù)下要比之前默認(rèn)參數(shù)中的表現(xiàn)要好很多，也證明了irace分析出來(lái)的參數(shù)要比之前默認(rèn)的參數(shù)在算法中的表現(xiàn)更優(yōu)。

5 總結(jié)與展望

本文采用最新的參數(shù)分析工具irace，應(yīng)用于分析求解帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問(wèn)題的GRASP算法中的參數(shù)，在對(duì)比了默認(rèn)參數(shù)值下的運(yùn)行結(jié)果和irace分析所得最佳參數(shù)組的運(yùn)行結(jié)果之后發(fā)現(xiàn)，無(wú)論是從最后求得的最優(yōu)解的個(gè)數(shù)還是最終的累積性能效果圖來(lái)看，最終運(yùn)行的結(jié)果都比算法默認(rèn)參數(shù)下的要好。這一結(jié)果首先說(shuō)明irace在參數(shù)分析的基礎(chǔ)上得出的結(jié)果要比在默認(rèn)參數(shù)下求得的結(jié)果更好，其次可以根據(jù)irace分析出的結(jié)果及時(shí)更改原來(lái)GRASP算法中的默認(rèn)參數(shù)，使得最終結(jié)果更接近最優(yōu)解。

圖3 第一個(gè)實(shí)例組γ∈[1,35]，計(jì)算時(shí)間限制為300s的性能概況

圖4 第一個(gè)實(shí)例組γ∈[1,35]，計(jì)算時(shí)間限制為1 800s的性能概況

圖5 第二個(gè)實(shí)例組γ∈[25,35]，計(jì)算時(shí)間限制為300s的性能概況

圖6 第二個(gè)實(shí)例組γ∈[25,35]，計(jì)算時(shí)間限制為1 800s的性能概況

求解MaxTFFAO問(wèn)題的過(guò)程中，除了GRASP算法之外還有其他對(duì)該問(wèn)題求解的啟發(fā)式算法，在之后的研究當(dāng)中可以完善更多的求解該問(wèn)題的（元）啟發(fā)式算法，同時(shí)也可以進(jìn)一步設(shè)計(jì)不同的（元）啟發(fā)式算法對(duì)該問(wèn)題進(jìn)行求解。在設(shè)計(jì)算法的過(guò)程中，可以運(yùn)用irace對(duì)算法中的參數(shù)進(jìn)行分析或者進(jìn)行最佳的參數(shù)設(shè)置，從而提升算法的性能，減輕人為調(diào)參的負(fù)擔(dān)。