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

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

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

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

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