《室内路径优化算法研究.doc》由会员分享，可在线阅读，更多相关《室内路径优化算法研究.doc（8页珍藏版）》请在三一办公上搜索。
1、室内路径优化算法研究摘 要在基于室内定位和物联网技术的支持下，论文针对室内经营场所的多目的地路径优化算法进行研究。二边逐次修正法是针对哈密顿回路进行的优化，不适合室内的多目的地开放性路径的特点，论文改进了二边逐次修正法，并利用矩阵翻转对多目标点的路径顺序进行了优化，获得室内行进路径的较优解，达到了优化的效果。论文算法模型进行了应用实现，进行了仿真实验的测试，并对测试结果进行了分析，测试结果反映该算法达到实际的需求。关键字 室内路径优化； NP难度； 二次逐边修正； 矩阵翻转 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 引言随着经济飞速发展，出现越来越多的大型购物中心、娱乐场所，展览中心，且内部布局越来越复杂，在这样的大型室内场所中的顾客往往需要花大量的时间在查找自己的行进路线，不仅费时，而且降低了顾客的体验。随着移动智能手机的普及和室内定位技术的成熟，为用户提供多目标路径推荐提供了技术支持。1 2 在大型室内经营场所，消费者往往会有多个行进目的地，而如何节省用户行进时间，在最短的时间完成消费目标，以提高用户的消费体验水平，使得消费场所对顾客具有更大吸引力，这是室内场所路径优化的目标。本课题的核心是室内多目的地路径的动态优化算法的设计和实现，其中多目的地指的是用户在智能手机终端上一次性选择多个想要去的服
5、务点，完成顾客对个人服务的兴趣选择。根据在经营场所中实际需求，文中设定用户对多个服务点的选择没有先后的区别， 并设定行进的消费者并不一定会到出发点。用户多目的地路径是指顾客要完成所有选择的多目的地的行进路径序列。多目的地路径优化是指在所有的多目的地行进路径序列中，找到最优的一条行进路径序列。本课题的研究的算法要实现产生一个优化后的完成多个目标点的行进顺序，使得时间权值和最小。对于N个行进目标点，遍历整个排序的时间复杂度是O(N!)，这种情况的时间复杂度无法满足实时性需求。而多目的地路径优化是一个NP难度问题。随着人们对NP-Hard问题的研究，提出了许多用于解决该类问题的方法，例如遗传算法、蚁
6、群算法、模拟退火算法、Dijistra算法、人工神经网络方法等等。而目前路径优化最常用的领域就是路径导航、物流配送、人员疏散等领域。目前的研究中主要采用进化算法进行优化的研究成果如文献3，提出的退火蚂蚁代理算法对复杂大型的环境中进行路径的动态优化，文献4采用算法粒子群优化针对物流配送特点，对开放的车辆路径优化问题进行算法研究，文献5采用遗传算法优化基于移动设备的车辆导航最短行进时间的路径，考虑到交通密度和最低行驶速度的影响因素，研究车辆行驶的最短时间路径问题的算法。文献6是基于基因算法对动态的随机路网进行路径优化。文献7是基于改进的Dijkstra算法对基于位置的导航路径进行优化。二边逐次修正
7、法是寻找最短Hamilton 圈的比较新而且高效的算法。在这个算法中，通过按照一定的规则交换顶点，重新分配无向图的权值矩阵的数据，以找到H圈的最优解。本文根据室内多目的地的路径特征，对矩阵翻转算法进行了修正，采用二边逐次修正法的交换顶点的规则，利用修正的矩阵翻转算法完成了路径的优化算法设计与实现。获得室内行进路径的较优解，时间复杂度和空间复杂度达到了优化的效果。781 算法分析与设计1.1二边逐次修正法求最佳H圈目的地之间的关系是用时间权值来衡量的，假设任意两点之间的时间权值w( e )都已知，那么目标点集合V和它们之间带时间权值的边集组成的图G必定是完备图。如果室内行走路径为Hamiton
8、回路，路径优化问题为找到一条时间权值和最小的环路，即在完备图G中寻找最佳H圈，这是一NP难度问题，可以采用二次逐边修正法来实现优化，获得较优解。二边逐次修正法的算法过程如下：图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重复步骤2，直到条件不满足为止，最后得到的C即为所求。1.2 二边逐次修正法的算法改进二边逐次修正法存在的问题分析：二边逐次修正法针对的是一个汉密尔顿环路，即从起点出发最终回到起点的环路；对于本课题，根据实际场景需求，寻找的是从顾客当前位置出发，经过一系列选定的消费目的地，最后到达商场出口点的一条优化路径。实际的路线是开环的路径，而不是环路。这里称为改进的开放完备路径图。如图2所
10、示。v1是当前位置，也可以为入口，需要经过 v2 , , vi , , vj , , vn , 到达出口vE，图2中n=6。（注：图中vi ,vj之间的实线表示两点之间是无向的，而带箭头的虚线表示两点之间是有向的。不可达的方向权值为无穷大。图2 为室内经营场所设计的开放的完备路径图图2 和图1不同，前者不是一个完备图，如果我们如针对图1的方法进行逐边修正，并不一定获得的路径的较优优的。即：在图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 转化为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不一定优于R0. 所以针对室内的路径特点，需要对二边逐次修正法进行改进。1.3 改进后的算法：.在图2中, 1）设初始路径为 R0 = v1
12、, v2, ., vi, ., vj, ., vn, vE，其中 v1, vE 设为入口和出口，它们之间是不可达的。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的权小于或等于从vi + 1, vj - 1, 到 vj 的权值, 去掉边 w( vi , vi + 1 )和 w ( vj , vj + 1 ) ,加上 w ( vi , vj ) 和 w ( vi + 1 , vj
13、+ 1 ), 将 R0 转化为R1， R1 = v1 , v2 , , vi , vj ,vj - 1 , , vi + 1 , vj + 1 , ., vn , vE. .3）重复步骤2, 直到条件不满足为止，最后获得的路径为最优解。如图2有六个点之间的边上数值为两个点之间的时间权值。如选取初始路径R0 = v1 v2 v3 v4 v5 v6 vE ，其总权为237。图3 部分路径图由于w (1, 4) +w (2, 5) w (1, 2) +w (4, 5) (见图3) ，并且v4 ,v3 ,到 v2的权等于从v2，v3, 到 v4 的权值，所以去掉边v1 v2 , v4 v5 添加边v1
14、 v4 , v2 v5 得到较优的路径R1为： R1 = v1 v4 v3 v2 v5 v6 vE ，其总权为210。2 算法实现 矩阵翻转实现改进的二边逐次修正算法通过用户选取目的地， 可以获得多目标点之间任意两点的权值矩阵，然后对权值矩阵进行计算优化。对于改进的完备路径图2，其权值矩阵A = (aij)n*n，其中aij为两点间的时间权值，且不可达的两点之间的的权值标为无穷大。矩阵翻转：在一个矩阵中，对它的第 i 行(列)到第 j 行(列)翻转是以 i 行(列)和 j 行(列)的中心位置为转轴、旋转180，这样：第 i 行(列)和第 j 行(列)位置互换，第 i + 1 行(列)和第 j
15、1 行(列)位置互换。用矩阵翻转在图2所示的开放的路径完备图中寻求最佳路径R的整个实现过程如下：1)任取初始路径R0： R0 = v1 , v2 , , vi , , vj , , vn , vE ，按此点顺序可组成一个距离矩阵A = ( aij ) n + 1*n + 1。2) 给A 在第一行和最后一行加一个点的排列顺序框，同时在第一列和最后一列加上2个0列，则R0 经过的总权为3)，对所有的i， j， 2 i + 1 j n - 2，当A ( i, j) +A ( i + 1, j + 1) A ( i, i + 1) +A ( j, j + 1)成立时，vj ,vj - 1 , , 到
16、vi + 1的权小于或等于从vi + 1, vj - 1, 到 vj 的权值把第i + 1至j列翻转过来，第i + 1至j行也翻转，形成新的距离矩阵。矩阵A中点的顺序就变成： R = v1 , v2 , , vi , vj , vj - 1 , , vi + 1 , , vn , vE。4)对A重复执行步骤3，直到条件不满足为止，最后得到R即为近似最佳路径，从而得到我们需要的排序。例如：将图2用距离矩阵A表示，使所选的初始圈为矩阵的主对角线的上方元素对应的顶点：A=对角线上方元素对应的顶点就组成初始的路线：R0 = v1 v2 v3 v4 v5 v6 v1 ，其经过的权为(A ( i, j)
17、表示矩阵A中的第 i 行，第 j 列元素) 。如果所选初始路径不是R0，可通过交换距离矩阵A的行和列，使矩阵的主对角线的上方元素对应的顶点为所选的初始R0。矩阵变化后，相应的顶点顺序也在变化，但对角线上方元素仍组成R的路线。经过的权为。在A中，存在A (2, 5) +A (3, 6) A (2, 3) +A (5, 6) ，所以把矩阵A第3至5列翻转、第3至5行也翻转，得到: A=除边框元素外，对角线上方元素或矩阵的第一行点序列组成新的R为R0 = v1 v4 v3 v2 v5 v6 v1，总权为。R1 是一次翻转后的较优路径R。待添加的隐藏文字内容3时间复杂度：O（n2）。作为一个NP-Ha
18、rd问题，该时间复杂度对于本课题可以接受，采用修正的二边逐次修正法并利用矩阵翻转寻找到路径是全局较优解。3 实验数据分析图4 手机客户端展示的北邮科技大厦一层平面图本文设计的室内场所的多目的地路径优化算法，根据“物联网室内环境定位应用示范系统项目”研究的要求，本课题算法模型的模块化。定位技术采用Wifi，应用实现代码为JAVA语言，开发环境为MyEclipse 6.0.1。优化结果和优化路径在Android平台的手机客户端显示给用户。4.1 优化效果评价选取了两个复杂营业场所的布局，作为测试对象，一个是大型商场，另一个是北邮科技大厦，分别选择4类优化路径，每条优化路径包含3，5，7，9 ，优化
19、后路径时间权值平均减少了31%。4.2 算法运算速度测试 在北邮科技大厦进行了实地测试，由于客户端采取每5秒钟，向服务器发送请求，获取实时的路径信息，该系统的路径优化计算速度，能够满足实时的需求。4 小结本文利用，并将室内开环的多目的地路径优化问题，转化为完备图，并对逐边修正法求最有哈密顿回路的算法进行改进，获取经营场所内的最优多目的地路径推荐给用户，具有创新性，并在真实的基于无线定位技术的大型营业场所的智能服务系统中得到使用，满足了实际的需求，为相关课题的后续研究做了一些铺垫。未来的研究工作还需在大量的移动终端上动态模拟，测量此算法的可靠性和实时性。人流密度的数据还需进一步细化。顾客的目的地
20、在动态环境中会动态变化，系统应该具有一定的适应性。今后还可以对于整个楼宇内的布局进行研究。总之，后面在室内路径优化方面还有很多的工作需要做。致谢论文由国家自然科学基金（60873244、60973110），北京市自然科学基金（4102059），江苏省科技支撑计划（BE2010017）。参考文献1 Yilin Zhao. Mobile Phone Location Determination and Its Impact on Intelligent Transportation Systems. IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION S
21、YSTEMS, 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
22、 Circuits System and Computers. 20卷，第3期，457-478，2011年5月.4 MirHassani SA, Abolghasemi N, A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems With Applications. 第38卷，第9期，11547-11551， 2011年9月出版。5 Karas IR, Atila U, A genetic algorithm approach for finding the shorte
23、st driving time on mobile devices. 卷：6，期：2 页：394-405，2011年1月186 Wunsch DC; Tan HH; Zeng DH; Luo Q, Research on route optimization of dynamic random network based on genetic algorithm. Nanotechnology and computer engineering. Advanced Materials research 卷：121-122，页：792-796，2010年7 XiuWen Yang, zhengJue Chen, AiLing Li, “Use Matrix Reversal Method to Find the Best H Cycle”, Journal of Logistical Engineering University, 2008,24(1):102-106.8 杨秀文,陈振杰,李爱玲 等. 利用矩阵翻转法求最佳H圈. 后勤工程学院学报. 第24卷第1期.
