摘要：针对团队出行过程中因信息孤岛导致出行路径非优化和延时等待等问题，提出了一种以团队成员信息共享为基础，以集中式计算为手段的协作式路径优化算法。该算法统筹考虑成员间会合的便捷性、路径/时间最短化等多种因素基础上，通过引入团队会合优先度因子对路径计算进行加权处理，从而实现整个团队出行路径的最优化。理论分析表明，协作式路径优化算法的计算复杂度随团队成员的数量线性增长，与传统的最短路径算法计算复杂度基本相当。仿真结果表明，会合优先度因子值的高低，将会影响会合点及出行路径的选择，因此，可根据实际需求设置会合优先度因子，实现团队会合和路径最短化的动态均衡。最后，以协作式路径优化算法的一个具体的工程应用，阐述团队成员间如何提供支持和帮助，从而安全、高效和有序地到达目的地。 　　关键词：最短路径；协作式导航；团体出行；动态导航；路径优化；信息共享 　　中图分类号： TP393.03 文献标志码：A 　　Abstract： Concerning the path nonoptimization and the delay due to mutualwaiting caused by information island in the team travel， a collaborative path optimization algorithm was proposed which employed centralized computing based on information sharing among team members. The algorithm calculated the optimum navigation path weighted by the factor of meeting priority， taking meeting convenience and path/time shortening into overall consideration. Theoretical analysis shows that the computation complexity increases linearly with the number of team members， and is approximately equal to that of the traditional path optimization algorithm. The simulation results show that the factor of meeting priority has a great influence on optimization path and meeting place. So， the factor of meeting priority needs to be set according to the actual requirement to ensure the dynamic balance between team cooperation and shortening path. A typical application solution of collaborative path optimization algorithm was given to illustrate how to support and to help each other among team members， and to travel together to the destination in order， safely and quickly. 　　Key words： shortest path； collaborative navigation； team travel； dynamic navigation； path optimization； information sharing 　　0 引言 　　随着社会经济迅猛发展及人民物质文化水平的提高，结伴出行和团体性的商务活动日益频繁。在团队出行过程中，为安全、有序、快捷到达目的地，迫切需要解决一些个体出行过程中未曾出现的问题。例如，团队成员如何实时获知其他成员的地理位置，如何快捷地实现成员间会合，如何避免团队成员在出行过程中的掉队问题，如何综合考虑所耗时间、道路拥挤程度等多个因素确定最佳出行路径等。 　　1 相关研究 　　路径优化问题是智能交通领域的重要分支，出行路径的最优化不仅可以减少出行者的时间和成本，而且可以有效缓解交通拥堵、废气污染等系列问题，因此，路径优化问题一直是众多业者和学者研究和关注的重点之一。 　　李军等[1]对车辆优化调度的相关理论和方法进行了深入分析，并给出了具体的车辆优化调度算法的计算机实现。文献[2-6]对多目标条件下的路径优化问题进行了研究，提出了系列策略将多目标问题转化为单目标问题，从而应用单目标路径优化算法进行处理。其中：文献[2]和文献[3]侧重于目标加权，所提算法存在的问题在于如何确定合理科学的权重值，而且难以实现均匀曲面上解的最优化；文献[4]和文献[5]的主要思路在于，确定一个主要目标的同时将其他目标转化为约束条件，但是可能导致算法无解的问题；Reinhardt等[6]针对条件和目标不可累加的多目标最短路问题，给出了一个通用的公式来处理一系列不可累加的条件，最后用动态规划算法进行求解。基于遗传算法在解决多目标优化问题的潜在优势，不少学者对遗传算法在多目标路径优化的相关应用进行了深入研究，比较典型的包括基于优先权的路径编码方法[7]和基因值顺序表示该基因连接的后续基因位置[8]的编码方法。 　　但是，现有的路径优化算法往往致力于解决个体出行过程中的系列问题，如何统筹考虑当前团队成员所处位置，结合其他一些目标或者约束条件，为团队成员选择一条合适的出行途径，迄今为止尚无相关机制提出。从工程应用而言，当前，小米[9-10]、中国联通[11-12]等厂商针对基于位置服务的相关应用，提出了一系列技术方案，用于实现用户之间地理位置等信息的共享。但是，上述方案主要着眼于位置信息的采集、传输及信息请求许可等操作，并未涉及如何基于共享的地理位置信息实现用户间的出行协作，尤其是如何实现面向团队出行的路径优化。 　　参考文献： 　　[1]LI J， GUO Y. Vehicle routing problem： theory and method [M]. Beijing： China Logistics Publishing House， 2001： 48-87.（李军，郭耀煌.车辆优化调度理论与方法[M].北京：中国物资出版社，2001：48-87.） 　　[2]MOONEY P A. An evolutionary algorithm for multiple criteria path optimization problems [J]. International Journal of Geographical Information Science， 2006， 20（4）： 401-423. 　　[3]PEREIRA C M N A. Evolutionary multicriteria optimization in core designs： basic investigations and case study [J]. Annals of Nuclear Energy， 2004， 31（1）： 1251-1264. 　　[4]LI R， LEUNG Y. Multipleobjective route planning for dangerous goods using compromise programming [J]. Journal of Geographical Systems， 2011， 13（3）： 249-271. 　　[5]CHAKRABORTY B. GAbased multiple router selection for car navigation [C]// AACC 2004： Proceedings of the Second Asian Applied Computing Conference， LNCS 3285. Berlin： Springer， 2004：76-83. 　　[6]REINHARDT L B， PISINGER D. Multiobjective and multiconstrained nodadditive shortest path problems [J]. Computers & Operations Research， 2011， 38（3）： 605-616 　　[7]GEN M， CHENG R， WANG D. Genetic algorithms for solving shortest path problems [C]// Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. Piscataway： IEEE， 1997： 401-406. 　　[8]INAGAKI J， HASEYAMA M， KITAJIMA H. A genetic algorithm for determining multiple routes and its applications [C]// Proceeding of the 1999 IEEE International Symposiums on Circuits and Systems. Piscataway： IEEE， 1999： 137-140. 　　[9]Millet Technology Co.， Ltd. Method and device of positioning and navigation： China， 103968846A [P]. 20140806.（小米科技有限责任公司.定位导航方法和装置：中国，103968846A[P].20140806.） 　　[10]Millet Technology Co.， Ltd. Method， device and system for location information sharing： China， 102740228A [P]. 20121017.（小米科技有限责任公司.一种位置信息共享方法、装置及系统：中国，102740228A [P]. 20121017.） 　　[11]China United Network Communications Group Co.， Ltd. Method of positioning service in mobile communication system： China， 1874589 [P]. 20061206.（中国联合网络通信集团有限公司.在移动通信系统中提供定位服务的方法：中国，1874589[P].20061206.） 　　[12]China United Network Communications Group Co.， Ltd. Method and device of mobile terminal positioning： China， 1719941 [P]. 20060111.（中国联合网络通信集团有限公司.一种通信网络的移动终端定位方法及装置：中国，1719941[P]. 20060111.） 转载注明来源:https://www.xzbu.com/8/view-11770908.htm