模糊粒子群優化算法的第四方物流運輸時間優化

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

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

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

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

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

1 第四方物流運輸時間優化問題

1.1 第四方物流運輸問題

在4PL運作中，第四方物流公司通過路徑網絡圖選擇合適的路線，將貨物從起點城市運輸到終點城市。圖1為運輸路線網絡圖。

圖1 運輸路線網絡Fig.1 Transport route network

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

1.2 運輸時間優化模型

1.2.1 模型假設與符號定義

1)模型假設

①每個作業任務至多由一個代理商負責完成。

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

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

2)符號定義

作業在節點i與節點j之間選擇代理商g完成。

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

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

dij：節點i與節點j之間的距離。

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

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

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

G：代理商的個數。

N：網絡中的節點數量。

1.2.2 數學模型

2 收斂模糊粒子群優化算法

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

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

2.1 基本PSO算法求解

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

2.2 PSO算法改進策略

通過加入隸屬度函數和收斂因子來更新飛行速度與狀態。

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

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

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

2.3 適應度函數

設計罰函數來構造適應度函數：

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

2.4 CFPSO算法流程

CFPSO算法流程見圖2。

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

3 算例設計

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

3.1 算例1

運輸網絡有6個節點城市，起點城市是杭州，終點城市是淮安。有2種代理商可以承擔每段路徑具體的運輸任務，代理商的運輸能力、報價信息如表1所示，每兩個相通城市節點之間的距離如表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

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

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

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

續表4

3.3 算例3

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

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

4 實驗與結果分析

4.1 CFPSO參數設置

4.1.1 收斂因子k的確定

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

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

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

表6適應值與c1 和c2的關系Table 6 Relationshipbetweenfitnessvalues c1 andc2

4.1.2 隸屬度函數中參數 β 的確定

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

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

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

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

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

4.2 實驗結果

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

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

4.3 多種算法的對比分析

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

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

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

續表9

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

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

1)實驗結果角度

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

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

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

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

2)CPU時間角度

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

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

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

5 結束語

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