需求可拆分車(chē)輛路徑問(wèn)題的迭代局部搜索算法研究.pdf

1、需求可拆分車(chē)輛路徑問(wèn)題(the Split Delivery Vehicle Routing Problem，SDVRP)是帶容量限制車(chē)輛路徑問(wèn)題（Capacitated Vehicle Routing Problem，CVRP）的變形，SDVRP放松了CVRP模型中一個(gè)客戶(hù)的需求只能由一輛車(chē)提供服務(wù)的限制。為了解決SDVRP，本文提出一種多起點(diǎn)的迭代局部搜索(multi-restart iterated localsearch，MRS

2、ILS)算法。
　　首先使用GENIUS算法求解出一個(gè)大的旅行商問(wèn)題(Travelling SalesmanProblem，TSP)解，然后以車(chē)輛的容量為標(biāo)準(zhǔn)，分割大的TSP解，使分割后的路徑滿(mǎn)足車(chē)輛的容量限制，作為MRSILS算法的初始解。迭代局部搜索算法是針對(duì)客戶(hù)節(jié)點(diǎn)進(jìn)行的，節(jié)點(diǎn)的局部搜索順序按照其刪除節(jié)約代價(jià)從大到小進(jìn)行。通過(guò)將節(jié)點(diǎn)從當(dāng)前解中刪除然后將此節(jié)點(diǎn)重新插入到其在當(dāng)前解中的最優(yōu)位置。提出了一個(gè)適用于SDVRP問(wèn)題模型

3、的貪婪的節(jié)點(diǎn)重新插入算法，嘗試通過(guò)這個(gè)簡(jiǎn)單的重新插入算法來(lái)優(yōu)化當(dāng)前解。在尋找最優(yōu)位置時(shí)，考慮節(jié)點(diǎn)的需求可拆分這一策略，即考慮需求可能被一個(gè)或多個(gè)車(chē)輛提供服務(wù)。如果經(jīng)過(guò)一定次數(shù)的連續(xù)的局部搜索，并且在這個(gè)過(guò)程中，當(dāng)前解的質(zhì)量均未得到提升，我們對(duì)當(dāng)前解進(jìn)行擾動(dòng)，然后從擾動(dòng)得到的解出發(fā)，繼續(xù)進(jìn)行局部搜索。為了在擴(kuò)大搜索空間的同時(shí)保證重新開(kāi)始局部搜索解的質(zhì)量，我們?cè)O(shè)計(jì)了一個(gè)精英解緩沖池策略，將一組得到最優(yōu)解可能性較大的精英解放入這個(gè)池中，從這個(gè)