不確定環(huán)境下在線旅行者問(wèn)題策略研究.pdf

1、C.H.Papadimiteiou和M.Yannakadis提出了加拿大旅行者問(wèn)題(Canadian Traveler Problem,簡(jiǎn)稱(chēng)CTP)。為了制定行走策略,Manasse S M和David S B將在線問(wèn)題和競(jìng)爭(zhēng)算法運(yùn)用到此問(wèn)題上,使該策略得到的解離最優(yōu)方案給出的解總在一定的比例之內(nèi),但以上的研究都與實(shí)際問(wèn)題有一定的差距,于是可恢復(fù)加拿大旅行者問(wèn)題提出,許多學(xué)者對(duì)此問(wèn)題進(jìn)行了進(jìn)一步的研究,但在這些研究中,在線的方法都是假設(shè)

2、旅行者在到達(dá)堵塞發(fā)生地時(shí)可獲得關(guān)于堵塞恢復(fù)時(shí)間的確定信息,這個(gè)假設(shè)與現(xiàn)實(shí)差異較大,如何使得堵塞恢復(fù)時(shí)間更接近于現(xiàn)實(shí)是有待研究的問(wèn)題。
　　本文將不確定性思想和方法引入其中,主要針對(duì)堵塞恢復(fù)時(shí)間不確定的旅行者問(wèn)題進(jìn)行了分析和研究,主要工作概括如下:
　　第一章首先介紹了加拿大旅行者問(wèn)題的背景,模型,策略和競(jìng)爭(zhēng)性能比的基本概念,然后闡述了堵塞可恢復(fù)和堵塞不可恢復(fù)的加拿大旅行者問(wèn)題的相關(guān)研究成果,最后對(duì)區(qū)間數(shù)的概念和相關(guān)性質(zhì)進(jìn)行了

3、總結(jié)。
　　第二章在堵塞可恢復(fù)且堵塞恢復(fù)時(shí)間隨機(jī)的基礎(chǔ)上,提出了堵塞恢復(fù)時(shí)間分別服從正態(tài)分布和指數(shù)分布的旅行者問(wèn)題,給出了堵塞恢復(fù)時(shí)間服從不同分布時(shí)采取等待策略和貪婪策略下的競(jìng)爭(zhēng)性能比的具體表達(dá)式,通過(guò)分析比較從而確定出最優(yōu)行走方案。
　　第三章在堵塞可恢復(fù)且堵塞恢復(fù)時(shí)間不確定的基礎(chǔ)上,引入了模糊的思想,提出了堵塞恢復(fù)時(shí)間為區(qū)間數(shù)的旅行者問(wèn)題,給出了旅行者在等待策略,迂回策略,混合策略下的競(jìng)爭(zhēng)性能比,并對(duì)相應(yīng)的問(wèn)題進(jìn)行了案例