Traditional vehicular routing protocols cannot accurately foresee future location of each vehicle for efficient packet forwarding. Recently, the data mining approach has been applied to analyze huge vehicle trajectory data. In this paper, we propose a novel trajectory-based routing (NTR) protocol to improve the packet replication efficiency of vehicles in the Vehicular Delay Tolerant Network (VDTN). By integrating the data mining technique, NTR first establishes the trajectory tree of each vehicular node based on its trajectory data. With this kind of trajectory trees, NTR then predicts future location of each vehicle and derives its contact possibilities with all other vehicles. Hence, NTR creates the vehicle encounter trees and the packet delivery graphs to predict the optimal Store-Carry-Forward (SCF) route for spraying the optimal number of packet tokens among intermediate nodes from the packet source vehicle to the destination one. Finally, we use the Opportunistic Network Environment (ONE) simulator to perform simulations. From performance results, we conclude that NTR significantly outperforms several well-known VDTN routing protocols, in terms of the average packet delivery ratio, average end-to-end delay and average packet forwarding overhead.