物流配送優(yōu)化(第二章)-資料下載頁
2025-03-10 15:36本頁面
【正文】 1 kiy ik26 ?模型 ? ? ?? ? ?Vi VjKkijkij xcMinKMin1 , ?????????????????? ? ?????????? ?? ?? ???? ?? ??? ??????kjiyxkSVSSxkViyxxKyViyKkCydikijkSi SjijkikVjjikVjijkKkkKkikViiki, ,10,(5) ,2||},0{\ ,1||(4) , (3) (2) }0{\ 1(1) ,2,1 101或?27 VRP的計算復(fù)雜性和求解算法 ?對 VRP求解算法的研究一直是重點(diǎn)和難點(diǎn)。 ?現(xiàn)已證明，幾乎所有類型的 VRP均為 NP難問題。 ?VRP之所以引起學(xué)術(shù)界的極大重視，除了它具有廣泛的應(yīng)用背景外，是因為相當(dāng)難解，從而富有挑戰(zhàn)性。 ?目前 已提出了許多求解 VRP的算法， 究其實質(zhì)，可 分為 精確算法 和 啟發(fā)式算法 兩大類。 28 ? 精確算法 ?指可求出其最優(yōu)解的算法，且一般要求問題能用相應(yīng)的數(shù)學(xué)模型表示。 ?目前用于求解 VRP的精確算法主要有 分支定界法 （ BranchandBound Algorithm） 分支切面法 （ BranchandCut Algorithm） 割平面法 （ Cutting Plane Method） ?因 VRP是 NP難問題，其精確算法的計算量隨問題規(guī)模的增大呈指數(shù)增長，在實際中的應(yīng)用范圍有限。但在對相應(yīng)的啟發(fā)式算法的質(zhì)量評估等理論研究工作中卻很有意義。 ?從實際應(yīng)用的角度來說，公認(rèn)的明智做法是設(shè)計相應(yīng)的啟發(fā)式算法來求出問題的近優(yōu)解。 29 ? 啟發(fā)式算法 ?是基于直觀或經(jīng)驗構(gòu)造的算法，一般不要求非得將問題表述為某種標(biāo)準(zhǔn)的數(shù)學(xué)模型；在可接受的計算量內(nèi)求出問題的滿意解，但不能保證最優(yōu)。 ?19601990年間，所提出的求解 VRP的啟發(fā)式算法都是基于 經(jīng)典的啟發(fā)式方法 的思想。 ?1990年以來，隨著 通用啟發(fā)式算法 （ metaheuristics）的 出現(xiàn)，如模擬退火 (SA)、禁忌搜索 (TS)、遺傳算法 (GA)等，研究運(yùn)用這些算法來構(gòu)造求解 VRP的算法已成為主流和當(dāng)前的研究熱點(diǎn)，并已取得了許多令人鼓舞的成果。 ?求出的解高出最優(yōu)解（或已知最好解）： ? 基于 經(jīng)典啟發(fā)式方法： 210%； ? 基于 通用啟發(fā)式方法： % 30 ? 發(fā)展趨勢 ?為了使現(xiàn)代啟發(fā)式算法能在商業(yè)軟件中得到應(yīng)用，開發(fā)更快、更簡單、更健壯的算法已成為一種趨勢，盡管這將在解的質(zhì)量方面帶來一些小損失。 ?在算法測試與比較方面，研究人員目前已取得一個共識：必須使用公開的標(biāo)準(zhǔn)測試算例（ benchmark instances)對所提出的算法進(jìn)行測試。這樣，其測試結(jié)果才具有可比性和說服力。 31
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1