基于蟻群算法的天然氣車輛調(diào)度優(yōu)化

徐 旭， 周靜遠

(1. 上海電機學(xué)院 商學(xué)院，上海 201306； 2. 燕山大學(xué)，河北 秦皇島 066004)

近幾年，液化天然氣發(fā)展?jié)摿艽蟆医y(tǒng)計局數(shù)據(jù)顯示，2017年1～12月份，天然氣產(chǎn)量1 474.2×108m3，日均生產(chǎn)4.4×108m3。截止2017年底，我國LNG車擁有量已增到26萬輛，LNG加氣站2 700座左右[1]。隨著天然氣運輸市場的發(fā)展，針對LNG運輸?shù)难芯坎粩嘣龆?，但主要集中在液化天然氣開發(fā)利用情況、技術(shù)裝備的介紹和LNG運輸?shù)奶攸c等方面，而對LNG運輸?shù)能囕v調(diào)度研究較少。LNG運輸不同于其他普通農(nóng)產(chǎn)品和一般工業(yè)品運輸?shù)?，屬于危險品運輸，具有鮮明的運輸特性。液化天然氣由于易燃，所以通常采用低溫常壓方式儲存在LNG儲罐中。目前，國內(nèi)LNG公路運輸?shù)闹饕ぞ呤堑蜏豅NG槽車，容積主要分為30 m3、40 m3、45 m3等幾種。國家對LNG槽車的拖掛數(shù)量有所限制，通常限制最多拖掛兩罐，因此,LNG車的載重量受到限制。但實際交易中客戶通常是以整罐為基本單位購買LNG，這使得其每次不能運輸超過兩家客戶,同時，LNG槽車在客戶處卸貨的時間比一般的貨物要長很多，通常要7 h，因此,每輛車等待的時間較長。如何最快、成本最低的滿足客戶需求,如何盡可能的減少等待時間,合理的車輛調(diào)度對LNG公路運輸企業(yè)獲得最大程度的利潤至關(guān)重要。

1 車輛調(diào)度概述

車輛調(diào)度問題(Vehicle Routing Problem,VRP)由Dantzig等[2]在1959年首先從旅行商問題中得到啟發(fā)而提出的。在之后的50多年里，VRP作為一個組合優(yōu)化問題，成為國內(nèi)外研究的熱點。在2010年,Sherbeny[3]對帶時間窗的車輛調(diào)度問題做了一系列綜述，對其模型和解法進行了詳細的闡述。Kim等[4]改進了Solomon插入算法并用于解決帶時間窗約束的垃圾收集問題。

目前,LNG運輸?shù)能囕v調(diào)度基本上都應(yīng)用遺傳算法來解決此類問題。遺傳算法采用概率化尋優(yōu)，尋求次優(yōu)路徑。劉振瑋[5]根據(jù)LNG運輸?shù)奶厥庑?，建立了一個LNG企業(yè)利潤最大化的車輛調(diào)度模型，運用遺傳算法解決某一LNG物流公司能否及時到貨和LNG運輸車輛到貨后等待卸貨時間過長的問題。但是遺傳算法的局部搜索能力較差，導(dǎo)致單純的遺傳算法比較費時，算法的搜索速度比較慢。在實際應(yīng)用中，遺傳算法容易產(chǎn)生早熟收斂的問題。相比較下，蟻群算法[6]實現(xiàn)了待解決問題的象限內(nèi)進行散點式搜索，提升了計算方法的信度與效度，并大大拓展了搜索的外延區(qū)間，更適合組合優(yōu)化的問題。因此，蟻群算法更適用于配送中心車輛調(diào)度優(yōu)化問題。

蟻群算法的基本原理是螞蟻們在不事先告訴食物的具體位置的前提下遍歷多地找食物。當(dāng)一只找到食物以后，它就會在路上放出一種具有可揮發(fā)性的信息素，濃度越大表示路徑越近，相反濃度越小表示路徑越遠；而其他的螞蟻會根據(jù)此信息來找尋食物。但是，有一些螞蟻并沒像這些螞蟻一樣重復(fù)著相同的路徑，他們會尋找其他路徑，如果走出來的其他道路比原來的所有道路更短，那么越來越多的螞蟻會被吸引到這條較短的路徑上。最后，經(jīng)過一段時間后，螞蟻們很可能會找出一條最短的路徑。當(dāng)前，基于蟻群算法的車輛調(diào)度研究較多。各個學(xué)科的專家與運輸計算制定者、管理者進行了大量的理論研究和實驗分析，取得了很大進展，運用這些研究成果，車輛調(diào)度問題己被成功運用到郵件速遞、出租車服務(wù)、奶品配送、糧食配送中。張強等[7]設(shè)計了螞蟻轉(zhuǎn)移策略、可行解構(gòu)造策略和信息素更新策略，采用K鄰域來限制螞蟻的轉(zhuǎn)移目標，并采用LK算法優(yōu)化策略來優(yōu)化多配送中心糧食車輛調(diào)度問題；孫曉瑩、徐紅霞[8]通過對基本蟻群算法的選擇策略和信息素的改進，優(yōu)化了煤礦運輸?shù)能囕v調(diào)度問題；魏明等[9]建立以車輛數(shù)、車輛等待和空駛時間最小為目標的混合整數(shù)規(guī)劃模型，在構(gòu)建人工螞蟻隨機游走的圖基礎(chǔ)上，優(yōu)化蟻群算法，解決區(qū)域公交“部分班次被一輛車完成”的集合劃分問題；盧曉珊等[10]通過對單環(huán)路旅行商問題進行斷環(huán)分析,將運行線路的好壞反饋給蟻群算法的目標函數(shù)優(yōu)化解決帶返程貨的車輛路由問題。上述文獻都是在蟻群算法的基本原理上，根據(jù)每一種問題的特征對蟻群算法進行改進，建立模型，最終解決問題。同樣，LNG的運輸特性使得螞蟻一次遍歷的地點有數(shù)量限制，而且很少，不能直接應(yīng)用蟻群算法基本原理，所以需要對基本蟻群算法進行改進。

本文將蟻群算法與LNG車輛調(diào)度相結(jié)合，進一步優(yōu)化蟻群算法，用兩兩抽樣的方法對某單配送中心LNG企業(yè)的車輛調(diào)度進行優(yōu)化，尋找最優(yōu)路徑，達到最小成本，提高蟻群算法的遍歷速度，減少整個搜索進程耗時。

2 單配送中心LNG車輛調(diào)度數(shù)學(xué)模型

2.1 問題描述

LNG運輸配送車輛調(diào)度問題：按收到的客戶訂單要求，配送中心指示帶有一個半掛車的LNG車輛發(fā)出，前往配送中心的天然氣母站裝氣，再向客戶要求的天然氣子站運送天然氣，一輛車一次最多送2個子站。然而LNG車卸氣時間一般要達到7 h，所以半掛車在前1個子站卸下后不需等待其卸完氣，LNG車即可馬上前往下1個子站卸氣，但LNG車最后要原路返回將前一個子站卸完氣后的半掛車拉上，再回到配送中心。全部的天然氣子站地理坐標和每次的需求量，確定每臺LNG車的載重量，且子站的每次需求量為一輛LNG車或一輛LNG車加一輛LNG罐掛車的載重量。LNG配送物流中心每次配送的最大里程數(shù)，由天然氣母站提供的天然氣可以滿足全部子站需求量確定，并且每輛LNG車要在一定的軟時間窗內(nèi)到達子站。其中軟時間窗是指假如LNG車輛不能在規(guī)定的時間窗內(nèi)到達子站，那么就會以早到或晚到時間長短為基礎(chǔ)收取一定等待成本和罰金[11]，作為LNG運輸配送的時間成本。

2.2 模型假設(shè)

為了使模型不至于太復(fù)雜且具有實用性，假設(shè)存在下面幾個條件：① 每條配送路線上所有子站的天然氣需求量之和小于等于一輛LNG車加一輛LNG罐掛車的載重量。② 每條配送路線的長度小于等于LNG車輛一次配送的最大里程數(shù)。③ 天然氣供應(yīng)母站能夠滿足子站需求，不會斷貨。④ 每個客戶的需求必須滿足[12]。⑤ 配送中心的LNG車能夠無限供應(yīng)，能滿足子站的需求。⑥ 天然氣運輸成本與總運距成正比[13]，運輸收入與運輸距離和需求量成正比，且所有LNG車輛每次運送相同噸位的天然氣。⑦ 子站需求的天然氣要在時間窗內(nèi)送達。⑧ 不考慮天然氣運輸中的其他不可避免的時間。

2.3 模型建立

LNG配送物流中心車輛調(diào)度問題(有軟時間窗)模型為：配送中心用R0表示，其配送中心的LNG車輛用k(k=1,2,…,n)表示，每輛LNG車和罐掛車載重量都為U；m則為客戶需求地個數(shù)，子站用集合R(R= {ri|i=1, 2,…,m})代表，每個子站ri的一次需求量為qi，并要求在時間窗[ETi，LTi]之內(nèi)送達并離開，即子站ri要求的最早到達時間為ETi和最晚離開時間為LTi；L代表天然氣供貨母站，就在配送中心附近。基本模型為

(1)

式中：z為LNG公司車輛調(diào)度的利潤；P為LNG的運費，t/km；qi為子站ri的一次需求量；di為從配送中心經(jīng)過母站L再到子站ri應(yīng)走的距離數(shù)；C為每km所需的汽油費；Dk為第k輛LNG車一次運輸中的總路程長度；X為LNG車運一趟的折舊費用；Y為司機運一次的工資；G為完成所有子站的需求量需要運的次數(shù)；Tx為LNG車一次的卸貨時間；Pz為LNG車早到的等待成本；Pw為LNG車晚到的懲罰成本；WTTik為第k輛LNG車在子站ri早到的時間；WTSik為第k輛LNG車在子站ri晚到的時間；Rk為第k輛LNG車一次可以服務(wù)子站個數(shù)；D為一輛LNG車一次可以走的最大里程數(shù)；Hi為消耗完子站ri的庫存所需的時間；RT為子站可以接受的等待時間；SD為司機可以接受的等待時間；ETik為第k輛LNG車到子站ri要求的最早到達時間。

該模型相關(guān)的約束條件如下:

式(2)表示根據(jù)實際情況，第k輛LNG車一次服務(wù)1或2個子站。式(3)表示子站ri的每次的需求量為一輛LNG車或一輛LNG車加一輛LNG罐掛車的載重量；式(4)表示第k輛LNG車在一次運輸中的總路徑長度小于等于一輛LNG車一次可以走的最大里程數(shù)；式(5)表示相鄰兩輛LNG車到達子站ri的間隔時間不少于消耗完子站ri的庫存所需的時間減司機可以接受的等待時間，也不能超過消耗完子站ri的庫存所需的時間加子站可以接受的等待時間。

模型主要是解決LNG公司配送走的合理路徑問題還有時間上的合理優(yōu)化，盡量降低等待時間，縮短路程。模型的基本利潤=收入-成本。假定配送收入為固定。

Dk就是通過蟻群算法得到的最短路徑，當(dāng)Dk最小時，汽油費最小，利潤就可以到達最大；PzTx則是模型中設(shè)立的等待時間成本，當(dāng)車輛的卸氣時間不能被合理利用起來去送其他子站時，就相當(dāng)于產(chǎn)生了成本，因此,在模型中考慮到這一點，有利于提高該公司的潛在利潤。

3 蟻群算法改進

(6)

式中:α為信息啟發(fā)式因子(α值越大表示螞蟻對信息素更敏感)；β為期望啟發(fā)式因子(β越大表示螞蟻對路線長短更敏感[14])。

在一次完整的遍歷中,每只螞蟻僅遍歷每個子站一次，用禁忌表控制，其中,tabu(k)表中第k只螞蟻已走過的所有子站，allowed(k)表示螞蟻k未曾走過的子站，而且allowed(k)=R-tabu(k)。螞蟻在行走過路線上釋放信息素。

當(dāng)全部螞蟻都遍歷完路徑后，每條路徑上的信息素為

式中：ρ為信息素揮發(fā)系數(shù)；1-ρ為信息素殘留系數(shù)，0<ρ<1；τ(t+n)為t+n時刻下在路徑dij上剩余的信息素量；Δτ為路徑dij上信息素增量。

第k只螞蟻在路徑dij上留下的信息素量為

(9)

式中：A為常數(shù)，代表所有螞蟻都走完全程所釋放的信息素總量；Dk為第k只螞蟻在一次遍歷中的總路徑長度。

其基本求解步驟如下:

(1) 參數(shù)初始化：輸入配送中心信息，輸入螞蟻數(shù)量K，也把子站信息導(dǎo)入allowed(k)；時間t←0；循環(huán)次數(shù)Nc←0；初始時刻信息素τij(0)←0；放于配送中心R0；設(shè)置最大迭代次數(shù)Nmax。

(2)Nc←Nc+1；k←1。

(3) 設(shè)定螞蟻k的禁忌表，將tabu(k)表清空，將螞蟻k的初始子站ri放入tabu(k)表中。

(4) 螞蟻k依據(jù)轉(zhuǎn)移概率公式算出將選擇的子站ri前進。

(5) 更改禁忌表tabu(k)，將已遍歷的子站ri從allowed(k)移到螞蟻k的禁忌tabu(k)表里。

(6) 判斷allowed(k)中的子站是否都被訪問，是則到步驟(7)，不然回到步驟(4)。

(7) 對信息素量進行局部更新，記下當(dāng)前最優(yōu)解，并把累計當(dāng)前最優(yōu)解列入禁忌表，螞蟻k←k+1。

(8) 若k≥K，則到步驟(9)，否則回到步驟(3)。

(9) 對K只螞蟻中的最優(yōu)解實行全部信息素更新。

(10) 判斷迭代條件：若Nc≥Nmax，循環(huán)終止得出結(jié)果；否則清空禁忌表，回到步驟(2)。

在蟻群算法的基本模型和步驟的基礎(chǔ)上，根據(jù)配送2個子站運輸?shù)奶攸c，加入了一個抽樣模型。

式(10)主要表示對所有子站進行兩兩抽樣的樣本集，式中XAi表示子站A與其他子站之間進行的組合，n為子站的個數(shù)。式(11)限制每只螞蟻每次只抽出2個子站去遍歷。式(12)限制每只螞蟻最終要原路返回。

圖1和圖2所示為蟻群算法基本走法和基于2個子站的蟻群算法走法對比圖。

圖1 蟻群算法基本走法

4 蟻群算法實例分析

以河北某液化天然氣運輸公司G公司為例，車輛調(diào)度主要是以傳統(tǒng)的人工或經(jīng)驗方式來進行調(diào)度。通過調(diào)查發(fā)現(xiàn)其運輸過程中存在如下問題。

圖2基于2個子站的蟻群算法走法

(1) 安排一輛LNG車接到訂單后馬上出發(fā)且只配送一個需求地就返回配送中心。相比滿足相同需求量的情況下，使得G公司的車輛的行車路程過長，許多路線交叉，并且出現(xiàn)了本可以避免的空駛現(xiàn)象，增加運輸費用，也降低了車輛的利用率。

(2) 由于在需求地卸氣時間太長，經(jīng)常一輛車運一次要2 d時間，而這段卸氣時間足夠滿足運送到其他子站的時間，使車輛等待成本提高了，車輛利用率下降了，也使得更多客戶需求不能滿足。

因此，現(xiàn)階段G公司需制定一個合理的車輛調(diào)度方案，盡量減少車輛的行駛路徑和等待時間，提高車輛的利用率，最大程度的滿足客戶要求，提升服務(wù)質(zhì)量，使公司利潤最大化。

收集到數(shù)據(jù)如下：其配送中心位置坐標為(0，0)，LNG槽車有100多輛，客戶需求的子站共有50個，每個子站的天然氣一次需求量為qi(單位：t)，要求送達的時間窗為[ETi，LTi](單位：周期)，所要用到的詳細參數(shù)見表1；各個子站的位置坐標見表2。這里要考慮的是：每次需求量為60 t的子站可以一次派一輛LNG車加一輛半掛車直接送到，而每次需求量為30 t的子站每次LNG車要走2次，所以需要合理規(guī)劃?，F(xiàn)如今要求制定所有每次需求量為30 t的子站的合理的行車路線，使G公司天然氣配送運輸?shù)目偫麧欁畲蟆?/p>

采用了bpython編寫改進蟻群算法進行兩兩子站抽樣得到最短路徑，對優(yōu)化模型求解。其中，通過試算取α為1，β為5，ρ為0.5，A為1。

將各個子站的坐標點轉(zhuǎn)化成矩陣后，代入軟件運算得出的蟻群算法抽樣圖見圖3。

圖3中25個點對應(yīng)的橫坐標和縱坐標分別代表組合起來的兩個子站序號，為：(1,26)(2,20)(3,12)(5,13)(6,23)(4,7)(21,41)(9,42)(8,26)(14,25)(10,28)(11,22)(15,38)(16,46)(17,47)(18,31)(19,50)(34,44)(35,43)(39,30)(32,45)(36,49)(33,48)(37,29)(24,40)。

表1 G公司LNG運輸相關(guān)參數(shù)

表2 G公司LNG運輸相關(guān)數(shù)據(jù)

圖3 蟻群算法抽樣圖

每一個坐標代表一個LNG車的路徑，綜合起來轉(zhuǎn)化成配送的最短路徑圖見圖4。

圖4 配送的最短路徑圖

運算后得出的結(jié)果要25輛LNG車，每輛LNG車配送路徑如下：

R0→R1→R26，R0→R2→R20，R0→R3→R12，R0→R5→R13，R0→R6→R23，R0→R4→R7，R0→R21→R41，R0→R9→R42，R0→R8→R26，R0→R14→R25，R0→R10→R28，R0→R11→R22，R0→R15→R38，R0→R16→R46，R0→R17→R47，R0→R18→R31，R0→R19→R50，R0→R34→R44，R0→R35→R43，R0→R39→R30，R0→R32→R45，R0→R36→R49，R0→R33→R48，R0→R37→R29，R0→R24→R40。

改進前根據(jù)模型式(1)得到G公司的利潤：z=85 009.28元；改進后根據(jù)模型式(1)得到G公司的最大利潤：max z=129 369.52元。因此，按本文所提出的方案進行優(yōu)化后，G公司利潤提高了44 360.24元，優(yōu)化方案理論上可行。

5 結(jié) 語

(1) 本文根據(jù)LNG運輸車輛調(diào)度的車輛的載重量受限和卸氣等待時間過長特殊性建立了一個每次只配送2個子站的LNG車輛調(diào)度模型，同時進一步改進蟻群算法，將蟻群算法與抽樣方法相結(jié)合，使得算法具有較快的收斂速度。通過試驗證明了改進算法的有效性和可行性，從而從理論上找到了一個LNG車輛調(diào)度蟻群算法優(yōu)化的方案，降低了等待時間，優(yōu)化了運輸路線，提高了公司利潤。

(2) 蟻群算法運用中，合理的參數(shù)值[15]對確定蟻群算法的效率會產(chǎn)生很大影響。本文是通過試算確定參數(shù)，但有待進一步從理論上探索確定蟻群算法合理的參數(shù)值。

參考文獻

[1] 景團朋, 夏鴻文. 我國LNG汽車發(fā)展現(xiàn)狀及前景分析[J].交通節(jié)能與環(huán)保, 2014,10(2):24-27，34.

[2] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science,1959,6(1):80-91.

[3] SHERBENY N A.Vehicle routing with time window: an overview of exact, heuristic and metaheuristic methods[J]. Journal of King Saud University(Science),2010,22:123-131.

[4] KIM B I, KIM S, SAHOO S. Waste collection vehicle routing problem with time window[J]. Computers & Operations Research,2006,33:3624-3642.

[5] 劉振瑋.LNG車輛運輸調(diào)度優(yōu)化模型研究[D]. 大連:大連海事大學(xué),2012.

[6] 吳珂. 基于蟻群算法的單配送中心車輛調(diào)度問題研究[D].大連:大連海事大學(xué),2013.

[7] 張強,熊盛武.多配送中心糧食物流車輛調(diào)度混合蟻群算法[J].計算機工程與應(yīng)用,2011,47(7):4-7，39.

[8] 孫曉瑩,徐紅霞.基于蟻群算法的煤礦運輸車輛調(diào)度應(yīng)用研究[J].煤炭技術(shù),2012,31(7):140-142.

[9] 魏明,靳文舟,孫博.求解區(qū)域公交車輛調(diào)度問題的蟻群算法研究[J].公路交通科技,2011,28(6):141-145,152.

[10] 盧曉珊,何偉,賀永金.郵政運輸網(wǎng)絡(luò)中的郵路規(guī)劃和郵車調(diào)度研究[J].數(shù)學(xué)的實踐與認識,2009,39(17):66-71.

[11] 王飛軍,呂建新,楊建偉. 基于蟻群算法的農(nóng)產(chǎn)品配送車輛調(diào)度問題研究[J].中國農(nóng)機化學(xué)報,2014,35(1):57-61.

[12] 郎茂祥.多配送中心車輛調(diào)度問題的模型與算法研究[J].交通運輸系統(tǒng)工程與信息,2006,6(5):65-69.

[13] 彭霞花,左丹,王秋霞. 基于遺傳算法的超市配送中心車輛調(diào)度優(yōu)化[J].山西科技,2009(3):99-101.

[14] 胡夏云. 基于蟻群算法的動態(tài)車輛調(diào)度問題的研究[D].廣州:廣東工業(yè)大學(xué),2013.

[15] 楊仁法,龔延成.帶時間窗車輛調(diào)度問題的蟻群算法[J].交通運輸工程學(xué)報,2009,9(4):71-74.