随着卫星全球定位系统和无线通讯技术等科学技术的快速发展,已经能够跟踪并记录移动对象的位置信息。移动对象在地理信息系统、移动计算和基于位置的电子商务等方面发挥着重要应用,各种查询方法不断提出。k路径近邻查询(k-PNN)作为一种新的查询方法,对用户的实时查询要准确快速的给出回答,因此,降低查询代价成为该查询方法的关键问题。Zaiben Chen等人提出了最优路网扩展(BNE)方法。本文中,运用预计算思想减少路网扩展代价,旨在进一步提高查询效率。首先,运用预计算思想提出了基于NN lists的BNNL算法,运用双向Dijkstra算法向在获得用户当前位置和目的地节点之间最短路径的基础上,预计算路网节点的m近邻信息,运用优先队列进行优化处理。对于路口节点的近邻不需要路网扩展得到,只需进行简单读取,从而提高了BNNL算法对路网k路径近邻的查询效率。其次,Voronoi图不仅对路网进行了简化处理,还预计算了路网中部分节点之间的最短距离,减少节点扩展次数,从而提高近邻查找效率。本文提出的基于Voronoi图的路网k路径近邻查询方法(VBk-PNN)。将相同的路网Voronoi多边形在用户当前位置和目的地节点之间最短路径上的路口节点作为一个集合来进行扩展。并运用优先队列进行优化处理,最终得到正确的k路径近邻。最后,通过实验将上述提出的两种方法和已有的最优路网扩展方法(BNE)进行实验比较,结果表明BNNL算法和VBk-PNN算法的执行效率均优于BNE算法。