基于擾動收縮粒子群算法的物聯網配送車輛調度

盧錦川

(廣西機電職業技術學院, 廣西 南寧 530007)

0 引言

目前物流行業對智能化的要求越來越高，通過物聯網融入可避免傳統車輛模式缺陷，物聯網配送車輛能夠記錄跟蹤車輛到達時間以及地理偏差等重要信息[1-2]，使得服務質量提高，減少運輸工程成本的增加[3]。

物聯網配送車輛調度要求運輸成本最優，解決方法主要有列生成法、集分割法、動態規劃法等，但是由于其計算復雜度與規模之間呈幾何級數變化關系，根本無法求得問題的最優解，不能滿足現代物聯網實際應用要求[4-5]。當前，智能優化算法具有求解效率高等優點，如遺傳算法(Genetic Algorithms,GA)[6]、蟻群算法(Ant Colony,AC)[7]、粒子群算法(Particle Swarm Optimization,PSO)等越來越受到研究者的關注[8-9]。但是在實際應用中也存在著局部搜索能力差、收斂時間過長、易陷于局部最優等問題，遺傳算法對初始種群產生十分敏感，蟻群算法易受參數影響，計算量大，粒子群算法收斂后期易陷入局部最優解。混沌量子粒子群算法(Chaotic Quantum Particle Swarm Optimization,CQPSO)應用于車輛調度問題[10]，取得了較好的效果；模擬退火粒子群算法(Simulated Annealing Particle Swarm Optimization,SAPSO)[11]，快速求得帶時間窗車輛路徑問題的優化解；柯西變異粒子群算法(Cauchy Mutation Particle Swarm Optimization,CMPSO)可應用在多車場多車型車輛路徑調度問題[12]，但是算法后期效率也比較低。

為了獲得更加理想的物聯網配送車輛調度方案，針對標準粒子群算法的不足，采用擾動收縮粒子群算法(Perturbation Contraction Particle Swarm Optimization,PCPSO)，擾動過程通過非線性控制，收縮通過加權系數進行，并完成相關仿真內容，以驗證算法的有效性。

1 物聯網配送車輛優化調度問題的數學模型

每輛車上裝載電子標簽，當經過讀寫器時，存儲在電子標簽芯片中的車牌號信息被獲取，為后續對該車信息管理提供了保障；GPS定位對車輛定位與跟蹤；管理系統對實現本地、外地的交通路線、車輛位置和軌跡等信息的可視化，實現實時獲取物流配送車輛的位置、速度、載貨量、到達及離開各配送節點的時間，使得車輛信息管理系統查看智能化；GPRS網絡實現完成車輛和各種數據網之間的數據傳送和格式轉換。物聯網配送車輛調度系統如圖1所示。

圖1 物聯網配送車輛調度系統Fig.1 Internet of Things distribution vehicle scheduling system

將無線數字傳輸模塊植入交通信號系統及聯網車輛，實現相互之間的信息傳輸，實現車輛與道路基礎設施、車輛之間的信息交換，汽車的顯示終端可作為城市道路交通導航系統使用，車輛之間可以相互提供數字化信號燈信息、位置、車速等信息，以此作為接受信息車輛安全行駛的依據。在執行配送任務過程中，基于反映顧客需求、車輛及道路等變化情況的實時信息，對車輛運行路重新進行設計和優化，形成新的調度方案并安排執行,考慮到貨物品種及數量、需求時間和地點、運輸線路以及運輸時間的不確定性，因此從運輸成本、時間懲罰成本、固定成本3個方面建立數學模型。

1.1 運輸成本

(1)

式中，λ為單位里程費用；d(i-1)i為客戶(i-1)到客戶i的距離。

1.2 時間懲罰成本

由于顧客對配送時效的要求越來越高，物聯網配送車輛在實際配送過程需要接受顧客的接收時間[14-15]，因此增設懲罰成本ζ2：

(2)

(3)

1.3 固定成本

物聯網配送車輛的固定成本ζ3與派遣車輛數量有關，使用較少的車輛數減少企業的固定成本。

(4)

式中，τ為單個物流配送車輛完成單次配送任務的固定費用，包括物聯網器材以及使用費、車輛保養費、司機費等；Nk為車輛k在配送過程中的客戶節點數量，sign(Nk)=1為車輛k被使用。

根據優化目標要求配送車輛總里程數為最短，并且固定成本、懲罰成本最少，則總成本最小化數學模型為：

(5)

2 隨機擾動粒子群過程

2.1 基本粒子群算法

(6)

2.2 擾動收縮過程

盡管傳統的粒子群算法可以解決非線性優化問題，為避免算法運行后期易出現局部最優解誤認為全局最優解現象發生，增設擾動收縮操作。

2.2.1 擾動操作

對基本粒子群算法增設擾動因子δ用來平衡粒子的全局和局部搜索[17]，則粒子更新速度和位置為：

(7)

δ為一個隨機數，主要作用是控制隨機擾動的振幅。δ值越大，粒子越具有強大的能力逃離當前位置，而δ值越小，越可以提高粒子的局部搜索能力。

圖2 δ控制過程Fig.2 δ Control process

對δ操作控制如圖2所示。在迭代前期δ值設置比較小，讓粒子主要進行局部搜索，而在后期δ值設置逐漸變大，讓粒子逃離當前位置，進行全局搜索。

2.2.2 收縮操作

(8)

2.3 粒子編碼方式

由于配送涉及到3個變量，即收貨點、物流配送車、行駛線路[18-19]，因此粒子編碼如表1所示。

表1 粒子編碼Tab.1 Particle coding

2.4 粒子解碼方式

(1)對粒子第2行的元素aij進行取整操作int(aij)，收貨點j得到分配的車輛i。

(2)對于車輛i的行駛路徑，先完成收貨點j的配送任務，然后按照收貨點j對第3行元素bij從小到大排序確定車輛i行駛路線。

把ζ作為所研究問題的目標函數，ζ越低越好，而粒子的適應度值是越高越好，適應度函數采用ζ的倒數表示。

算法流程：

① 初始化粒子的參數及迭代次數；

② 計算粒子適應度，找出個體最優和全局最優值；

③ 對粒子群進行擾動收縮；

④ 更新粒子的速度和位置，并更新歷史全局最優值；

⑤ 滿足迭代次數，輸出尋優結果，否則進行步驟③。

3 試驗仿真

3.1 數據來源

試驗設置粒子群個數為80個，最大迭代次數為200，采用Matlab進行仿真試驗。假設某企業有物聯網配送車輛3輛，需要配送客戶9個，車輛額定載質量為5 t，單位里程費用為3元，車輛的行駛時間與距離成正比，每個任務點的需求量、裝卸貨的時間以及任務點的時間窗要求如表2所示。比如任務序號1，其貨運量為3 t，配送時間為1.3 h，最早到達時間為1 h，最晚到達時間為2.5 h。

表2 貨運量及時間窗Tab.2 Freight volume and time window

倉庫與任務點以及各任務點之間的距離如表3所示。

表3 倉庫與任務點以及各任務點之間的距離(單位：km)Tab.3 Distance between warehouse and each task point and distance between task points (unit:km)

3.2 結果與分析3.2.1 目標函數優化分析

物聯網配送車輛總成本是評價分析算法性能的重要指標，對本研究涉及到的GA，AC，PSO，CQPSO，SAPSO，CMPSO以及PCPSO算法對比分析，目標函數總成本優化的迭代曲線如圖3(a)所示，任務目標點尋優地理位置偏差如圖3(b)所示。

圖3 目標函數優化分析Fig.3 Analysis of objective function optimization

從圖3(a)可以看出，各種算法都隨進化迭代次數的增加而目標函數總成本呈遞減趨勢，但是本研究PCPSO算法前期遞減速率較快，在第60次迭代時，總成本值逐漸趨于穩定，其他算法需要較多的迭代次數才能夠趨于穩定；從圖3(b)可以看出，本研究PCPSO算法對任務目標點尋優地理位置偏差值最小，避免了總成本增加。

各種算法獲得目標函數總成本最優時消耗時間結果對比如表4所示。

表4 目標函數總成本最優時消耗時間結果對比Tab.4 Comparison of time-consuming results for optimal total cost of object function

從表4可以看出，本研究PCPSO算法消耗時間少于其他算法，在處理時間上都有著明顯的提高，說明本研究PCPSO算法可以在較少的時間內獲得總成本最優化，主要是PCPSO算法通過非線性控制δ值，迭代前期讓粒子主要進行局部搜索，后期進行全局搜索，從而獲得最優結果。

3.2.2 算法其他性能對比分析

涉及到的對比算法有GA，AC，PSO，CQPSO，SAPSO，CMPSO以及本研究PCPSO算法，對每種算法均進行30次蒙特卡羅試驗。搜索成功率、違約懲罰成本占總成本比例如圖4、圖5所示。

圖4 搜索成功率Fig.4 Search success rate

圖5 違約懲罰成本占總成本比例Fig.5 Proportion of default penalty cost to total cost

從圖4可以看出，本研究PCPSO算法每次試驗的搜索成功率最高為70%，同時從圖5可以看出，本研究PCPSO算法每次試驗的違約懲罰成本占總成本比例最低為3%，說明本研究PCPSO算法具有較好的搜索成功率以及控制違約懲罰成本，主要是PCPSO算法可通過較少的迭代次數找到最優解，增強算法搜索功能，從而獲得更優的車輛配送方案。

4 結論

針對物聯網配送車輛調度過程中的效率問題，提出了擾動收縮粒子群算法，對成本最小化模型尋優使得配送成本最優，避免了運輸成本的增加。試驗仿真顯示本研究算法對目標函數總成本優化中使用最少的迭代次數即可獲得最優值，每次試驗的搜索成功率最低為70%，每次試驗的違約懲罰成本占總成本比例最高為3%，是一種高效的優化方法，為物聯網配送車輛調度提供了一種新方法。