基于粒子群算法的農(nóng)產(chǎn)品物流車輛路徑問題

文/朱利

引言

由于生鮮農(nóng)產(chǎn)品具有易腐和易損的特殊性，為了保證農(nóng)產(chǎn)品的品質(zhì)以及新鮮度，減少農(nóng)產(chǎn)品的變質(zhì)損壞率，需要將農(nóng)產(chǎn)品快速送到客戶手中，這使得在農(nóng)產(chǎn)品物流車輛路徑問題中對運(yùn)輸時間、運(yùn)輸距離的要求非常高。Dantzig和Ramser[1]1959年首次提出車輛路徑問題（VRP），研究了如何調(diào)度配送車輛使得車輛行駛的總距離最短。Clarke和Wright[2]將車輛調(diào)度問題推廣到物流運(yùn)輸中的優(yōu)化問題.隨著研究的不斷深入，衍生了帶時間窗的車輛路徑問題（VRPTW）的研究，Solmon[3]在1986年對VRPTW 進(jìn)行了問題描述，構(gòu)建了該問題的數(shù)學(xué)模型并完成了問題求解。VRPTW 在實(shí)際問題中表示每個客戶都有一定的接受服務(wù)的時間要求，車輛服務(wù)此客戶在其要求的時間范圍內(nèi)，否則客戶不接受服務(wù)或會產(chǎn)生一定的時間（懲罰）成本[4]。本文在農(nóng)產(chǎn)品物流車輛路徑問題研究中，考慮客戶服務(wù)時間窗，構(gòu)建了物流配送總成本最小化的優(yōu)化模型，并運(yùn)用粒子群算法求解該模型，最后通過實(shí)例驗(yàn)證了模型和算法的有效性，對農(nóng)產(chǎn)品物流車輛路徑優(yōu)化提供了參考和決策支持。

1.問題描述

農(nóng)產(chǎn)品對物流的時效性有著嚴(yán)苛的要求，帶時間窗的農(nóng)產(chǎn)品物流車輛路徑問題可以描述為：K輛農(nóng)產(chǎn)品物流配送車輛從同一配送中心出發(fā)，對屬于配送范圍的客戶需求點(diǎn)進(jìn)行配送，在滿足客戶需求及服務(wù)時間窗的前提下，考慮農(nóng)產(chǎn)品物流配送車輛的容量限制，以農(nóng)產(chǎn)品物流配送總成本（配送車輛的租賃成本、配送成本、違反時間窗懲罰成本）最小化為目標(biāo)，對農(nóng)產(chǎn)品物流配送車輛路徑優(yōu)化，進(jìn)而降低農(nóng)產(chǎn)品物流配送成本。

2.模型構(gòu)建

2.1 符號說明

I={i｜i=1，2，3，…，n}表示客戶點(diǎn)集合；I0表示配送中心和客戶點(diǎn)集合；K={k|k=1，2，3，…，v}表示農(nóng)產(chǎn)品物流配送車輛集合；Nk表示農(nóng)產(chǎn)品物流配送車輛k服務(wù)客戶點(diǎn)集合；|Nk|表示農(nóng)產(chǎn)品物流配送車輛k服務(wù)客戶的數(shù)量；Qk表示農(nóng)產(chǎn)品物流配送車輛最大裝載量；qi表示客戶i的需求量，且qi≤Qk；[ei，li]表示客戶i的服務(wù)時間窗；atik表示農(nóng)產(chǎn)品物流配送車輛k到達(dá)節(jié)點(diǎn)i的時間；dtik表示農(nóng)產(chǎn)品物流配送車輛k離開節(jié)點(diǎn)i的時間；ttik表示農(nóng)產(chǎn)品物流配送車輛從客戶i到客戶j的行駛時間；α 表示農(nóng)產(chǎn)品物流配送車輛早到的單位時間懲罰系數(shù)，β 表示表示農(nóng)產(chǎn)品物流配送車輛晚到的單位時間懲罰系數(shù)；dij表示客戶i到j(luò)的配送距離；ck表示農(nóng)產(chǎn)品物流配送車輛k單位距離行駛成本；δk表示農(nóng)產(chǎn)品物流配送車輛的租賃成本；NN表示一個足夠大的正數(shù)。xijk為0-1變量，如果農(nóng)產(chǎn)品物流配送車輛k從客戶i行駛到客戶j時等于1，否則等于0；yik為0-1變量，如果客戶由農(nóng)產(chǎn)品物流配送車輛服務(wù)是等于1，否則等于0。

2.2 數(shù)學(xué)模型

本文以總配送成本最小為優(yōu)化目標(biāo)，其中，包括配送車輛的租賃成本、配送成本和違反時間窗懲罰成本。農(nóng)產(chǎn)品物流配送優(yōu)化模型如下：minZ=TC+FC+PC

TC：農(nóng)產(chǎn)品物流配送車輛將農(nóng)產(chǎn)品送達(dá)客戶的配送成本

FC：農(nóng)產(chǎn)品物流配送車輛的租賃成本

PC：農(nóng)產(chǎn)品物流配送車輛違反客戶服務(wù)時間窗的懲罰成本

式（1）表示每個客戶只能被一輛農(nóng)產(chǎn)品物流配送車服務(wù)；式（2）表示農(nóng)產(chǎn)品物流配送車輛將農(nóng)產(chǎn)品送達(dá)客戶后必須離開；式（3）表示消除農(nóng)產(chǎn)品物流配送線路上的子回路約束；式（4）表示產(chǎn)品物流配送車輛的容量約束；式（5）和式（6）農(nóng)產(chǎn)品物流配送車輛到達(dá)客戶的時間；式（7）和式（8）表示農(nóng)產(chǎn)品物流配送車輛離開和到達(dá)配送中心的時間在配送中心的服務(wù)時間窗內(nèi)；式（9）和式（10）表示變量約束。

3.粒子群算法

粒子群優(yōu)化算法是由Kennedy和Eberhart[5]在1995年提出的一種基于群體智能優(yōu)化算法，實(shí)質(zhì)是模仿鳥群覓食的行為，通過個體間的協(xié)作與競爭來搜索最優(yōu)解。粒子群算法將每個粒子的行為規(guī)則設(shè)定為類似鳥類運(yùn)動的簡單的行為規(guī)則，從而是粒子群的運(yùn)動表現(xiàn)出與鳥類迷失行為相類似的特性，每一個個體將自身所學(xué)習(xí)到的知識或經(jīng)驗(yàn)與種群中其他的個體共享，同時也獲得其他個體的經(jīng)驗(yàn)，并基于這些信息不斷地調(diào)整自己的行為模式。粒子群算法的思路是將研究問題的解空間作為鳥群的飛行空間，根據(jù)問題的不同約束條件，限制解空間的范圍，解空間的每一個點(diǎn)都代表問題的一個可行解，食物則是接空降中最優(yōu)解的位置。每個粒子都有決定飛行方向和距離的速度，粒子根據(jù)自身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)來調(diào)整飛行，用適應(yīng)值來評價粒子當(dāng)前位置的好壞。整個優(yōu)化的過程與鳥群在整個解空間中尋找食物的過程類似，粒子們追尋當(dāng)前的最優(yōu)粒子在解空間中搜尋。每個粒子都具有記憶個體歷史最優(yōu)位置的能力，且粒子與粒子之間的信息能夠共享，這樣就可以實(shí)現(xiàn)種群中每一個個體的自我學(xué)習(xí)和相互學(xué)習(xí)，利用個體最優(yōu)信息和種群最優(yōu)信息進(jìn)行種群的迭代來實(shí)現(xiàn)問題的優(yōu)化求解。

3.1 相關(guān)變量定義及公式

相關(guān)的定義和符號定義如下：

np：粒子群優(yōu)化過程中使用的粒子數(shù)。

c1和：c2粒子群算法中使用的加速系數(shù)。

w1和：w2粒子群算法中使用的慣性因子。

pbesth（t）：粒子群優(yōu)化算法中迭代次數(shù)為t的粒子h的個體最佳位置。

gbesth（t）：粒子群優(yōu)化算法中迭代次數(shù)為t的粒子h的個體最佳位置。

完成配送服務(wù)的粒子群的速度和位置更新的公式如下：

其中，c1和：c2是兩個加速度，rand（t）表示介于0到1之間的隨機(jī)數(shù)，fix（t）表示每個粒子的位置是一個整數(shù)，Vn表示配送服務(wù)允許的最大速度，randint[0，Tn']表示0或Tn'的整數(shù)，其中Tn'表示配送服務(wù)所需物流設(shè)施的數(shù)量。

3.2 步驟及實(shí)現(xiàn)過程

Step1：算法初始化。在[0，Tn']內(nèi)隨機(jī)生成粒子的位置矢量，在[-Vn，Vn]內(nèi)隨機(jī)生成粒子的速度矢量，并設(shè)置迭代次數(shù)run=1；

Step2：計(jì)算粒子適應(yīng)度值，并找到個體最優(yōu)pbesth（t）和全局最優(yōu)gbesth（t）；

Step3：按式（9）和式（10）更新粒子的速度和位置

Step4：計(jì)算粒子適應(yīng)度值

Step5：對所有粒子，若其當(dāng)前適應(yīng)度優(yōu)于其歷史最優(yōu)適應(yīng)度，則將當(dāng)前位置設(shè)置為該粒子的歷史最優(yōu)位置，然后更新全局最優(yōu)。

Step6：如果達(dá)到最大迭代次數(shù)run_max，則循環(huán)完成；否則，返回Step3。

4.算例分析

4.1 算例相關(guān)數(shù)據(jù)

為驗(yàn)證模型與算法的有效性，以重慶市某農(nóng)產(chǎn)品物流配送中心（DC）及其服務(wù)的35個客戶點(diǎn)（C1-C50）為例進(jìn)行研究，相應(yīng)的地理位置分布如圖所示。根據(jù)已有相關(guān)文獻(xiàn)[6，7]和實(shí)例數(shù)據(jù)規(guī)模，設(shè)置相應(yīng)參數(shù)為：Qk=200，δk=100，ck=3，α=10，β=25，np=100，run_max=，c1=c2=2。

4.2 結(jié)果與分析

運(yùn)用粒子群算法求解農(nóng)產(chǎn)品物流配送車輛路徑優(yōu)化問題，得到農(nóng)產(chǎn)品物流配送車輛優(yōu)化方案：農(nóng)產(chǎn)品物流配送車輛1的配送路線為DC→C33→C3→C19→C25→C31→C28→DC，農(nóng)產(chǎn)品物流配送車輛2的配送路線為DC→C1→C17→C34→C29→C2→DC，農(nóng)產(chǎn)品物流配送車輛3的配送路線為DC→C27→C5→C9→C13→C23→C10→C21→DC，農(nóng)產(chǎn)品物流配送車輛4的配送路線為DC→C12→C30→C11→C20→C15→C7→DC，農(nóng)產(chǎn)品物流配送車輛5的配送路線為DC→C26→C14→C16→C6→C18→DC，農(nóng)產(chǎn)品物流配送車輛6的配送路線為DC→C35→C32→C4→C22→C24→C8→DC。農(nóng)產(chǎn)品物流配送車輛路徑優(yōu)化前，車輛使用數(shù)為8，車輛租賃成本為800元，配送成本為2258元，違反時間窗懲罰成本為254元，物流配送總成本為3312元。農(nóng)產(chǎn)品物流配送車輛路徑優(yōu)化后，車輛使用數(shù)為6，車輛租賃成本為600元，配送成本為1463元，違反時間窗懲罰成本為28元，物流配送總成本為2091元。應(yīng)用粒子群算法優(yōu)化后的農(nóng)產(chǎn)品物流配送方案相比優(yōu)化前的配送方案，農(nóng)產(chǎn)品物流配送車輛使用數(shù)節(jié)省了25%，農(nóng)產(chǎn)品物流配送車輛租賃成本節(jié)省了25%，違反時間窗懲罰成本減少了88.98%，農(nóng)產(chǎn)品物流配送成本減少了35.21%，農(nóng)產(chǎn)品物流配送總成本節(jié)約了36.87%。

5.結(jié)論

本文研究了帶時間窗的農(nóng)產(chǎn)品物流車輛路徑優(yōu)化問題，考慮農(nóng)產(chǎn)品物流配送車輛的容量限制和客戶不同的服務(wù)時間窗進(jìn)行合理的農(nóng)產(chǎn)品物流配送路線優(yōu)化，建立了包含農(nóng)產(chǎn)品物流配送車輛的租賃成本、配送成本和違反時間窗懲罰成本的農(nóng)產(chǎn)品物流配送總成本最小化的目標(biāo)優(yōu)化模型，并運(yùn)用粒子群算法求解該模型，最后結(jié)合重慶市某農(nóng)產(chǎn)品物流配送中心的實(shí)際配送數(shù)據(jù)，通過求解該模型，進(jìn)一步驗(yàn)證所提模型與算法的可行性。計(jì)算結(jié)果表明，相對于農(nóng)產(chǎn)品物流配送車輛路徑優(yōu)化前，優(yōu)化后的農(nóng)產(chǎn)品物流配送車輛路徑優(yōu)化方案的物流配送總成本和車輛使用數(shù)分別減少了35.21%和25%，違反時間窗懲罰成本降低了88.98%。研究結(jié)果表明對農(nóng)產(chǎn)品物流配送車輛進(jìn)行合理的路徑優(yōu)化，能減少農(nóng)產(chǎn)品配送的運(yùn)輸距離和運(yùn)輸時間，降低農(nóng)產(chǎn)品配送的物流總成本。

引用出處

[1]Dantzig G B,Ramser JH.The truck dispatching problem［J］.Management Science,1959,6(1):80-91

[2]Clarke G,Wright JW.Scheduling of Vehiclesfrom a Central Depot to a Number of Delivery Points[J].Operations Research,1964,12(4):568-581.

[3]Solmon MM.Algorithm for the Vehicle Routing Scheduling Problemswith Time Window Constraints[J].Operations Research,1987,35(2):254-256.

[4]龐燕,羅華麗,邢立寧等.車輛路徑優(yōu)化問題及求解方法研究綜述[J].控制理論與應(yīng)用,2019,36(10):1573-1584.

[5]Kennedy J,Eberhart R.Particle swarm optimization[C]//IEEEInternational Conference on Neural Networks.Piscataway,USA,IEEE,1995:1942-1948.

[6]Li J,Li Y,Pardalos PM.Multi-depot vehicle routing problem with time windowsunder shared depot resources[J].Journal of Combinatorial Optimization,2016,31(2):515-532.

[7]Veenstra M,Roodbergen K J,Coelho L C,Zhu SJ.A simultaneous facility location and vehicle routing problem arising in health care logistics in the Netherlands[J].European Journal of Operational Research,2018,268(2):703-715.