路徑規(guī)劃算法的研究及應(yīng)用.pdf

1、路徑規(guī)劃近年來一個熱點(diǎn)研究問題，它被廣泛應(yīng)用于多個領(lǐng)域也形成了較完善的理論體系和算法基礎(chǔ)。隨著科學(xué)技術(shù)的不斷進(jìn)步，路徑規(guī)劃的應(yīng)用范圍也不斷擴(kuò)展，逐漸成為眾多領(lǐng)域的關(guān)鍵技術(shù)。其應(yīng)用最多的領(lǐng)域有：機(jī)器人避障行駛、智能交通、物流運(yùn)輸?shù)?。路徑?guī)劃方法已經(jīng)拓展到一切以點(diǎn)線構(gòu)成網(wǎng)絡(luò)拓?fù)涞亩嗄繕?biāo)問題當(dāng)中。因此，路徑規(guī)劃算法由于其廣泛的應(yīng)用范圍、種類繁多更是得到廣大研究人員廣泛的關(guān)注。本文將通過對路徑規(guī)劃算法進(jìn)行一定的研究，旨在應(yīng)用路徑規(guī)劃算法解決實(shí)際

2、應(yīng)用問題。
　　首先，本文將針對VRPTW（Vehicle Routing Problem with Time Window）問題構(gòu)建一種改進(jìn)的禁忌搜索（Tabu Search）算法進(jìn)行求解。改進(jìn)TS算法主要從初始解生成方式、禁忌結(jié)構(gòu)設(shè)計以及禁忌長度等方面進(jìn)行。文中將詳細(xì)介紹改進(jìn)TS算法的各個組成部分以及執(zhí)行流程，并通過實(shí)驗(yàn)對該改進(jìn)方法進(jìn)行效果驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，本文所構(gòu)建的算法對具有一定聚集分布特性的數(shù)據(jù)集能夠達(dá)到理想目標(biāo)，但是

3、也存在對隨機(jī)分布數(shù)據(jù)的適用性不足的缺陷。
　　通過對VRPTW問題的求解，本文將根據(jù)實(shí)際運(yùn)輸中可能出現(xiàn)新的運(yùn)送需求、或者原來客戶偶然提出的服務(wù)需求量的變化等情況，在VRPTW模型中增加動態(tài)需求，構(gòu)成 DCVRPTW（Demand Change Vehicle Routing Problem with Time Window）模型。本文將進(jìn)一步將改進(jìn)TS算法應(yīng)用到DCVRPTW中，并使用局部最小變動為目標(biāo)對動態(tài)需求進(jìn)行調(diào)整。通過實(shí)驗(yàn)

4、表明，本文所使用的局部調(diào)整算法對DCVRPTW問題具有一定的適用性并且加快調(diào)整速度從而保證實(shí)時需求。
　　最后，本文將進(jìn)一步將路徑規(guī)劃算法的應(yīng)用范圍進(jìn)行拓展探究。本文將路徑規(guī)劃技術(shù)與社交網(wǎng)絡(luò)進(jìn)行有機(jī)結(jié)合，從路徑規(guī)劃的角度重新審視社交網(wǎng)絡(luò)中不同用戶間信任關(guān)系或者影響力的計算問題。文中將構(gòu)建一種簡單并且高效的影響力計算方法并將該方法應(yīng)用到微博關(guān)注關(guān)系中以驗(yàn)證算法的有效性。為了將計算結(jié)果進(jìn)行實(shí)用性探究，本文將影響力大小應(yīng)用到好友推薦中，