基于多目標混合粒子群算法的車輛路徑優(yōu)化

李琦翔,栗振鋒,李興莉

(1.太原科技大學 交通與物流學院,太原 030024;2.太原科技大學 應用科學學院,太原030024)

車輛路徑問題(Vehicle Routing Problem,VRP)于1959年由Dantzig和Ramser[1]首次提出,可描述為:已知一個配送中心和一定數(shù)量的客戶點及其地理位置、所需貨物需求量等信息,在滿足一定約束條件(如車輛數(shù)最少、路徑最短、花費時間最少,成本最低等)的前提下,規(guī)劃出一條或多條路徑來滿足客戶的需求。Savelsbergh[2]證明帶時間窗的車輛路徑問題是一個NP-hard問題,在VRP的基礎上,考慮時間窗限制,這類組合優(yōu)化問題難以在合理的時間內得到最優(yōu)解,因此學者們嘗試采用智能優(yōu)化算法求解該問題,如遺傳算法[3]、禁忌搜索算法[4]、模擬退火算法[5]等,并得到了不錯的效果。

粒子群算法(Particle Swarm Optimization,PSO)由J.Kennedy和R.C.Eberhart[6]于1995年提出的一種新的進化算法,粒子群算法模擬了鳥類種群覓食的行為,它以操作簡單、收斂速度快等優(yōu)點被人們廣泛應用于各類實際問題中。遺傳算法由John Holland教授[7]于1975年首次提出,是借鑒了生物進化規(guī)律,隨之衍生出的智能優(yōu)化算法。因其具有良好的全局尋優(yōu)能力、便于求解離散問題等特點,使得該方法得以廣泛應用。由于單個智能優(yōu)化算法解決實際問題存在一定缺陷,例如:收斂速度過快、易于陷入局部最優(yōu)等,因此學者們將兩種或多種算法相融合,設計出新的混合智能優(yōu)化算法求解各類組合優(yōu)化問題,比如廖良才等[8]將遺傳算法和節(jié)約算法融合,提出一種混合遺傳算法解決車輛調度優(yōu)化問題;徐杰等[9]提出一種混合粒子群優(yōu)化算法處理多目標離散問題;羅耀[10]將細菌覓食優(yōu)化算法與粒子群算法結合,提出一種改進的粒子群算法用于求解車輛路徑優(yōu)化問題;熊昕霞等[11]提出一種混合粒子群優(yōu)化算法解決移動機器人的路徑規(guī)劃問題。目前單目標車輛路徑優(yōu)化問題的研究較為成熟,但已有的大部分多目標優(yōu)化問題研究都是基于理想的狀態(tài)下,例如:車輛行駛速度一直處于勻速狀態(tài)、車輛行駛總成本未考慮司機所服務的客戶點數(shù)量不同等,這在實際應用中會產生較大的誤差。

針對現(xiàn)有研究存在的一些不足,本文考慮了在實際配送過程中,隨著車輛服務的客戶點數(shù)量的不同,其所產生的固定成本也產生一定的變化,以此構建了以車輛配送總成本和客戶平均滿意度為目標的多目標數(shù)學優(yōu)化模型,在文獻[12]的基礎上考慮了配送過程中車輛速度隨路況變化的因素,在不同的時間段,車輛的行駛速度不同,對于車輛配送總成本和客戶滿意度的計算更加貼合實際;將遺傳算法中的交叉和變異思想引入到基本粒子群算法中,使得粒子可以有效跳出局部最優(yōu)從而快速尋求全局最優(yōu)解,設計出一種多目標混合粒子群算法求解物流配送中的多目標路徑優(yōu)化問題。針對23條實際案例進行實驗仿真并對結果進行對比分析,驗證了該算法的有效性,具有很強的實際意義。

1 車輛路徑優(yōu)化問題模型構建

1.1 問題描述

已知一個配送中心和若干個客戶點,在配送中心和各個客戶點之間的位置坐標及所需貨物數(shù)量等信息已知的情況下,配送中心接收到客戶點下達的訂單數(shù)量,安排車輛從配送中心出發(fā),向各個客戶點配送貨物,在滿足車輛裝載能力、客戶服務時間限制等約束的前提下,設計合理的路線以達到降低配送總成本和提高客戶平均滿意度兩個目標。

1.2 模型假設

(1)物流配送中心數(shù)量單一,且配送中心的貨物數(shù)量足夠,不存在缺貨現(xiàn)象;

(2)物流配送中心具有一定數(shù)量的同種類型車輛;

(3)各個客戶點的地理位置、所需貨物數(shù)量、時間窗限制等基本信息已知;

(4)配送車輛只負責將貨物送至給顧客,不提供換貨及退貨服務;

(5)配送車輛的速度隨路況的變化而變化。

1.3 模型符號說明

G=(V,E):G為無向圖,其中V表示所有節(jié)點的集合,E表示邊集,V=D∩N,D表示配送中心,用0表示,N表示客戶點集合,N={1,2,3,…,n},則V={0,1,2,…,n};E={(i,j)|i,j∈V},(xi,yi)為客戶節(jié)點i的位置坐標;以下列出建立模型所需要的數(shù)學符號。

K:配送車輛的總數(shù),車輛k(k=1,2,…,K)

dij:客戶點i到客戶點j之間的距離

qi:客戶點i的貨物需求量

Q:配送車輛的最大裝載量

c:配送車輛的單位距離行駛成本

gk:單個車輛的指派成本

g0:點位費

α:早到的懲罰成本系數(shù)

β:晚到的懲罰成本系數(shù)

[ei,li]:客戶點i要求服務的時間窗

[Ei,Li]:客戶點i可以接受服務的最早和最晚時間窗

1.4 模型建立

綜合考慮配送總成本最低和客戶平均滿意度最大的雙目標優(yōu)化模型,其中配送總成本由運輸成本、固定成本及懲罰成本組成,運輸成本需要根據(jù)車輛的行駛距離來確定;固定成本由車輛指派成本和運輸車輛行駛的多點位費組成;且車輛提前或延遲到達客戶點會產生一定的懲罰。如圖1所示,在[ei,li]中車輛到達客戶點,不會產生懲罰,在其余時間內送達會產生相應的懲罰。

圖1 懲罰區(qū)間圖Fig.1 Punishment interval graph

在車輛配送的過程中,由于道路擁擠、突發(fā)情況等諸多因素導致車輛無法在顧客所期待的時間內到達,就會降低客戶滿意度,客戶滿意度與車輛到達時間關系如圖2所示。

圖2 客戶滿意度與時間關系圖Fig.2 Relationship between customer satisfaction and time

運輸成本C1為

(1)

固定成本C2為

(2)

懲罰成本C3為

(3)

顧客滿意度函數(shù)為

(4)

綜上所述,建立配送總成本最小和客戶滿意度最大的多目標數(shù)學模型如下:

minZ1=C1+C2+C3

(5)

(6)

約束條件:

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

其中,式(7)表示車輛k所裝載的一條路線上的客戶總需求量不得超過車輛的最大載重量;式(8)表示配送車輛從配送中心出發(fā),在完成配送任務后返回配送中心;式(9)表示到達和離開客戶點的配送車輛是同一輛;式(10)表示保證每個客戶點都被服務到且僅有一輛車為其提供服務;式(11)表示消除子回路;式(12)表示能夠提供配送服務的車輛數(shù)不得超過車輛總數(shù);式(13)表示車輛到達客戶點j的時間點;式(14)表示不同的時間段車輛的行駛速度不同;式(15)和式(16)表示決策變量。

2 多目標混合粒子群優(yōu)化算法設計

2.1 基本粒子群優(yōu)化算法

粒子群優(yōu)化算法的基本思想是模擬鳥群尋找食物,通過群體中各粒子間相互合作,尋求最優(yōu)解。粒子通過追尋個體極值Pbest和群體極值Gbest來更新個體的位置,粒子更新速度和位置遵循下列公式:

(17)

(18)

其中,Vi代表粒子的速度;Xi代表粒子的位置;ω代表初始權重,可以用來調整粒子群算法的全局和局部搜索能力,當ω的值較大時,算法的全局搜索能力較強,ω較小時,算法的局部搜索能力較強;rand()是介于(0,1)之間的隨機數(shù);c1、c2是加速度因子,一般情況下c1=c2=2.

2.2 多目標混合粒子群優(yōu)化算法

將粒子群算法和遺傳算法中的交叉和變異操作相結合,增強算法的搜索能力,防止算法易陷入局部最優(yōu)。

2.2.1 個體編碼

本文采用方便直觀的自然數(shù)編碼方式,具體方式為:在有N個客戶點的實際問題中, 0表示配送中心,自然數(shù)1,2,…,N表示各個客戶點,車輛從配送中心出發(fā),依次經(jīng)過各個有需求的客戶點,最后返回配送中心。例如在有4個客戶需求點的路徑中,其中一條配送路徑可以表示為(0,2,1,4,3),即車輛從配送中心0出發(fā),依次經(jīng)過2號客戶點、1號客戶點、4號客戶點、3號客戶點,然后返回配送中心。

2.2.2 粒子交叉

個體粒子通過和個體極值與群體極值交叉進行更新,如圖3所示,隨機選取個體粒子和個體極值粒子的交叉位置為4和7,交換這兩組粒子的位置,然后檢測粒子是否沖突,如果沖突,通過映射關系將粒子進行轉換,直至沒有沖突位置,形成新的個體粒子和個體極值粒子,通過計算適應度值,根據(jù)適應度值的大小判斷粒子的優(yōu)劣,從而保留比較優(yōu)秀的粒子。

圖3 交叉操作Fig.3 Crossover operation

2.2.3 粒子變異

變異操作即在交叉后得到的新粒子上隨機選取兩個位置進行互換。如圖4所示,隨機選取變異位置3和6進行互換得到新的粒子。

圖4 變異操作Fig.4 Mutation operation

圖5 多目標混合粒子群算法流程圖Fig.5 Multi-objective hybrid PSO flow chart

2.3 多目標混合粒子群算法流程圖

3 案例分析

基于上述算法,以某物流公司提供的城市配送信息為例,其中配送中心地理坐標為(113.832 1,34.700 393),各個客戶點的地理坐標、貨物體積、門店服務時間及可接受的服務時間窗已知,由于配送的是電子產品,車輛裝載能力根據(jù)貨物的體積進行計算,客戶點的具體信息如表1所示。

表1 客戶點具體信息

相關參數(shù)值設置為:車輛指派成本為210元/輛,車輛行駛的多點位費為40元/客戶,單位運輸成本為2.5元/km,車輛早到的懲罰成本為5元/h,晚到的懲罰成本為15元/h,若超過了客戶所能接受的最晚時間限制,懲罰成本增加至350元,配送車型為金杯車,可容納8 m3貨物。

在實際配送過程中,由于道路擁堵、突發(fā)事項等諸多不確定因素,不同時間段車輛的行駛速度不同,本文將道路交通狀態(tài)分為道路順暢時段、道路輕微擁堵時段、道路擁堵時段,具體時間段和速度值設置情況如表2所示。

表2 不同時間段的行駛速度

采用基本粒子群算法及多目標混合粒子群算法分別對上述案例在MATLAB軟件上進行實驗,為了更好的對比兩種算法的結果,將種群數(shù)量均設置為100,最大迭代次數(shù)均設置為400,分別進行計算,計算結果如表3所示,兩種算法的目標函數(shù)迭代關系如圖6和圖7所示。

表3 基本PSO和多目標混合PSO的運行結果對比

圖6 配送總成本迭代關系對比Fig.6 Total distribution cost iterative relation comparison

圖7 客戶滿意度迭代關系對比Fig.7 Customer satisfaction iterative relationship comparison

從計算結果可知,多目標混合粒子群算法的優(yōu)化結果明顯優(yōu)于基本粒子群算法,其中平均配送車輛數(shù)量相較于基本粒子群算法的優(yōu)化結果下降了20%,平均配送總成本減少了10.59%,客戶平均滿意度提高了5.30%,平均行駛總路徑長度縮短了24.73%,每輛車的平均配送量提升了4.48%,達到了降低配送總成本,提高客戶滿意度的兩個目標。

從圖6配送總成本的迭代關系圖中可以看出,基本粒子群算法迭代至約第245次時,成本函數(shù)趨于穩(wěn)定,這時的配送總成本約為2 361元;多目標混合粒子群算法迭代至約第200次時,成本函數(shù)趨于穩(wěn)定,這時的配送總成本約為2 353元;從圖7客戶滿意度迭代關系圖中可以看出,基本粒子群算法迭代至約第247次時,客戶滿意度函數(shù)趨于穩(wěn)定,這時的客戶滿意度約為0.95,多目標混合粒子群算法迭代至約第197次時,函數(shù)圖像趨于穩(wěn)定,此時的客戶滿意度為1.

從圖6和圖7兩個目標的迭代關系曲線中可以得出,多目標混合粒子群優(yōu)化算法的搜索能力和搜索精度明顯優(yōu)于基本粒子群優(yōu)化算法,基本粒子群優(yōu)化算法易于過早收斂,后期搜索能力下降,陷入局部最優(yōu),而多目標混合粒子群優(yōu)化算法可以有效跳出局部最優(yōu),從而快速尋求全局最優(yōu)解。

4 結論

本文以配送總成本最低和客戶平均滿意度最高為目標,構建了帶時間窗車輛路徑問題的多目標模型。在基本粒子群算法中引入遺傳算法的交叉和變異操作,提高算法的搜索能力和搜索精度,設計了多目標混合粒子群算法。結合23條實例對設計的算法進行實驗仿真,并與基本粒子群算法的優(yōu)化結果做對比,可以得到以下結論:

(1)采用多目標混合粒子群算法計算得到的平均配送車輛數(shù)量下降了20%、平均配送總成本減少了10.59%、客戶平均滿意度提高了5.30%、平均行駛總路徑長度縮短了24.73%、每輛車平均配送量提升了4.48%,計算結果均優(yōu)于基本粒子群算法。

(2)多目標粒子群算法相較于基本粒子群算法解的質量得到了優(yōu)化,能夠快速尋求全局最優(yōu)解,進而證明設計的多目標混合粒子群算法相較于基本粒子群算法有更好的尋優(yōu)性能,能夠有效地求解車輛路徑優(yōu)化問題。