定向問題（Orienteering Problem,OP）是一類特殊的NP-hard組合優(yōu)化問題,其基本定義為:在指定的時(shí)間限制內(nèi)有序的經(jīng)過部分帶有一定收益的點(diǎn),使形成的路徑最終獲得的收益最大。由于良好的模型特性,定向問題越來越受到國內(nèi)外研究學(xué)者的關(guān)注,其基本模型及變體被廣泛應(yīng)用于旅行規(guī)劃、物流運(yùn)輸、救災(zāi)救險(xiǎn)、選址規(guī)劃等實(shí)際應(yīng)用場景中,以優(yōu)化資源分配,減少成本,獲取最大利益。按照求解的路徑個(gè)數(shù),定向問題可分為單路徑定向問題（OP）和多路徑團(tuán)隊(duì)定向問題（team Orienteering Problem,TOP）。本文主要研究單條路徑的優(yōu)化問題。在介紹完國內(nèi)外研究現(xiàn)狀后,引出本文研究的收益可變定向問題,考慮收益變化的兩種情況:一類是在整個(gè)時(shí)間限制內(nèi)收益可變的定向問題,稱為收益可變泛化定向問題;另一類是在時(shí)間窗內(nèi)收益變化的定向問題,稱為帶時(shí)間窗收益可變定向問題�？紤]收益可變情況的定向問題,進(jìn)一步豐富了該領(lǐng)域的研究,同時(shí)將收益可變的定向問題應(yīng)用到實(shí)際應(yīng)用場景中,體現(xiàn)了其應(yīng)用價(jià)值。具體的,考慮實(shí)際災(zāi)后搜救場景中,每個(gè)救援點(diǎn)有多種不同類型、不同重要程度的待救物資,且其價(jià)值會(huì)隨著救援時(shí)間的延長而面... 

【文章頁數(shù)】：65 頁

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

【文章目錄】：
摘要
abstract
1 緒論
    1.1 研究背景與意義
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 定向問題研究現(xiàn)狀
        1.2.2 收益可變定向問題相關(guān)研究現(xiàn)狀
    1.3 本文研究內(nèi)容
    1.4 論文結(jié)構(gòu)
2 遺傳算法在定向問題上的應(yīng)用
    2.1 遺傳算法概述
    2.2 基于遺傳算法的收益可變定向問題研究
        2.2.1 選擇算子
        2.2.2 交叉算子
        2.2.3 變異算子
        2.2.4 本文采用的遺傳算法
    2.3 本章小結(jié)
3 收益可變泛化定向問題
    3.1 問題描述及建模
    3.2 算法求解
        3.2.1 染色體編碼及適應(yīng)值計(jì)算
        3.2.2 種群初始化
        3.2.3 遺傳算子
    3.3 仿真實(shí)驗(yàn)
        3.3.1 仿真數(shù)據(jù)
        3.3.2 算法及參數(shù)
        3.3.3 實(shí)驗(yàn)結(jié)果及分析
    3.4 本章小結(jié)
4 帶時(shí)間窗收益可變定向問題
    4.1 問題描述及建模
    4.2 算法求解
        4.2.1 染色體編碼及適應(yīng)值計(jì)算
        4.2.2 種群初始化
        4.2.3 遺傳算子
    4.3 仿真實(shí)驗(yàn)
        4.3.1 仿真數(shù)據(jù)
        4.3.2 算法及參數(shù)
        4.3.3 實(shí)驗(yàn)結(jié)果及分析
        4.3.4 模型應(yīng)用
    4.4 本章小結(jié)
5 總結(jié)與展望
    5.1 總結(jié)
    5.2 展望
致謝
參考文獻(xiàn)
附錄


【參考文獻(xiàn)】：
期刊論文
[1]基于蟻群算法的m-團(tuán)隊(duì)定向問題求解[J]. 呂志民,楊娟,徐金梧.  計(jì)算機(jī)工程. 2006(24)
[2]遺傳算法在組合優(yōu)化問題中的應(yīng)用[J]. 馬立肖,王江晴.  計(jì)算機(jī)工程與科學(xué). 2005(07)
[3]基于小生境遺傳算法的物流配送路徑優(yōu)化研究[J]. 王輝,任傳祥,尹唱唱,郝新剛.  計(jì)算機(jī)應(yīng)用. 2009(10)
[4]遺傳算法研究綜述[J]. 葛繼科,邱玉輝,吳春明,蒲國林.  計(jì)算機(jī)應(yīng)用研究. 2008(10)
[5]基于蟻群算法的定向運(yùn)動(dòng)問題求解研究[J]. 楊理云.  計(jì)算機(jī)工程與設(shè)計(jì). 2009(10)
[6]遺傳算法選擇策略比較[J]. 張琛,詹志輝.  計(jì)算機(jī)工程與設(shè)計(jì). 2009(23)
[7]一種改進(jìn)蟻群算法研究和旅游景區(qū)路徑規(guī)劃問題求解[J]. 胡軍國,祁亨年,董峰,汪杭軍.  計(jì)算機(jī)應(yīng)用研究. 2011(05)
[8]動(dòng)態(tài)團(tuán)隊(duì)定向問題的模型及其優(yōu)化算法[J]. 柯良軍,尚可,馮祖仁.  西安交通大學(xué)學(xué)報(bào). 2011(06)
[9]一類求解帶時(shí)間窗的團(tuán)隊(duì)定向問題的改進(jìn)蟻群算法[J]. 柯良軍,章鶴,尚可,馮祖仁.  計(jì)算機(jī)科學(xué). 2012(04)
[10]基于改進(jìn)蟻群算法的定向問題研究[J]. 馮禹.  物流工程與管理. 2013(09)

博士論文
[1]基于局部搜索策略的若干組合優(yōu)化問題求解算法研究[D]. 李睿智.東北師范大學(xué) 2017

碩士論文
[1]改進(jìn)的遺傳算法求解TSP問題的應(yīng)用與研究[D]. 葛海明.江西理工大學(xué) 2016



本文編號(hào)：3705352