一種基于蟻群算法的帶時間窗物流運輸車輛路徑優(yōu)化方法

汪 越，王向前，劉 敏

安徽理工大學經濟與管理學院，淮南,232000

1 相關研究與問題提出

隨著對物流運輸問題研究的不斷深入以及對運送貨物時間的要求越來越高，發(fā)現配送中心在安排貨物運輸時，加入時間窗限制運送時間能節(jié)約運輸成本，提高車輛的利用效率，因此國內外對帶有時間窗的車輛路徑問題(Vehicle Routing Problem With Time Windows，VRPTW)采取了多種方法進行研究。

Juliandri等針對車輛路徑選擇問題，將車輛調度問題建模為線性混合整數規(guī)劃問題，開發(fā)了一個結合啟發(fā)式和精確的方法來解決模型，最終得出了一組車輛的調度最佳路線集[1]。Masutti等認為窮舉法解決車輛路徑選擇時具有局限性，因此基于群體智能的運用，闡述了蜜蜂啟發(fā)法求解車輛路徑問題，最終得出了最優(yōu)路線[2]。Akhand等將車輛路徑選擇問題轉化為旅行商問題，并利用掃描聚類算法處理，算法得出的最優(yōu)路線集優(yōu)于原結果中的路線集[3]。

國內對于車輛路徑優(yōu)化的研究中，覃運梅等針對時間和地點對接要求而導致投遞效率不夠高的問題，利用遺傳算法處理該問題，最終使得配送車輛數目最少和配送成本最小[4]。裴小兵等針對多目標車輛路徑優(yōu)化問題，利用改進遺傳算法、SPSS聚類分析等方法，最終提高了車輛路徑的優(yōu)化率和準確率[5]。侯玉梅等為改善整車物流配送問題，設計了自適應遺傳算法并運用成品汽車配送案例進行驗證，最終在滿足要求的基礎上提高了經濟效益[6]；麻存瑞等人設計了自然素編碼來綜合考慮快遞件數量、汽車載重等要求，構建了符合快遞配送路徑優(yōu)化的數學模型，最終得出當前快遞車輛能夠滿足運輸需求而不需更換運輸車輛[7]。何小峰等提出量子蟻群算法，經實例檢驗該算法性能更優(yōu)，有效避免了車輛路徑優(yōu)化問題陷入局部最優(yōu)及收斂速度較慢的問題[8]。

上述文獻對車輛路徑優(yōu)化問題進行了詳細研究，但是只選取了一個指標來闡明路徑優(yōu)化的過程，容易造成配送路徑減少時，空載率及配送成本增大，因此本文利用配送路徑長度和配送車輛空載率兩個指標，對帶時間窗物流運輸車輛路徑優(yōu)化問題進行研究。

2 配送模型的建立

2.1 配送模型參數定義

已知客戶的需求量及地理位置的情況下，配送中心利用m輛配送車為n個客戶提供配送服務，設N=2,…,n為客戶集合，配送中心賦為1，則在配送網絡圖中頂點集合為D=1∪N，配送車集合為K=1,2,3…,m。設車輛從配送點出發(fā)的時刻為T0，配送車輛到達客戶i的時刻為T，客戶i允許接受服務的最早和最晚時間分別為ETi和LTi,設客戶的需求量為Q，S表示車輛k所服務的客戶集，S表示客戶集中含有的客戶個數，如果配送車輛提前到達客戶i處則須等待的時間為W，客戶i接受服務需要的時間為s，當配送車輛完成對i的服務后緊接著去往下一個客戶點j，路徑長度為d。

2.2 車輛配送路徑模型

決策變量：

數學模型：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

ETi≤Ti+Wi≤LTi,?i∈N

(8)

X=Xik∈D

(9)

(1)表示配送車輛配送模型的目標函數，即配送車輛追求配送路徑最小化的函數模型；

(2)表示車輛不能超載；

(3)表示每個客戶只能由一輛車配送貨物且只能接受服務一次；

(4)(6)表示從配送中心出發(fā)的車輛在完成配送任務后須回到配送中心，且配送時的路線不能形成回路；

(5)表示配送車在完成對客戶i的配送服務后需要緊接著去下一個客戶點j；

(7)表示配送車到達客戶的時刻；

(8)表示客戶的時間窗要求，配送車到達時間不能超出時間范圍ETi，LTi；

(9)表示車輛k的線路必須是聯通的。

3 配送車輛的蟻群算法模型表示

當配送車輛到達指定客戶點，并完成相關任務后，只能移動到下一個未經過的客戶點或者回到配送中心，不能再次向已經到達過的客戶點移動。在滿足上述配送車輛數學模型約束的條件下，當配送車輛到達一個客戶點并完成配送任務后，接下來便會按照一定的規(guī)則選擇下一個客戶點，具體規(guī)則如下[9]：

(10)

S表示配送車輛下一個選擇到達的客戶點，U∈allowed表示配送車輛尚未到達的客戶點集合，會優(yōu)先在客戶點V=(2,3,…,n)中選擇向配送路徑短的地點移動[10]。配送車輛每一次從配送中心至客戶點的循環(huán)中，都會在尚未到達的客戶點集合中選取下一個客戶點，每次的路徑都在不再減少，直至到最短路徑，選擇下一個客戶點的概率公式如下：

(11)

當一次循環(huán)結束后進入t+1時刻，此時各個路徑由于路徑長短不同，使得路徑上的信息素殘留不同，所以應對路徑上的信息素做出調整和更新，本文對信息素進行全局更新，公式如下：

τijt+1=ρ·τijt+Δτijt,t+1

(12)

ρ為常數系數，表示信息素的持久率，其取值范圍為[0,1]，所以ρτijt表示在時刻t時刻地點i到地點j的信息素殘留量。m表示配送車輛表示在時刻t和時刻t+1中車輛k在客戶點i到j路徑上時所增加的信息素量。Q表示當車輛完成一次循環(huán)，即完成一次路徑探索后所釋放的信息素總和。lk表示車輛k在完成一次路徑探索時的路徑總長度。

求解步驟：

Step1設置最大迭代次數為N，令n=1，將各個參數進行初始化，將車輛放在配送路徑中，計算出配送中心到各個客戶點之間的距離以及各個客戶點之間的距離。

Step2令配送車輛從初始位置即配送中心1出發(fā)，故i=1，接下來車輛將會隨機到達下一個節(jié)點j，但必須滿足約束條件(8)。當滿足約束條件(8)后，對j進行卸載貨物，當完成對j的任務時繼續(xù)搜索下一個客戶點，直到搜索完j的所有的相鄰客戶點。當沒有客戶點滿足約束條件時，配送車輛將會從當前的客戶點返回配送中心1，將此條路徑作為解放入可行解集中。

Step3根據狀態(tài)轉移公式(11)，從步驟二中的可行解集尋找出路徑最短的下一個最優(yōu)節(jié)點j，根據節(jié)點j的需求量調整配送車輛的車載量。

近年來，河道整治工作一方面受到大眾的普遍關注，另一方面又受到諸多因素的影響。當前基于生態(tài)環(huán)境保護的河道整治工作處于一個十分尷尬的位置，很難推進。這種尷尬的境遇是自然的發(fā)展與人類的需求不能很好融合以及一些宏觀政策的影響。因此，河道整治工作需要做一些改變。傳統(tǒng)的邊岸固化方式未考慮到河流本身的特質，強硬的對自然環(huán)境加以干預和破壞。所以，現階段的河道整治工作要重新規(guī)劃，要考慮人的需要與河床演變的自然規(guī)律，考慮人與自然的關系，考慮河道演變的適度性，如此才能做出合理的河道整治方案[2]。

Step4當n

4 實例分析

現利用實例來檢驗上述模型的可行性，具體描述如下：淮南市有一主要從事電子產品的物流配送中心，共有4輛配送車輛，配送過程中平均速度為50 km/h，每輛車的最大載重量均為2.5 t，百公里油耗為11 L。配送中心編號為1，其地理位置為(10.6 km，40.4 km)，現在需要向15個客戶點運送相關貨物，配送中心每天自早上7點開始向各客戶點配送貨物，設單位卸貨時間相同，客戶點編號依次為2～16。15個客戶的地理位置坐標、客戶的貨物需求量以及時間要求見表1。

表1 客戶資料表

為方便算出各條路徑的總路程,將表1的配送中心和客戶點的距離制成距離矩陣如表2所示(假設各客戶點距離均為直線距離且道路情況良好，在行駛過程中不存在耽誤時間的意外情況發(fā)生)。

表2 配送中心及客戶點距離矩陣表

該配送中心在未采用蟻群算法處理數據時，由于配送中心有4輛配送車，所以經常出現無論貨物的多少都會使用4輛配送車配送貨物的情況，這不僅使得配送成本加大，還會出現當新的貨物到達配送中心時可能無法立即分配及無配送車輛可使用的情況，原配送路線、車輛到達時刻、運輸量、空載率、總路程如表3所示。

表3 原車輛調度表

由表3可知，該物流配送中心原來在處理配送任務時，分配4輛配送車輛并形成了4條運輸路線：第一條路線為：1→16→15→13→12→1，貨運量為1.321 t，運輸路程為95.1 km；第二條路線為：1→10→7→8→1，貨運量為1.114 t，運輸距離為113.4 km；第三條路線為：1→6→4→2→3→5→1，貨運量為1.841 t，運輸距離為178.5 km；第四路線為1→14→11→9→1，貨運量為1.640 t，運輸距離為95.4 km。4條路線的總運輸量為6.01 t，并且四條路線的空載率均較高，其中第一條路線、第二條路線空載率高達47.16%、55.44%，4條路線的總路程為482.4 km，按照現行0號柴油油價6.55元/L，日行駛成本為348元。

表4 現車輛調度情況

由表4可知，該物流配送中心在處理帶有時間窗的車輛路徑選擇時，分配3輛配送車輛來運輸貨物會使得車輛的運輸距離最短，第一條路線為：1→16→15→13→12→10→1，貨運量為1.536 t，運輸總路程為96.9 km；第二條路線為：1→8→7→6→4→2→3→1，貨運量為 2.362 t，運輸距離為190.2 km；第三條路線為：1→14→11→9→5→1，貨運量為2.112 t，運輸距離為129.1 km。三條路線的總運輸量為6.01 t，3條路線的總路程為416.2 km，該路線日行駛成本為300元，該距離比表3的總路程少，該結果符合數學模型中的約束條件。

將表3和表4的最終結果做比較(見表5)，可以得出當蟻群算法處理帶有時間窗的車輛路徑問題時，不僅會降低車輛路徑的距離，還會大幅降低車輛的空載率，提高了車輛的利用率，降低了運輸成本。

表5 對比表

5 結 論

物流的配送過程是向著低成本、高效率的方向發(fā)展的，在配送車輛載重量已知的情況下可以通過一系列算法來優(yōu)化車輛路徑選擇問題以達到減少配送距離及配送車輛數的目的[13]。本文利用蟻群算法處理配送中心的現行車輛調度情況，為了解決優(yōu)化指標過少的問題，在得出配送路徑長度減少的情況下，增加了車輛空載率指標，對蟻群算法優(yōu)化車輛路徑問題做了進一步闡述，得出該配送中心現行車輛調度需要改進。

雖然對車輛的路徑優(yōu)化問題研究較早，但仍有許多方面需要改進，例如，如何平衡車輛路徑距離、配送成本、空載率等各項指標的重要性問題，車輛行駛過程中的成本變動問題，路況所導致的配送時間變動問題等，因此在配送過程中需要綜合考慮各種因素以及各因素間的影響關系，使得物流配送效率得到進一步提高。