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

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

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

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