唐 震 霆， 胡 志 華

(上海海事大學(xué) 物流研究中心，上海 201306)

0 引 言

兩級(jí)選址路徑問題(two-echelon location routing problem，2E-LRP)是近年來物流領(lǐng)域的熱點(diǎn)問題，選址路徑問題從結(jié)構(gòu)上來說首先要完成選址，而后進(jìn)行路徑規(guī)劃.在一個(gè)多級(jí)運(yùn)輸配送系統(tǒng)中，一條完整的運(yùn)輸配送鏈也被分成多級(jí)，貨物從倉庫運(yùn)輸至樞紐點(diǎn)整合并移交至最終客戶，高效利用各樞紐點(diǎn)與車輛容量是降本提效的關(guān)鍵，而將客戶點(diǎn)合理分配至每一個(gè)客戶是樞紐點(diǎn)高效運(yùn)作的條件之一[1].

截至目前，許多優(yōu)秀的學(xué)者提出了多級(jí)車輛運(yùn)輸?shù)南嚓P(guān)選址路徑規(guī)劃方案以及方法論.有關(guān)2E-LRP的文獻(xiàn)開始涉及城市物流中兩級(jí)配送結(jié)構(gòu)的運(yùn)營(yíng)和資源管理的短期綜合調(diào)度問題[2-7]，在確定樞紐點(diǎn)之后問題轉(zhuǎn)變?yōu)閮杉?jí)車輛路徑問題(two-echelon vehicle routing problem，2E-VRP)；傳統(tǒng)的車輛路徑問題一般為單級(jí)物流系統(tǒng)，即車輛從中心場(chǎng)站直接向需求點(diǎn)提供服務(wù).一般地，物流運(yùn)輸車輛體積較大、質(zhì)量較重，加重了城市道路交通擁堵、噪聲、污染等情況，地方政府對(duì)此也提出了限行條例：運(yùn)輸物資先通過大型運(yùn)輸車輛調(diào)配至企業(yè)位于郊區(qū)的中轉(zhuǎn)設(shè)施中，而后通過污染較小、較為靈活的小型運(yùn)輸車輛進(jìn)行配送，這也就是兩級(jí)車輛路徑問題的起源.Grangier等介紹了一個(gè)具有衛(wèi)星同步的兩級(jí)多行程車輛路徑問題，并提出了一種自適應(yīng)大鄰域搜索(adaptive large neighborhood search，ALNS)算法[8].Boccia 等考慮了多中心場(chǎng)站的場(chǎng)景，針對(duì)不同類型的車隊(duì)和兩級(jí)物流網(wǎng)絡(luò)路徑之間的聯(lián)系等要素采用了禁忌搜索算法對(duì)算例進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了該算法的有效性[9].Yang等研究城市物流系統(tǒng)中帶時(shí)間約束的兩級(jí)選址路徑問題，基于概率選擇原則提出了一種綜合考慮時(shí)間和空間可達(dá)性的元啟發(fā)式算法來求解該類問題，并通過隨機(jī)生成的實(shí)例來驗(yàn)證算法有效性[10].Pichka等認(rèn)為多級(jí)分銷系統(tǒng)普遍存在于人們的日常生活中，其提出3種基于流通路徑的混合整數(shù)線性規(guī)劃以及1種混合啟發(fā)式算法來求解開放式選址與路徑優(yōu)化問題[11].

對(duì)于上述研究，兩級(jí)設(shè)施選址與車輛路徑規(guī)劃問題的雙層結(jié)構(gòu)特征是其復(fù)雜性的核心，兩級(jí)物流網(wǎng)絡(luò)的搭建與布局一直是許多物流企業(yè)的痛點(diǎn)，如何從備選節(jié)點(diǎn)中選擇有利于降低整體系統(tǒng)成本的節(jié)點(diǎn)來作為樞紐點(diǎn)、確定車輛經(jīng)過節(jié)點(diǎn)的先后次序即車輛路徑以及客戶點(diǎn)、樞紐點(diǎn)與中心場(chǎng)站的對(duì)應(yīng)關(guān)系是該問題的幾個(gè)重大難點(diǎn)，也是物流企業(yè)進(jìn)行多級(jí)物流網(wǎng)絡(luò)建設(shè)所避不開的問題.在一些研究中將問題分割為兩個(gè)階段來進(jìn)行求解[12-13]，這在一定程度上導(dǎo)致了求解問題的獨(dú)立性，對(duì)于兩級(jí)選址路徑問題，雙智能集成算法的表現(xiàn)優(yōu)于其他傳統(tǒng)啟發(fā)式算法.本研究中進(jìn)行節(jié)點(diǎn)資源配置的算法為ALNS的改進(jìn)算法，擁有一組破壞與修復(fù)算子是其與常規(guī)ALNS算法[14]最明顯的不同，而模擬退火算法則用于路徑尋優(yōu).

1 多中心場(chǎng)站下兩級(jí)選址路徑問題的建模

基本的兩級(jí)選址路徑問題表述如下：從備選節(jié)點(diǎn)中選出若干個(gè)合適的節(jié)點(diǎn)作為樞紐點(diǎn)優(yōu)化配送體系，降低系統(tǒng)成本；一組運(yùn)輸車輛從中心場(chǎng)站出發(fā)，將貨物運(yùn)輸碼放至樞紐點(diǎn)，而后由樞紐點(diǎn)委派運(yùn)輸車輛將貨物交付給客戶，所有運(yùn)輸車輛在完成配送后回到始發(fā)節(jié)點(diǎn)；每個(gè)客戶點(diǎn)的坐標(biāo)位置已知；配送車輛有荷載限制；要求合理配置資源、優(yōu)化行車路徑，以實(shí)現(xiàn)目標(biāo)的優(yōu)化.

多中心場(chǎng)站下兩級(jí)設(shè)施選址與車輛路徑規(guī)劃問題的圖論表述如下：D代表中心場(chǎng)站集合，通過τ∈D索引；N代表客戶點(diǎn)集合，一般通過i∈N索引每個(gè)客戶點(diǎn)，通過υ∈N索引樞紐點(diǎn)；候選樞紐點(diǎn)集合S?N；定義J=D∪N.Cij≥0為車輛從i∈J到j(luò)∈J的行駛成本；F1≥0與F2≥0分別為兩級(jí)運(yùn)輸中單輛運(yùn)輸車的固定成本；F3≥0為設(shè)置一個(gè)樞紐點(diǎn)的固定成本；由客戶需求Ri得出每一個(gè)樞紐點(diǎn)所需要的貨物量.第一級(jí)和第二級(jí)配送車輛的容量上限為K1和K2.C1和C2表示第一級(jí)和第二級(jí)車輛配送的單位里程成本.Ud表示中心場(chǎng)站數(shù)量，Us表示樞紐點(diǎn)數(shù)量.

變量qijτ表示從中心場(chǎng)站τ∈D出發(fā)的車輛經(jīng)過i∈N到達(dá)j∈N路段中車輛的載貨量；變量pijυ表示從樞紐點(diǎn)υ∈N出發(fā)的車輛經(jīng)過i∈N到達(dá)j∈N路段中車輛的載貨量.

決策變量βijτ=1，表示客戶點(diǎn)i分配給樞紐點(diǎn)j，并且j分配給中心場(chǎng)站τ；否則，βijτ=0.其中，i≠j.若節(jié)點(diǎn)i被選作樞紐點(diǎn)，則βiiτ=1.

決策變量xijτ=1，表示第一級(jí)配送車輛從中心場(chǎng)站τ出發(fā)，服務(wù)i∈N后下一個(gè)緊接的服務(wù)節(jié)點(diǎn)是j∈N；否則，xijτ=0.

決策變量yijυ=1，表示第二級(jí)配送車輛從樞紐點(diǎn)υ出發(fā)，服務(wù)i∈N后下一個(gè)緊接的服務(wù)節(jié)點(diǎn)是j∈N；否則，yijτ=0.

對(duì)2E-LRP問題中的變量與約束條件設(shè)置特點(diǎn)進(jìn)行總結(jié)，完善數(shù)學(xué)模型的構(gòu)建，所求得的解必須滿足以下約束：

(1)每個(gè)被選作樞紐點(diǎn)的節(jié)點(diǎn)至少服務(wù)一個(gè)客戶點(diǎn)；

(2)每次配送任務(wù)中任意車輛只運(yùn)行一次；

(3)每條路徑從設(shè)施出發(fā)，最后要回到出發(fā)的設(shè)施；

(4)每個(gè)客戶點(diǎn)由且僅由一輛貨車進(jìn)行服務(wù)；

(5)車輛服務(wù)的顧客的需求總和不能超過車輛的容量約束；

(6)每個(gè)客戶的需求Ri均為常量且已知；

(7)每個(gè)中心場(chǎng)站都至少輻射一個(gè)樞紐點(diǎn).

首先，目標(biāo)函數(shù)主要由兩部分組成，分別是兩級(jí)運(yùn)輸中的路徑成本總和以及車輛、樞紐設(shè)施的固定使用成本，如下式所示：

minz=z1+z2

(1)

其中

針對(duì)樞紐點(diǎn)的選擇以及客戶點(diǎn)的分配這兩個(gè)子問題，考慮兩個(gè)層級(jí)下樞紐點(diǎn)集合與客戶點(diǎn)集合的分配邏輯構(gòu)造約束，以便于路徑問題的求解，控制選址以及樞紐點(diǎn)分配的模型如下：

(2)

(3)

(4)

(5)

βikτ≤βkkτ；?i，k∈N，τ∈D

(6)

其中，約束(2)表示任意節(jié)點(diǎn)i∈N都會(huì)被分配一個(gè)樞紐點(diǎn)，且歸屬于一個(gè)中心場(chǎng)站；約束(3)表示樞紐點(diǎn)個(gè)數(shù)等于Us；約束(4)表示任意樞紐點(diǎn)僅被分配給一個(gè)中心場(chǎng)站；約束(5)表示若節(jié)點(diǎn)i∈N不是樞紐點(diǎn)必會(huì)被分配給一個(gè)樞紐點(diǎn)；約束(6)表示僅當(dāng)k∈N為樞紐點(diǎn)時(shí)才會(huì)將客戶點(diǎn)分配至樞紐點(diǎn)k.

(7)

(8)

(9)

(10)

(11)

(12)

約束(7)～(9)去除了車輛從中心場(chǎng)站出發(fā)的無效路徑，約束(10)～(12)表示第一級(jí)運(yùn)輸中的路徑約束與流平衡限制，且第一級(jí)運(yùn)輸車輛經(jīng)過的節(jié)點(diǎn)是被選作樞紐的節(jié)點(diǎn).

(13)

(14)

qijτ≥xijτ；?i∈J，j∈N，τ∈D

(15)

qijτ≤K1xijτ；?i，j∈J，τ∈D

(16)

xijτ≤βjjτ；?i∈J，j∈N，τ∈D

(17)

xjiτ≤βjjτ；?i∈J，j∈N，τ∈D

(18)

(19)

約束(13)～(14)將車輛裝載量、路徑、分配問題相聯(lián)立，保證了車輛運(yùn)輸過程中，經(jīng)過樞紐點(diǎn)的順序與車輛裝載量同步變化，即當(dāng)車輛經(jīng)過任意樞紐點(diǎn)時(shí)裝載量減少相應(yīng)節(jié)點(diǎn)所需的貨物量.約束(15)～(16)將變量qijτ與第一級(jí)運(yùn)輸路徑xijτ建立聯(lián)系；約束(17)～(18)將第一級(jí)運(yùn)輸路徑限制在樞紐點(diǎn)與中心場(chǎng)站間；約束(19)表示車輛回到中心場(chǎng)站時(shí)的裝載量為零.

(20)

(21)

約束(20)～(21)表示了第二級(jí)運(yùn)輸中車輛裝載量與運(yùn)輸路徑的聯(lián)系，以確立運(yùn)輸順序與車輛裝載量的變化關(guān)系.

(22)

(23)

(24)

pijυ≤K2yijυ；?i，j，υ∈N

(25)

pijυ≥yijυ；?i，j，υ∈N，j≠υ

(26)

約束(22)～(24)對(duì)第二級(jí)運(yùn)輸路徑進(jìn)行約束，建立流平衡約束；約束(25)～(26)將變量pijυ與路徑y(tǒng)ijυ聯(lián)立，確保車輛裝載量不超過車輛容量.

(27)

(28)

(29)

(30)

(31)

約束(27)～(30)將第二級(jí)運(yùn)輸路徑與節(jié)點(diǎn)分配邏輯保持統(tǒng)一，若客戶點(diǎn)j由樞紐點(diǎn)υ服務(wù)且歸屬于中心場(chǎng)站τ，則允許在客戶點(diǎn)j處存在入度與出度；約束(31)表示第二級(jí)運(yùn)輸車輛回到樞紐點(diǎn)時(shí)的裝載量為零.該模型綜合樞紐點(diǎn)選擇、兩級(jí)節(jié)點(diǎn)分配、車輛路徑規(guī)劃3個(gè)問題同時(shí)求解，保證了解決系統(tǒng)問題的連貫性、完整性.

2 雙智能集成算法

2.1 算法設(shè)計(jì)依據(jù)與邏輯

黃凱明等通過對(duì)多層級(jí)設(shè)施選址路徑規(guī)劃問題的研究，提出一種雙智能集成算法：量子進(jìn)化算法負(fù)責(zé)設(shè)施選址和資源分配，而遺傳算法負(fù)責(zé)子路徑尋優(yōu)[15].雙智能集成算法在求解選址路徑問題過程中體現(xiàn)出較大的優(yōu)勢(shì)，在應(yīng)對(duì)不同問題時(shí)都可以選擇針對(duì)問題具有較好求解性能的啟發(fā)式算法來進(jìn)行處理，通過信息交互、共同迭代來求解復(fù)雜問題是一種較為優(yōu)秀的求解思路.由此，本文在算法設(shè)計(jì)時(shí)采用了改進(jìn)的自適應(yīng)大鄰域搜索算法與模擬退火算法集成的雙智能算法，該混合啟發(fā)式算法通過兩種不同類型算法的交互，將求解任務(wù)分解，從而有效求解問題.

算法設(shè)計(jì)依據(jù)：兩級(jí)選址路徑問題的復(fù)雜性主要是因?yàn)樵搯栴}不僅需要確定節(jié)點(diǎn)分配方案，確定運(yùn)輸工具遍歷樞紐點(diǎn)以及客戶點(diǎn)的次序，還需要留意運(yùn)輸工具容量限制及樞紐點(diǎn)必須有子節(jié)點(diǎn)等條件，本混合啟發(fā)式算法能有效求解子問題并在算法內(nèi)部交互迭代，因此該混合啟發(fā)式算法適合解決兩級(jí)選址路徑問題.自適應(yīng)大鄰域搜索算法在多鄰域迭代過程中有著較優(yōu)秀的表現(xiàn)，因此選擇自適應(yīng)大鄰域搜索算法作為算法主體框架，使用模擬退火算法求解子路徑的最優(yōu)排序，這也加快了問題整體的求解效率，算法邏輯如圖1所示.

算法設(shè)計(jì)邏輯：兩級(jí)自適應(yīng)大鄰域搜索(two-echelon adaptive large neighborhood search，2E-ALNS)算法控制兩級(jí)節(jié)點(diǎn)分配方案，分別改變樞紐點(diǎn)被分配至中心場(chǎng)站的方案以及客戶點(diǎn)被分配至樞紐點(diǎn)的方案，根據(jù)分配方案確定每個(gè)旅行商問題(TSP)的構(gòu)成節(jié)點(diǎn)，但此時(shí)的分配方案中節(jié)點(diǎn)是無序的，經(jīng)過模擬退火算法進(jìn)行求解后，節(jié)點(diǎn)分配方案中的排序與TSP解的節(jié)點(diǎn)排序一致，因此兩個(gè)算法分工明確且相輔相成.

2.2 模擬退火算法

采用模擬退火算法以解決車輛經(jīng)過節(jié)點(diǎn)的次序問題，算法的輸入集是主節(jié)點(diǎn)編號(hào)、子節(jié)點(diǎn)編號(hào)以及節(jié)點(diǎn)坐標(biāo)位置.算法采用隨機(jī)交換節(jié)點(diǎn)次序來進(jìn)行路徑排序問題的尋優(yōu)，模擬退火算法初始溫度設(shè)為50；冷卻速率為0.98；算法以一定概率接受改造解，概率公式如下：

式中：ρ為接受改造解的概率；Sc為當(dāng)前迭代中的局部最優(yōu)解，Sn為算法產(chǎn)生的新解；E(S)代表解S的能量，在本例中即為路徑成本；T為當(dāng)前溫度；?為溫度與能量差值的轉(zhuǎn)換系數(shù)，本例中取?=0.8.當(dāng)改造解的運(yùn)輸成本小于局部最優(yōu)解的運(yùn)輸成本以，將改造解替代局部最優(yōu)解；當(dāng)改造解的運(yùn)輸成本大于局部最優(yōu)解的運(yùn)輸成本時(shí)，以一定概率接受改造解，將接受概率和當(dāng)前溫度相關(guān)聯(lián)，使得該算法在運(yùn)行初期搜索區(qū)域變大，加快收斂速度，而在后期削減其搜索區(qū)域進(jìn)行精細(xì)搜索.

2.3 改進(jìn)的自適應(yīng)大鄰域搜索算法

兩級(jí)自適應(yīng)大鄰域搜索算法是在自適應(yīng)大鄰域搜索算法的機(jī)理上再加一組破壞與修復(fù)算子使其能解決兩級(jí)問題，其中，通過第一級(jí)算子改變樞紐點(diǎn)至中心場(chǎng)站的分配方案，從而使得第一級(jí)的解改變，相似地，通過第二級(jí)算子改變非樞紐點(diǎn)的客戶點(diǎn)至樞紐點(diǎn)的分配方案.為了保證每個(gè)樞紐點(diǎn)承擔(dān)的中轉(zhuǎn)工作盡量相當(dāng)，在算子設(shè)計(jì)上，使每一級(jí)運(yùn)輸過程中每個(gè)主節(jié)點(diǎn)被分配的子節(jié)點(diǎn)數(shù)量盡量相當(dāng)，這樣才能確保每個(gè)樞紐點(diǎn)工作量差距不會(huì)太大，不會(huì)有廢棄樞紐點(diǎn)的情況出現(xiàn).

第一級(jí)算子設(shè)計(jì)邏輯有以下幾種：

第二級(jí)算子設(shè)計(jì)如下：

本算法的時(shí)間復(fù)雜度與自適應(yīng)大鄰域搜索算法的運(yùn)行過程極度相關(guān)，自適應(yīng)大鄰域搜索算法在迭代過程中會(huì)根據(jù)算子權(quán)重自主地選擇算子，由于在該算法中包括破壞算子和修復(fù)算子，且每個(gè)算子都有不同的時(shí)間復(fù)雜度，故本算法的自身時(shí)間復(fù)雜度并不確定且處于一個(gè)區(qū)間中，因此本算法的時(shí)間復(fù)雜度并不穩(wěn)定，且最壞情況為O(1952(3Ud+2Us)).

2.4 參與對(duì)比的啟發(fā)式算法

2.4.1 基于聚類算法的貪婪程式 聚類算法常用于分類問題，一般地，同一簇中的任意個(gè)體與同簇個(gè)體具有較高的相似度，而不同簇中的個(gè)體往往有較大差異.本啟發(fā)式的聚類算法以若干數(shù)據(jù)點(diǎn)為中心，將點(diǎn)集分為若干類，再根據(jù)中心點(diǎn)位置匹配距離較近的中心場(chǎng)站以提供配送服務(wù).在貪婪程式中，將簇中距離中心場(chǎng)站以及簇中心位置最短的若干節(jié)點(diǎn)作為樞紐點(diǎn)并以此確定第一級(jí)運(yùn)輸中的節(jié)點(diǎn)分配方案，而第二級(jí)運(yùn)輸中的節(jié)點(diǎn)分配方案主要由K-means聚類的方法來控制，整個(gè)貪婪程式中蘊(yùn)含了兩層貪心法則，在節(jié)點(diǎn)簇地理位置分隔較為明顯的案例下，該算法較為高效.

2.4.2 變鄰域搜索算法 變鄰域搜索算法是求解車輛路徑問題的最有利算法之一，通過復(fù)現(xiàn)并設(shè)計(jì)對(duì)應(yīng)本問題的算子以方便將雙智能集成算法與之進(jìn)行對(duì)比分析.

變鄰域搜索算法的擾動(dòng)算子設(shè)計(jì)如下：

(1)x′←ExchangeOneHub(x)：選擇一個(gè)樞紐點(diǎn)將其與備選樞紐點(diǎn)中的剩余節(jié)點(diǎn)進(jìn)行交換.

(2)x′←ChangeSequence1(x)：選擇任意兩個(gè)樞紐點(diǎn)進(jìn)行次序變更.

(3)x′←ChangeSequence2(x)：變更任意車輛路徑中服務(wù)的客戶點(diǎn)先后次序.

(4)x′←AddOrDelete(x)：增加或刪除從某個(gè)樞紐點(diǎn)出發(fā)的無人機(jī)路徑.

變鄰域搜索算法的鄰域動(dòng)作算子設(shè)計(jì)如下：

(1)x″←ChangeNodesSequence(x′)：選擇一條第二級(jí)路徑，將路徑中相近的兩個(gè)節(jié)點(diǎn)進(jìn)行次序調(diào)換.

(2)x″←Remove&Insert(x′)：若子節(jié)點(diǎn)個(gè)數(shù)不少于1，去除任意子節(jié)點(diǎn)并將其插入其他路徑中.

(3)x″←ExchangeNodes(x′)：選定兩條不同路徑，并選擇兩者中的任意節(jié)點(diǎn)進(jìn)行交換.

(4)x″←WorstNodesRemove(x′)：選擇任意第二級(jí)路徑中相近的客戶，去除其中任意一個(gè)并將其插入其他路徑中.

(5)x″←WorstExchange(x′)：選擇任意兩條第二級(jí)路徑，將各自距離樞紐點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)進(jìn)行交換.

3 實(shí)例驗(yàn)證

本研究求解的問題不同于常規(guī)的車輛路徑規(guī)劃問題，需要綜合考慮樞紐點(diǎn)選址問題、客戶點(diǎn)分配方案以及兩級(jí)車輛的路徑規(guī)劃問題.選擇車輛路徑問題的經(jīng)典數(shù)據(jù)集作為實(shí)驗(yàn)案例，對(duì)同一案例進(jìn)行多次實(shí)驗(yàn)，主要進(jìn)行了模型與算法求解的對(duì)比.通過將本文提出的算法與基于聚類算法的貪婪程式以及在路徑優(yōu)化問題領(lǐng)域較為成熟的變鄰域搜索算法進(jìn)行對(duì)比實(shí)驗(yàn)，證明算法的有效性.

3.1 實(shí)驗(yàn)環(huán)境和算法參數(shù)確定

實(shí)驗(yàn)環(huán)境如下：Intel i7-4720HQ 2.60 GHz CPU，8 GB內(nèi)存，操作系統(tǒng)為Windows 7，編程環(huán)境為Python 3.7.

選擇CVRPLIB中的P-n101-k4數(shù)據(jù)集進(jìn)行第一組實(shí)驗(yàn)，增加中心場(chǎng)站位置數(shù)據(jù)，其余數(shù)據(jù)保持不變，數(shù)據(jù)集主要包含了3個(gè)中心場(chǎng)站、100個(gè)客戶點(diǎn)的位置數(shù)據(jù)以及客戶點(diǎn)的需求量數(shù)據(jù)，記錄運(yùn)行結(jié)果的最優(yōu)值，考慮收斂速度和平均最優(yōu)值.參數(shù)設(shè)置：初始溫度50；溫度冷卻速率0.98；權(quán)重控制因子0.5.第二組實(shí)驗(yàn)的算例為P-n50-k4，其中包含3個(gè)中心場(chǎng)站和50個(gè)客戶點(diǎn)，記錄不同運(yùn)行時(shí)間下的啟發(fā)式算法運(yùn)算結(jié)果與CPLEX求解數(shù)學(xué)模型的結(jié)果，并求出兩者間的差距，證明算法應(yīng)對(duì)中等及大規(guī)模算例的有效性.在第三組實(shí)驗(yàn)中，將本文提出的雙智能集成算法與貪婪程式以及變鄰域搜索算法進(jìn)行對(duì)比實(shí)驗(yàn).

3.2 實(shí)驗(yàn)結(jié)果與分析

將數(shù)據(jù)集P-n101-k4中各節(jié)點(diǎn)以及新增的中心場(chǎng)站進(jìn)行編碼，取不同樞紐點(diǎn)數(shù)量進(jìn)行實(shí)驗(yàn).在3組實(shí)驗(yàn)中取10個(gè)樞紐點(diǎn)的平均路程成本最小.在此情景下，第一級(jí)車輛使用數(shù)量與中心場(chǎng)站數(shù)量相同(本例中為3).最后，樞紐點(diǎn)數(shù)量的確定需要考量車輛成本、樞紐點(diǎn)設(shè)立費(fèi)用等累加再比較總成本大小，使用本文算法求解算例所花費(fèi)的時(shí)間較為穩(wěn)定，在相同樞紐點(diǎn)數(shù)量下，5個(gè)樣本在求解時(shí)間上的方差很小.同一算例下，樞紐點(diǎn)數(shù)量對(duì)成本的影響見表1.

表1 樞紐點(diǎn)數(shù)量對(duì)成本的影響

在完成樞紐點(diǎn)數(shù)量對(duì)整個(gè)兩級(jí)物流系統(tǒng)的成本影響實(shí)驗(yàn)后，選取中等規(guī)模樣本進(jìn)行反復(fù)實(shí)驗(yàn)，將雙智能集成算法與數(shù)學(xué)模型求解的結(jié)果進(jìn)行對(duì)比.實(shí)驗(yàn)數(shù)據(jù)表明，雙智能集成算法在有限時(shí)間內(nèi)能普遍求得優(yōu)于數(shù)學(xué)模型求解的結(jié)果，其在兩級(jí)自適應(yīng)算法外層還嵌套了模擬退火思想以控制整體迭代次數(shù)，外層框架中模擬退火初始溫度的不同對(duì)最終結(jié)果產(chǎn)生影響，實(shí)驗(yàn)數(shù)據(jù)見表2.

表2 數(shù)學(xué)模型與雙智能集成算法求解結(jié)果對(duì)比

在本實(shí)驗(yàn)中，將雙智能集成算法中的算子在不同算例下的得分與權(quán)重記錄下來，并分析修復(fù)與破壞算子的優(yōu)劣，固定初始溫度為50，且取樞紐點(diǎn)數(shù)量為6，算子順序與前文介紹算子順序一致.算子總得分結(jié)果表明，雙智能集成算法中的算子得分均勻，并未出現(xiàn)使用次數(shù)極少或極多的算子.

而后，將前文提到的貪婪程式和變鄰域搜索算法與本文的雙智能集成算法進(jìn)行對(duì)比分析，在該實(shí)驗(yàn)中，分別選取樞紐點(diǎn)數(shù)量為6、8、10進(jìn)行實(shí)驗(yàn)，求解結(jié)果的對(duì)比見表3，實(shí)驗(yàn)編號(hào)為中心場(chǎng)站數(shù)量-客戶點(diǎn)數(shù)量.

表3 貪婪程式、變鄰域搜索算法與雙智能集成算法求解結(jié)果對(duì)比

本實(shí)驗(yàn)表明，在P-n50-k4這個(gè)案例中取8個(gè)樞紐點(diǎn)較優(yōu).雙智能集成算法與貪婪程式的平均差異為3.7%.此外雙智能集成算法中的算子設(shè)計(jì)依附了實(shí)際的運(yùn)用情景，例如在城市物流中每一個(gè)驛站的選址路徑問題不僅涉及整體成本的多少，還應(yīng)考慮單個(gè)樞紐點(diǎn)輻射客戶點(diǎn)的數(shù)量、上級(jí)節(jié)點(diǎn)對(duì)其配送的難易等，因此在算子設(shè)計(jì)過程中需要盡量保持每一個(gè)樞紐點(diǎn)服務(wù)的下屬節(jié)點(diǎn)均有一定量，也就是使得每個(gè)樞紐點(diǎn)的工作量差距不要太大.由此，雙智能集成算法在實(shí)際場(chǎng)景具有一定的泛用性，對(duì)于不同規(guī)模的算例皆可直接進(jìn)行計(jì)算并獲取其解決方案.在與車輛路徑問題中主流方法的對(duì)比中，雙智能集成算法在多案例的求解結(jié)果中都略優(yōu)于變鄰域搜索算法，且在該次實(shí)驗(yàn)中，雙智能集成算法的平均求解時(shí)間(24.92 s)略小于變鄰域搜索算法的平均求解時(shí)間(26.54 s)，體現(xiàn)出該算法的高效性.此外，對(duì)于確定算例下樞紐點(diǎn)數(shù)量問題，也可通過改變選址數(shù)量的參數(shù)，運(yùn)用雙智能集成算法對(duì)比不同樞紐點(diǎn)數(shù)量的系統(tǒng)成本高低，給予決策者較大的便利，解決整體系統(tǒng)中樞紐點(diǎn)選擇、節(jié)點(diǎn)分配及節(jié)點(diǎn)數(shù)量與系統(tǒng)最優(yōu)性關(guān)系等問題.

在算例P-n50-k4中，實(shí)驗(yàn)表明選取8個(gè)樞紐點(diǎn)相較于選取6個(gè)或10個(gè)樞紐點(diǎn)都更優(yōu)，貪婪程式也呈現(xiàn)出相類似的趨勢(shì)，這也強(qiáng)有力地支持了本文算法的有效性以及對(duì)選址數(shù)量確定問題的求解效能.在算例p-n101-k4中，系統(tǒng)成本隨樞紐點(diǎn)數(shù)量的增加而減少，清晰地呈現(xiàn)了選取樞紐點(diǎn)數(shù)量與系統(tǒng)成本的變化趨勢(shì).根據(jù)先前的實(shí)驗(yàn)經(jīng)驗(yàn)，如果繼續(xù)增加樞紐點(diǎn)，在某個(gè)閾值點(diǎn)，系統(tǒng)成本會(huì)不降反升.本研究中提到的算法不僅可以提供不同規(guī)模問題集的較優(yōu)解決方案，還可以幫助決策者確定固定案例下樞紐點(diǎn)數(shù)量的較優(yōu)選取數(shù)量與位置，功能集成化與泛用性是該算法的重要優(yōu)勢(shì).

4 結(jié) 論

(1)本研究針對(duì)兩級(jí)車輛路徑與節(jié)點(diǎn)分配問題，提出了一種雙智能集成算法，該算法能完整地求解節(jié)點(diǎn)分配與車輛路徑這一系統(tǒng)問題，保證了問題求解的完整性.

(2)通過對(duì)自適應(yīng)大鄰域搜索算法中破壞、修復(fù)算子的設(shè)計(jì)，使得每一級(jí)運(yùn)輸下每一個(gè)主節(jié)點(diǎn)的工作量都相當(dāng)，不會(huì)出現(xiàn)廢棄樞紐點(diǎn)的情況，這樣也比較符合該問題在現(xiàn)實(shí)中的應(yīng)用.隨著中國(guó)現(xiàn)代化進(jìn)程的不斷推進(jìn)，人們對(duì)不同物資的需求越來越多，需求量的敏感性也越來越強(qiáng)，這勢(shì)必帶來物流網(wǎng)絡(luò)的復(fù)雜化和多級(jí)物流網(wǎng)絡(luò)的廣泛應(yīng)用，網(wǎng)絡(luò)中不同層級(jí)的節(jié)點(diǎn)分配問題以及路徑問題是該情景下的主要問題.

(3)運(yùn)用雙智能集成算法，決策者可以在較短時(shí)間內(nèi)得到某個(gè)案例下選擇不同樞紐點(diǎn)數(shù)量對(duì)整個(gè)物流系統(tǒng)的影響并提供決策方案.從實(shí)驗(yàn)結(jié)果來看，雙智能集成算法在不同算例下都優(yōu)于本研究中給出的貪婪程式、變鄰域搜索算法，通過改變樞紐點(diǎn)數(shù)量生成多組實(shí)驗(yàn)數(shù)據(jù)得出樞紐點(diǎn)數(shù)量與總成本之間存在一定的效益悖反.