蝙蝠算法及其在CVRPTW-SDP問題中的應用.pdf

1、蝙蝠算法(Bat Algorithm, BA)是 Yang受自然界中蝙蝠通過回聲定位的方式進行搜索、捕食的生物學特性的啟發(fā)，于2010年提出的一種新型群智能仿生優(yōu)化算法[1]。截至目前，BA算法用于求解的問題包括連續(xù)域函數優(yōu)化問題，如基準測試函數；組合優(yōu)化問題，如二值優(yōu)化問題、背包問題、最小比率TSP問題、可靠性冗余分配問題等。BA因其具有結構簡單、參數少、搜索能力強、穩(wěn)定性強、易于實現等優(yōu)點，在函數優(yōu)化、調度問題、模式識別、圖像處理、

2、故障診斷等方面表現出極大優(yōu)勢。
　　隨著電子商務的繁榮發(fā)展，車輛路徑問題(Vehicle Routing Problem, VRP問題)作為物流過程中的一項經典組合優(yōu)化問題，涉及到的客戶規(guī)模越來越大，所在區(qū)域分布也越來越廣泛，客戶對配送時間和同時取送貨的要求也越來越苛刻。由于電商的發(fā)展促使物流快遞公司增多，使得用戶的選擇面增多，物流快遞業(yè)的競爭也隨之加劇，使得用戶對配送時間、商家對送貨成本和有取送貨相關的需求更高。
　　結合

3、求解VRP問題的相關文獻可以了解到：對基本VRP問題求解較多，單獨考慮時間窗或取送貨為限制條件的VRP問題也不在少數，但是對結合時間窗懲罰值、車輛載重限制和取送貨的VRP問題求解較少。因此，本文設計求解考慮時間窗限制、車載限制和取送貨的VRP問題(Capacitated Vehicle Routing Problem with Time Windows, Simultaneous Delivery and Pickup and Vehi

4、cle Restraint, CVRPTW-SDP)。
　　由于VRP問題是NP-HARD難題，經典算法不能在有限時間內給出最優(yōu)解，但是可以使用智能算法在有限時間內給出相對較優(yōu)解。本文根據CVRPTW-SDP問題的特點以及BA算法的尋優(yōu)機制，研究并設計求解CVRPTW-SDP問題的離散蝙蝠算法（Discrete Bat Algorithm, DBA）。為了使用用來求解連續(xù)優(yōu)化問題的BA算法求解CVRPTW-SDP問題，定義蝙蝠算法

5、的離散化編碼策略和操作算子，需要進行離散化編碼的對象包括蝙蝠的所在位置和飛行速度；需要重新定義的操作算子包括加法操作算子、兩個解的減法操作算子以及修正操作算子。
　　為了進一步提高DBA算法的穩(wěn)定性，使用K-means聚類算法對每次迭代的初始解進行聚類分析，K-means算法應用到CVRPTW-SDP問題的求解目標就是把鄰近的配送點聚合成一類，因而加入聚類因子的DBA算法有更高的魯棒性和穩(wěn)定性，同時在一定程度上提高了DBA算法的求

6、解速度；為了進一步增強BA算法的局部搜索能力，借鑒遺傳算法的交叉、變異因子在較優(yōu)解附近進行局部搜索。
　　為了驗證該DBA算法的有效性，首先根據是否帶車載限制、時間窗和同時取送貨約束把CVRPTW-SDP問題拆分為TSP問題、CVRP問題、VRPTW問題、CVRPTW問題、CVRP-SDP問題、CVRPTW-SDP問題。然后分別設計出求解這6個 VRP問題的DBA算法。最后使用DBA算法與PSO、GA算法在相同運行時間內求解所得最