隨著現(xiàn)代經(jīng)濟飛速發(fā)展,尤其是電子商務(wù)平臺的快速崛起,城市商品配送成為社會物流活動不可或缺的一部分,人們對物流配送服務(wù)的要求也在日益提高。車輛路徑規(guī)劃問題作為物流配送行業(yè)的重要問題,自提出以來就吸引了運籌優(yōu)化等領(lǐng)域工作者的廣泛研究。在商品配送領(lǐng)域,客戶對于交付的及時性要求日趨嚴格,帶時間窗的車輛路徑問題越來越受到重視,而對該問題的研究由于其復雜性目前還沒有突出進展。本文基于此開展研究,研究內(nèi)容主要有以下幾個方面。結(jié)合實際背景將城市商品配送問題抽象為多目標帶有時間窗約束的車輛路徑問題（VRPTW）,建立相應(yīng)的數(shù)學模型。本文模型基于電商企業(yè)考察了總行駛距離和未服務(wù)客戶點數(shù)量這兩個目標,基于車隊承運商考察了司機收入均衡程度和司機作業(yè)時間均衡程度這兩個目標。選擇設(shè)計ALNS算法對問題進行求解,對算法引入隨機性,改進了算子設(shè)計和選擇策略部分。利用Solomon公共算例集考察了本文ALNS算法的求解性能和效率。在某公司的實際大件派工項目背景下,將公司的業(yè)務(wù)數(shù)據(jù)和相關(guān)的要求與論文模型進行匹配,將多目標優(yōu)化問題轉(zhuǎn)化為求解目標矩陣和理想值矩陣最短歐式距離的問題,并且利用ALNS算法進行求解。對比ALNS算... 

【文章來源】：南京大學江蘇省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：78 頁

【學位級別】：碩士

【部分圖文】：

常見VRP及其拓展問題

南京大學碩士學位論文第二章車輛路徑問題類型及求解方法—16—圖2-2LNS算法解決VRP問題示例2.5ALNS算法介紹自適應(yīng)大規(guī)模鄰域搜索算法(ALNS)是大規(guī)模鄰域搜索算法的一種擴展，由Ropke和Pisinger[23]提出。ALNS算法不同于LNS算法的地方主要在于ALNS在搜索過程中采用多種移除和插入的算子，在每一輪算法迭代中只會選擇一個移除和插入算子，算子的每一輪的選擇概率與其歷史表現(xiàn)相對應(yīng)，并且隨之發(fā)生變化，而LNS只采用一個移除算子和一個插入算子。ALNS算法的流程如算法2-3所示。算法2-3：AdaptiveLargeNeighborSearchInput:probleminstanceIcreateinitialsolution=s∈()whilestoppingcriterianotmetdofori=1,…,selectr∈R,d∈Daccordingtoprobabilitiesp,=(())ifaccept(,,)=,if(,)<()=endifendifendforendwhilereturn自適應(yīng)大規(guī)模鄰域搜索方法通過使用啟發(fā)式方法探索復雜的鄰域，使用較大的鄰域可以在每次迭代中找到更好的候選解，從而遵循更有希望的搜索路徑。

南京大學碩士學位論文第二章車輛路徑問題類型及求解方法—17—圖2-3ALNS算法解決VRP問題示例相對于其他算法，ALNS的優(yōu)勢包括：(1)對優(yōu)化模型要求寬松ALNS算法類似GA算法，對優(yōu)化模型的目標沒有可微可導等要求，同時優(yōu)化目標的設(shè)置基本不影響算法本身的求解效率。(2)ALNS算法的框架容易拓展ALNS算法可以提供類似模塊化的組合方案，根據(jù)求解的問題對算子進行自定義和組合。ALNS算法在提出時即被用來解決VRPPDPTW問題，對于其他類型的VRP問題此算法同樣擁有良好的求解能力。(3)能實現(xiàn)不同的搜索策略在ALNS算法中，可以根據(jù)具體的優(yōu)化問題，設(shè)計相應(yīng)類型的算子，利用不同算子的鄰域操作可以實現(xiàn)不同的搜索策略。(4)擁有更大的解空間ALNS算法相比于普通的本地搜索、鄰域搜索算法，可以探索更大的鄰域空間，因而有可能獲得更優(yōu)的解。(5)對算子的自適應(yīng)選擇通過給定算子的自適應(yīng)選擇機制，在ALNS算法中可以對算子的表現(xiàn)進行記錄打分，進而可以通過反饋機制決定下一次迭代時算子的選擇概率，表現(xiàn)更好的算子更容易被選擇進行鄰域操作。自然，相同問題的不同實例，甚至不同的解決方案都由不同的移除和插入算子構(gòu)成，其成功程度也各不相同，通常很難預(yù)測哪種啟發(fā)式的構(gòu)造是最有利的。


本文編號：3465971