軟時(shí)間窗和匹配運(yùn)輸下的供應(yīng)鏈配送網(wǎng)絡(luò)優(yōu)化

張 霞，張岐山

(福州大學(xué)管理學(xué)院，福建 福州 350002)

物流配送網(wǎng)絡(luò)優(yōu)化問題是物流系統(tǒng)規(guī)劃的重要課題，它涉及多個(gè)要素，包括物流中心選址、客戶需求配給和車輛路徑優(yōu)化等，屬于NP－h(huán)ard問題。國內(nèi)外學(xué)者已對物流配送網(wǎng)絡(luò)優(yōu)化問題進(jìn)行了深入細(xì)致的研究。朱戰(zhàn)國等[1]提出客戶供應(yīng)商匹配運(yùn)輸下的工廠選址問題。該匹配運(yùn)輸模式是對配送網(wǎng)絡(luò)優(yōu)化的創(chuàng)新和完善，可以大大減少供應(yīng)鏈配送網(wǎng)絡(luò)中的空車運(yùn)輸次數(shù)，從而降低供應(yīng)鏈運(yùn)營總成本。

粒子群優(yōu)化算法(particle swarm optimization，PSO)由EBERHART和KENNEDY首次提出，是一種基于群體的演化計(jì)算技術(shù)[2]。該算法具有概念簡單、易于編程、收斂速度快和不需要復(fù)雜的算子等特點(diǎn)，廣泛應(yīng)用于物流中心選址及車輛路徑優(yōu)化問題中。但是物流中心選址及車輛路徑優(yōu)化問題屬于離散組合優(yōu)化問題，而目前PSO算法一般應(yīng)用于連續(xù)空間優(yōu)化問題[3]，在離散優(yōu)化問題上的研究和應(yīng)用還很少[4]。李寧等[5]提出局部版粒子群算法，用整數(shù)編碼方式構(gòu)建了雙層粒子模型，分別采用取整和排序規(guī)范的方法，通過算例求解取得了比遺傳算法更好的效果。肖健梅等[6]設(shè)計(jì)了實(shí)數(shù)編碼方案，將車輛路徑問題轉(zhuǎn)化成準(zhǔn)連續(xù)優(yōu)化問題，并采用罰函數(shù)法處理約束條件。已有文獻(xiàn)大都采用取整方法進(jìn)行粒子更新，這種方式對于帶時(shí)間窗的VRP求解質(zhì)量不高[7]。

筆者針對客戶和供應(yīng)商匹配運(yùn)輸下的供應(yīng)鏈配送網(wǎng)絡(luò)優(yōu)化問題，建立全新的0－1整數(shù)規(guī)劃模型，采用基于整數(shù)編碼和交換序的離散粒子群優(yōu)化算法(DPSO)求解。通過算例將PSO、LPSO和DPSO算法的運(yùn)行結(jié)果進(jìn)行比較，表明離散粒子群優(yōu)化算法有較好的性能。

1 優(yōu)化問題的描述及模型的構(gòu)建

筆者研究的網(wǎng)絡(luò)由供應(yīng)和配送兩個(gè)階段構(gòu)成，優(yōu)化問題既考慮了工廠選址，又包含了工廠車輛的調(diào)度以及客戶的分配。運(yùn)輸過程將原材料采購過程和產(chǎn)品配送過程進(jìn)行匹配運(yùn)輸。假設(shè)工廠的自身車隊(duì)在最大行駛距離內(nèi)可以進(jìn)行多次運(yùn)輸，運(yùn)輸過程為整車運(yùn)輸，不考慮訂貨費(fèi)用、裝卸費(fèi)用和庫存成本。

模型中涉及的參數(shù)有:工廠集合(r∈R)，客戶集合(i∈I)，供應(yīng)商集合(j∈J)以及車輛集合(k∈K)。工廠的建設(shè)成本為gr，每輛車的固定使用成本為u，每個(gè)客戶的需求量為qi，每個(gè)供應(yīng)商的供應(yīng)能力為Qj，每個(gè)工廠的生產(chǎn)能力為Mr，車輛最大行駛距離為D，單位產(chǎn)品單位距離的車輛成本系數(shù)為 C，客戶時(shí)間窗為[ai，bi]，Sik為車輛到達(dá)客戶的時(shí)間，p為車輛在客戶點(diǎn)處等待損失的單位時(shí)間機(jī)會(huì)成本，e為車輛在要求的時(shí)間之后到達(dá)客戶點(diǎn)的罰值，drijk為車輛行駛的三角回路距離。模型中涉及的決策變量均為0－1整數(shù)變量，其中Xr=1為修建工廠r;Zrijk=1為運(yùn)輸車輛k從工廠r到客戶i，接著從客戶i到供應(yīng)商j，再從供應(yīng)商j運(yùn)送原料回到工廠r;Wrk=1為工廠r派出車輛k。根據(jù)以上描述，構(gòu)建的0－1整數(shù)規(guī)劃模型如下:

目標(biāo)函數(shù)式(1)表示工廠的選址費(fèi)用、車輛固定使用成本、運(yùn)輸費(fèi)用和違反客戶時(shí)間窗限制的懲罰成本、機(jī)會(huì)成本之和最小;約束條件式(2)表示每個(gè)開建工廠配送的產(chǎn)品總量不超過該工廠的生產(chǎn)能力;約束條件式(3)表示供應(yīng)商供應(yīng)的原材料/零部件總量不超過其供應(yīng)能力;約束條件式(4)表示每個(gè)客戶的需求被滿足;約束條件式(5)表示被工廠選中的車輛才可以用來配送產(chǎn)品和運(yùn)送原材料;約束條件式(6)表示只有開建的工廠才能派出車輛;約束條件式(7)表示車輛的最大行駛距離限制;約束條件式(8)表示客戶的時(shí)間窗限制;約束條件式(9)表示決策變量的類型和范圍均為0～1整數(shù)變量。

2 離散粒子群算法的實(shí)現(xiàn)及其求解步驟

2.1 粒子的編碼

采用整數(shù)編碼方法，每個(gè)粒子用3層來表示，第一層表示工廠編號(hào)，第二層表示供應(yīng)商編號(hào)，第三層表示車輛編號(hào)。每一列表示一個(gè)運(yùn)輸回路，Xrijk=1(i∈客戶集合)表示每個(gè)客戶的配送方案。每個(gè)粒子的位置向量可表示為 Xi(Xi1，Xi2，…，XiD)，其中維數(shù)D為客戶點(diǎn)數(shù)，i∈粒子群，每一維的元素均為整數(shù)。例如客戶點(diǎn)數(shù)為10，工廠數(shù)為6，供應(yīng)商數(shù)為8，每個(gè)工廠的車輛數(shù)為5，則一個(gè)粒子的位置編碼Xi可表示為:

從以上編碼中可以看出被選中的工廠有5個(gè)，其中工廠2未被選中;被選中的供應(yīng)商有6個(gè)，其中供應(yīng)商1和3未被選中;被選中的車輛情況如表1所示。

表1 粒子編碼對應(yīng)的工廠車輛分配情況(Zrk=1)

車輛路徑表示如下(這里列舉兩條路徑):

Z13=1:工廠1→客戶5→供應(yīng)商6→工廠1(車輛3);

Z31=1:工廠3→客戶1→供應(yīng)商2→工廠3(車輛1)。

上述第一條路徑表示車輛從工廠1出發(fā)，為客戶5配送產(chǎn)品，再到供應(yīng)商6處運(yùn)取原材料，最后回到工廠1。其余編碼的解碼類似。此外，每個(gè)粒子的速度向量可表示為 Vi(Vi1，Vi2，…，ViD)，每一維用整數(shù)表示。在算法迭代尋優(yōu)過程中，用速度向量Vi來表示每次迭代中粒子的隨機(jī)交換序。

2.2 約束條件的處理

筆者采用罰函數(shù)法來處理優(yōu)化模型中的約束條件，取一個(gè)較大的正數(shù)H作為罰系數(shù)，用H乘以違反約束的部分加到目標(biāo)函數(shù)上，如違反工廠生產(chǎn)能力約束的懲罰部分為這樣，不可行解將被賦予很大的適應(yīng)值，在迭代求解過程中，整個(gè)微粒群會(huì)逐漸收斂于可行解。

2.3 DPSO算法的求解步驟

參照文獻(xiàn)[8－10]提出的改進(jìn)微粒群優(yōu)化算法，該算法符合組合優(yōu)化問題的特點(diǎn)，其求解步驟如下:

(1)設(shè)定參數(shù)w、c1、c2和懲罰系數(shù)R。其中，c1、c2為[0，1]之間的可調(diào)參數(shù)，R 為足夠大的正整數(shù)。

(2)初始化粒子種群。給每一個(gè)粒子賦一個(gè)隨機(jī)的初始解Xid和隨機(jī)交換序Vid，其維數(shù)均等于客戶數(shù)，均由3層編碼組成。第一層的解編碼表示工廠編號(hào)，每一維隨機(jī)取1～R之間的整數(shù)，相應(yīng)的交換序編碼每一維隨機(jī)?。?R－1)～(R－1)之間的整數(shù);第二層的解編碼表示供應(yīng)商編號(hào)，每一維隨機(jī)取1～J之間的整數(shù)，相應(yīng)的交換序編碼每一維隨機(jī)?。?J－1)～(J－1)之間的整數(shù);第三層的解編碼表示車輛編號(hào)，每一維隨機(jī)取1～K之間的整數(shù)，相應(yīng)的交換序編碼每一維隨機(jī)取－(K－1)～(K－1)之間的整數(shù)。其中，R為工廠個(gè)數(shù)，J為供應(yīng)商個(gè)數(shù)，K為車輛數(shù)。

(3)用評(píng)價(jià)函數(shù)fitness評(píng)價(jià)每個(gè)粒子的適應(yīng)值，并將這個(gè)適應(yīng)值作為各粒子的個(gè)體最優(yōu)解Pid，根據(jù)個(gè)體最優(yōu)解Pid求出全局最優(yōu)解Pgd。

(4)根據(jù)粒子當(dāng)前位置Xid計(jì)算其下一個(gè)位置，即新解:

計(jì)算Pgd與之間的差根據(jù)式(12)計(jì)算，以作為新解。

(5)用評(píng)價(jià)函數(shù)fitness評(píng)價(jià)每個(gè)粒子的適應(yīng)值，并與上一代的Pid和Pgd進(jìn)行比較，如果較好，則更新 Pid和 Pgd。

(6)如未達(dá)到最大迭代次數(shù)，則返回步驟(4)。

3 算例分析

算例參照文獻(xiàn)[1]，有6個(gè)備選工廠，20個(gè)客戶，10個(gè)供應(yīng)商，每個(gè)工廠擁有5輛可選車輛。各參數(shù)服從以下均勻分布:工廠的產(chǎn)能服從U(100，500)，供應(yīng)商的供應(yīng)能力服從 U(100，400)，客戶需求量服從U(10，50)，工廠開建成本服從U(400，600)，供應(yīng)商、客戶、工廠的位置坐標(biāo)服從U(10，60)。車輛固定使用成本為50萬元/年，車輛最大行駛距離為200 km，車輛行駛速度為50 km/h，運(yùn)輸成本系數(shù)為0.1，每輛車早上6點(diǎn)從工廠出發(fā)，且均為滿載運(yùn)輸。以上均勻分布的數(shù)據(jù)如表2～表4所示。

表2 客戶的位置坐標(biāo)、需求量和時(shí)間窗上下限

表3 供應(yīng)商的位置坐標(biāo)和供應(yīng)能力

表4 各備選工廠的位置坐標(biāo)、生產(chǎn)能力(車數(shù))和建設(shè)成本

為了便于比較，PSO算法參數(shù)設(shè)置為:加速因子c1=1，c2=1，慣性權(quán)重 w=0.729，進(jìn)化代數(shù)為160，粒子規(guī)模為100，違反客戶時(shí)間窗約束、車輛最大行駛距離約束和車輛容量約束的懲罰系數(shù)R=10 000。LPSO算法參數(shù)設(shè)置為:加速因子c1=1，c2=1，c3=1，相鄰子群間重疊粒子數(shù)為 3，其他同PSO算法的設(shè)置。DPSO算法的參數(shù)設(shè)置同PSO算法參數(shù)的設(shè)置。分別將3種算法運(yùn)行20次后，對其運(yùn)行結(jié)果進(jìn)行比較分析，如表5所示。

表5 3種算法各自運(yùn)行20次后結(jié)果分析

從表5中可以看出，DPSO算法得到的最優(yōu)值平均迭代次數(shù)和平均最優(yōu)值都優(yōu)于其他兩種算法。其最優(yōu)值隨迭代次數(shù)變化圖如圖1所示。

圖1 DPSO算法最優(yōu)值隨迭代次數(shù)變化圖

其中，DPSO算法在第11次運(yùn)行時(shí)的運(yùn)行結(jié)果是最優(yōu)的，最優(yōu)值為33 302.080;最優(yōu)值對應(yīng)的粒子編碼如表6和表7所示。

表6 運(yùn)輸車輛分配及匹配情況Xrijk=1

表7 工廠車輛分配情況Zrk=1

4 結(jié)論

筆者針對匹配運(yùn)輸下的供應(yīng)鏈配送網(wǎng)絡(luò)優(yōu)化問題，在模型中加入客戶軟時(shí)間窗約束、車輛行駛距離約束和容量約束，建立全新的0－1整數(shù)規(guī)劃模型，引入基于整數(shù)編碼和交換序的離散粒子群優(yōu)化算法(DPSO)進(jìn)行求解。通過罰函數(shù)來處理約束條件，可以有效剔除不可行解。算例分析結(jié)果表明，DPSO算法能快速收斂，并能獲得較好的優(yōu)化結(jié)果。

[1] 朱戰(zhàn)國，孫林巖，吳瀛峰.基于服務(wù)距離限制和匹配運(yùn)輸?shù)墓S選址問題[J].運(yùn)籌與管理，2010，19(2):40－44.

[2] EBERHART R C，KENNEDY J.A new optimizer using particles swarm theory[C]//Proceeding of Sixth International Symposium on Micro Machine and Human Science.Nagoya:[s.n.]，1995:39 －43.

[3] EBERHART R C，SHI Y.Particle swarm optimization:developments，applications and resources[C]//Proc Congress on Evolutionary Computation 2001.Piscataway:IEEE Press，2001:81 －86.

[4] 黃嵐，王康平，周春光，等.粒子群優(yōu)化算法求解旅行商問題[J].吉林大學(xué)學(xué)報(bào):理學(xué)版，2003，41(4):477－480.

[5] 李寧，鄒彤，孫德寶.帶時(shí)間窗車輛路徑問題的粒子群算法[J].系統(tǒng)工程理論與實(shí)踐，2004，24(4):130 －135.

[6] 肖健梅，李軍軍，王錫淮.求解車輛路徑問題的改進(jìn)微粒群優(yōu)化算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2005，11(4):577－581.

[7] 馬炫，彭芄，劉慶.求解帶時(shí)間窗車輛路徑問題的改進(jìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(27):200－202.

[8] 肖健梅，李軍軍，王錫淮.改進(jìn)微粒群優(yōu)化算法求解旅行商問題[J].計(jì)算機(jī)工程與應(yīng)用，2004(35):50－52.

[9] CLERC M.Discrete particle swarm optimization illustrated by traveling salesman problem[M].Berlin:Springer－Verlag，2004:87 －98.

[10] ZHU Z G，CHU F，SUN L Y.The capacitated plant location problem with customers and suppliers matching[J].Transportation Research Part E，2010(46):469 －480.