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

劉春苗　張惠珍　馬祥麗

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

關鍵詞車輛路徑問題；蝙蝠算法；離散；遺傳算法

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

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

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

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

經濟數學第 33卷第4期劉春苗等：求解車輛路徑問題的離散蝙蝠算法

2VRP的數學模型

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

3基本蝙蝠算法

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

蝙蝠算法是將虛擬蝙蝠類比成當前的可行域內所分布的搜索點，將蝙蝠飛行移動來不斷探測獵物的過程類比為尋找目標函數最優解的過程[8].

3.1虛擬蝙蝠的運動

4.2線路設計

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

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

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

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

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

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

6結論

本文將蝙蝠算法用于求解VRP問題，根據VRP問題的具體特性重新定義了蝙蝠算法的相關操作算子，設計出了求解VRP問題的離散蝙蝠算法.本文的實驗結果顯示出了離散蝙蝠算法在求解VRP問題上的可行性、有效性和優越性.

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

參考文獻

[1]吳斌. 物流配送車輛路徑問題及其智能優化算法[M]. 北京：經濟管理出版社，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調度問題中的應用研究[J]. 工業工程，2013，16（1）： 119-124.

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

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

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

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

[9]趙玉新，XinShe YANG，劉利強. 新興元啟發式優化方法[M]. 北京：科學出版社，2013.

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

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