室內(nèi)路徑優(yōu)化算法研究

1、室內(nèi)路徑優(yōu)化算法研究摘 要在基于室內(nèi)定位和物聯(lián)網(wǎng)技術(shù)的支持下，論文針對室內(nèi)經(jīng)營場所的多目的地路徑優(yōu)化算法進(jìn)行研究。二邊逐次修正法是針對哈密頓回路進(jìn)行的優(yōu)化，不適合室內(nèi)的多目的地開放性路徑的特點(diǎn)，論文改進(jìn)了二邊逐次修正法，并利用矩陣翻轉(zhuǎn)對多目標(biāo)點(diǎn)的路徑順序進(jìn)行了優(yōu)化，獲得室內(nèi)行進(jìn)路徑的較優(yōu)解，達(dá)到了優(yōu)化的效果。論文算法模型進(jìn)行了應(yīng)用實(shí)現(xiàn)，進(jìn)行了仿真實(shí)驗(yàn)的測試，并對測試結(jié)果進(jìn)行了分析，測試結(jié)果反映該算法達(dá)到實(shí)際的需求。關(guān)鍵字 室內(nèi)路徑優(yōu)化； np難度； 二次逐邊修正； 矩陣翻轉(zhuǎn) algorithm of indoor route optimization with the support of i

2、ndoor location technology, this paper achieves a route optimization for customers with multi-walking destinations in indoor environment. two sides successive correction method is for optimization of hamiton cycle, not suitable for the indoor open route optimization. two sides successive correction m

3、ethod will be corrected in this paper. iimplementation of the algorithm is completed in this paper. a large number of testing showed that he algorithm was efficient to meet the actual need.key words: indoor route optimization; np-hard problems; two sides successive correction method; vertex-exchange

4、 0 引言隨著經(jīng)濟(jì)飛速發(fā)展，出現(xiàn)越來越多的大型購物中心、娛樂場所，展覽中心，且內(nèi)部布局越來越復(fù)雜，在這樣的大型室內(nèi)場所中的顧客往往需要花大量的時(shí)間在查找自己的行進(jìn)路線，不僅費(fèi)時(shí)，而且降低了顧客的體驗(yàn)。隨著移動智能手機(jī)的普及和室內(nèi)定位技術(shù)的成熟，為用戶提供多目標(biāo)路徑推薦提供了技術(shù)支持。1 2 在大型室內(nèi)經(jīng)營場所，消費(fèi)者往往會有多個(gè)行進(jìn)目的地，而如何節(jié)省用戶行進(jìn)時(shí)間，在最短的時(shí)間完成消費(fèi)目標(biāo)，以提高用戶的消費(fèi)體驗(yàn)水平，使得消費(fèi)場所對顧客具有更大吸引力，這是室內(nèi)場所路徑優(yōu)化的目標(biāo)。本課題的核心是室內(nèi)多目的地路徑的動態(tài)優(yōu)化算法的設(shè)計(jì)和實(shí)現(xiàn)，其中多目的地指的是用戶在智能手機(jī)終端上一次性選擇多個(gè)想要去的服

5、務(wù)點(diǎn)，完成顧客對個(gè)人服務(wù)的興趣選擇。根據(jù)在經(jīng)營場所中實(shí)際需求，文中設(shè)定用戶對多個(gè)服務(wù)點(diǎn)的選擇沒有先后的區(qū)別， 并設(shè)定行進(jìn)的消費(fèi)者并不一定會到出發(fā)點(diǎn)。用戶多目的地路徑是指顧客要完成所有選擇的多目的地的行進(jìn)路徑序列。多目的地路徑優(yōu)化是指在所有的多目的地行進(jìn)路徑序列中，找到最優(yōu)的一條行進(jìn)路徑序列。本課題的研究的算法要實(shí)現(xiàn)產(chǎn)生一個(gè)優(yōu)化后的完成多個(gè)目標(biāo)點(diǎn)的行進(jìn)順序，使得時(shí)間權(quán)值和最小。對于n個(gè)行進(jìn)目標(biāo)點(diǎn)，遍歷整個(gè)排序的時(shí)間復(fù)雜度是o(n!)，這種情況的時(shí)間復(fù)雜度無法滿足實(shí)時(shí)性需求。而多目的地路徑優(yōu)化是一個(gè)np難度問題。隨著人們對np-hard問題的研究，提出了許多用于解決該類問題的方法，例如遺傳算法、蟻

6、群算法、模擬退火算法、dijistra算法、人工神經(jīng)網(wǎng)絡(luò)方法等等。而目前路徑優(yōu)化最常用的領(lǐng)域就是路徑導(dǎo)航、物流配送、人員疏散等領(lǐng)域。目前的研究中主要采用進(jìn)化算法進(jìn)行優(yōu)化的研究成果如文獻(xiàn)3，提出的退火螞蟻代理算法對復(fù)雜大型的環(huán)境中進(jìn)行路徑的動態(tài)優(yōu)化，文獻(xiàn)4采用算法粒子群優(yōu)化針對物流配送特點(diǎn)，對開放的車輛路徑優(yōu)化問題進(jìn)行算法研究，文獻(xiàn)5采用遺傳算法優(yōu)化基于移動設(shè)備的車輛導(dǎo)航最短行進(jìn)時(shí)間的路徑，考慮到交通密度和最低行駛速度的影響因素，研究車輛行駛的最短時(shí)間路徑問題的算法。文獻(xiàn)6是基于基因算法對動態(tài)的隨機(jī)路網(wǎng)進(jìn)行路徑優(yōu)化。文獻(xiàn)7是基于改進(jìn)的dijkstra算法對基于位置的導(dǎo)航路徑進(jìn)行優(yōu)化。二邊逐次修正

7、法是尋找最短hamilton 圈的比較新而且高效的算法。在這個(gè)算法中，通過按照一定的規(guī)則交換頂點(diǎn)，重新分配無向圖的權(quán)值矩陣的數(shù)據(jù)，以找到h圈的最優(yōu)解。本文根據(jù)室內(nèi)多目的地的路徑特征，對矩陣翻轉(zhuǎn)算法進(jìn)行了修正，采用二邊逐次修正法的交換頂點(diǎn)的規(guī)則，利用修正的矩陣翻轉(zhuǎn)算法完成了路徑的優(yōu)化算法設(shè)計(jì)與實(shí)現(xiàn)。獲得室內(nèi)行進(jìn)路徑的較優(yōu)解，時(shí)間復(fù)雜度和空間復(fù)雜度達(dá)到了優(yōu)化的效果。781 算法分析與設(shè)計(jì)1.1二邊逐次修正法求最佳h圈目的地之間的關(guān)系是用時(shí)間權(quán)值來衡量的，假設(shè)任意兩點(diǎn)之間的時(shí)間權(quán)值w( e )都已知，那么目標(biāo)點(diǎn)集合v和它們之間帶時(shí)間權(quán)值的邊集組成的圖g必定是完備圖。如果室內(nèi)行走路徑為hamiton

8、回路，路徑優(yōu)化問題為找到一條時(shí)間權(quán)值和最小的環(huán)路，即在完備圖g中尋找最佳h圈，這是一np難度問題，可以采用二次逐邊修正法來實(shí)現(xiàn)優(yōu)化，獲得較優(yōu)解。二邊逐次修正法的算法過程如下：圖1 完備圖1)在完備圖1中，任取初始h圈：c0 = v1 , v2 , , vi , , vj , , vn , v1。2)對所有的i， j， 1 i + 1 j n，若w ( vi , vj ) +w ( vi + 1 , vj + 1 ) w ( vi , vi + 1 ) +w ( vj , vj + 1 ) ，則在c0 中刪去邊w ( vi , vi+1 )和w ( vj , vj + 1 )而加入邊w ( vi

9、 , vj )和w ( vi+1 , vj + 1 ) ，形成新的h圈c1，即c1 = v1 , v2 , , vi , vj ,vj - 1 , , vi + 1 , vj + 1 , , vn , v1。3) 對c重復(fù)步驟2，直到條件不滿足為止，最后得到的c即為所求。1.2 二邊逐次修正法的算法改進(jìn)二邊逐次修正法存在的問題分析：二邊逐次修正法針對的是一個(gè)漢密爾頓環(huán)路，即從起點(diǎn)出發(fā)最終回到起點(diǎn)的環(huán)路；對于本課題，根據(jù)實(shí)際場景需求，尋找的是從顧客當(dāng)前位置出發(fā)，經(jīng)過一系列選定的消費(fèi)目的地，最后到達(dá)商場出口點(diǎn)的一條優(yōu)化路徑。實(shí)際的路線是開環(huán)的路徑，而不是環(huán)路。這里稱為改進(jìn)的開放完備路徑圖。如圖2所

10、示。v1是當(dāng)前位置，也可以為入口，需要經(jīng)過 v2 , , vi , , vj , , vn , 到達(dá)出口ve，圖2中n=6。（注：圖中vi ,vj之間的實(shí)線表示兩點(diǎn)之間是無向的，而帶箭頭的虛線表示兩點(diǎn)之間是有向的。不可達(dá)的方向權(quán)值為無窮大。圖2 為室內(nèi)經(jīng)營場所設(shè)計(jì)的開放的完備路徑圖圖2 和圖1不同，前者不是一個(gè)完備圖，如果我們?nèi)玑槍D1的方法進(jìn)行逐邊修正，并不一定獲得的路徑的較優(yōu)優(yōu)的。即：在圖2中，如果 w ( vi , vj ) +w ( vi + 1 , vj + 1 ) w ( vi , vi + 1 ) +w ( vj , vj + 1 ) ，刪除邊 w ( vi , vi + 1 )

11、 和 w ( vj , vj + 1 ), 加上邊 w ( vi , vj ) and w ( vi + 1 , vj + 1 )，將路線由r0 = v1, v2, ., vi, ., vj, ., vn, ve 轉(zhuǎn)化為r1= v1 , v2 , , vi , vj ,vj - 1 , , vi + 1 , vj + 1 , , vn , ve , 但在圖2中, vj ,vj - 1 , , vi + 1可能長于 vi + 1 ,vj ,vj 1 . r1不一定優(yōu)于r0. 所以針對室內(nèi)的路徑特點(diǎn)，需要對二邊逐次修正法進(jìn)行改進(jìn)。1.3 改進(jìn)后的算法：.在圖2中, 1）設(shè)初始路徑為 r0 = v1

12、, v2, ., vi, ., vj, ., vn, ve，其中 v1, ve 設(shè)為入口和出口，它們之間是不可達(dá)的。2）對于所有的 i， j， 1 i + l j n，如果 w ( vi , vj ) +w ( vi + 1 , vj + 1 ) w ( vi , vi + 1 ) +w ( vj , vj + 1 ) ，并且如果 vj ,vj - 1 , , 到 vi + 1的權(quán)小于或等于從vi + 1, vj - 1, 到 vj 的權(quán)值, 去掉邊 w( vi , vi + 1 )和 w ( vj , vj + 1 ) ,加上 w ( vi , vj ) 和 w ( vi + 1 , vj

13、+ 1 ), 將 r0 轉(zhuǎn)化為r1， r1 = v1 , v2 , , vi , vj ,vj - 1 , , vi + 1 , vj + 1 , ., vn , ve. .3）重復(fù)步驟2, 直到條件不滿足為止，最后獲得的路徑為最優(yōu)解。如圖2有六個(gè)點(diǎn)之間的邊上數(shù)值為兩個(gè)點(diǎn)之間的時(shí)間權(quán)值。如選取初始路徑r0 = v1 v2 v3 v4 v5 v6 ve ，其總權(quán)為237。圖3 部分路徑圖由于w (1, 4) +w (2, 5) w (1, 2) +w (4, 5) (見圖3) ，并且v4 ,v3 ,到 v2的權(quán)等于從v2，v3, 到 v4 的權(quán)值，所以去掉邊v1 v2 , v4 v5 添加邊v1

14、 v4 , v2 v5 得到較優(yōu)的路徑r1為： r1 = v1 v4 v3 v2 v5 v6 ve ，其總權(quán)為210。2 算法實(shí)現(xiàn) 矩陣翻轉(zhuǎn)實(shí)現(xiàn)改進(jìn)的二邊逐次修正算法通過用戶選取目的地， 可以獲得多目標(biāo)點(diǎn)之間任意兩點(diǎn)的權(quán)值矩陣，然后對權(quán)值矩陣進(jìn)行計(jì)算優(yōu)化。對于改進(jìn)的完備路徑圖2，其權(quán)值矩陣a = (aij)n*n，其中aij為兩點(diǎn)間的時(shí)間權(quán)值，且不可達(dá)的兩點(diǎn)之間的的權(quán)值標(biāo)為無窮大。矩陣翻轉(zhuǎn)：在一個(gè)矩陣中，對它的第 i 行(列)到第 j 行(列)翻轉(zhuǎn)是以 i 行(列)和 j 行(列)的中心位置為轉(zhuǎn)軸、旋轉(zhuǎn)180，這樣：第 i 行(列)和第 j 行(列)位置互換，第 i + 1 行(列)和第 j

15、1 行(列)位置互換。用矩陣翻轉(zhuǎn)在圖2所示的開放的路徑完備圖中尋求最佳路徑r的整個(gè)實(shí)現(xiàn)過程如下：1)任取初始路徑r0： r0 = v1 , v2 , , vi , , vj , , vn , ve ，按此點(diǎn)順序可組成一個(gè)距離矩陣a = ( aij ) n + 1*n + 1。2) 給a 在第一行和最后一行加一個(gè)點(diǎn)的排列順序框，同時(shí)在第一列和最后一列加上2個(gè)0列，則r0 經(jīng)過的總權(quán)為i=2n-2ai,i+13)，對所有的i， j， 2 i + 1 j n - 2，當(dāng)a ( i, j) +a ( i + 1, j + 1) a ( i, i + 1) +a ( j, j + 1)成立時(shí)，vj ,v

16、j - 1 , , 到 vi + 1的權(quán)小于或等于從vi + 1, vj - 1, 到 vj 的權(quán)值把第i + 1至j列翻轉(zhuǎn)過來，第i + 1至j行也翻轉(zhuǎn)，形成新的距離矩陣。矩陣a中點(diǎn)的順序就變成： r = v1 , v2 , , vi , vj , vj - 1 , , vi + 1 , , vn , ve。4)對a重復(fù)執(zhí)行步驟3，直到條件不滿足為止，最后得到r即為近似最佳路徑，從而得到我們需要的排序。例如：將圖2用距離矩陣a表示，使所選的初始圈為矩陣的主對角線的上方元素對應(yīng)的頂點(diǎn)：a=對角線上方元素對應(yīng)的頂點(diǎn)就組成初始的路線：r0 = v1 v2 v3 v4 v5 v6 v1 ，其經(jīng)過的權(quán)

17、為i=16a(i,i+1)=237(a ( i, j) 表示矩陣a中的第 i 行，第 j 列元素) 。如果所選初始路徑不是r0，可通過交換距離矩陣a的行和列，使矩陣的主對角線的上方元素對應(yīng)的頂點(diǎn)為所選的初始r0。矩陣變化后，相應(yīng)的頂點(diǎn)順序也在變化，但對角線上方元素仍組成r的路線。經(jīng)過的權(quán)為i=27ai,i+1。在a中，存在a (2, 5) +a (3, 6) a (2, 3) +a (5, 6) ，所以把矩陣a第3至5列翻轉(zhuǎn)、第3至5行也翻轉(zhuǎn)，得到: a=除邊框元素外，對角線上方元素或矩陣的第一行點(diǎn)序列組成新的r為r0 = v1 v4 v3 v2 v5 v6 v1，總權(quán)為i=27ai,i+1=

18、210。r1 是一次翻轉(zhuǎn)后的較優(yōu)路徑r。待添加的隱藏文字內(nèi)容3時(shí)間復(fù)雜度：o（n2）。作為一個(gè)np-hard問題，該時(shí)間復(fù)雜度對于本課題可以接受，采用修正的二邊逐次修正法并利用矩陣翻轉(zhuǎn)尋找到路徑是全局較優(yōu)解。3 實(shí)驗(yàn)數(shù)據(jù)分析圖4 手機(jī)客戶端展示的北郵科技大廈一層平面圖本文設(shè)計(jì)的室內(nèi)場所的多目的地路徑優(yōu)化算法，根據(jù)“物聯(lián)網(wǎng)室內(nèi)環(huán)境定位應(yīng)用示范系統(tǒng)項(xiàng)目”研究的要求，本課題算法模型的模塊化。定位技術(shù)采用wifi，應(yīng)用實(shí)現(xiàn)代碼為java語言，開發(fā)環(huán)境為myeclipse 6.0.1。優(yōu)化結(jié)果和優(yōu)化路徑在android平臺的手機(jī)客戶端顯示給用戶。4.1 優(yōu)化效果評價(jià)選取了兩個(gè)復(fù)雜營業(yè)場所的布局，作為測試

19、對象，一個(gè)是大型商場，另一個(gè)是北郵科技大廈，分別選擇4類優(yōu)化路徑，每條優(yōu)化路徑包含3，5，7，9 ，優(yōu)化后路徑時(shí)間權(quán)值平均減少了31%。4.2 算法運(yùn)算速度測試 在北郵科技大廈進(jìn)行了實(shí)地測試，由于客戶端采取每5秒鐘，向服務(wù)器發(fā)送請求，獲取實(shí)時(shí)的路徑信息，該系統(tǒng)的路徑優(yōu)化計(jì)算速度，能夠滿足實(shí)時(shí)的需求。4 小結(jié)本文利用，并將室內(nèi)開環(huán)的多目的地路徑優(yōu)化問題，轉(zhuǎn)化為完備圖，并對逐邊修正法求最有哈密頓回路的算法進(jìn)行改進(jìn)，獲取經(jīng)營場所內(nèi)的最優(yōu)多目的地路徑推薦給用戶，具有創(chuàng)新性，并在真實(shí)的基于無線定位技術(shù)的大型營業(yè)場所的智能服務(wù)系統(tǒng)中得到使用，滿足了實(shí)際的需求，為相關(guān)課題的后續(xù)研究做了一些鋪墊。未來的研究工

20、作還需在大量的移動終端上動態(tài)模擬，測量此算法的可靠性和實(shí)時(shí)性。人流密度的數(shù)據(jù)還需進(jìn)一步細(xì)化。顧客的目的地在動態(tài)環(huán)境中會動態(tài)變化，系統(tǒng)應(yīng)該具有一定的適應(yīng)性。今后還可以對于整個(gè)樓宇內(nèi)的布局進(jìn)行研究?？傊竺嬖谑覂?nèi)路徑優(yōu)化方面還有很多的工作需要做。致謝論文由國家自然科學(xué)基金（60873244、60973110），北京市自然科學(xué)基金（4102059），江蘇省科技支撐計(jì)劃（be2010017）。參考文獻(xiàn)1 yilin zhao. mobile phone location determination and its impact on intelligent transportation system

21、s. ieee transactions on intelligent transportation systems, vol.1, no.1. 2000年3月.2 sinr-indoor navigator with rfid locator. third international conference on next generation mobile applications, services and technologies. 2009 ieee3 zafar k，baig r，bukhari n, halim z, route planning and optimization of route using simulated agent systemgong journal of circuits system and computers. 20卷，第3期，457-478，2011年5月.4 mirhassani sa, a