摘要
针对多停靠点线路优化问题,提出一种基于邻接矩阵网络拓扑树构建的路径寻优方法,借鉴系统生物学中进化树分类的思想,引入路网结点间邻接关系评价标准邻接值的概念,将路网按照其结点邻接关系归类划分为以路网结点间邻接值为表征的路网拓扑进化树,同时对线路路径寻优问题中目标结点进行动态回溯分类,在限定路网搜索区域同时采用分支定界搜索策略进行搜索优化,降低了搜索算法时间复杂度.最后依据国家基础地理信息系统网站提供的国界、省会城市及主要公路基础地理数据进行系统实现,证明该算法的有效性.
To address the problem of multi-stops path optimization,a novel method based on construction of adjacency matrix network topology tree is proposed.According to adjacent relationship among each node,network is classified into phylogenetic topological tree which is characterized by means of adjacent value,while is introduced as the evaluation criteria of adjacent relationship using the idea of evolutionary tree classification in biology.Furthermore,target nodes in this optimization problem will be classified in dependence on dynamic backtracking algorithm while the strategy of branch and bound search is used for optimization in the limited search area of network to reduce time complexity.Finally,we display its feasibility by development of a WebGIS Multi-Stop optimization system using the data from the NFGIS of China.
出处
《计算机学报》
EI
CSCD
北大核心
2012年第5期964-971,共8页
Chinese Journal of Computers
基金
国家自然科学基金(61075062
50908213)
浙江省自然科学基金(Y1100891)资助~~
关键词
进化树
邻接值
动态回溯
分支定界
phylogenetic tree
adjacent values
dynamic backtracking
branch and bound
