Travel time is a variable that varies over both time and space. Hence, an ideal formulation should be able to capture its evolution over time and space. A mathematical representation capturing such variations was formulated from first principles, using the concept of conservation of vehicles. The availability of position and speed data obtained from GPS enabled buses provide motivation to rewrite the conservation equation in terms of speed alone. As the number of vehicles is discrete, the speed-based equation was discretized using Godunov scheme and used in the prediction scheme that was based on the Kalman filter. With a limited fleet size having an average headway of 30 min, availability of travel time data at small interval that satisfy the requirement of stability of numerical solution possess a big challenge. To address this issue, a continuous speed fill matrix spatially and temporally was developed with the help of historic data and used in this study. The performance of the proposed Advanced Time-Space Discterization (AdTSD) method was evaluated with real field data and compared with existing approaches. Results show that AdTSD approach was able to perform better than historical average approach with an advantage up to 11% and 5% compared to Base Time Space Discretization (BTSD) approach. Also, from the results it was observed that the maximum deviation in prediction was in the range of 2–3 min when it is predicted 10 km ahead and the error is close to zero when it is predicted a section ahead i.e. when the bus is close to a bus stop, indicating that the prediction accuracy achieved is suitable for real field implementation. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.