Optimal location query in road networks is a basic operation in the location intelligence applications.Given a set of clients and servers on a road network,the purpose of optimal location query is to obtain a location for a new server,so that a certain objective function calculated based on the locations of clients and servers is optimal.Existing works assume no la-bels for servers and that a client only visits the nearest server.These assumptions are not realistic and it renders the existing work not useful in many cases.In this paper,we relax these assumptions and consider the k nearest neighbours(KNN)of clients.We introduce the problem of KNN-based optimal lo-cation query(KOLQ)which considers the k nearest servers of clients and labeled servers.We also introduce a variant problem called relocation KOLQ(RKOLQ)which aims at relocating an existing server to an optimal location.Two main analysis algo-rithms are proposed for these problems.Extensive experiments on the real road networks illustrate the efficiency of our pro-posed solutions.