求解車輛路徑問題的離散蝙蝠算法

劉春苗　張惠珍　馬祥麗

摘要根據(jù)車輛路徑問題的數(shù)學(xué)模型，分析了它的具體特征，從而對BA的操作算子又進行了重新定義，設(shè)計了求解VRP問題的離散蝙蝠算法，并通過實例測試將離散蝙蝠算法與其他算法進行比較，驗證了該算法求解VRP問題的有效性與可行性.

關(guān)鍵詞車輛路徑問題；蝙蝠算法；離散；遺傳算法

中圖分類號U492.3文獻標識碼A

AbstractBased on the mathematical model and specific features of the vehicle routing problem（VRP），this paper redefined the operators for bat algorithm（BA） and designed a discrete bat algorithm （DBA） for solving it. And numerical experiment was implemented by using DBA to solve a testing example， and its solution was compared with the one obtained with the stateoftheart algorithm. The results show that DBA can effectively and feasibly solve VRP.

Keywordsvehicle routing problem； bat algorithm； discrete； genetic algorithm

1引言

車輛路徑問題（Vehicle Routing Problem， VRP）主要目的是在一定的約束條件下，最大化滿足客戶需求的同時消耗最少的時間，所行駛的路程最短，成本最小，學(xué)者們也通常稱它為有能力約束的車輛路徑問題（Capacity Vehicle Routing Problem， CVRP），它最早來源于貨物交通運輸工程領(lǐng)域[1]，是車輛調(diào)度中最基本的問題之一.求解旅行商問題（Traveling Salesman Problem， TSP）和裝箱問題（Bin Packing Problem， BPP）分別是求解車輛路徑問題（VRP）的兩種特殊情況，研究者們通常把VRP問題看作是這兩種問題的的混合問題，其已被證明屬于NP完全問題.

車輛路徑問題（VRP）首次由美國學(xué)者在1959年提出[2]，其逐漸成為運籌學(xué)與組合優(yōu)化領(lǐng)域的研究熱點，并引起了廣大學(xué)者們的高度重視.目前，求解VRP問題的經(jīng)典算法主要有：網(wǎng)絡(luò)流算法、列生成算法、和割平面法等等，但是，這些經(jīng)典的方法僅適用于求解小規(guī)模車輛路徑問題；面對大規(guī)模的VRP問題時，其龐大的計算量導(dǎo)致計算速度緩慢，運行效率低，甚至出現(xiàn)無法求解的情況.隨著遺傳算法、蟻群算法、遺傳算法、禁忌搜索算法、粒子群算法等智能優(yōu)化算法的提出及其在組合優(yōu)化問題中的應(yīng)用，求解大規(guī)模VRP問題得到了較好地解決.

2010年劍橋大學(xué)的一名資深研究員楊提出了一種新的群體智能優(yōu)化算法——蝙蝠算法[3]，它是根據(jù)微型蝙蝠在自然界中通過回聲定位來捕捉獵物和躲避障礙物的生物學(xué)特性研究出的一種算法，是一種基于種群的隨機尋優(yōu)算法.目前為止很少有學(xué)者將蝙蝠算法應(yīng)用到離散問題中去，還停留在解決求解連續(xù)函數(shù)優(yōu)化問題中.學(xué)者盛曉華等人[4]在2013年通過分析PFSP調(diào)度的問題發(fā)現(xiàn)蝙蝠算法能夠更加有效地解決這類離散型車輛路徑問題；在同一年，李枝勇[5]等人，他們設(shè)計出了求解TSP問題的離散蝙蝠算法；在2014年，中國學(xué)者馬邦雄[6]等人提出了一種蝙蝠退火算法，采用ROV編碼的方式實現(xiàn)了蝙蝠算法（BA）的連續(xù)編碼.

目前，尚未有文獻將蝙蝠算法應(yīng)用于VRP問題的求解，將蝙蝠算法應(yīng)用于VRP問題的求解是一個新的研究方向.

經(jīng)濟數(shù)學(xué)第 33卷第4期劉春苗等：求解車輛路徑問題的離散蝙蝠算法

2VRP的數(shù)學(xué)模型

車輛路徑優(yōu)化問題一般描述為：假設(shè)配送中心（這里的配送中心用0來表示）最多可以用K（k=1，2，…K）輛車對L（i=1，2，…L）個客戶進行配送運輸服務(wù)，配送運輸車輛的載重量分別為qk（k=1，2，…K），每個客戶的需求量分別為gi=（i=1，2，…L），客戶i到客戶j的運輸成本為cij（可以是距離、費用等），要求配送中心用最短的行駛距離或運輸費用完成對所有客戶的配送任務(wù).

3基本蝙蝠算法

蝙蝠是一種神奇的動物，有很強的回聲定位能力.微型蝙蝠使用一種叫做回音定位的聲波定位器，主要用來探測食物位置，躲避障礙物，捕捉獵物，找到自己的巢穴等.它們發(fā)出的聲音脈沖很響亮這樣更有助于根據(jù)從周圍物體反射回來的回聲響度和蝙蝠的雙耳時間差去建立一個立體的三維環(huán)境場景[7].

蝙蝠算法是將虛擬蝙蝠類比成當(dāng)前的可行域內(nèi)所分布的搜索點，將蝙蝠飛行移動來不斷探測獵物的過程類比為尋找目標函數(shù)最優(yōu)解的過程[8].

3.1虛擬蝙蝠的運動

4.2線路設(shè)計

本文采用最近鄰算法構(gòu)造初始配送路線，采用2opt算法對路線進行改進.下面分別給出配送路線構(gòu)造和改進的方法.

配送線路構(gòu)造方法最鄰近算法（Nearest Neighbor Algorithm，NNA）[10]：首先取配送中心（0）作為線路的起點；然后尋找與當(dāng)前線路中最后一個結(jié)點的距離最近的點，并將其加入配送線路，重復(fù)該操作，直到所有的點均已被考慮，就得到一條配送線路.

值得注意的是：利用上述最近鄰法得到的是一條包含所有客戶點的配送線路.本文所設(shè)計的離散蝙蝠算法將會根據(jù)線路中客戶的排序，車輛載重量和客戶需求量進一步求解實際配送車輛數(shù)及相應(yīng)的配送路線.

配送路線的改進方法——2opt算法[10]：2opt算法的基本思想是對給定的初始回路，通過每次交換兩邊來改進當(dāng)前解.

例如如圖2（a）所示，車輛初始得行駛路徑為：由客戶i到達客戶i+1，再由客戶i+1經(jīng)若干客戶后到達客戶j，然后再訪問客戶j+1；采用2opt算法對圖2（a）中得路線進行變換，若以（i，j）、（i+1，j+1）替代（i，i+1）、（j，j+1），則可變?yōu)槿鐖D2（b）所示的配送路線.

由表2可知：本文采用離散蝙蝠算法求解的最短路徑（r）897.56km要優(yōu)于文獻[11]中遺傳算法求解的最優(yōu)路徑964.48km；并且本文為最優(yōu)路徑安排車輛時只需要安排5輛車即可，而文獻[11]需要安排6輛車才能滿足需要，這樣勢必會增加一定的成本.從對比分析可知，蝙蝠算法對于求解CVRP問題是行之有效的，且該算法參數(shù)設(shè)置簡單，易于操作，運行周期短，便于求解大規(guī)模VRP問題.

6結(jié)論

本文將蝙蝠算法用于求解VRP問題，根據(jù)VRP問題的具體特性重新定義了蝙蝠算法的相關(guān)操作算子，設(shè)計出了求解VRP問題的離散蝙蝠算法.本文的實驗結(jié)果顯示出了離散蝙蝠算法在求解VRP問題上的可行性、有效性和優(yōu)越性.

蝙蝠算法參數(shù)設(shè)置簡單，在各類VRP問題的求解中擁有廣闊的應(yīng)用前景.為了擴展蝙蝠算法的應(yīng)用領(lǐng)域，并進一步研究蝙蝠算法求解相關(guān)問題的可行性和有效性，利用離散蝙蝠算法求解設(shè)施選址問題將是作者下一步的研究工作.

參考文獻

[1]吳斌. 物流配送車輛路徑問題及其智能優(yōu)化算法[M]. 北京：經(jīng)濟管理出版社，2013.

[2]G B DANTZIG，J H RAMSER.The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.

[3]X S YANG. A new metaheuristic batinspired algorithm[C]//Nature Inspired Cooperative Strategies for Optimization （NISCO 2010） （Eds. J R Gonzalez et al.），SCI 284，2010： 65-74.

[4]盛曉華，葉春明. 蝙蝠算法在PFSP調(diào)度問題中的應(yīng)用研究[J]. 工業(yè)工程，2013，16（1）： 119-124.

[5]李枝勇，馬良，張惠珍. 求解最小比率旅行商問題的離散蝙蝠算法[J]. 計算機應(yīng)用研究，2015，32（12）：356-359.

[6]馬邦雄，葉春明. 基于蝙蝠退火算法的無等待流水線調(diào)度問題研究[J]. 數(shù)學(xué)理論與應(yīng)用，2014，34（1）：92-101.

[7]孫文捷，張惠珍，張健，等. 基于Fuch映射的混沌蝙蝠算法[J]. 上海理工大學(xué)學(xué)報，2014，36（1）：26-30.

[8]高珊，馬良，張惠珍. 函數(shù)優(yōu)化的小生境蝙蝠算法[J]. 數(shù)學(xué)的實踐與認識，2014，44（15）：253-260.

[9]趙玉新，XinShe YANG，劉利強. 新興元啟發(fā)式優(yōu)化方法[M]. 北京：科學(xué)出版社，2013.

[10]李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國物資出版社，2001.

[11]陳湘州，黎志明，劉祖潤. 一種改進的整數(shù)編碼遺傳算法在車輛路徑優(yōu)化問題中的應(yīng)用[J]. 南方冶金學(xué)院學(xué)報，2004，25（1）：36-41.