唐志強(qiáng)，李 銳

遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001

在現(xiàn)代物流配送系統(tǒng)的構(gòu)建中，如何構(gòu)建高效、綠色、可靠的配送網(wǎng)絡(luò)來(lái)降低物流成本，減少環(huán)境污染和提高安全性對(duì)于物流系統(tǒng)可持續(xù)發(fā)展至關(guān)重要。合理的配送中心選址和車輛路徑規(guī)劃對(duì)于物流配送系統(tǒng)的有效運(yùn)作和降低物流成本具有重要作用。由于單獨(dú)考慮選址問(wèn)題和車輛路徑問(wèn)題都很難達(dá)到全局優(yōu)化的效果，而集成的選址-路徑規(guī)劃問(wèn)題（LRP）同時(shí)包括戰(zhàn)略和戰(zhàn)術(shù)層面，能夠?qū)崿F(xiàn)整體優(yōu)化。目前，國(guó)內(nèi)外學(xué)者對(duì)LRP問(wèn)題進(jìn)行了廣泛的研究。

近年來(lái)，隨著環(huán)境污染的加劇，一種“低能耗、低排放”的綠色物流受到了廣泛的關(guān)注。Dukkanci等[1]首次將低碳路徑與低碳選址相結(jié)合，提出了最小化碳排放的選址-路徑問(wèn)題模型；Toro等[2]研究了多目標(biāo)綠色選址-路徑問(wèn)題，建立了最小化燃油消耗及總成本的多目標(biāo)混合整數(shù)線性規(guī)劃模型；Wang等[3]研究了綠色、帶時(shí)間窗的取貨和派送兩階段選址-路徑問(wèn)題，并設(shè)計(jì)一個(gè)基于拉格朗日松弛的啟發(fā)式算法來(lái)求解模型；趙燕偉等[4]提出了一種綜合考慮多車型和同時(shí)取送貨的低碳選址-路徑問(wèn)題，并構(gòu)建三維指數(shù)混合整數(shù)規(guī)劃模型，同時(shí)設(shè)計(jì)一種進(jìn)化式超啟發(fā)式算法進(jìn)行求解；Zhang等[5]研究了帶時(shí)間窗的時(shí)間依賴綠色選址路徑問(wèn)題，并設(shè)計(jì)了一種兩級(jí)超啟發(fā)式算法進(jìn)行求解。

在現(xiàn)實(shí)世界中，客戶的需求可能是模糊的或者不確定。Nadizadeh等[6]于2013年首次提出建立需求不確定的選址-路徑問(wèn)題模型并對(duì)其進(jìn)行求解；Ghaffari-Nasab等[7]研究了模糊選址路徑問(wèn)題，并設(shè)計(jì)了一種混合模擬退火算法進(jìn)行求解；Nadizadeh等[8]應(yīng)用螞蟻算法求解能力受限和模糊需求的選址-路徑問(wèn)題；Pekel等[9]設(shè)計(jì)一種結(jié)合可變鄰域搜索和進(jìn)化局部搜索的啟發(fā)式搜索算法，解決了模糊需求的選址-路徑問(wèn)題。

在實(shí)際的物流配送過(guò)程中，由于供求關(guān)系和外部環(huán)境因素的影響，客戶需求、配送中心和運(yùn)輸路徑的可靠性在各個(gè)運(yùn)營(yíng)周期可能不同，因此考慮多周期選址路徑問(wèn)題更符合現(xiàn)實(shí)。Wang等[10]針對(duì)兩級(jí)多周期選址路徑問(wèn)題，建立了一個(gè)最小化總成本和車輛數(shù)量的多目標(biāo)LRP模型，并設(shè)計(jì)了一種兩階段混合算法來(lái)求解；Cheng等[11]在災(zāi)后垃圾清理任務(wù)中引入了多周期雙梯度選址-路徑問(wèn)題，建立了最小化成本和清理時(shí)間的LRP模型，并用改進(jìn)的遺傳算法進(jìn)行求解；Saffarian等[12]針對(duì)災(zāi)后救助工作，考慮了一個(gè)包含災(zāi)害管理周期的多目標(biāo)LRP模型，同時(shí)使用全局性準(zhǔn)則方法將其轉(zhuǎn)化為單目標(biāo)進(jìn)行求解。

總的來(lái)說(shuō)，目前關(guān)于LRP問(wèn)題的研究已經(jīng)取得了大量的成果。與現(xiàn)有的研究相比，本文在LRP問(wèn)題的研究中同時(shí)考慮了不確定、可靠性、多周期和綠色四個(gè)因素，并基于模糊可信度理論建立了問(wèn)題模型。此外，本文對(duì)基本的遺傳算法進(jìn)行了改進(jìn)，設(shè)計(jì)了一種混合遺傳算法HGA，實(shí)驗(yàn)表明該算法能在有限的時(shí)間內(nèi)提供較優(yōu)的結(jié)果。

1 問(wèn)題描述及模型建立

物流配送網(wǎng)絡(luò)如圖1所示，包括候選配送中心、運(yùn)輸車輛、客戶和運(yùn)輸線路。運(yùn)輸車輛從配送中心出發(fā)，按照規(guī)劃的配送線路依次服務(wù)該線路上的所有客戶，最后返回對(duì)應(yīng)的配送中心。

圖1 物流配送網(wǎng)絡(luò)Fig.1 Logistics distribution network

模型假設(shè)條件如下：

（1）候選配送中心的數(shù)量、位置、開設(shè)成本、運(yùn)營(yíng)成本、能力及其在各個(gè)周期的可靠性已知；

（2）車輛的數(shù)量、固定運(yùn)營(yíng)成本、運(yùn)輸能力、單位距離運(yùn)輸成本和單位距離折舊成本已知，并且每輛車只能從一個(gè)配送中心出發(fā)，最終回到該配送中心；

（3）客戶的數(shù)量、位置和需求已知，并考慮需求為模糊變量；

（4）每個(gè)客戶的需求最多由一輛車服務(wù)一次；

（5）任意兩點(diǎn)之間的距離及其在各個(gè)周期的可靠性已知；

（6）單位燃油成本已知。

考慮模糊需求的多周期可靠性綠色LRP問(wèn)題是指通過(guò)開設(shè)配送中心和規(guī)劃各個(gè)周期的車輛運(yùn)輸路徑來(lái)最小化物流配送成本和燃油消耗成本，同時(shí)滿足各周期內(nèi)車輛運(yùn)輸路徑的可靠性及模糊需求約束。

1.1 符號(hào)說(shuō)明

模型符號(hào)定義如下：I表示候選配送中心集合，J表示客戶集合，K表示車輛集合，T表示周期集合。OCi、MCi、Ui和Rti分別表示配送中心i∈I的開設(shè)成本、運(yùn)營(yíng)成本、能力及其在周期t∈T的可靠性；Hk、Pk、TCk和DCk分別表示車輛k∈K的固定運(yùn)營(yíng)成本、運(yùn)輸能力、單位距離運(yùn)輸成本和單位距離折舊成本；Dsl和rstl分別表示任意兩點(diǎn)s∈M和l∈M之間的距離及其在周期t∈T的可靠性，M=I?J；表示客戶j∈J在周期t∈T的 需 求，且為 三 角 模 糊 數(shù)Fuel表示單位燃油成本。

決策變量定義如下：xtslk∈{0,1}，如果周期t∈T車輛k∈K從s∈M到l∈M，則xtslk取值為1，否則取值為0；yitk∈{0,1}，如果周期t∈T車輛k∈K分配給配送中心i∈I，則yitk取1，否則yitk取0；zi∈{0,1}，如果配送中心i∈I開設(shè)，則zi取值為1，否則zi為0。

引入如下輔助變量：f stlk≥0表示在周期t∈T車輛k∈K在點(diǎn)s∈M和點(diǎn)l∈M之間的運(yùn)輸量。

1.2 優(yōu)化模型

基于以上符號(hào)和變量的定義，建立考慮模糊需求的多周期綠色選址-路徑問(wèn)題模型如下：

目標(biāo)函數(shù)（1）為最小化總成本，包括配送中心的開設(shè)成本及各個(gè)周期內(nèi)配送中心的運(yùn)營(yíng)成本、車輛的固定運(yùn)營(yíng)成本、車輛的運(yùn)輸成本、燃油消耗成本；其中，F(xiàn)stlk表示周期t車輛k在點(diǎn)i和點(diǎn)j之間的運(yùn)輸油耗，計(jì)算詳見(jiàn)1.3節(jié)；式（2）為車輛路徑的可靠性約束，γ表示要求的可靠性水平；式（3）表示每個(gè)周期內(nèi)車輛與配送中心的分配關(guān)系；約束（4）表示未開設(shè)的配送中心在各個(gè)周期內(nèi)都沒(méi)有車輛駛出；約束（5）表示開設(shè)的配送中心必須有車輛駛出；式（6）表示在每個(gè)周期內(nèi)每輛車從一個(gè)點(diǎn)駛?cè)耄仨氁獜脑擖c(diǎn)駛出；式（7）避免客戶之間形成子環(huán)路；式（8）保證配送中心之間沒(méi)有車輛路徑；式（9）表示在每個(gè)周期內(nèi)每輛車輛至多服務(wù)于一個(gè)配送中心；式（10）表示在每個(gè)周期內(nèi)每個(gè)客戶最多只能由一輛車服務(wù)；式（11）表示在每個(gè)周期內(nèi)車輛能力的機(jī)會(huì)約束，α1表示要求的置信水平；式（12）表示每個(gè)周期內(nèi)配送中心能力的機(jī)會(huì)約束，α2表示要求的置信水平；式（13）和（14）保證客戶點(diǎn)兩端的流量平衡；式（15）~（17）為二值變量約束；式（18）為產(chǎn)品運(yùn)輸量的非負(fù)約束。

1.3 油耗計(jì)算

車輛在運(yùn)輸過(guò)程中，裝載量和行駛距離等因素都會(huì)影響燃油消耗。本文采用文獻(xiàn)[13]的方法來(lái)計(jì)算油耗，運(yùn)輸車輛的燃油消耗量F可按照式（19）進(jìn)行計(jì)算：

其中，G為道路坡度因子；D為車輛的行駛距離；f為載貨量；a和b分別為燃油消耗參數(shù)。

基于以上油耗計(jì)算方法，周期t內(nèi)車輛k在點(diǎn)s∈M和點(diǎn)l∈M之間的油耗為：

據(jù)此，燃油消耗成本可按如下計(jì)算：

當(dāng)xtslk=1，?s∈M,?l∈J,?k∈K,?t∈T時(shí)，表示周期t內(nèi)的車輛k經(jīng)過(guò)s和l之間線路，由約束（6）可得，根據(jù)文獻(xiàn)[14]則有：

對(duì)于?s∈I,?l∈J,?k∈K,?t∈T，當(dāng)xtslk=1時(shí)，根據(jù)式（7）可推出，則有：

莫莉在克里斯蒂娜不提防時(shí)向她的側(cè)身踢了一腳，克里斯蒂娜后背著地癱在那里?？吹竭@兒，艾爾突然松開手，把我拉到他身邊緊緊地靠著。我咬緊牙不想哭出來(lái)。第一天晚上，雖然我對(duì)艾爾的哭泣無(wú)動(dòng)于衷，但我還不是鐵石心腸的人。此時(shí)此刻，看著克里斯蒂娜痛苦地捂著胸肋，我真想沖上去擋在她們中間。

1.4 模糊機(jī)會(huì)約束的清晰化

2 算法設(shè)計(jì)

由于經(jīng)典LRP問(wèn)題是NP-hard問(wèn)題，而考慮模糊需求的多周期綠色選址-路徑問(wèn)題是經(jīng)典LRP問(wèn)題的擴(kuò)展問(wèn)題，也屬于NP-hard問(wèn)題，因此設(shè)計(jì)啟發(fā)式算法對(duì)該問(wèn)題進(jìn)行求解。

遺傳算法（GA）作為經(jīng)典的啟發(fā)式算法，已經(jīng)在組合優(yōu)化領(lǐng)域取得了較好的成果。本文采用整數(shù)編碼，針對(duì)本文問(wèn)題的特點(diǎn)，設(shè)計(jì)了一種混合進(jìn)化算法HGA進(jìn)行求解。在該算法中，優(yōu)化了交叉算子和設(shè)計(jì)了兩階段變異操作，提高了算法的搜索能力。

2.1 算法的主要步驟

HGA算法的主要步驟如下：

步驟1按照2.2節(jié)中編碼方法隨機(jī)初始化種群；

步驟2對(duì)個(gè)體進(jìn)行解碼，并計(jì)算個(gè)體適應(yīng)值（詳見(jiàn)2.2）；

步驟3更新全局最優(yōu)解；

步驟4判斷是否滿足終止條件，如果滿足，輸出最優(yōu)解并結(jié)束運(yùn)行，否則，繼續(xù)運(yùn)行；

步驟5基于輪盤賭選擇法進(jìn)行選擇操作；

步驟7個(gè)體變異（詳見(jiàn)2.4節(jié)），然后返回步驟2。

算法的具體流程如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flowchart

2.2 個(gè)體的編碼與解碼

本文采用整數(shù)向量對(duì)個(gè)體進(jìn)行編碼。向量由三個(gè)部分組成，第一部分表示客戶的服務(wù)順序，第二部分表示客戶所屬的車輛，第三部分表示車輛所屬的配送中心。假設(shè)當(dāng)前有5個(gè)客戶、3輛車和2個(gè)配送中心，則編碼如圖3所示。

圖3 個(gè)體編碼Fig.3 Individual code

在圖3中，根據(jù)第二部分可知，客戶1和4由車輛1服務(wù)，客戶2和3由車輛2服務(wù)，客戶5由車輛3服務(wù)。由第三部分知車輛1和2屬于配送中心1，車輛3屬于配送中心2，再結(jié)合第一部分客戶的服務(wù)順序即可確定所有每輛車的行駛路徑。

對(duì)于解碼得到的車輛路徑，首先檢測(cè)是否滿足本文問(wèn)題模型中的所有約束條件，如果不滿足，則無(wú)需通過(guò)式（1）計(jì)算最終結(jié)果，直接設(shè)為一個(gè)極大值，否則通過(guò)式（1）計(jì)算最終的成本。

2.3 交叉操作

采用部分映射交叉方法，個(gè)體通過(guò)與全局最優(yōu)個(gè)體交叉來(lái)更新。如圖4所示，首先在編碼的每個(gè)部分都選擇兩個(gè)交叉位置，然后將個(gè)體與全局最優(yōu)解交叉得到新個(gè)體。

圖4 交叉操作Fig.4 Cross operation

在遺傳算法早期階段，交叉概率較小，可以提高全局搜索能力；在后期階段，交叉概率較大，可以提高局部搜索能力，本文采用以下方法優(yōu)化交叉算子。

其中，Pc表示交叉概率；Gen和MAXGEN分別表示當(dāng)前迭代次數(shù)和最大迭代次數(shù)；Pcmin和Pcmax分別表示最小交叉概率和最大交叉概率。

2.4 變異操作

變異操作分為兩個(gè)階段，低概率的變異操作1用于保持種群的多樣性，高頻率的變異操作2用于擴(kuò)展算法的搜索空間。變異方法1采用個(gè)體內(nèi)部?jī)晌换Q方法。如圖5所示，在編碼的每個(gè)部分都隨機(jī)選擇兩個(gè)變異位置，然后把這兩個(gè)變異位置的值互換。

圖5 變異操作1Fig.5 Mutation operation 1

變異操作2如圖6所示。在編碼的第一部分，采用個(gè)體內(nèi)部?jī)晌换Q的方法，在編碼的第二部分隨機(jī)地選取一個(gè)位置，然后在1到最大車輛數(shù)量之間隨機(jī)地獲取一個(gè)整數(shù)來(lái)替換該位置的數(shù)值，編碼的第三部分更新操作與第二部分更新類似。

圖6 變異操作2Fig.6 Mutation operation 2

3 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證模型的合理性和HGA算法的有效性，對(duì)隨機(jī)產(chǎn)生的不同規(guī)模的算例進(jìn)行測(cè)試。所有算法均采用Matlab編程實(shí)現(xiàn)，且實(shí)驗(yàn)環(huán)境為AMD Core i5 2.4 GHz CPU，內(nèi)存16 GB RAM，操作系統(tǒng)Windows 10。

3.1 參數(shù)設(shè)置

表1給出不同算例的規(guī)模，包括配送中心的數(shù)量、客戶數(shù)量、車輛數(shù)量和周期數(shù)量。算例的參數(shù)設(shè)置如下：配送中心的坐標(biāo)和客戶點(diǎn)的坐標(biāo)均在[?100，100]之間隨機(jī)生成；車輛的運(yùn)輸能力Pk為900，固定運(yùn)營(yíng)成本Hk取值為1 200，每公里折舊成本DCk為0.28，單位距離運(yùn)輸成本TCk為1；配送中心的能力Ui為[2 000，3 000]之間的隨機(jī)值，開設(shè)成本OCi取值范圍為[10 000，15 000]、運(yùn)營(yíng)成本MCi取值范圍為[4 000，6 000]，在各個(gè)周期的可靠性Rti為[0.9，1]之間的隨機(jī)值；客戶的需求，其中p1tj在[100，120]之間隨機(jī)取值，在[120，140]之間隨機(jī)取值，p3t j在[140，160]之間隨機(jī)取值；任意兩點(diǎn)之間線路在各個(gè)周期的可靠性ritj為[0.9，1]之間的隨機(jī)值；單位燃油成本Fuel取值為7.99；道路坡度因子G取值為1；燃油消耗系數(shù)和b分別取值為0.006 208和0.212 5[13]。種群數(shù)量為20，迭代次數(shù)為300。

表1 算例規(guī)模Table 1 Case scale

3.2 算法性能分析

為了驗(yàn)證HGA算法的有效性，對(duì)算例I1~I5進(jìn)行求解，并將結(jié)果與標(biāo)準(zhǔn)GA算法以及優(yōu)化DE算法[15]進(jìn)行比較。對(duì)于所有算例，置信水平α1和α2設(shè)置為0.5，可靠性水平γ設(shè)置為0.3。其中，HGA算法的參數(shù)設(shè)置為交叉概率最大值0.9、最小值0.1，變異概率為0.05、0.9；GA算法的參數(shù)設(shè)置為交叉概率0.9、變異概率0.05；DE算法的參數(shù)設(shè)置為參照文獻(xiàn)[15]。

對(duì)于每個(gè)算例，每種算法分別運(yùn)行10次。表2給出幾種算法求解的最優(yōu)值、最差值、平均值、平均偏差率及平均CPU時(shí)間的比較。由表2可見(jiàn)，對(duì)于不同規(guī)模的算例，HGA算法的最優(yōu)值、平均值、最差值、平均偏差率和運(yùn)行時(shí)間均優(yōu)于GA算法和優(yōu)化DE算法。其中，從平均偏差率來(lái)看，HGA算法的變化范圍為0.045 4~0.096 1，而GA算法為0.384 4~0.604 5，DE算法為0.2~0.313 0，可見(jiàn)HGA算法的平均偏差率明顯優(yōu)于其他算法。綜上可見(jiàn)，HGA算法能夠?qū)Σ煌?guī)模問(wèn)題有效求解。

表2 不同規(guī)模算例下HGA與GA、DE結(jié)果對(duì)比Table 2 Comparison of results of HGA，GA and DE under different scale calculation examples

為了驗(yàn)證置信水平α1和α2以及可靠性水平γ對(duì)算法性能和求解結(jié)果的影響，對(duì)算例I3進(jìn)行測(cè)試。其中，α1和α2在0.1~0.95范圍內(nèi)取值，γ在0.1~0.7范圍內(nèi)取值。對(duì)于不同置信和可靠性取值，每種算法分別求解10次。表3給出不同置信水平和可靠性下幾種算法性能的比較。由表中數(shù)據(jù)可知，對(duì)于不同可靠性水平和置信水平，HGA算法仍然能保持穩(wěn)定，并且求解效果優(yōu)于GA和DE。

表3 不同置信水平和可靠性水平下算法性能比較Table 3 Comparison of algorithm performance under different confidence levels and reliability levels

3.3 模型參數(shù)分析

為了研究置信水平α1、α2和γ對(duì)總成本的影響，對(duì)算例I3進(jìn)行測(cè)試，具體分析不同置信水平和可靠性水平對(duì)總成本的影響。其中可靠性水平γ在0.1~0.7范圍內(nèi)取值，α1和α2在0.1~1.0范圍內(nèi)取值。由表4可知，對(duì)于一定的α2和α1值，隨著γ值的增加，使用車輛的數(shù)量和運(yùn)輸距離增加，導(dǎo)致運(yùn)輸費(fèi)用、車輛固定成本、油耗成本和車輛折舊成本增加，并最終導(dǎo)致總成本的增加；對(duì)于一定的γ值，隨著置信水平α2和α1的增加，配送中心的開設(shè)成本、車輛的固定成本、運(yùn)輸成本、油耗成本以及車輛折舊成本單調(diào)遞增。

表4 不同置信水平和可靠性水平下算例I3的詳細(xì)結(jié)果Table 4 Detailed results of example I3 under different confidence levels and reliability levels

4 結(jié)束語(yǔ)

本文對(duì)基本的選址路徑問(wèn)題進(jìn)行了拓展，考慮包含模糊需求、多周期、可靠性和綠色的選址-路徑問(wèn)題，并建立了相應(yīng)的優(yōu)化模型，同時(shí)設(shè)計(jì)了一個(gè)混合的遺傳算法對(duì)模型進(jìn)行求解。在該算法中，使用自適應(yīng)參數(shù)替代固定值參數(shù)和增加了一個(gè)高頻率變異操作，在保持種群多樣性的同時(shí)擴(kuò)展了算法的搜索空間。最后，將HGA算法、GA算法和DE算法分別應(yīng)用到求解不同規(guī)模算例的仿真實(shí)驗(yàn)中，結(jié)果表明了HGA算法在不同規(guī)模的算例中均優(yōu)于GA算法和DE算法。本文最后分析了不同置信水平和可靠性水平對(duì)總成本的影響，結(jié)果表明置信水平和可靠性水平都會(huì)對(duì)總成本造成較大的影響。