Abstract: Travel time estimation (TTE) is a fundamental task to build intelligent transportation systems. However, most existing TTE solutions design models upon simple homogeneous graphs and ignore the heterogeneity of traffic networks, where, e.g., main roads typically contribute differently from side roads. In terms of spatial dimension, few studies consider the dynamic spatial correlations across road segments, e.g., the traffic speed/volume on road segment A may correlate with the traffic speed/volume on road segment B, where A and B could be adjacent or non-adjacent, and such correlations may vary across time. In terms of temporal dimension, even fewer studies consider the dynamic temporal dependences, where, e.g., the historical states of road A may directly correlate with the recent state of A, and may also indirectly correlate with the recent state of road B. To track all aforementioned issues of existing TTE approaches, we provide HDTTE, a solution that employs heterogeneous and dynamic spatio-temporal predictive learning. Specifically, we first design a general multi-relational graph constructor that extracts hidden heterogeneous information of road segments, where we model road segments as nodes and model correlations as edges in the multi-relational graph. Next, we propose a dynamic graph attention convolution module that aggregates dynamic spatial dependence of neighbor roads to focal roads. We also present a novel correlation-augmented temporal convolution module to capture the influence of states at past time steps on current traffic states. Finally, in view of the periodic dependence of traffic, we develop a multi-scale adaptive fusion layer to enable HDTTE to exploit periodic patterns from recent, daily, and weekly traffic states. An experimental study using real-life highway and urban datasets demonstrates the validity of the approach and its advantage over others.