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

【文章來(lái)源】：南京大學(xué)江蘇省 211工程院校 985工程院校 教育部直屬院校

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

常見(jiàn)VRP及其拓展問(wèn)題

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

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


本文編號(hào)：3465971