盧錦川

(廣西機(jī)電職業(yè)技術(shù)學(xué)院, 廣西 南寧 530007)

0 引言

目前物流行業(yè)對(duì)智能化的要求越來(lái)越高，通過(guò)物聯(lián)網(wǎng)融入可避免傳統(tǒng)車輛模式缺陷，物聯(lián)網(wǎng)配送車輛能夠記錄跟蹤車輛到達(dá)時(shí)間以及地理偏差等重要信息[1-2]，使得服務(wù)質(zhì)量提高，減少運(yùn)輸工程成本的增加[3]。

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

為了獲得更加理想的物聯(lián)網(wǎng)配送車輛調(diào)度方案，針對(duì)標(biāo)準(zhǔn)粒子群算法的不足，采用擾動(dòng)收縮粒子群算法(Perturbation Contraction Particle Swarm Optimization,PCPSO)，擾動(dòng)過(guò)程通過(guò)非線性控制，收縮通過(guò)加權(quán)系數(shù)進(jìn)行，并完成相關(guān)仿真內(nèi)容，以驗(yàn)證算法的有效性。

1 物聯(lián)網(wǎng)配送車輛優(yōu)化調(diào)度問(wèn)題的數(shù)學(xué)模型

每輛車上裝載電子標(biāo)簽，當(dāng)經(jīng)過(guò)讀寫器時(shí)，存儲(chǔ)在電子標(biāo)簽芯片中的車牌號(hào)信息被獲取，為后續(xù)對(duì)該車信息管理提供了保障；GPS定位對(duì)車輛定位與跟蹤；管理系統(tǒng)對(duì)實(shí)現(xiàn)本地、外地的交通路線、車輛位置和軌跡等信息的可視化，實(shí)現(xiàn)實(shí)時(shí)獲取物流配送車輛的位置、速度、載貨量、到達(dá)及離開(kāi)各配送節(jié)點(diǎn)的時(shí)間，使得車輛信息管理系統(tǒng)查看智能化；GPRS網(wǎng)絡(luò)實(shí)現(xiàn)完成車輛和各種數(shù)據(jù)網(wǎng)之間的數(shù)據(jù)傳送和格式轉(zhuǎn)換。物聯(lián)網(wǎng)配送車輛調(diào)度系統(tǒng)如圖1所示。

圖1 物聯(lián)網(wǎng)配送車輛調(diào)度系統(tǒng)Fig.1 Internet of Things distribution vehicle scheduling system

將無(wú)線數(shù)字傳輸模塊植入交通信號(hào)系統(tǒng)及聯(lián)網(wǎng)車輛，實(shí)現(xiàn)相互之間的信息傳輸，實(shí)現(xiàn)車輛與道路基礎(chǔ)設(shè)施、車輛之間的信息交換，汽車的顯示終端可作為城市道路交通導(dǎo)航系統(tǒng)使用，車輛之間可以相互提供數(shù)字化信號(hào)燈信息、位置、車速等信息，以此作為接受信息車輛安全行駛的依據(jù)。在執(zhí)行配送任務(wù)過(guò)程中，基于反映顧客需求、車輛及道路等變化情況的實(shí)時(shí)信息，對(duì)車輛運(yùn)行路重新進(jìn)行設(shè)計(jì)和優(yōu)化，形成新的調(diào)度方案并安排執(zhí)行,考慮到貨物品種及數(shù)量、需求時(shí)間和地點(diǎn)、運(yùn)輸線路以及運(yùn)輸時(shí)間的不確定性，因此從運(yùn)輸成本、時(shí)間懲罰成本、固定成本3個(gè)方面建立數(shù)學(xué)模型。

1.1 運(yùn)輸成本

(1)

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

1.2 時(shí)間懲罰成本

由于顧客對(duì)配送時(shí)效的要求越來(lái)越高，物聯(lián)網(wǎng)配送車輛在實(shí)際配送過(guò)程需要接受顧客的接收時(shí)間[14-15]，因此增設(shè)懲罰成本ζ2：

(2)

(3)

1.3 固定成本

物聯(lián)網(wǎng)配送車輛的固定成本ζ3與派遣車輛數(shù)量有關(guān)，使用較少的車輛數(shù)減少企業(yè)的固定成本。

(4)

式中，τ為單個(gè)物流配送車輛完成單次配送任務(wù)的固定費(fèi)用，包括物聯(lián)網(wǎng)器材以及使用費(fèi)、車輛保養(yǎng)費(fèi)、司機(jī)費(fèi)等；Nk為車輛k在配送過(guò)程中的客戶節(jié)點(diǎn)數(shù)量，sign(Nk)=1為車輛k被使用。

根據(jù)優(yōu)化目標(biāo)要求配送車輛總里程數(shù)為最短，并且固定成本、懲罰成本最少，則總成本最小化數(shù)學(xué)模型為：

(5)

2 隨機(jī)擾動(dòng)粒子群過(guò)程

2.1 基本粒子群算法

(6)

2.2 擾動(dòng)收縮過(guò)程

盡管傳統(tǒng)的粒子群算法可以解決非線性優(yōu)化問(wèn)題，為避免算法運(yùn)行后期易出現(xiàn)局部最優(yōu)解誤認(rèn)為全局最優(yōu)解現(xiàn)象發(fā)生，增設(shè)擾動(dòng)收縮操作。

2.2.1 擾動(dòng)操作

對(duì)基本粒子群算法增設(shè)擾動(dòng)因子δ用來(lái)平衡粒子的全局和局部搜索[17]，則粒子更新速度和位置為：

(7)

δ為一個(gè)隨機(jī)數(shù)，主要作用是控制隨機(jī)擾動(dòng)的振幅。δ值越大，粒子越具有強(qiáng)大的能力逃離當(dāng)前位置，而δ值越小，越可以提高粒子的局部搜索能力。

圖2 δ控制過(guò)程Fig.2 δ Control process

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

2.2.2 收縮操作

(8)

2.3 粒子編碼方式

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

表1 粒子編碼Tab.1 Particle coding

2.4 粒子解碼方式

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

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

把ζ作為所研究問(wèn)題的目標(biāo)函數(shù)，ζ越低越好，而粒子的適應(yīng)度值是越高越好，適應(yīng)度函數(shù)采用ζ的倒數(shù)表示。

算法流程：

① 初始化粒子的參數(shù)及迭代次數(shù)；

② 計(jì)算粒子適應(yīng)度，找出個(gè)體最優(yōu)和全局最優(yōu)值；

③ 對(duì)粒子群進(jìn)行擾動(dòng)收縮；

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

⑤ 滿足迭代次數(shù)，輸出尋優(yōu)結(jié)果，否則進(jìn)行步驟③。

3 試驗(yàn)仿真

3.1 數(shù)據(jù)來(lái)源

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

表2 貨運(yùn)量及時(shí)間窗Tab.2 Freight volume and time window

倉(cāng)庫(kù)與任務(wù)點(diǎn)以及各任務(wù)點(diǎn)之間的距離如表3所示。

表3 倉(cāng)庫(kù)與任務(wù)點(diǎn)以及各任務(wù)點(diǎn)之間的距離(單位：km)Tab.3 Distance between warehouse and each task point and distance between task points (unit:km)

3.2 結(jié)果與分析3.2.1 目標(biāo)函數(shù)優(yōu)化分析

物聯(lián)網(wǎng)配送車輛總成本是評(píng)價(jià)分析算法性能的重要指標(biāo)，對(duì)本研究涉及到的GA，AC，PSO，CQPSO，SAPSO，CMPSO以及PCPSO算法對(duì)比分析，目標(biāo)函數(shù)總成本優(yōu)化的迭代曲線如圖3(a)所示，任務(wù)目標(biāo)點(diǎn)尋優(yōu)地理位置偏差如圖3(b)所示。

圖3 目標(biāo)函數(shù)優(yōu)化分析Fig.3 Analysis of objective function optimization

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

各種算法獲得目標(biāo)函數(shù)總成本最優(yōu)時(shí)消耗時(shí)間結(jié)果對(duì)比如表4所示。

表4 目標(biāo)函數(shù)總成本最優(yōu)時(shí)消耗時(shí)間結(jié)果對(duì)比Tab.4 Comparison of time-consuming results for optimal total cost of object function

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

3.2.2 算法其他性能對(duì)比分析

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

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

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

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

4 結(jié)論

針對(duì)物聯(lián)網(wǎng)配送車輛調(diào)度過(guò)程中的效率問(wèn)題，提出了擾動(dòng)收縮粒子群算法，對(duì)成本最小化模型尋優(yōu)使得配送成本最優(yōu)，避免了運(yùn)輸成本的增加。試驗(yàn)仿真顯示本研究算法對(duì)目標(biāo)函數(shù)總成本優(yōu)化中使用最少的迭代次數(shù)即可獲得最優(yōu)值，每次試驗(yàn)的搜索成功率最低為70%，每次試驗(yàn)的違約懲罰成本占總成本比例最高為3%，是一種高效的優(yōu)化方法，為物聯(lián)網(wǎng)配送車輛調(diào)度提供了一種新方法。