Hybrid Peer-to-Peer (P2P) networks based on the direct connection model have two shortcomings which are high bandwidth consumption and poor semi-parallel search. However, they can further be improved by the query propagation model. In this paper, we propose a novel query routing strategy called GAroute based on the query propagation model. By giving the current P2P network topology and relevance level of each peer, GAroute returns a list of query routing paths that cover as many relevant peers as possible. We model this as the Longest Path Problem in a directed graph which is NP-complete and we obtain high quality (0.95 in 100 peers) approximate solutions in polynomial time by using Genetic Algorithm (GA). We describe the problem modeling and proposed GA for finding long paths. Finally, we summarize the experimental results which measure the scalability and quality of different searching algorithms. According to these results, GAroute works well in some large scaled P2P networks.