Evolutionary algorithms (EAs) are often applied to deal with UAV route planning. The solution encoding is one of important factor in designing effective EAs. In a traditional encoding mechanism, each individual represents one route. The whole population then consists of a number of routes. We argue that such an encoding is less effective in route planning, and then proposed an alternative encoding mechanism in which one individual represents only one navigation point. The whole population then represents one route. This implicitly turns EAs into single-point based search with high exploitation ability. To further improve the exploration ability of algorithms using this new encoding, a slightly modified differential evolution operator is applied. Combining the modified DE operator and the new encoding mechanism, the performance of the derived algorithm is significantly improved, obtaining much better route planning results than DE with the traditional encoding mechanism.