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

1、室內(nèi)路徑優(yōu)化算法研究摘 要在基于室內(nèi)定位和物聯(lián)網(wǎng)技術(shù)的支持下，論文針對室內(nèi)經(jīng)營場所的多目的地路徑優(yōu)化算法進行研究。二邊逐次修正法是針對哈密頓回路進行的優(yōu)化，不適合室內(nèi)的多目的地開放性路徑的特點，論文改進了二邊逐次修正法，并利用矩陣翻轉(zhuǎn)對多目標點的路徑順序進行了優(yōu)化，獲得室內(nèi)行進路徑的較優(yōu)解，達到了優(yōu)化的效果。論文算法模型進行了應(yīng)用實現(xiàn)，進行了仿真實驗的測試，并對測試結(jié)果進行了分析，測試結(jié)果反映該算法達到實際的需求。關(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)濟飛速發(fā)展，出現(xiàn)越來越多的大型購物中心、娛樂場所，展覽中心，且內(nèi)部布局越來越復雜，在這樣的大型室內(nèi)場所中的顧客往往需要花大量的時間在查找自己的行進路線，不僅費時，而且降低了顧客的體驗。隨著移動智能手機的普及和室內(nèi)定位技術(shù)的成熟，為用戶提供多目標路徑推薦提供了技術(shù)支持。1 2 在大型室內(nèi)經(jīng)營場所，消費者往往會有多個行進目的地，而如何節(jié)省用戶行進時間，在最短的時間完成消費目標，以提高用戶的消費體驗水平，使得消費場所對顧客具有更大吸引力，這是室內(nèi)場所路徑優(yōu)化的目標。本課題的核心是室內(nèi)多目的地路徑的動態(tài)優(yōu)化算法的設(shè)計和實現(xiàn)，其中多目的地指的是用戶在智能手機終端上一次性選擇多個想要去的服

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

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

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

8、回路，路徑優(yōu)化問題為找到一條時間權(quán)值和最小的環(huán)路，即在完備圖g中尋找最佳h圈，這是一np難度問題，可以采用二次逐邊修正法來實現(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 +

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

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

11、 w ( vi , vi + 1 ) 和 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)的路徑特點，需要對二邊逐次修正法進行改進。1.3 改進后的算法：.在圖2中

12、, 1）設(shè)初始路徑為 r0 = v1, v2, ., vi, ., vj, ., vn, ve，其中 v1, ve 設(shè)為入口和出口，它們之間是不可達的。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 ) ,加上

13、w ( vi , vj ) 和 w ( vi + 1 , vj + 1 ), 將 r0 轉(zhuǎn)化為r1， r1 = v1 , v2 , , vi , vj ,vj - 1 , , vi + 1 , vj + 1 , ., vn , ve. .3）重復步驟2, 直到條件不滿足為止，最后獲得的路徑為最優(yōu)解。如圖2有六個點之間的邊上數(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，v

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

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

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

17、對應(yīng)的頂點：a=對角線上方元素對應(yīng)的頂點就組成初始的路線：r0 = v1 v2 v3 v4 v5 v6 v1 ，其經(jīng)過的權(quán)為i=16a(i,i+1)=237(a ( i, j) 表示矩陣a中的第 i 行，第 j 列元素) 。如果所選初始路徑不是r0，可通過交換距離矩陣a的行和列，使矩陣的主對角線的上方元素對應(yīng)的頂點為所選的初始r0。矩陣變化后，相應(yīng)的頂點順序也在變化，但對角線上方元素仍組成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=除邊框元素

18、外，對角線上方元素或矩陣的第一行點序列組成新的r為r0 = v1 v4 v3 v2 v5 v6 v1，總權(quán)為i=27ai,i+1=210。r1 是一次翻轉(zhuǎn)后的較優(yōu)路徑r。待添加的隱藏文字內(nèi)容3時間復雜度：o（n2）。作為一個np-hard問題，該時間復雜度對于本課題可以接受，采用修正的二邊逐次修正法并利用矩陣翻轉(zhuǎn)尋找到路徑是全局較優(yōu)解。3 實驗數(shù)據(jù)分析圖4 手機客戶端展示的北郵科技大廈一層平面圖本文設(shè)計的室內(nèi)場所的多目的地路徑優(yōu)化算法，根據(jù)“物聯(lián)網(wǎng)室內(nèi)環(huán)境定位應(yīng)用示范系統(tǒng)項目”研究的要求，本課題算法模型的模塊化。定位技術(shù)采用wifi，應(yīng)用實現(xiàn)代碼為java語言，開發(fā)環(huán)境為myeclipse 6

19、.0.1。優(yōu)化結(jié)果和優(yōu)化路徑在android平臺的手機客戶端顯示給用戶。4.1 優(yōu)化效果評價選取了兩個復雜營業(yè)場所的布局，作為測試對象，一個是大型商場，另一個是北郵科技大廈，分別選擇4類優(yōu)化路徑，每條優(yōu)化路徑包含3，5，7，9 ，優(yōu)化后路徑時間權(quán)值平均減少了31%。4.2 算法運算速度測試 在北郵科技大廈進行了實地測試，由于客戶端采取每5秒鐘，向服務(wù)器發(fā)送請求，獲取實時的路徑信息，該系統(tǒng)的路徑優(yōu)化計算速度，能夠滿足實時的需求。4 小結(jié)本文利用，并將室內(nèi)開環(huán)的多目的地路徑優(yōu)化問題，轉(zhuǎn)化為完備圖，并對逐邊修正法求最有哈密頓回路的算法進行改進，獲取經(jīng)營場所內(nèi)的最優(yōu)多目的地路徑推薦給用戶，具有創(chuàng)新性，

20、并在真實的基于無線定位技術(shù)的大型營業(yè)場所的智能服務(wù)系統(tǒng)中得到使用，滿足了實際的需求，為相關(guān)課題的后續(xù)研究做了一些鋪墊。未來的研究工作還需在大量的移動終端上動態(tài)模擬，測量此算法的可靠性和實時性。人流密度的數(shù)據(jù)還需進一步細化。顧客的目的地在動態(tài)環(huán)境中會動態(tài)變化，系統(tǒng)應(yīng)該具有一定的適應(yīng)性。今后還可以對于整個樓宇內(nèi)的布局進行研究?？傊竺嬖谑覂?nèi)路徑優(yōu)化方面還有很多的工作需要做。致謝論文由國家自然科學基金（60873244、60973110），北京市自然科學基金（4102059），江蘇省科技支撐計劃（be2010017）。參考文獻1 yilin zhao. mobile phone location

21、determination and its impact on intelligent transportation systems. 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