云計算優(yōu)化物流車輛路徑規(guī)劃算法

張娟萍

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

1 引言

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

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

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

2 物流車路徑規(guī)劃建模

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

2.1 模型目標函數(shù)

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

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

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

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

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

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

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

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

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

2.2 模型約束條件

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

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

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

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

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

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

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

3.1 適應(yīng)度函數(shù)構(gòu)造

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

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

式中：α、β—懲罰系數(shù)；γ—調(diào)整懲罰系數(shù)關(guān)系；ρi、θi、ρ0、θ0—路徑的極徑和極角。適應(yīng)度函數(shù)構(gòu)造后，隨機生成初始種群。

在適應(yīng)度函數(shù)基礎(chǔ)上，設(shè)計粒子群算法的慣性權(quán)重和學習因子的自適應(yīng)調(diào)整策略。設(shè)在第i次迭代過程時，粒子k與當次迭代過程獲得的全局最優(yōu)位置之間的歐氏距離邊界值分別為Lmax和Lmin，則當距離Lij＞Lthre時，有：

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

對于學習因子，相應(yīng)的在Lij＞Lthre時，有：

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

3.2 變異操作

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

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

式中：δ—變異幅值；

r—隨機數(shù)；

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

p—變異概率；

pt—變異概率閾值。

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

3.3 冗余點篩選及算法流程

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

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

4 仿真實驗分析

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

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

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

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

表1 三種路徑規(guī)劃算法結(jié)果比較Tab.1 Comparison of Three Path Planning Algorithms

6 小結(jié)

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