王 寧，張玉萍，趙 姣，金子陽

(長安大學(xué) 汽車學(xué)院，陜西 西安 710064)

市場全球化的今天，能否快速、準(zhǔn)確地滿足客戶的需求，越來越成為企業(yè)制勝的關(guān)鍵。現(xiàn)在企業(yè)之間的競爭，不僅僅是效益的角逐，更是供應(yīng)鏈的競爭。如今實(shí)現(xiàn)供應(yīng)鏈總體最優(yōu)已是商界、學(xué)術(shù)界的熱門話題。一直以來，物流系統(tǒng)優(yōu)化中的3個核心問題都是設(shè)施選址、庫存控制和車輛路徑安排。早期研究學(xué)者們在這3個問題上進(jìn)行研究，同時也取得了大量的成果。近些年越來越多的研究在選址?庫存?路徑問題(location-inventory-routing problem，LIRP)進(jìn)行延伸。LIRP是指考慮潛在設(shè)施點(diǎn)固定成本、庫存成本和運(yùn)輸成本的同時，明確設(shè)施位置，并確定庫存水平和配送車輛的運(yùn)輸路線。集成化物流系統(tǒng)規(guī)劃是企業(yè)管理的重要方面，也是物流系統(tǒng)規(guī)劃研究的新方向。

目前，LIRP的研究已引起國內(nèi)外學(xué)者的廣泛關(guān)注。Liu等[1]是LIRP研究較早的學(xué)者，他們在原有的單一產(chǎn)品、多節(jié)點(diǎn)選址?路徑問題的數(shù)學(xué)模型基礎(chǔ)上考慮庫存控制決策，針對模型提出兩階段的啟發(fā)式算法。在此基礎(chǔ)上，針對文獻(xiàn)[1]中算法容易陷入局部最優(yōu)的缺陷，Liu等[2]重新構(gòu)建了LIRP模型，提出一種基于模擬退火算法的全局優(yōu)化啟發(fā)式算法，對文獻(xiàn)[1]中的算法進(jìn)行改進(jìn)。Zeynep[3]對上述文獻(xiàn)研究的問題進(jìn)行擴(kuò)展，建立單一產(chǎn)品、多節(jié)點(diǎn)的LIRP模型，運(yùn)用禁忌搜索的兩階段算法來求解該問題。Shen等[4]研究隨機(jī)需求下的LIRP模型，證實(shí)集成考慮選址庫存路徑?jīng)Q策的必要性。唐瓊等[5]使用二層規(guī)劃建模方法描述LIRP，并設(shè)計(jì)雙層模擬退火算法求解。王嬋嬋[6]研究再制造閉環(huán)物流系統(tǒng)和再利用閉環(huán)物流系統(tǒng)優(yōu)化中的LIRP。趙經(jīng)緯[7]以醫(yī)療廢氣物回收為背景，針對感染性和非感染性的醫(yī)療廢氣回收建立LIRP模型。崔飛濤[8]考慮物流系統(tǒng)隨時間變化的動態(tài)情況，建立動態(tài)環(huán)境下的LIRP模型。對于帶時間窗的LIRP問題，呂飛[9]考慮備件需求的隨機(jī)性和時間的緊迫性，建立客戶需求服從泊松分布的LIRP模型，同時設(shè)計(jì)混合啟發(fā)式算法來求解該模型。唐瓊等[10]考慮到客戶對送貨時間的要求，建立帶軟時間窗的LIRP模型，并提出結(jié)合禁忌搜索算法的模擬退火算法求解該模型。呂飛等[11]考慮到備件物流系統(tǒng)優(yōu)化中時間因素的情況，分別建立考慮訂貨周期和帶軟時間窗的LIRP模型。對于帶碳排放的模型問題，曹劍東等[12]以總成本最小化為優(yōu)化目標(biāo)研究考慮碳排放因素的車輛路徑問題(vehicle routing problem，VRP)。Jemai等[13]研究最小化運(yùn)輸路徑和碳排放的多目標(biāo)VRP模型。魯建廈等[14]研究最小化成本和車輛數(shù)的VRP模型。

綜上，目前對于傳統(tǒng)LIRP問題的研究已較為全面和深入，基本涵蓋了動態(tài)車輛調(diào)度、時間窗、環(huán)境限制等多種情況，求解方法主要以啟發(fā)式算法為主。但將綠色交通、時間窗與傳統(tǒng)路徑優(yōu)化相結(jié)合的研究相對較少，且在低碳物流研究方面，我國起步比較晚。因此，綜合考慮碳排放成本和時間窗懲罰成本，與傳統(tǒng)LIRP問題相結(jié)合構(gòu)建模型。由于LIRP問題的復(fù)雜性，其求解方法主要以智能優(yōu)化算法為主，包括模擬退火和其他智能算法，如遺傳、禁忌搜索等。差分進(jìn)化算法(differential evolution algorithm，DE) 作為一種高效且功能強(qiáng)大的全局優(yōu)化算法，由Storn和Price首次提出，主要是用來求解實(shí)數(shù)優(yōu)化問題。該算法已成功應(yīng)用于各種領(lǐng)域，比如在電磁學(xué)、數(shù)據(jù)挖掘等方面都有較好的成果。DE是一種直接的、并行的、隨機(jī)的搜索方法，也是基于實(shí)數(shù)編碼的進(jìn)化算法，具有結(jié)構(gòu)簡單、收斂速度快、魯棒性強(qiáng)等特點(diǎn)。在搜索較復(fù)雜的全局最優(yōu)問題時，DE是一種有效的算法，因此本文運(yùn)用DE求解該模型。

1 問題描述與模型構(gòu)建

1.1 問題描述

本文考慮碳排放以及時間窗的LIRP問題表述如下。汽車零部件企業(yè)為位置和需求已知的客戶提供配送服務(wù)。該區(qū)域存在3個配送中心分區(qū)進(jìn)行配送，配送中心擁有的配送車輛數(shù)不限，只考慮配送中心的庫存成本，客戶要求的配送時間用模糊時間窗表示，每條線路上的配送車輛早于或晚于客戶要求的配送時間窗都會產(chǎn)生相應(yīng)的懲罰成本。根據(jù)車輛對載重以及路程的限制為配送車輛安排合適經(jīng)濟(jì)的行駛路線，目標(biāo)使總成本最小。對于多配送中心如何選擇的問題，根據(jù)客戶到達(dá)配送中心的距離，選擇路程最短的來決定由幾個配送中心進(jìn)行配送。對于客戶如何選擇的問題，根據(jù)距離最近原則，計(jì)算客戶與各配送中心的距離，該客戶離哪個配送中心最近，將其分配到哪個配送中心，由該配送中心為其提供服務(wù)。且每個配送中心的服務(wù)能力均足以滿足需求。配送中心作為車輛路徑的起點(diǎn)和終點(diǎn)，每輛車必須從一個選定的配送中心出發(fā)，并最終返回該配送中心。區(qū)域配送網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。

圖1 區(qū)域配送網(wǎng)絡(luò)示意圖Figure 1 Schematic diagram of regional distribution network

本文基于以下假設(shè)進(jìn)行研究。

1) 備選點(diǎn)為離散點(diǎn)，備選配送中心的位置已知，需求點(diǎn)的需求量已知；

2) 從生產(chǎn)中心到配送中心和配送中心到客戶的距離及單位運(yùn)價(jià)已知；

3) 每個客戶的需求必須滿足，且只能由一臺配送車輛送貨；

4) 每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離；

5) 所有運(yùn)輸車輛的規(guī)格相同，且每個線路上的運(yùn)輸由一輛車負(fù)責(zé)送貨；

6) 車輛從配送中心發(fā)出，送完貨后回到所隸屬的配送中心；

7) 不關(guān)心零部件的配送途中所發(fā)生的任何突發(fā)情形，例如整車生產(chǎn)中心的生產(chǎn)需求改變、交通管制、天氣原因等。

1.2 模型構(gòu)建

1.2.1 參數(shù)和變量說明

本文所用參數(shù)和變量說明見表1。

表1 基本模型符號及定義Table 1 Basic model symbols and definitions

1.2.2 建立模型

根據(jù)問題描述及符號說明，建立企業(yè)配送路徑多目標(biāo)優(yōu)化模型。

1) 配送中心的選址成本

2) 庫存成本

3) 配送成本

4) 綜合油耗模型

瞬時燃油消耗率 OR為

因此，總?cè)加拖牧?O等于瞬時燃油消耗率OR與運(yùn)行時間tk=d/v的乘積，即

式(7)燃油消耗量O取決于3個方面，即發(fā)動機(jī)性能、運(yùn)行速度和車輛載重。

5) 目標(biāo)函數(shù)

其中，目標(biāo)函數(shù)(8)表示成本函數(shù)，主要由選址費(fèi)用、庫存費(fèi)用、運(yùn)輸費(fèi)用、時間懲罰成本、碳排放成本5部分組成；約束(9)為決策變量的約束，保證每個客戶由一個配送中心送貨；約束(10)、(11)保證每個客戶均能被服務(wù)到，且只能由一輛車服務(wù)；約束(12)保證運(yùn)輸路線的連續(xù)性，即將貨物運(yùn)至某一點(diǎn)的車輛，必須在同一點(diǎn)離開；約束(13)為決策變量的約束；約束(14)只有被選中的配送中心才能配送貨物；約束(15)保證每條路徑上各客戶的貨物需求量之和不超過配送車輛的載重量；約束(16)為決策變量的約束；約束(17)為客戶時間窗，即客戶可接受服務(wù)的時間；約束(18)保證配送中心最大庫存量大于等于客戶總需求量；約束(19)消除子回路約束；約束(20)到達(dá)時間的約束。

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

本節(jié)將設(shè)計(jì)一個差分進(jìn)化算法來求解LIRP問題。DE是一種采用實(shí)數(shù)編碼，在連續(xù)空間中進(jìn)行隨機(jī)搜索的優(yōu)化算法。相比于其他進(jìn)化算法，DE保留了基于種群的全局搜索策略。其最大的特點(diǎn)就是變異操作是基于染色體的差異向量進(jìn)行的，即在每個新個體的生成過程中用到父代多個個體的線性組合，它的整體結(jié)構(gòu)類似于遺傳算法。為了解決帶有時間窗和碳排放的LIRP問題，提高全局搜索能力，本文對標(biāo)準(zhǔn)的差分進(jìn)化算法在變異上進(jìn)行改進(jìn)，如圖2所示。以8個客戶點(diǎn)為例，對算例進(jìn)行說明分析。

DE算法的主要算法過程主要有變異、交叉和選擇操作。通過求解 f(X1,X2,···,Xl) 的 最小值問題，Xj滿足, j=1,2,···,l，來介紹差分算法的進(jìn)化過程。

圖2 差分進(jìn)化算法流程Figure 2 Flow of differential evolution algorithm

令 Xi(t)是第t代的第i個染色體，則

其中，l是解空間的維數(shù)，即變量的個數(shù)；NP為群體規(guī)模； tmax為最大的進(jìn)化代數(shù)。

1) 生成初始種群。

種群中每個個體代表一個可行解，個體中的每一位代表了一個客戶，個體的順序代表了車輛到達(dá)每個客戶的次序。

在l維空間里隨機(jī)產(chǎn)生滿足約束條件的NP個染色體，實(shí)施措施為

首先對8個個體進(jìn)行編碼處理，采用自然數(shù)1～8分別表示8個客戶點(diǎn)，對客戶進(jìn)行隨機(jī)的排列組合，形成8位數(shù)向量的初始種群。假設(shè)產(chǎn)生的初始種群為Xi(t)為245 | 186 | 37，作為目標(biāo)向量，表示該路徑需要3輛車配送，配送順序?yàn)?-4-5，1-8-6，3-7。

2) 變異操作的改進(jìn)。

從群體中隨機(jī)選擇3個染色體Xp1,Xp2,Xp3(i ≠p1≠p2≠p3)，則標(biāo)準(zhǔn)的變異操作為

其中， Xp2j(t)?Xp3j(t) 為 差分向量； η為縮放因子，用于控制差分向量的影響力。

而改進(jìn)的變異操作，先隨機(jī)選取一個向量為Xp1(t)作為目標(biāo)向量，對目標(biāo)向量的各分矢量乘以2得到新的向量 Xp2(t)， 再隨機(jī)選取一個向量 Xp3(t)，將 Xp2(t)、 Xp3(t)相減得到Ui(t+1)。對Ui(t+1)進(jìn)行處理。具體說明如下。Xp1(t)=2 4 5 1 8 6 3 7；Xp2(t)= 4 8 10 2 16 12 6 14； Xp3(t)= 4 5 7 1 3 6 8 2；Ui( t+1)= 0 3 3 1 13 6 ?2 12。

刪除為0的分向量，大于8或者小于0的分向量則減去8或者加上8，出現(xiàn)重復(fù)分向量則留下前一位分向量，按照順序依次補(bǔ)上目標(biāo)向量中沒有出現(xiàn)的分向量，即得到新的變異向量Ui(t+1)。

修正后的變異向量Ui(t+1)=3 1 5 6 4 2 8 7。

3) 交叉操作。

交叉操作是為了增加群體的多樣性。按規(guī)則選擇目標(biāo)個體，把目標(biāo)個體與變異個體進(jìn)行參數(shù)混合產(chǎn)生實(shí)驗(yàn)個體。

其中，r and(0,1)是 [0,1]之 間的隨機(jī)小數(shù)；r and(i)是[1,l]之 間的隨機(jī)整數(shù)；CR為交叉概率，C R ∈[0,1]。

4) 選擇操作。

為了決定 Xij(t)是否成為下一代的成員，把實(shí)驗(yàn)個體 Vij(t+1)與 目標(biāo)個體 Xij(t)進(jìn)行比較。若實(shí)驗(yàn)個體的適應(yīng)度值更優(yōu)，則實(shí)驗(yàn)個體取代目標(biāo)個體，否則保留目標(biāo)個體。

反復(fù)執(zhí)行2至4操作，直至達(dá)到最大的進(jìn)化代數(shù)tmax。

3 算例分析

3.1 案例介紹

某汽車企業(yè)配送零部件，擁有1個生產(chǎn)中心和3個備選配送中心A、B、C，由配送中心向多個客戶點(diǎn)進(jìn)行配送，生產(chǎn)中心到配送中心的單位距離運(yùn)費(fèi)為20元，配送客戶的單位距離運(yùn)費(fèi)為25元，速度為40 km·h?1。建設(shè)成本為1 000元，單位庫存成本分別是10元及15元，懲罰成本分別是C1=50元；C2=60元。設(shè)定種群規(guī)模NP=100，交叉概率取值0.3，縮放因子取值0.5，最大迭代次數(shù)為500。

本文以國內(nèi)物流配送常用的江淮HFC1082KD廂式貨車為例，給出了計(jì)算式中的參數(shù)取值，如表2所示。

3.1.1 小規(guī)模算例

該算例中通過Matlab隨機(jī)生成10個坐標(biāo)點(diǎn)，其中有6個客戶點(diǎn)，3個備選配送中心，1個生產(chǎn)中心。車輛載重為2 t。隨機(jī)生成10組數(shù)據(jù)，通過Matlab與Lingo對目標(biāo)函數(shù)進(jìn)行求解，對比分析如表3所示。

設(shè)計(jì)差分進(jìn)化算法對考慮碳排放和時間窗的LIRP問題進(jìn)行求解。采用Matlab R2016a進(jìn)行編程，所有實(shí)驗(yàn)均在處理器為Windows 2.20 GHz、inter Core i5-5200U CPU、內(nèi)存為4G的電腦上進(jìn)行，并將其結(jié)果與采用Lingo11.0求解的結(jié)果進(jìn)行比較。

表2 車輛燃油消耗參數(shù)Table 2 Vehicle fuel consumption parameters

表3 實(shí)驗(yàn)數(shù)據(jù)對比Table 3 Comparison of experimental data

通過表3可以看出，DE求解的平均時間為49.88 s，與Lingo相比平均偏差均在2%以內(nèi)，其中對于算例1、3、5、6、8、10等6組算例DE均獲得了最優(yōu)解，證明本文提出的DE算法在求解該問題小規(guī)模算例時的有效性。對于小規(guī)模算例，Lingo平均求解時間達(dá)到1.5 h，對于大規(guī)模算例無法快速獲得全局最優(yōu)或者局部最優(yōu)解。因此，本文用DE算法求解大規(guī)模算例。

3.1.2 中規(guī)模算例

對于中規(guī)模算例，隨機(jī)生成23個節(jié)點(diǎn)。其中包含1個生產(chǎn)中心，坐標(biāo)為(25,30)；3個備選配送中心A、B、C，坐標(biāo)分別為(43,21)、(10,20)和(38,38)，車輛由配送中心向20個客戶點(diǎn)配送零部件，車輛載重為5 t?？蛻粜畔⒓翱蛻粜枨罅咳绫?所示。

3個備選配送中心，分別計(jì)算客戶到A、B、C、AB、AC、BC和ABC的距離，依據(jù)距離最近原則，得出選取兩兩配送中心的距離最短。因此，通過Matlab進(jìn)行求解，結(jié)果如表5所示。

從表5可知，其中配送中心A有9次得到最優(yōu)解，其成本為5 000.0元，運(yùn)行時間約為30 s，而配送中心B有4次運(yùn)行結(jié)果得到的解質(zhì)量最高，其成本為5 120.9元，總成本為10 120.9元。

表4 客戶坐標(biāo)及需求量Table 4 Customer coordinates and demand

表5 差分進(jìn)化算法求解結(jié)果Table 5 Solution results of differential evolution algorithm

同樣，分別以A、C和B、C作為配送中心，在Matlab中進(jìn)行求解，得到最優(yōu)成本分別為11 407元和10 659.7元。比較3種方案，顯然配送中心A、B成本最小，為10 120.9元。選取A、B作為配送中心。

為了便于分析，差分進(jìn)化算法的尋優(yōu)過程見圖3。

圖3 求解中規(guī)模算例算法尋優(yōu)過程Figure 3 Optimization process of scale example algorithm in solution

從圖3可以看出，在整個進(jìn)化的過程中，差分進(jìn)化算法的局部搜索能力較強(qiáng)。隨著迭代次數(shù)的增加，解的質(zhì)量越來越高。且僅需很少的迭代次數(shù)就可得到質(zhì)量較高的解，體現(xiàn)了差分進(jìn)化算法具備較好的收斂性。

路徑配送方案如表6所示，0為配送中心。

為了直觀體現(xiàn)，客戶點(diǎn)分布在一個50 km的正方形區(qū)域內(nèi)，最優(yōu)配送路線如圖4所示，點(diǎn)23為生產(chǎn)中心，點(diǎn)21、22為配送中心A、B。

3.2 結(jié)果分析

整個過程分析采用3組起始種群NP和迭代次數(shù)G：1) NP=10，G=20；2) NP=20，G=20；3) NP=100，G=200。以配送中心A為例進(jìn)行分析。

表7為NP=10時隨機(jī)產(chǎn)生的初始化種群，總配送路程最長為218.86 km，最短為145.97 km，平均為194.19 km?？偝杀咀罡邽? 610.2元，最低為5 811.77元。這些初始化種群的可行解相比上文得到的最優(yōu)解5 000元還差較遠(yuǎn)。

表8為當(dāng)NP=10時，經(jīng)過20次迭代后的可行解?？芍囕v的運(yùn)輸總里程與總成本都有了減少，最短總里程為142.96 km，平均為157.58 km，總成本最低為5 712.4元。

表9為當(dāng)NP=20時，經(jīng)過20次迭代運(yùn)行10次后的優(yōu)化解，車輛的運(yùn)輸總里程為137.08 km，運(yùn)費(fèi)為3 427.1元，總成本為5 504.8元。

表10為當(dāng)NP=100時，經(jīng)過200次迭代后運(yùn)行10次的優(yōu)化解，車輛的運(yùn)輸總里程為114.54 km，運(yùn)費(fèi)為2 863.4元，總成本為5 000元。

表11為多種群多次迭代時運(yùn)行10次得到的最優(yōu)解，通過對比可知，隨著種群的增多和迭代次數(shù)的增加，搜索結(jié)果會越來越趨向于最優(yōu)解。在考慮碳排放的情況下，目標(biāo)函數(shù)總成本隨之提高，說明低碳出行的重要性。

表6 車輛路徑配送方案Table 6 Vehicle route distribution scheme

圖4 路徑軌跡Figure 4 Path trace

表7 初始化種群(NP=10)Table 7 Initial population (NP=10)

4 結(jié)論

針對考慮碳排放和時間窗的LIRP問題，建立混合整數(shù)規(guī)劃模型，設(shè)計(jì)改進(jìn)的差分進(jìn)化算法進(jìn)行求解。針對小規(guī)模算例，通過將Lingo和DE求解結(jié)果進(jìn)行對比，驗(yàn)證模型的正確性以及算法的有效性。針對中規(guī)模問題，考慮算法中種群數(shù)與迭代次數(shù)不同對結(jié)果的影響，以及碳排放對于物流成本的影響。該問題將碳排放、時間窗考慮到LIRP的研究中，對物流配送企業(yè)實(shí)際運(yùn)作具有一定的參考價(jià)值。

表8 20次迭代后的種群(NP=10)Table 8 Population after 20 iterations (NP=10)

表9 20次迭代后的種群(NP=20)Table 9 Population after 20 iterations (NP=20)

表10 200次迭代后的種群(NP=100)Table 10 Population after 200 iterations (NP=100)

表11 多次迭代后最優(yōu)解對比Table 11 Comparison of optimal solutions after multiple iterations

在實(shí)際的配送企業(yè)，客戶的需求大多是不確定的，而且隨著低碳生活的不斷滲透，在未來的LIRP問題研究中，將考慮動態(tài)情況和無人車配送情況。在算法方面，雖然DE算法在求解全局最優(yōu)問題時有明顯的優(yōu)勢，但是隨著迭代次數(shù)的增加，各個體之間的差異化逐漸縮小，導(dǎo)致后期收斂速度變慢。因此，將針對算法上進(jìn)一步改進(jìn)，更好地解決LIRP問題。