基于用戶評(píng)價(jià)的路徑查詢優(yōu)化技術(shù)研究.pdf

1、現(xiàn)下于人們的日常生活中，基于地理位置信息的服務(wù)(LBS，Location-Based Services)是一種經(jīng)常性被使用的應(yīng)用服務(wù)，絕大多數(shù)以LBS為核心的實(shí)際應(yīng)用都依賴于路徑規(guī)劃技術(shù)，以提供人們相關(guān)交通性質(zhì)的應(yīng)用服務(wù)。隨著移動(dòng)互聯(lián)網(wǎng)以及地理信息定位技術(shù)的快速發(fā)展，人們能夠愈發(fā)容易地通過智能終端設(shè)備使用集成了路徑規(guī)劃技術(shù)的應(yīng)用程序，這些應(yīng)用程序可以為其用戶便捷地規(guī)劃優(yōu)質(zhì)的出行路徑?；谝陨鲜聦?shí)，路徑規(guī)劃算法在提高人們出行的質(zhì)量與效率上

2、起了很重要的作用。
　　在路徑規(guī)劃研究領(lǐng)域中，幾乎所有的研究工作所面臨的最大挑戰(zhàn)就是：如同著名的旅行商問題(Traveling Salesman Problem)一樣，其核心問題都是NP完全問題。換而言之，當(dāng)空間路網(wǎng)中的節(jié)點(diǎn)數(shù)目激增時(shí)，各種路徑規(guī)劃算法的算法效率就會(huì)讓人難以接受了，即無法在多項(xiàng)式時(shí)間內(nèi)給出精確解。除此之外，現(xiàn)存的路徑規(guī)劃算法很少考慮到對(duì)POI興趣點(diǎn)的可能限制，比如根據(jù)用戶的意圖活動(dòng)來限制所規(guī)劃出的路徑需涵蓋的興趣點(diǎn)

3、活動(dòng)類型。
　　本文主要研究基于活動(dòng)意圖的多準(zhǔn)則路徑規(guī)劃問題，其目的是為用戶規(guī)劃一條路徑，該路徑能夠在給定的距離或時(shí)間閾值內(nèi)最大化用戶滿意度。本課題不同于其他研究工作之處如下所示：
　　(1)不同于傳統(tǒng)的路徑規(guī)劃，本文引入了用戶滿意度這個(gè)概念。一個(gè)POI興趣點(diǎn)的用戶滿意度可以通過計(jì)算歷史用戶對(duì)其評(píng)分的平均值獲得，并在一定程度上反應(yīng)了該興趣點(diǎn)一般意義上的評(píng)價(jià)等級(jí)。
　　(2)本文不僅提出了基礎(chǔ)的精確算法，同時(shí)也提出了空間