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

汪 越，王向前，劉 敏

安徽理工大學(xué)經(jīng)濟與管理學(xué)院，淮南,232000

1 相關(guān)研究與問題提出

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

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

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

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

2 配送模型的建立

2.1 配送模型參數(shù)定義

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

2.2 車輛配送路徑模型

決策變量：

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

X=Xik∈D

(9)

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

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

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

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

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

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

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

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

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

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

(10)

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

(11)

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

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

(12)

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

求解步驟：

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

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

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

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

Step4當(dāng)n

4 實例分析

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

表1 客戶資料表

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

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

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

表3 原車輛調(diào)度表

由表3可知，該物流配送中心原來在處理配送任務(wù)時，分配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，并且四條路線的空載率均較高，其中第一條路線、第二條路線空載率高達(dá)47.16%、55.44%，4條路線的總路程為482.4 km，按照現(xiàn)行0號柴油油價6.55元/L，日行駛成本為348元。

表4 現(xiàn)車輛調(diào)度情況

由表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的總路程少，該結(jié)果符合數(shù)學(xué)模型中的約束條件。

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

表5 對比表

5 結(jié) 論

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

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