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

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

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

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