基于粒子群算法的農產品物流車輛路徑問題

文/朱利

引言

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

1.問題描述

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

2.模型構建

2.1 符號說明

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

2.2 數學模型

本文以總配送成本最小為優化目標，其中，包括配送車輛的租賃成本、配送成本和違反時間窗懲罰成本。農產品物流配送優化模型如下：minZ=TC+FC+PC

TC：農產品物流配送車輛將農產品送達客戶的配送成本

FC：農產品物流配送車輛的租賃成本

PC：農產品物流配送車輛違反客戶服務時間窗的懲罰成本

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

3.粒子群算法

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

3.1 相關變量定義及公式

相關的定義和符號定義如下：

np：粒子群優化過程中使用的粒子數。

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

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

pbesth（t）：粒子群優化算法中迭代次數為t的粒子h的個體最佳位置。

gbesth（t）：粒子群優化算法中迭代次數為t的粒子h的個體最佳位置。

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

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

3.2 步驟及實現過程

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

Step2：計算粒子適應度值，并找到個體最優pbesth（t）和全局最優gbesth（t）；

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

Step4：計算粒子適應度值

Step5：對所有粒子，若其當前適應度優于其歷史最優適應度，則將當前位置設置為該粒子的歷史最優位置，然后更新全局最優。

Step6：如果達到最大迭代次數run_max，則循環完成；否則，返回Step3。

4.算例分析

4.1 算例相關數據

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

4.2 結果與分析

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

5.結論

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

引用出處

[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]龐燕,羅華麗,邢立寧等.車輛路徑優化問題及求解方法研究綜述[J].控制理論與應用,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.