基于混合蝙蝠算法的多車場車輛調度研究

曹慶奎， 高亞偉， 任向陽

(1.河北工程大學 管理工程與商學院，河北 邯鄲 056038；2.廊坊師范學院 經濟與管理學院，河北 廊坊 065000)

隨著客戶需求量的增多，客戶網點分布不規則，物流運營商若只考慮用一個車場對客戶進行物流配送服務已遠遠不能滿足現實生活的需要，配備多個車場必然是未來的趨勢。物流運營商需要在多個車場間合理的安排車輛的行駛路線，在考慮物流配送成本的同時，還需考慮到時間窗、客戶滿意度、碳排放等因素，由此出現多車場車輛調度問題。該問題是基本車輛調度問題的擴展，是更為復雜的NP難題，近年來受到了國內外學者的廣泛關注。Yoshinori等[1]以能耗和碳排放量最小為目標，構建了帶時間窗限制的多車場車輛調度模型，并利用啟發式算法進行求解。Nadjafi等[2]探討了帶時間窗約束和車輛限制的多車場車輛調度問題，以最小配送費用為目標進行規劃，設計出一種啟發式算法求解數學模型，并成功的運用到180個實驗案例中。Zhou等[3]探討了帶有燃料限制的多車場車輛路徑問題，以總配送成本最低為目標，提出了四種新的混合整數線性規劃公式來計算模型的最優解。魯建夏等[4]在多車場車輛調度問題中考慮了供給價格和運輸成本的因素，以總成本最小為目標構建了多點配送車輛調度模型，并采用改進的變鄰域搜索算法進行求解。

2010年，劍橋大學學者Yang[5]首次提出了蝙蝠算法，該算法是通過模擬蝙蝠回聲定位系統而提出的一種隨機尋優算法。蝙蝠算法自提出以來就受到國內外學者的廣泛關注，現有的研究成果表明，蝙蝠算法擁有較好的收斂性和魯棒性。近年來，蝙蝠算法已被學者們應用到了車輛調度領域并得到了相應的研究成果。Zhou等[6]將貪婪自適應搜索算法與路徑重鏈接引入到蝙蝠算法中提出了一種混合蝙蝠算法，并將其運用到確定性VRP問題的求解。Osaba等[7]為了求解對稱和非對稱的旅行商問題，設計出一種離散型的蝙蝠算法，并與其他算法進行比較，證明了蝙蝠算法的優越性。殷亞等[8]在蝙蝠算法中引入了交叉算子和重組算子，并將其運用到多目標車輛調度問題的求解，通過算例證明了該方法可以很好地解決蝙蝠算法過早收斂的問題。孫奇等[9]在研究車輛調度問題上，將自適應啟發式算法和病毒進化機制引入到蝙蝠算法中，并驗證了該算法的有效性。

以上學者在多車場車輛調度問題以及蝙蝠算法上進行了深刻的研究。但是，現有的研究過分看重對物流運輸成本的優化，往往忽視了客戶的滿意度，而且傳統的蝙蝠算法在局部搜索能力上存在著缺陷。本文針對多車場車輛調度問題的特點，綜合考慮了客戶和物流運營商的利益，把遺傳算法中的自適應交叉操作引入到蝙蝠算法中，設計了一種混合蝙蝠算法，并將其運用到本文的模型進行求解。

一、問題描述及模型建立

以車場和客戶點間的配送網絡為研究對象，假設物流服務商有M個車場，每個車場配備容量為Q的貨車Km(m=1,2,…,M)輛，貨車給N個客戶實施物流配送服務，客戶點i的需求量為qi(i=1,2,…,N)，車輛從各自的初始車場發車送貨，給客戶配送完貨物后返回初始車場。所有客戶都能被任何一個車場的車輛服務，但每個客戶僅僅可以被一輛車服務一次，且需求一次得到滿足,已知客戶的期望時間窗，客戶收到貨物的時間不可早于客戶能接受的最早服務時間，也不可晚于客戶能接受的最晚服務時間。設客戶的編碼為1,2,…,N，車場編碼為N+1,N+2,…,N+M。

(一)模型假設

為了簡化模型的構建與求解，讓模型在現實中有更高的實用價值，對構造的模型給出如下假設：

(1)所有車場的坐標位置、配備貨車的數量以及貨車的最大運輸量己知，且每輛貨車的型號相同；

(2)所有的運輸車輛在車輛的初始車場發車，且完成送貨任務后回到原車場；

(3)車場可利用的車輛數不可多于該車場配備的車輛總數；

(4)每輛車運輸的重量不可多于該車輛的最大承重量；

(5)客戶收到貨物的時間不可早于客戶能接受的最早服務時間，也不可晚于客戶能接受的最晚服務時間；

(6)每輛運輸車輛勻速行駛，且單位行駛成本固定；

(7)所有客戶都能被任意一個車場的車輛服務，但每個客戶僅僅可以被一輛車服務一次，且需求一次得到滿足。

(二)變量說明

下面對多車場車輛調度問題數學模型中的變量進行說明：

dij：表示客戶節點i到j的距離；

Q：表示車輛的最大載重量；

C0：表示車輛的單位運輸成本；

V0：表示車輛的行駛速度；

timk：表示車場m的車輛k到達客戶點i的時刻；

STi：表示車輛在客戶點i的服務時間；

[Ei,Li]：表示客戶i的期望時間窗；

δ：表示超出客戶期望時間窗的最大忍耐時間；

(三)運輸成本度量

物流的運輸成本為運輸車輛從配送中心或客戶點開往下一個客戶點所產生的費用。本文假設物流運營商的運輸成本只與運輸車輛行駛的距離相關，運輸成本等于所有車輛的行駛距離乘以車輛的單位運輸成本。故本文的運輸成本計算公式如下：

(1)

(四)客戶不滿意度度量

本文假設客戶的不滿意度只與客戶收到貨物的時間相關。當客戶的收貨時間在期望時間窗內時，客戶的不滿意度最低，當客戶的收貨時間提前或延遲于期望時間窗，會增加客戶的不滿意度，但客戶不會選擇拒絕收貨。客戶時間窗懲罰圖如圖1所示：

圖1 客戶時間窗懲罰圖

(2)

式中:ai、bi、mi和ni均為懲罰系數。客戶平均不滿意度的計算方法如下：

(3)

(五)多車場車輛調度模型

根據上述條件，本文以客戶不滿意度最低、物流運輸成本最低為目標構造如下的多車場車輛調度數學模型:

f1=minDP

(4)

f2=minDF

(5)

(6)

(7)

(8)

(9)

(10)

(N+1,…,N+M),k∈Km

(11)

m∈(N+1,…,N+M)

(12)

模型中式(4)、(5)為目標函數，代表客戶不滿意度和物流運輸成本最低；式(6)表示車場可利用的車輛數不可超過該車場配備的車輛總數；式(7)表示所有的運輸車輛在車輛的初始的車場發車，且完成送貨后回到原車場；式(8)和(9)表示一個客戶僅僅可以被一輛車服務一次；式(10)表示每輛車的裝載量不可多于該車的最大運輸量；式(11)表示車輛不可直接從車場到車場；式(12)表示客戶時間窗約束。

二、多目標處理

針對多目標優化問題的處理，本文首先按照各目標之間的重要性給予對應的權重，然后對各目標函數進行規范化處理，將規范化處理后的目標函數乘以相應的權重，最后相加當作本文的目標函數，進而把多目標問題化簡為單目標問題。

(一)確定權重

為了保證權重賦值的客觀性，本文按照各目標的重要性程度對權重進行隨機化處理，在提高算法搜索能力的同時可以得到多個最優解。目標函數的權重le為：

(13)

(二)規范化處理

本文要求解的多個目標之間的量綱不是統一的，不能直接采用線性加權法進行求解。本文采用如下權重模型[16]對兩個目標函數進行規范化處理。

(14)

三、混合蝙蝠算法

蝙蝠是一種神奇的動物，擁有特殊的回聲定位功能，可以通過向周圍發出聲音脈沖，接受周圍物體反射回來的回聲，基于接收回聲的時間差及響度變化去構建周圍環境的三維場景，從而鎖定捕食目標[12]。

(一)蝙蝠的速度與位置

fi=fmin+(fmax-fmin)β

(15)

(16)

(17)

式中：fi為當前時刻蝙蝠i的脈沖頻率，fmin和fmax表示蝙蝠脈沖頻率的最小值和最大值，β表示[0,1]之間的一個隨機數，X*為當前的全局最優解。

蝙蝠算法在尋優過程中，同其他啟發式算法一樣，可以進行局部搜索產生新的位置，更新公式如下：

Xnew(i)=Xold(i)+εAt

(18)

式中：ε表示[-1,1]之間的一個隨機數，At為當前時刻全部蝙蝠響度的均值。

(二)蝙蝠的脈沖與頻率

(19)

(20)

(三)編碼與解碼

(四)交叉操作

蝙蝠算法在前期通過速度和位置的更新具有快速收斂、魯棒性強等優點，但同時也有“早熟”的現象[13]。本文把遺傳算法中的自適應交叉操作引入到蝙蝠算法中，該方法能夠提高蝙蝠算法的尋優性能。

本文采用順序交叉操作。隨機選取兩個蝙蝠個體，將蝙蝠1中與蝙蝠2中后三個相同的客戶編碼刪除，得到刪除編碼后的蝙蝠1，以同樣的方法得到刪除編碼后的蝙蝠2。然后將蝙蝠2中的后三位客戶編碼順序插入蝙蝠1中的空缺編碼位，得到新的蝙蝠個體1，以同樣的方法獲得新的蝙蝠個體2。如圖2所示：

圖2 交叉操作

式中，交叉概率并不是一個不變的值，而是根據每代種群中最佳蝙蝠個體的適應值和其它蝙蝠個體的之間差額關系決定的。交叉概率公式[14]見下式：

(21)

式中：min是個體的最小適應值，f是種群中所有適應度值低于平均適應度值個體的均值。k>0,exp()為以e為底數的指數函數。因為min-f<0，所以0

(五)混合蝙蝠算法實現過程

步驟2：通過約束條件確定每只蝙蝠路徑上的運輸車輛及車輛的運輸路線，將適應度值最優的蝙蝠作為當前最優蝙蝠X*。

步驟3：通過公式(15)至(17)調整頻率，更新當前蝙蝠的速度和位置，產生新的解。

步驟4：隨機產生一個數rand1，若rand1>ri，則對當前最優解進行局部搜索，生成一個新解Xnew。

步驟5：隨機產生一個數rand2，若rand2

步驟6：按照公式(19)、(20)更新Ai和ri，排列所有蝙蝠找出最優解。

步驟7：把當前最優解的客戶編碼進行自適應交叉操作，若適應度值優于當前最優解則更新當前最優解。

步驟8：令iter=iter+1,如果iter

四、模型仿真及分析

(一)問題描述

某物流公司擁有的車場數量M為3，每個車場配備2輛相同型號的車輛，客戶點的數量N為16，每輛運輸車輛的車速V0為40 km/h，車輛的單位運輸成本C0為每公里5元。其中，3個車場的具體坐標分別為(20，20)，(75，45)，(50，80)，每輛車的最大運輸量為9 t。具體的數據如表1所示：

表1 車場信息

16個客戶地址的具體坐標、貨物需求量、客戶期望的時間窗以及服務每個客戶所需要的時間，如表2所示：

表2 客戶信息

(二)仿真結果

為了檢驗本文多車場車輛調度數學模型與混合蝙蝠算法的可行性，本文在MATLAB 2016a 版本上對傳統蝙蝠算法、混合蝙蝠算法進行編程實現。2種算法均在Intel Core i3-3217U 1.80 GHz (8.00 GB RAM)，操作系統為64位Win8.1的環境下進行。2種算法的設置參數如下：α=0.95，γ=0.95，A0∈[0,1]，r0∈[0,1]，蝙蝠種群數n=100，迭代次數100。時間窗懲罰參數設置如下：ai=0.05，bi=0.5，mi=0.02，ni=0.03。將2種方法計算的結果進行比較，其中車場1，車場2，車場3分別用數字17,18,19表示，具體結果如表3所示：

表3 傳統蝙蝠算法與本文方法對比

兩種算法求解得出的車輛運輸路線對比如圖3、圖4所示：

圖3 傳統蝙蝠算法路線圖

圖4 混合蝙蝠算法路線圖

兩種算法求解過程中的成本收斂情況對比如圖5所示：

圖5 成本收斂對比圖

從兩種算法的成本收斂過程來看，本文采用的混合蝙蝠算法與傳統的蝙蝠算法相比擁有更強的尋優能力，這主要得益于將自適應交叉操作引入到蝙蝠算法中，該方法可以對結果較差的蝙蝠進行交叉操作，從而能夠擴大搜索范圍。

(三)對比分析

通過對比傳統的蝙蝠算法和本文的求解結果方法可以得出結論：

(1)從客戶的利益來看，本文的方法在客戶不滿意度方面比傳統的蝙蝠算法降低了4.57%，這表明本文的方法在減少客戶不滿意度方面的效果是顯著的。

(2)從運營商的利益來看，本文的方法在配送成本優化方面不僅提高了求解的速度，而且運輸成本比傳統的蝙蝠算法減少了425.15元，這表明本文的方法在減少配送成本方面優于傳統的蝙蝠算法。

綜上，從物流運營商的長遠利益來看，本文的方法在減少配送成本的同時降低了客戶的不滿意度，這有助于物流運營商與客戶維持長期的合作關系，使物流運營商能夠持久盈利。

五、結束語

本文綜合考慮了客戶和物流運營商的利益,設計了適合本文研究的多目標車輛調度模型。并對蝙蝠算法進行了改進，使算法更適用于求解本文的數學模型，并經過仿真檢驗了本文算法的可行性。本文是蝙蝠算法在多車場車輛調度領域的成功運用，為求解多車場領域車輛調度難題進行了有益的探索。

須指出的是，在現實生活中物流運輸的過程必然伴隨著多種擾動因素，因此，將擾動因素與車輛調度相結合是下一步研究的方向。