<p>Travel time estimation is a vital task in location-based services and intelligent transportation systems. However, it is nontrivial to achieve stable estimation performance over time since the travel patterns evolve as well as the efficiency of model to tackle this evolutionary dynamics. To this end, we propose a novel efficient evolutionary travel time estimation model, coined as EETTE, to learn travel patterns in both temporal and spatial dimensions with attention based neural networks and efficient meta learning mechanism. Specifically, to address the evolutionary dynamics in temporal dimension, instead of utilizing the vanilla meta learning strategy (e.g., MAML) during gradient optimization towards learning tasks (i.e., limited number of trajectories on different days of week), we design a meta teacher that dynamically generates weights for prediction based on the indicator of the corresponding day of week, which improves the efficiency. Moreover, we utilize the full-attention scheme to enable efficient parallel computation compared to recurrent neural network based works on this topic. At last, to address the evolutionary dynamics in spatial dimension, we constrain our model not to employ the road network information, which makes it tolerate the evolving spatial correlations. Extensive experimental results on four real-world datasets demonstrate the superiority of our proposed model.</p>