Multi-Constrained Optimal Path Algorithm in Multi-Weighted Graphs

摘要：

Efficient path query processing is a key requirement for advanced database applications including GIS (Geographic Information Systems) and ITS (Intelligent Transportation Systems). Querying an optimal path satisfying a set of constraints in Multi-Weighted Graphs (MWG) that ones per edge corresponds to multiple weights, is NP-complete. Traditional heuristic algorithm reduces the NP-complete problem to a simpler one which can be solved in polynomial time.But it couldnt ensure to find a solution all the time. In this paper we apply the lagrange relaxation to traditional heuristic algorithm to increase the chance of find a possible solution. We prove the correctness of our algorithm by experiment and analysis.

作者: Lai Wei Yong-gui Zou Dong-wook Lee Hae-young Bae

作者单位: Sino-Korea ChongQing GIS Research Center, College of Computer Science,Chongqing univ. of Posts & Tel Dept. of Computer Science & Engineering, Inha University Younghyun-dong, Nam-ku, Incheon, 402-751, K

会议类型: 国际会议

会议名称: The 5th Asian Symposium on Geographic Information Systems from Computer Science & Engineering View(ASGIS 2007)(第五届亚洲地理信息系统国际学术研讨会)

会议地点: 重庆

会议语种:英文

页码: 220-223

在线出版日期: 2007-04-24（万方平台首次上网日期，不代表论文的发表时间）