蝙蝠算法及其在CVRPTW-SDP問題中的應(yīng)用.pdf

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

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

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

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

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

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