基于改進蝙蝠算法的帶模糊需求的車輛路徑問題

朱 顥

(湖州職業(yè)技術(shù)學院，浙江 湖州 313000)

基于改進蝙蝠算法的帶模糊需求的車輛路徑問題

朱 顥

(湖州職業(yè)技術(shù)學院，浙江 湖州 313000)

蝙蝠算法作為一種新的元啟發(fā)式算法，尚未被應用到模糊車輛路徑問題中；針對帶模糊需求的車輛路徑問題，以極小化總運輸距離為目標，建立基于可信性理論的模糊規(guī)劃模型，提出一種改進的蝙蝠算法；算法采用基于客戶編號的編碼方式，利用隨機模擬算法計算額外行駛距離；在蝙蝠位置更新時，引入基于非線性調(diào)整的慣性權(quán)重和基于子路徑的局部搜索；為提高全局搜索能力，避免算法早熟，對處于較差位置的蝙蝠進行交叉操作；最后，利用隨機實驗數(shù)據(jù)進行仿真，分析了決策者主觀偏好值對目標值的影響，并與其它算法的尋優(yōu)結(jié)果進行對比分析，結(jié)果表明，算法具有一定的可行性和有效性。

蝙蝠算法;模糊需求;車輛路徑問題

0 引言

車輛路徑問題(VRP問題)作為物流領(lǐng)域內(nèi)的一類經(jīng)典的組合優(yōu)化問題，由Dantzig和Ramser[1]于1959年首次提出,該問題描述為：若干車輛從車場出發(fā)，為一系列客戶提供取貨服務(送貨服務類似)，取貨完畢后返回車場，每個客戶一次只能由一輛車提供取貨服務，在取貨過程中需要滿足車輛裝載能力約束、車輛行駛里程約束和客戶時間窗口約束等條件，為此，為每輛車選擇相應的客戶，并安排訪問的順序，使得某些目標達到最優(yōu)(如總路程最短、成本最低等)。目前，關(guān)于車輛路徑問題的文獻很多，大多數(shù)都是關(guān)于確定性的VRP問題，但是在實際應用中，由于受客觀世界不確定和人類認識事物的模糊性的影響，某些信息可能是模糊的、不確定的，例如客戶需求量大概為30，或者在30到50之間，此時，需要運用模糊變量來處理這類情況，模糊車輛路徑問題就是一類用來反映某些信息為不確定的、模糊的車輛路徑問題。

針對客戶需求量為模糊變量的車輛路徑問題，Teodorovic[2]等通過引入決策者偏好，以模糊推理算法為基礎(chǔ)，運用掃描算法和蟻群算法進行求解；國內(nèi)學者祝崇雋等[3]較早地運用模糊模擬的方法計算車輛的額外行駛里程，并提出了基于可能性分布和基于需求上界的 2-OPT 算法；張建勇[4-6]等建立了基于可能性理論的規(guī)劃模型，先后運用遺傳算法和sweeping算法進行求解，并分析了決策者的偏好對優(yōu)化目標的影響；曹二保[7-8]等建立了基于模糊可能性的規(guī)劃模型，運用差分進化算法進行求解，在算法中為避免產(chǎn)生的解不可行，設計了基于整數(shù)序規(guī)范的輔助算子；彭北青[9]、戎麗霞[10]針對類似問題，先后運用遺傳算法進行了求解；吳天羿[11]等運用混合遺傳算法求解了該問題，在算法中運用種群掃描法初始化種群，為了降低車輛調(diào)用數(shù)量,提高車輛利用率和裝載率，設計了專門的混合交叉算子和差分掃描變異算子；Lian xue[12]利用改進的差分進化算法進行求解，在交叉環(huán)節(jié)，交叉概率隨迭代次數(shù)線性增加；R.J. Kuo[13]等提出了基于粒子群算法和遺傳算法的混合算法，讓每個粒子同其自身經(jīng)歷過的最優(yōu)位置及全局最優(yōu)位置進行多次交叉，選取較優(yōu)的子代粒子作為下一代粒子；Cao Erbao等[14]設計了隨機模擬算法來估算額外行駛里程，并針對可能產(chǎn)生的不可行解，引入了相應的懲罰函數(shù)，利用差分進化算法進行求解；Yang Peng等[15]提出了基于整數(shù)編碼的粒子群算法，對粒子更新的過程中產(chǎn)生的實數(shù)，利用基于升序的排序規(guī)則，將實數(shù)轉(zhuǎn)換成整數(shù)。

蝙蝠算法作為一種新型的仿生智能算法，由劍橋大學學者Yang[16]于2010年提出, 該算法利用自然界中蝙蝠運用超聲波來搜尋獵物這一生物學特性，將蝙蝠隨機分布在解空間，通過蝙蝠不斷變化的脈沖頻率來搜尋獵物。截至目前,蝙蝠算法在VRP問題的應用尚不多見，只有馬祥麗[17-18]等針對有能力約束的確定性VRP問題和帶時間窗的確定性VRP問題，以2L維向量編碼，運用蝙蝠算法進行了求解；Yongquan Zhou[19]等針對確定性的VRP問題，運用基于貪婪隨機自適應搜索算法和基本蝙蝠算法的混合算法進行了求解。目前蝙蝠算法在帶模糊需求的VRP問題中的應用尚未出現(xiàn)，本文基于可信性理論，建立相應的模糊規(guī)劃模型，并運用改進的蝙蝠算法求解帶模糊需求量的車輛路徑問題。

1 問題描述

帶模糊需求量的VRP可以描述為：某運輸網(wǎng)絡中有一個車場(用0表示)和n個需要取貨的客戶(用1,2,…,n表示)；該車場共有m輛車(用1,2,...,m表示)可以利用；每輛車的標記載重量相同，用Q表示；車輛從車場出發(fā)，為一定數(shù)量的客戶提供取貨服務后需返回車場；每個客戶一次只能由一輛車服務；每個客戶的貨物需求量(在取貨環(huán)境下，可以理解為客戶需要寄送的貨物量)不確定，用一個三角模糊數(shù)d=(d1,d2,d3)表示；客戶i和客戶j之間的距離用Dij表示；本文的目標是在一系列約束條件下，為車輛選擇合適的取貨順序，使得總運輸距離最短(包括計劃行駛距離和額外行駛距離)。

Cr{dk+1

(1)

根據(jù)模糊理論，車輛的剩余載重能力Qk越大，第k+1個客戶的需求量dk+1越小，則Cr{dk+1

然而，在實際的取貨過程中，當車輛按上述策略所計劃的路線到達某個客戶處時，客戶的模糊需求變?yōu)椤皩嶋H需求”，而車輛的剩余載重能力也變?yōu)橐粋€確定值，此時，可能會出現(xiàn)車輛剩余載重能力不能滿足該客戶的“實際需求”而導致原計劃路線“失敗”，此時，車輛需要先返回車場，卸貨完畢后再空駛至該“失敗點”，然后繼續(xù)完成剩余的運輸任務，從該“失敗點”到車場的往返即構(gòu)成了車輛的額外行駛距離。因此，評估一個車輛路線安排的優(yōu)劣時，既要考慮計劃行駛距離，還要考慮由于路線“失敗”而產(chǎn)生的額外行駛距離。由于客戶需求具有模糊性，在按照上述可信性條件安排計劃路線時，無法明確路線“失敗”發(fā)生的地點、次數(shù)及由此產(chǎn)生的額外行駛距離，因此，采用隨機模擬的方式產(chǎn)生客戶的“實際需求”，并對可能產(chǎn)生的額外行駛距離進行估算。

2 構(gòu)建問題的模型

定義問題的變量為yik、xijk。其含義如下：

該問題的模型如下：

(2)

(3)

(4)

(5)

(6)

1,2,...,m

(7)

(8)

3 基本蝙蝠算法

蝙蝠是一種神奇的動物，擁有令人驚異的回聲定位能力，通過向四周發(fā)出一定頻率的聲音脈沖，然后聆聽從周圍物體反射回來的回聲波，利用雙耳接收回聲波的時間差、回聲波音強的變化來建立周圍環(huán)境的三維場景，以此來搜尋獵物或者避開障礙物[20]。

在基本蝙蝠算法中，第i只蝙蝠搜尋獵物時的飛行速度更新公式為[20]：

(9)

fi=fmin+(fmax-fmin)×rand

(10)

式(10)中fmax和fmin分別為蝙蝠搜尋獵物時使用的最大脈沖頻率和最小脈沖頻率，rand為區(qū)間[0,1]內(nèi)服從均勻分布的隨機數(shù)。

根據(jù)蝙蝠的飛行速度公式，第i只蝙蝠在第t時刻的位置為：

(11)

在利用蝙蝠算法尋優(yōu)的過程中，還可以進行局部搜索，局部搜索時，蝙蝠的位置更新公式如下：

Xnew=Xold+εAt

(12)

式(12)中Xnew為蝙蝠的一個待定解，Xold一般為當前蝙蝠群體中的最優(yōu)位置，ε為區(qū)間[-1,1]內(nèi)的一個隨機數(shù)，At=[At]為所有蝙蝠在同一時刻的平均響度。

蝙蝠在搜尋獵物的過程中發(fā)射脈沖的響度和脈沖發(fā)射率更新公式為：

(13)

(14)

4 改進蝙蝠算法求解模糊車輛路徑問題

4.1 生成初始種群

隨機生成pop_size只蝙蝠。每只蝙蝠用客戶編號1,2,…,n的一個重排表示。對于每只蝙蝠，采用如下方法進行解碼，以表示一個路徑安排[5]：

Step1:選擇第1輛車出列，準備執(zhí)行任務；

Step2:選擇排列中最左邊的客戶，按公式(1)計算該客戶的模糊需求量小于當前車輛剩余載重能力的可信性，若該可信性值大于給定的主觀偏好值Cr*，則將客戶安排給當前車輛；否則，新派一輛車，將客戶安排給新開的車；

Step3:將該客戶從排列中刪除；

Step4:重復Step2和Step3，若所有的客戶均安排完畢，則獲得了一個可行的路徑安排。

4.2 隨機模擬算法計算額外行駛距離

如前所述，對于任意一個可行的路徑安排，由于客戶的需求量為三角模糊數(shù)，車輛按原計劃抵達客戶處時，客戶的“實際需求”可能超過車輛剩余載重能力，從而導致計劃“失敗”，車輛需返還車場，卸完貨后再重新回到該客戶處，此時額外行駛距離的計算方法如下。

1)對某個客戶i，先隨機模擬其“實際需求”，采用如下方法：

(1)隨機產(chǎn)生一個位于區(qū)間[d1i,d3i]內(nèi)的值d′，代表該客戶的需求，計算d′的隸屬度μ；

(2)隨機產(chǎn)生一個位于區(qū)間[0,1]內(nèi)均勻分布的隨機數(shù)a；

(3)若μ>a，則接受d′作為該客戶的“實際需求”，否則，d′暫時不接受，重復(1)和(2)，直到條件μ>a成立，能接受d′作為該客戶的“實際需求”為止。

2)重復Step1，直至生成所有客戶的“實際需求”。

3)讓車輛依照此路徑安排行駛，計算所有客戶的需求變?yōu)椤皩嶋H需求”的前提條件下，所有車輛的總額外行駛距離。

4)重復上述步驟(1)至(3)共M次，取其平均值，作為該路徑安排由于可能發(fā)生計劃“失敗”而產(chǎn)生的額外行駛距離的估計值。

4.3 基于升序的排序規(guī)則

在利用蝙蝠算法的速度和位置更新公式(9)～(11)更新蝙蝠的位置時，生成的新位置中元素會出現(xiàn)實數(shù)，而本文算法中每只蝙蝠的位置應該處于離散空間中，即每個位置元素應該為{1,2,...,n}中的整數(shù)，此時需要采取基于升序的排序規(guī)則進行調(diào)整，具體表述如下：將新位置中取值最小的元素用1代替，取值第二小的元素用2代替，依次類推，取最大值的元素用n代替。例如，經(jīng)過速度和位置更新公式更新后，某只蝙蝠的位置為[-0.8,3.4,2.5,6.7,-5.4,9.7,4.8]，則利用基于升序的排序規(guī)則進行調(diào)整后，該蝙蝠對應的位置應為[2, 4,3,6,1,7,5]。若不采用基于升序的排序規(guī)則，而采用其它的取整方法，如向下取整、向上取整或四舍五入取整等方法，均不能得到5.1節(jié)所要求的編碼形式。

4.4 基于子路徑的局部搜索

針對車輛路徑問題這一類的組合優(yōu)化問題，由于問題解空間是離散的，不能直接運用公式(14)的方法來定義蝙蝠的局部搜索。因此，在當前最優(yōu)蝙蝠X*的周圍進行局部搜索時，首先按照5.1節(jié)的方式進行解碼，然后隨機選擇一條子路徑(需保證該子路徑內(nèi)客戶數(shù)大于1)，隨機選擇子路徑內(nèi)的兩個客戶，然后采用如下3種操作：

1)交換操作：交換其位置；

2)插入操作：將后一個客戶插入到前一個客戶的前面；

3)逆序操作：將它們之間的客戶序列根據(jù)原來的順序逆序排列。

基于子路徑的局部搜索策略步驟如下。

1)獲取當前最優(yōu)蝙蝠X*，并按照5.1節(jié)的方式進行解碼。令ct=1，設置最大嘗試次數(shù)ctmax。

2)令l←1。

3)若l=1，執(zhí)行交換操作；若l=2，執(zhí)行插入操作；若l=3，執(zhí)行逆序操作；若得到的新位置Xnew優(yōu)于X*，則接受Xnew,直接返回5)；否則，令l=l+1，重新執(zhí)行3)直至l>3，并不斷更新三種操作所獲得的最好的Xnew，返回4)。

4)令ct=ct+1，若ct

5)結(jié)束局部搜索。

4.5 慣性權(quán)重的調(diào)整

基本蝙蝠算法通過向處于最優(yōu)位置的蝙蝠學習，從而進行速度和位置更新，達到快速收斂，但這容易產(chǎn)生早熟現(xiàn)象，導致算法過早地處于停滯階段。為提高算法在運行前期的全局搜索能力和后期的局部搜索能力，本文在速度更新公式(9)中引入慣性權(quán)重，見下式(15)。

(15)

其中ω為慣性權(quán)重。在迭代初期，為使算法擁有較強的全局搜索能力，需要一個較大的ω；在迭代后期，需要在當前最優(yōu)解周圍進行精確搜索，需要較小的ω。為此，對慣性權(quán)重ω采用基于非線性調(diào)整的策略，見下式(16)。

(16)

式(16)中ωmax和ωmin分別表示最大慣性權(quán)重和最小慣性權(quán)重，max_iter為最大迭代次數(shù)，iter為當前迭代次數(shù)，β為區(qū)間[0,1]內(nèi)的常數(shù)。

4.6 交叉操作

為維持種群多樣性，避免算法過早地陷入局部極小，在每一次迭代完成后，采用精英保留策略，對種群內(nèi)蝙蝠進行優(yōu)劣排序，排在前一半的蝙蝠直接進入下一次迭代，而排在后一半的蝙蝠兩兩之間隨機進行交叉，隨機產(chǎn)生兩個交叉點，將第一個蝙蝠的交叉段移到另一個蝙蝠的首部，消去后面相同的元素，得到兩個新的位置，進入下一次迭代，如圖1所示為兩只蝙蝠進行交叉的過程，虛線框內(nèi)的元素為交叉段。不同于5.4節(jié)的所述的局部搜索，局部搜索為某條子路徑內(nèi)的客戶調(diào)整，而通過交叉操作，在很大程度上可以看作子路徑之間的客戶調(diào)整，這將將有利于擴大搜索空間，避免算法早熟。

圖1 蝙蝠的交叉操作

5 算法步驟

Step1：參數(shù)的初始化。設置主觀偏好值Cr*，隨機模擬次數(shù)M，最大迭代次數(shù)max_iter，蝙蝠種群規(guī)模pop_size，最大慣性權(quán)重ωmax和最小慣性權(quán)重ωmin，最大脈沖頻率fmax和最小脈沖頻率fmin，最大脈沖發(fā)射率r0，最大脈沖響度A0，脈沖發(fā)射率增加系數(shù)γ，響度衰減系數(shù)α。

Step2：隨機生成蝙蝠種群和每只蝙蝠的速度向量，計算其目標值，并找出當前群體中的最優(yōu)位置X*及其對應的目標值Z*。

Step3：對每只蝙蝠Xi，生成隨機數(shù)rand_1，若rand_1>ri，則對處于當前群體中最優(yōu)位置的蝙蝠X*按照5.4節(jié)方式進行局部搜索，產(chǎn)生一個新位置Xnew，否則，按照公式(10)、(11)、(15)、(16)進行更新，產(chǎn)生一個新位置Xnew。

Step4：對新位置Xnew進行評估。產(chǎn)生隨機數(shù)rand_2，若rand_2

Step5：對所有蝙蝠進行排序，更新當前最優(yōu)蝙蝠X*和其目標值Z*。

Step6：判斷是否滿足迭代終止條件，若滿足，則返回Step7。否則，保留排在前一半的蝙蝠，對排在后一半的蝙蝠進行交叉操作，代替原來的父代蝙蝠，并返回Step3。

Step7：終止迭代，輸出最優(yōu)蝙蝠X*和其目標值Z*。

6 仿真實驗

隨機生成一組實驗數(shù)據(jù)，包含40個客戶和1個車場，其中每個客戶的橫坐標和縱坐標均在范圍[100×100]內(nèi)隨機產(chǎn)生，車場的橫坐標和縱坐標均為50。車輛的標記載重量Q均為100噸，每個客戶的模糊需求在車輛標記載重量Q范圍內(nèi)隨機產(chǎn)生，相關(guān)參數(shù)設置如下表1：

表1 模型參數(shù)及蝙蝠算法參數(shù)設置

6.1 仿真結(jié)果

選取主觀偏好值Cr*為0.5，利用改進的蝙蝠算法進行仿真，利用Matlab編程得到如下的路徑安排(見表2和圖2)。

表2 最優(yōu)解對應的路徑安排

此時該路徑安排對應的總行駛距離為2 151.8944，額外行駛距離為134.9335，計劃行駛距離為2 016.960 9。

圖2 最優(yōu)解對應的路徑示意圖

6.2 主觀偏好值Cr*對結(jié)果的影響分析

以上基本參數(shù)保持不變，讓主觀偏好值Cr*在區(qū)間[0,1]內(nèi)變動，每個Cr*下隨機運行10次，并統(tǒng)計額外行駛距離、計劃行駛距離和總行駛距離的均值，表3為主觀偏好值Cr*對結(jié)果的影響分析。

從表3所統(tǒng)計的結(jié)果來看，當主觀偏好值Cr*為0時，其額外行駛距離最大，計劃行駛距離最小，此時決策者希望充分利用車輛的剩余載重能力，同時甘愿冒車輛剩余載重能力不能滿足下一客戶的“實際需求”而導致原計劃路線“失敗”的風險。隨著主觀偏好值Cr*的增加，額外行駛距離單調(diào)遞減，而計劃行駛距離單調(diào)遞增。當Cr*取值小于0.5時，隨著Cr*取值增加，額外行駛距離的減小量大于計劃行駛距離的增加量，因而總行駛距離逐步遞減；而當Cr*取值大于0.5時，隨著Cr*取值增加，額外行駛距離的減小量小于計劃行駛距離的增加量，因而總行駛距離逐步遞增。綜合分析看，當Cr*取值為0.5時，總行駛距離最小。

表3 主觀偏好值Cr*對結(jié)果的影響

6.3 本文算法與其它算法的對比分析

針對本節(jié)所選取的仿真實例，設定Cr*=0.5，種群規(guī)模pop_size=40，最大迭代次數(shù)max_iter=200，隨機模擬次數(shù)M=100，分別采用本文算法、基本蝙蝠算法、文獻[15]所介紹的粒子群算法、文獻[10]所介紹的遺傳算法、文獻[7]所介紹的差分進化算法進行仿真，對仿真實例各運行10次，其中基本蝙蝠算法參數(shù)中最大脈沖頻率fmax、最小脈沖頻率fmin、最大脈沖發(fā)射率r0、最大脈沖響度A0、脈沖發(fā)射率增加系數(shù)γ、響度衰減系數(shù)α等參數(shù)與本文一致；粒子群算法中慣性權(quán)重為0.5，加速度常數(shù)c1=1.5，c2=1.5；遺傳算法中交叉概率為0.3，變異概率為0.2；差分進化算法中最小交叉概率為0.3，最大交叉概率為0.9，變異縮放因子為0.5。對10次運行結(jié)果的總行駛距離最優(yōu)值、最差值和平均值進行比較，見下表4所示。

表4 五種算法運行結(jié)果對比

從表4可以看出，本文算法的最優(yōu)值、平均值明顯優(yōu)于基本蝙蝠算法、粒子群算法和遺傳算法，稍弱于差分進化算法。另外，五種算法取得最優(yōu)值時算法的迭代過程見下圖3所示。

圖3 五種算法的迭代過程比較

從迭代過程來看，本文提出的改進蝙蝠算法對比基本蝙蝠算法、粒子群算法和遺傳算法，能較快地搜尋到較優(yōu)解，這得益于該算法引入了基于非線性調(diào)整的慣性權(quán)重，并對處于較差位置的蝙蝠進行交叉，有效地擴大了搜索范圍，同時使用了基于子路徑的局部搜索策略，使算法又具備一定的局部搜索能力。不過，從最終解的質(zhì)量來看，該算法稍劣于差分進化算法，對該算法的改進還需要進一步的研究。

7 結(jié)論

本文針對帶模糊需求的車輛路徑問題，運用改進的蝙蝠算法進行了求解。在算法迭代過程中，為了有效地擴大搜索范圍，避免算法陷入早熟，引入非線性調(diào)整的慣性權(quán)重，對位置較差的蝙蝠進行交叉操作，同時，為了提高算法的局部搜索能力，提出了基于子路徑的局部搜索策略。最后給出了仿真實驗，分析了決策者主觀偏好值對目標值的影響，并將改進的蝙蝠算法與其他算法進行比較，經(jīng)過實驗證明，該算法對于解決此類模糊VRP問題是有效的。

[1]Dantzing G,Ramser J.The truck dispatching problem[J].Management Science,1959,10(6):80-91.

[2]Teodorovic D,et al.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J].Fuzzy Sets and Systems,1996,82:307-317.

[3]祝崇雋,劉 民,吳 澄,等.針對模糊需求的 VRP 的兩種 2-OPT 算法[J].電子學報,2001,29(8):1-2.

[4]張建勇,郭耀煌,李 軍.模糊需求信息條件下的車輛路徑問題研究[J].系統(tǒng)工程學報,2004,19(1):74-78.

[5]張建勇,李 軍.模糊車輛路徑問題的一種混合遺傳算法[J].管理工程學報,2005,19(2):23-26.

[6]張建勇,李 軍.模糊需求VRP的一種Sweeping啟發(fā)式算法[J].中國管理科學,2007,15(10):71-75.

[7]曹二保,賴明勇,張漢江.模糊需求車輛路徑問題研究[J].系統(tǒng)工程,2007,25(11):14-18.

[8]曹二保,賴明勇,李董輝.基于混合差分進化算法的模糊需求車輛路徑問題[J].系統(tǒng)工程理論與實踐,2009,29(2):106-113.

[9]彭北青.第三方物流配送車輛路徑問題模型及算法研究[D].武漢：華中科技大學，2009.

[10]戎麗霞.模糊需求條件下車輛路徑問題的模糊模擬[J].計算機工程與應用,2010,46(18):209-210.

[11]吳天羿,許繼恒.基于混合遺傳算法的模糊需求車輛路徑問題[J].解放軍理工大學學報(自然科學版) ,2014,15(5):475-482.

[12]Xue L. Fuzzy Simulation on the Vehicle Routing Problem[J].Information Technology Journal,2013,12(21): 6098-6102.

[13]Kuo R J, Zulvia Ferani E, Kadarsah Suryadi. Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand-A case study on garbage collection system[J]. Applied Mathematics and Computation,2012,219:2574-2588.

[14]Cao Erbao, Lai Ming yong. The open vehicle routing problem with fuzzy demands[J].Expert Systems with Application,2010,37(3):2405-2411.

[15]Yang Peng, Ye-mei Qian .A particle swarm optimization to vehicle routing problem with fuzzy demands[J]. Journal of Convergence Information Technology,2010,8(5).

[16]Yang X S. A new metaheuristic bat-inspired algorithm[C].Nature Inspired Cooperative Strategies for Optimization (NICSO 2010),Springer,2010:65-74.

[17]馬祥麗,張惠珍,馬 良.蝙蝠算法在物流配送車輛路徑優(yōu)化問題中的應用[J].數(shù)學的實踐與認識,2015,45(24):79-86.

[18]馬祥麗,張惠珍,馬 良.帶時間窗物流配送車輛路徑問題的蝙蝠算法[J].計算機工程與應用,2016，52(11):254-264.

[19]Zhou Y Q, Xie J, Zheng H Q. A hybrid bat algorithm with path relinking for capacitated vehicle routing problem[J]. Mathematical Problems in Engineering,2013:1-10.

[20] 劉長平,葉春明.具有Lévy 飛行特征的蝙蝠算法[J].智能系統(tǒng)學報,2013,8(3):240-246.

Vehicle Routing Problem with Fuzzy Demands Based onAn Improved Bat Algorithm

Zhu Hao

(Huzhou Vocational Technical College, Huzhou 313000，China)

As a new meta-heuristic, bat algorithm has not yet been applied to solve fuzzy vehicle routing problem until now. In this paper, the vehicle routing problem with fuzzy demands is considered at first, in which the final objective is to minimize the total distance, and then a fuzzy programming model based on fuzzy credibility theory is presented, in order to solve this problem, an improved bat algorithm with the coding method of customer number is introduced. In this algorithm, a stochastic simulation is proposed to calculate the additional distance, moreover, a nonlinear adjustment strategy for the inertia weight and a local search strategy on sub-route are designed at the stage of location updating of each bat, on the other hand, to improve the global search ability of this algorithm and avoid premature convergence, crossover operation on the worst bats is applied. To illustrate the effectiveness and good performance of the proposed algorithm, an example is carried out by using the random experimental data, and the influence of the decision-maker’s preference on the objective of this problem is discussed, moreover, the improved bat algorithm is compared with other algorithms.

bat algorithm; fuzzy demand; vehicle routing problem

2017-04-01；

2017-04-24。

湖州市自然科學基金 (2015YZ07)。

朱 顥(1980-)男，湖北監(jiān)利人，碩士，主要從事車輛路徑問題的研究。

1671-4598(2017)07-0276-06

10.16526/j.cnki.11-4762/tp.2017.07.069

TP302

A