云計算優化物流車輛路徑規劃算法

張娟萍

（山西工程科技職業大學，山西 晉中 030031）

1 引言

網絡時代電子商務的興起，帶動商品配送物流的快速發展，而待配送任務隨之逐漸呈海量的增長趨勢和發展態勢［1-2］。給傳統物流業帶來極大的沖擊，亟待探索新的配送方式以滿足實際業務需求，云計算能夠有效的將車軸在物流配送中心，收方及車輛配置等方面進行合理調試，充分利用云資源降低配送的時間和成本，提高配送效率。因此，云計算的有效利用，優化配送模式管理，合理規劃物流車路徑，對現代物流發展意義重大，成為一個研究的熱點問題［3］。

為充分發揮云計算物流業車輛管理和路徑規劃方面的優勢，文獻［4］提將交通擁堵影響作為其物流路徑優化模型的一個因素，在時變網絡下基于云計算統籌車輛安排和優化路徑，算法對規避擁堵降低成本效果較好，但是算法易收斂失衡而計算不了最優解。文獻［5］采用改進的粒子群算法迭代計算最短路徑目標函數，算法對于一定范圍內的配送車輛路徑方案效果較好，可以獲得最短路徑，但整體性能不佳，且對于擁堵時段和客戶滿意度考慮不周。文獻［6］基于云計算構建裝配調度與路徑規劃的一體模型，以全連路網代替以往單一的中心節點結構，采用多個指標對調試進行優劣評價，通過多目標優化算法進行模型求解。文獻［7］提出基于云計算的物流船運的路徑規劃，通過云端的航線整合，將客觀數據與云端聯通，并通過云端的最優路徑規劃實現航道的設計。

為此，為充分利用云計算的資源調度優勢，提出云計算下，基于改進粒子群算法的物流企業車輛最優路徑規劃算法，算法首先構建路徑規劃的多目標優化函數，然后通過改進的粒子群算法對路徑進行尋優，以提高算法的迭代收斂速度和收路徑規劃質量，實例驗證了所提算法路徑規劃上的優勢和車輛高度上的有效性。

2 物流車路徑規劃建模

高效的物流配送的提升企業效益和服務滿意度的關鍵［7］，文中路徑規劃的最終目標物流車輛通過最優高度和路徑規劃在保證客戶滿意前提下，使得配送成本和配送時間最低。當前城市物流模式通常為以中心站為圓心，配送區域為其輻射周邊，并根據密集度建立集散點和輻射小區域，為此，通常將物流配送抽像建模為中心與多輻射點的結構，基于以上考慮建立物流車的路徑規劃模型。

2.1 模型目標函數

物流車輛行駛的規劃路徑應使得整個企業的成本最低、配送速度最快，并確保貨物到達目的地的時間既定，成本分析的形式化描述為S(sh1，sh2，…，shk)，式中：shk—調度狀態，其通常由車輛標識、當前位置、目的地及運行路徑點組成，則考慮道路的時間、距離及其他費用的加權成本代價為：

式中：Price(shi)—最優路徑下將所有貨物配送完成的代價；tv—shi高度狀態下的總運輸量。在不考慮滿載與否的情況下，裝卸成本可以簡化為：

式中：k、ul(shi)—裝配與卸載車次；lp、lu—裝配與卸載一次成本。

而貨物配送的剩余時間可以簡化為：

式中：Time(shi)—配送過程中車上貨物配送完成所需時間；loɑd(shi)—配送物品總量。

tr(S)與lu(S)最優可以保證物流最低配送成本和最快配送速度，lt(S)可以確保最緊急物品被優先配送，以提高客戶滿意度，平均滿意度可以簡化為［8］：

式中：N—客戶數；ui—單個客戶的滿意度，在滿中條件0≤ti≤Ti下，其計算方式為ui(ti)=Ti-ti Ti，式中：Ti—期望最遲貨物到達時間；ti—實際到達時間。

根據以上分析，總的配送成本可以建模為：

式中：Cij—兩個收貨客戶之間距離造成的單位成本；dij—兩客戶之間的配送距離；Cf—配送過程中車輛自身消耗帶來的固有成本。

2.2 模型約束條件

在模型構建過程中，配送使用車輛需滿足載荷約束［9］和數量約束，即

而在路徑規劃高度時，需要滿足約束：

同時，由編號為k車輛完成客戶i的貨物配送，則其必須完成j的貨物配送，即有：

此外，在模型求解過程中，目標函數的迭代計算需在式（9）所示約束下取值，即：

其中，i=0，1，…，N，j=0，1，…，N且i≠j。

3 基于粒子群算法的模型求解

粒子群算法中粒子代表一個優化解，因此將粒子視為一個階段路徑，可以將粒子群算法與物流車路徑規劃聯系起來，則可以通過粒子群算法求解上述模型而獲得最優路徑。

3.1 適應度函數構造

為了對算法迭代尋優得到的路徑時行優劣評價，粒子群算法需要先構造合適的適應度函數，適應函數也是粒子更新位置和速度的依據。這里構建適應度函數為：

式中：f(d)—配送車輛的起始位置至客戶的歐氏距離；f(d′)—粒子群算法迭代過程中的總路徑長度；g1(p)、g2(p)—懲罰函數，計算式為：

式中：α、β—懲罰系數；γ—調整懲罰系數關系；ρi、θi、ρ0、θ0—路徑的極徑和極角。適應度函數構造后，隨機生成初始種群。

在適應度函數基礎上，設計粒子群算法的慣性權重和學習因子的自適應調整策略。設在第i次迭代過程時，粒子k與當次迭代過程獲得的全局最優位置之間的歐氏距離邊界值分別為Lmax和Lmin，則當距離Lij＞Lthre時，有：

式中：ωij—當次迭代粒子的慣性權重及邊界值；ωmax、ωmin—權重邊界值，式（12）表明，距離當前最優粒子越遠的粒子，其全局搜索能力越強，從而提高了潛在全局最優粒子的性，(tmax-ti)tmax保證了粒子在后期的更優搜索能力。

對于學習因子，相應的在Lij＞Lthre時，有：

式（13）表明，距離當次迭代獲得的最優粒子越遠的粒子，其在更新時更多經驗來自自身歷史經驗，而距離越近，粒子在更新時經驗來自種群的社會最優經驗。

3.2 變異操作

為避免算法迭代后期樣本多樣化受限而陷入局部最優問題，對算法進行變異操作。在多樣性降低到一定值后，對粒子進行變換，粒子多樣式采用粒子與種群中心間的距離表示，即：

式中，m、xi—粒子數量及其位置；pc—群中心位置，pc=m-1∑xi。當多樣性降低到預設閾值，即p＞pt時，對其某一維度進行變異操作，以使粒子保留一部分歷史搜索經驗。

式中：δ—變異幅值；

r—隨機數；

bmax、bmin—粒子在變異維度的邊界值；

p—變異概率；

pt—變異概率閾值。

pt值決定變異操作對粒子的影響，值越大，粒子變異可能越小，種群多樣性受限，不易跳出局部最優；值越小，粒子變異概率較大，但容易損失以往搜索經驗，而偏離全局最優值。

3.3 冗余點篩選及算法流程

當物流車可選路徑較多啊，粒子群算法會變得很復雜，參數的不同設置及迭代過程差異使得最終得到的最優路徑并非最優，存在較多的冗余點，因而需要進一步去除冗余路徑點，以使路徑最優。這里基于云計算和粒子群優化的物流車路徑規劃算法流程，如圖1所示。基于云計算的資源調試，粒子群在完成一次迭代后，先根據式（12）計算多樣性，并判斷其與閾值關系，如果p＞pt則算法進入概率變異，否則該粒子根據適應度值大小來判斷下一次迭代的保留概率，數值越，保留概率相應的越高。算法最優路徑迭代選擇完成后，進行冗余路徑的篩選，以得到最終的最優路徑。

圖1 物流車輛路徑規劃流程Fig.1 Logistics Vehicle Path Planning Process

4 仿真實驗分析

為驗證文中提出基于云計算和粒子群相結合的物流車路徑規劃算法的性能，利用matlab 2016a進行模型構建與測試分析，以Solomon benchmark中含有100個收貨客戶的C101模型算例作為實驗數據。粒子群迭代最大次數為1200，參數值取值為：δ=0.049，pt=0.75，以遺傳算法［8］和基于車聯網和云計算的物流車高度算法［11］（記為IVCCIS算法）作為路徑規劃性能比較算法，實驗中每個算法運行100次取平均值。首先分析改進算法的概率變異對粒子多樣性的影響，如圖2所示。可以看出未加入概率變異時，在迭代一定次數（300次）后，粒子的多樣性降低到接近0，且繼續迭代計算，多樣性變化不大，說明算法很容易局部最優，而在算法中加入概率變異后，粒子的多樣性一直持續到迭代終止，說明粒子在整個迭代過程中一直在進行分局搜索，有利用跳出局部最優。物流中心的倉儲能力與物流車的運輸總能力之間的比值（τ）是影響物流車輛路徑最優規劃的重要因素，這里算法與基于遺傳算法的物流車路徑規劃算法在不同的比值τ下的加權成本tr(S)的多次實驗平均值如圖3所示。可以看出文中算法計算得到的最優路徑對應的加權成本，在不同的能力比下，都取得比基于遺傳算法的算法獲得的最優路徑對應的加權成本要低，說明文中算法的路徑更優。

圖2 多樣性隨迭代次數的變化Fig.2 Diversity Changes with the Number of Iterations

圖3 不同能力比加權成本比較Fig.3 Comparison of Different Abilities than Weighted Costs

三種算法最優解平均值，如表1所示。從表1實驗結果可以看出，算法取得相同的Parto解值，均為19，在平均滿意度上，IVCCIS算法最低，主要因為其算法復雜，涉及參數調整較多，且存在較的冗余點，這從配送時間上也可以看出其時間最長，總成本上遺傳算法要高于IVCCIS算法，而從三個指標看，這里算法最優從而驗證了提出的改進物流車路徑規劃算法的良好性能。

表1 三種路徑規劃算法結果比較Tab.1 Comparison of Three Path Planning Algorithms

6 小結

基于云計算的資源高度優勢，研究了物流企業的車輛配送最優路徑規劃問題，提出了云計算條件下基于改進粒子群算法的車輛優化調試算法，算法以加權成本、裝卸成本、平均滿意度和剩余時間四個指標描述物流車輛的調度問題，并建立了多目標優化函數，通過對粒子群算法的適度函數改進、參數自適應調整和概率變異操作提高算法路徑規劃尋優能力和迭代求解速度。實驗結果驗證了所提方法的路徑規劃優勢及車輛調度上的合理性。