模糊粒子群優(yōu)化算法的第四方物流運輸時間優(yōu)化

盧福強，劉婷，杜子超，畢華玲，黃敏

（1. 燕山大學 經(jīng)濟管理學院，河北 秦皇島 066004; 2. 東北大學 信息科學與工程學院，遼寧 沈陽 816819）

隨著信息技術(shù)的發(fā)展，很多制造型企業(yè)將物流業(yè)務(wù)外包給第三方物流代理商(third party logistics, 3PL)，由他們承擔倉儲、運輸?shù)热蝿?wù)。對于一些大型企業(yè)，多元化、國際化的趨勢逐漸增強，供應鏈策略的設(shè)計、優(yōu)化要與企業(yè)的競爭策略相輔相成，考慮內(nèi)外環(huán)境因素的影響，這一問題已然成為一個規(guī)模龐大、構(gòu)造復雜的系統(tǒng)工程[1]。但是3PL只承擔實際的物流操作業(yè)務(wù)，在資源配置、統(tǒng)籌規(guī)劃、集成技術(shù)、綜合技能等方面存在一定的局限性，無法實現(xiàn)整個物流系統(tǒng)的優(yōu)化[2]。美國埃森哲(Accenture)咨詢公司在1996年最先提出了第四方物流(fourth party logistics, 4PL)的概念[3]，4PL是在3PL的基礎(chǔ)上發(fā)展起來的，通過集合資源、技術(shù)、能力來構(gòu)建一套完整的供應鏈解決方案[4]。與3PL相比，4PL具備獲取資源和協(xié)調(diào)規(guī)劃的能力[5]。企業(yè)將供應鏈的整體優(yōu)化外包給4PL，4PL通過一系列的考察、分析、規(guī)劃、設(shè)計，將具體的物流作業(yè)外包給3PL，進一步提升物流運輸?shù)男?，同時使企業(yè)能夠?qū)⒆陨淼馁Y源用于其核心業(yè)務(wù)[6]。

4PL具有明顯的優(yōu)勢，在物流領(lǐng)域中起到舉足輕重的作用，得到了國內(nèi)外學者的廣泛研究。同時，4PL也面臨著巨大挑戰(zhàn)，歸結(jié)起來可分為2個方面：1)黃敏等[7]提出4PL如何激勵3PL提高物流服務(wù)質(zhì)量并降低配送過程中的風險問題；2)如何對資源進一步整合優(yōu)化使得3PL在可以接受的配送成本條件下提高物流服務(wù)質(zhì)量，使得3PL切實感受到4PL的加入可以使它們能夠?qū)⒆陨碣Y源用于其核心業(yè)務(wù)。因此，考慮在委托商可接受的最大成本約束下，提高加入4PL后的3PL的物流服務(wù)質(zhì)量具有重要研究價值。本文對4PL的路徑優(yōu)化問題進行研究，縮短配送時間，提高物流服務(wù)質(zhì)量。關(guān)于4PL的運輸路徑優(yōu)化問題，綜合考慮3PL的能力、信譽、轉(zhuǎn)運時間及運輸成本等因素的影響，如黃敏等[7]充分考慮不確定環(huán)境的影響，將3PL代理商的配送時間設(shè)定為不確定變量，建立了4PL路徑規(guī)劃模型，并采用多種改進的遺傳算法進行求解；崔研等[8]考慮中轉(zhuǎn)發(fā)車時間，以運輸時間為約束條件，以總成本最小為目標函數(shù)，建立了基于一點到多點的多任務(wù)第四方物流路徑優(yōu)化模型，并設(shè)計蟻群優(yōu)化算法求解模型；薄桂華等[9]將嵌入刪除算法和聲搜索算法兩階段算法，用于加快求解帶時間窗約束的4PL路徑優(yōu)化問題的運行時間；王勇等[10]考慮了時間和風險因素的約束，研究多任務(wù)、多代理商的4PL作業(yè)整合優(yōu)化，采用柔性禁忌算法求解模型[10]；崔研等[11]結(jié)合模糊的轉(zhuǎn)運時間和最小的成本約束，研究多點到單點的4PL路徑優(yōu)化問題，設(shè)計文化基因算法求解模型；陳建清等[12]建立了賦予多維權(quán)的有向圖模型，描述第四方物流中路徑優(yōu)化、3PL代理商選擇等問題，并提出基于Dijkstra算法的求解方法。對于4PL的路徑優(yōu)化問題，既要考慮委托商提出的成本約束，又要滿足客戶對運輸時間的期望。同時，由于運輸環(huán)境的不確定性，各個3PL代理商運輸能力的不同，城市節(jié)點中存在的轉(zhuǎn)運時間，4PL路徑優(yōu)化已然成為一個復雜、影響因素相互制約的系統(tǒng)工程問題。在一定的成本預算約束下，如何設(shè)計運輸路徑，選擇合適的3PL代理商，形成一套完整的供應鏈解決方案以實現(xiàn)客戶期望的時間，已經(jīng)成為4PL亟待解決、不斷優(yōu)化的問題。

本文針對4PL運作中的運輸時間優(yōu)化問題，建立了4PL運輸時間優(yōu)化模型。引入收斂因子和隸屬度函數(shù)，對基本粒子群優(yōu)化算法(particle swarm optimization, PSO)進行改進，設(shè)計收斂模糊粒子群優(yōu)化算法(convergence fuzzy particle swarm optimization, CFPSO)對4PL運輸時間優(yōu)化問題進行求解。通過3個規(guī)模逐漸增大的算例對CFPSO算法的性能進行驗證，并且將實驗結(jié)果與基本PSO、枚舉算法(enumeration algorithm, EA)、遺傳算法(genetic algorithm, GA)和量子粒子群優(yōu)化算法(quantum-behaved particle swarm optimization,QPSO)對本問題的求解結(jié)果進行比較分析。

1 第四方物流運輸時間優(yōu)化問題

1.1 第四方物流運輸問題

在4PL運作中，第四方物流公司通過路徑網(wǎng)絡(luò)圖選擇合適的路線，將貨物從起點城市運輸?shù)浇K點城市。圖1為運輸路線網(wǎng)絡(luò)圖。

圖1 運輸路線網(wǎng)絡(luò)Fig.1 Transport route network

圖1中的每個節(jié)點表示一個城市，節(jié)點1表示起點，節(jié)點6表示終點。在物流運輸路線上，每兩個連通的節(jié)點之間有2個備選的代理商，分別是代理商a和代理商b。本文考慮在一定的運輸成本約束下，通過選擇最佳路徑和合適的代理商，實現(xiàn)整體物流作業(yè)運輸時間最短的目標。

1.2 運輸時間優(yōu)化模型

1.2.1 模型假設(shè)與符號定義

1)模型假設(shè)

①每個作業(yè)任務(wù)至多由一個代理商負責完成。

②本問題是單任務(wù)問題，且只有一個起點和一個終點。

③從出發(fā)點運送到終點的過程中，任務(wù)需要完成的總運輸量不會改變。

2)符號定義

作業(yè)在節(jié)點i與節(jié)點j之間選擇代理商g完成。

Q：從配送起點到配送終點需要被配送的總運量。

Qg：代理商g能夠承擔的最大運量。

dij：節(jié)點i與節(jié)點j之間的距離。

代理商g在節(jié)點i與節(jié)點j之間單位運輸距離、單位運載量的運輸成本。

代理商g在節(jié)點i與節(jié)點j之間運輸單位運量貨物的運輸時間。

C：委托人能夠承擔的最大運輸成本。

G：代理商的個數(shù)。

N：網(wǎng)絡(luò)中的節(jié)點數(shù)量。

1.2.2 數(shù)學模型

2 收斂模糊粒子群優(yōu)化算法

4PL運輸時間優(yōu)化問題的自變量眾多，且對算法的運行時間和運行結(jié)果的精度要求高，因此采用PSO算法進行求解。PSO算法是一種模擬自然界鳥類覓食過程的生物啟發(fā)式算法[12-13]。PSO初始化為一群隨機粒子，這些粒子在搜索空間中4處移動來尋找問題最佳的解。Shi等[14]引入慣性權(quán)重的概念，被大家認為是標準的粒子群優(yōu)化算法。

模糊粒子群優(yōu)化算法(fuzzy particle swarm optimization, FPSO)[15]通過改變影響粒子飛行速度、方向的狀態(tài)更新公式，保持了種群的活躍度，使得算法的精確度大大提升。但是，F(xiàn)PSO需要較長的收斂時間。為了縮短收斂時間，可以引入收縮因子，形成收斂粒子群優(yōu)化算法(convergence particle swarm optimization, CPSO)，相關(guān)實驗表明此舉可以大大提升整個種群的收斂速度[16]。本文考慮吸收FPSO和CPSO的長處，將隸屬度函數(shù)和收縮因子引入PSO的速度更新公式，從而設(shè)計收斂模糊粒子群優(yōu)化算法(convergence fuzzy particle swarm optimization, CFPSO)。CFPSO不僅可以保證算法的收斂速度，加快全局收斂，還能豐富種群的多樣性，減小搜索粒子陷入局部最優(yōu)的概率，提升算法的整體運算精確度，涵蓋了眾多改進PSO算法的優(yōu)勢與特點。

2.1 基本PSO算法求解

將基本的PSO算法應用到第四方物流運輸時間控制問題中，在編碼方面，每個粒子被設(shè)定為一個備選方案，搜索空間的維數(shù)為運輸問題中的城市個數(shù)，粒子的位置狀態(tài)信息即是從起點城市向終點城市運輸貨物的路徑。因此，本文采用多進制的編碼方式，0表示運輸路徑不經(jīng)過該城市，1表示運輸路徑經(jīng)過該城市且選擇1號代理商承擔此段運輸任務(wù)，2、3等數(shù)字與上述意義相同；在初始化種群方面，采用隨機初始化的方式，若有兩個代理商可供選擇，則粒子每一維搜索空間的初始位置在0、1、2中隨機產(chǎn)生。第一維與最后一維空間除外，因為這兩維代表的是運輸路線的起點城市與終點城市，粒子的位置在1、2中隨機選取。在選擇策略方面，采取優(yōu)勝劣汰的選擇策略。首先，將粒子當前的適應值與自身歷史最優(yōu)值得出的適應值進行比較，若當前的適應值優(yōu)于自身歷史最優(yōu)值，則更新該粒子的個體歷史最優(yōu)值。然后，對所有粒子的個體歷史最優(yōu)值進行比較，擇優(yōu)選取當代全局最優(yōu)值，若優(yōu)于原值，則進行更新，否則進入下次循環(huán)，并且以最大迭代次數(shù)為終止條件。

2.2 PSO算法改進策略

通過加入隸屬度函數(shù)和收斂因子來更新飛行速度與狀態(tài)。

式中： ω為慣性權(quán)重，在[0,1]之間取值，用來衡量粒子i保留上一次迭代速度的大小， ω 越大，本次迭代速度與上一次的迭代速度越接近；c1為自我學習因子；c2為社會學習因子，是兩個常量，使粒子具有自我總結(jié)和向群體中優(yōu)秀個體學習的能力；r1和r2是兩個在0～1取值的隨機數(shù)；k為收斂因子； φ (h) 為隸屬度函數(shù)。

式(6)為粒子的速度更新公式，式(8)是粒子的位置更新公式[16]。隸屬度表示為一個模糊變量，本文基于Bell函數(shù)建立隸屬度函數(shù)[17]，如式(9)所示：

式中：f(pg) 表示由全局最優(yōu)粒子的位置計算得來的適應值，即最小的運輸時間；f(ph) 表示某粒子的鄰居粒子的適應值；β 是一個常數(shù)。由式(9)可以看出，該鄰居粒子的適應值越接近于全局最優(yōu)的適應值，所對應的模糊隸屬度就越大，對該粒子的影響程度就越大，反之亦然。這樣粒子就能夠更加充分、合理地利用周圍若干鄰居粒子的優(yōu)點。

2.3 適應度函數(shù)

設(shè)計罰函數(shù)來構(gòu)造適應度函數(shù)：

式中：w1、w2、w3都為懲罰項的系數(shù)。

2.4 CFPSO算法流程

CFPSO算法流程見圖2。

圖2 CFPSO的流程Fig.2 Solution procedeure of the CFPSO

3 算例設(shè)計

本節(jié)給出3個不同規(guī)模的算例，某物流公司承擔運量為100 t的運輸任務(wù)，在3個規(guī)模不同的運輸網(wǎng)絡(luò)中，要求給出在不同的運輸成本約束下最小的運輸時間、運輸路線方案。

3.1 算例1

運輸網(wǎng)絡(luò)有6個節(jié)點城市，起點城市是杭州，終點城市是淮安。有2種代理商可以承擔每段路徑具體的運輸任務(wù)，代理商的運輸能力、報價信息如表1所示，每兩個相通城市節(jié)點之間的距離如表2所示。

表1 算例1代理商運輸信息Table 1 Details of the transportation agency in case 1

表2 算例1城市間距離Table 2 Distances between cities in case 1 km

3.2 算例2

運輸網(wǎng)絡(luò)有12個節(jié)點城市，起點城市是杭州，終點城市是石家莊。有3種代理商可以承擔每段路徑具體的運輸任務(wù)，代理商的運輸能力、報價信息如表3所示，每兩個相通城市節(jié)點之間的距離如表4所示。

表3 算例2代理商運輸信息Table 3 Details of the transportation agency in case 2

表4 算例2城市間距離Table 4 Distances between cities in case 2 km

續(xù)表4

3.3 算例3

運輸網(wǎng)絡(luò)有18個節(jié)點城市，起點城市是杭州，終點城市是石家莊。每兩個相通城市節(jié)點之間的距離如表5所示，有3種代理商可以承擔每段路徑具體的運輸任務(wù)，代理商的運輸能力、報價信息和算例2中相同。

表5 算例3城市間距離Table 5 Distances between cities in case 3 km

4 實驗與結(jié)果分析

4.1 CFPSO參數(shù)設(shè)置

4.1.1 收斂因子k的確定

為了確定收斂因子k的最優(yōu)取值，以算例3為例，進行數(shù)值仿真實驗，設(shè)委托商提出的最大成本約束為100 000元，種群由20個粒子構(gòu)成，每個粒子有18維搜索空間，代表著18個城市節(jié)點，以算法循環(huán)迭代100次為停止準則。c1和c2分別在[1,6]和[0,6]之間取值，將最小運輸時間作為粒子的適應值。圖3是2種學習因子的取值組合對適應值的影響。

圖3 學習因子對適應值的影響Fig.3 Influence of learning factors on fitness value

可以看出，隨著c1和c2取值組合的不同，測試函數(shù)的適應值存在一定的波動性，但以上的兩個二維曲面圖的大致趨勢基本相同，當c1和c2都接近于2時，適應值即最小的運輸時間明顯小于其他取值范圍輸出的結(jié)果。

表6適應值與c1 和c2的關(guān)系Table 6 Relationshipbetweenfitnessvalues c1 andc2

4.1.2 隸屬度函數(shù)中參數(shù) β 的確定

本節(jié)仿真實驗參數(shù) β 取值為0～100，跨度為0～0.5的離散點，仍以算例3為例，設(shè)最大成本約束為100 000元，種群由20個粒子構(gòu)成，每個粒子有18維搜索空間，以循環(huán)迭代100次為停止準則，計算最小的運輸時間。實驗結(jié)果如圖4所示。

圖4 參數(shù) β 對適應值的影響Fig.4 Influence of β on fitness value

從圖4中可以看出，隨著參數(shù) β 的不斷變化，適應值以40為基準呈現(xiàn)上下波動，當β∈[26,29]時，結(jié)果最好。將 β 取值為整數(shù)，分別令 β=26、27、28、29，計算最小運輸時間，得到的結(jié)果如圖5所示。

圖5 參數(shù) β 對適應值的影響Fig.5 Influence of β on fitness value

從圖5可以看出，當 β =28 時，在各個最大運輸成本條件的約束下，CFPSO算法得到的運輸時間最小，隸屬度函數(shù)中的參數(shù) β 取值為28。

4.2 實驗結(jié)果

為了說明問題這里僅給出算例3的實驗結(jié)果，見表7。從實驗結(jié)果可以看出：1)隨著運輸成本約束的增加，負責每段路徑的代理商在不斷地變化，最小運輸時間也逐漸減少，通過不同的成本約束來控制貨物的運輸時間；2)委托商給出的整個運輸方案的成本預算越多，CFPSO算法運行出的最佳運輸路徑越傾向于選擇速度快的代理商承擔運輸任務(wù)，即花更多的錢來實現(xiàn)運輸時間的最優(yōu)化。

表7 實驗結(jié)果(算例3)Table 7 Experimental results (case 3)

4.3 多種算法的對比分析

為了驗證CFPSO算法的性能，本節(jié)采用枚舉算法(EA)、基本PSO算法、GA算法和量子粒子群優(yōu)化(QPSO)算法[18-25]求解上述3個算例，并從最小運輸時間、CPU時間等方面進行對比分析。各算例實驗結(jié)果的對比分別列于表8、9、10中。

表8 各算法運行結(jié)果(算例1)Table 8 Results obtained from the algorithm (case 1)

表9 各算法運行結(jié)果(算例2)Table 9 Results obtained from the algorithm (case 2)

續(xù)表9

表10 各算法運行結(jié)果(算例3)Table 10 Results obtained from the algorithm (case 3)

綜合以上5個算法對3個算例的實驗結(jié)果，可以得出以下結(jié)論：

1)實驗結(jié)果角度

當算例的規(guī)模比較小時，如算例1，根據(jù)5個算法得到的平均運輸時間的優(yōu)劣性，如圖6所示，可以將算法按照收斂能力排序為：QPSO>EA>CFPSO>GA>基本PSO。當算例的規(guī)模增大時，如算例2，如圖7所示算法收斂能力排序為：CFPSO=EA=GA>基本PSO>QPSO。當算例規(guī)模很大時，如算例3，EA已經(jīng)不能在可接受的時間內(nèi)運行出結(jié)果，如圖8所示，其他4種算法的收斂能力排序為： CFPSO>GA>基本PSO>QPSO。

圖6 算例1實驗結(jié)果對比Fig.6 Comparison of experimental results in case 1

圖7 算例2實驗結(jié)果對比Fig.7 Comparison of experimental results in case 2

圖8 算例3實驗結(jié)果對比Fig.8 Comparison of experimental results in case 3

2)CPU時間角度

隨著3個算例規(guī)模的逐漸增大，算法程序的復雜度也顯著增加，在這里將城市個數(shù)、代理商個數(shù)這兩個變量的乘積作為各算例程序的時間復雜度，即T(mn)=O(n2),m是代理商的個數(shù)，n是城市的個數(shù)。算例1、2和3的時間復雜度分別為12、36、54。從圖9中可以看出，隨著各算例運輸方案個數(shù)的增加，EA算法的運行時間呈現(xiàn)快速增長的趨勢，相比之下，基本PSO算法和GA算法的增長速度適中，QPSO算法的CPU運行時間較為緩慢，CFPSO算法的增長速度則最為緩慢?？梢?，CFPSO算法中收斂因子加快程序運行的作用比較明顯，隨著程序復雜度的增加，CFPSO算法的運行時間始終小于其他3種算法，具有一定的穩(wěn)定性?？蓪?種算法的運行速度進行以下的排序： CFPSO>QPSO>GA>基本PSO>EA。

圖9 各算法運行時間對比分析Fig.9 Comparison of the algorithm’s run time

綜上所述，CFPSO、QPSO、GA、基本PSO和EA求解本優(yōu)化問題時各有優(yōu)劣。針對第四方物流運輸時間控制問題，選取最適合的求解算法應從實驗結(jié)果、CPU時間這兩個方面來衡量。通過以上的分析，可以將這4種算法的性能進行排序：CFPSO>GA>QPSO>基本PSO>EA。

5 結(jié)束語

本文針對第四方物流運輸時間優(yōu)化問題，建立了數(shù)學模型，設(shè)計了收斂模糊粒子群優(yōu)化算法，設(shè)計了多個算例進行實驗分析。實驗結(jié)果分析表明，建立的數(shù)學模型合理，能夠輔助決策，提供滿足運輸成本和運輸時間要求的決策方案。所設(shè)計的收斂模糊粒子群優(yōu)化算法與枚舉算法、基本粒子群優(yōu)化算法、遺傳算法和量子粒子群優(yōu)化算法相比具有更好的收斂能力和更快的收斂速度，能夠有效地解決第四方物流運輸時間優(yōu)化問題，具備可行性。