The paper firstly proposes a deterministic deep feedforward neural network model aimed at predicting the city bus velocity profile over receding time horizon based on the following inputs: actual vehicle position, actual velocity or short-term history of vehicle velocities, time of day and day of week. A systematic analysis of the influence of different input subsets, history interval length and prediction horizon length is carried out to find an optimal configuration of NN model inputs and hyperparameters. Secondly, a stochastic version of neural network prediction model is proposed, which predicts expectations and standard deviations of velocity patterns over the receding time horizon. The stochastic model prediction accuracy is verified against the recorded test dataset features, as well as by comparing the predicted velocity expectation with the deterministic model prediction and correlating the predicted velocity standard deviation with deterministic model prediction uncertainty metrics. The verification results indicate that: (i) the deterministic model velocity prediction accuracy is characterized by the R2 score greater than 0.8 for the prediction horizon length of 10 s and remains to be solid (greater than 0.6) for the horizon lengths up to 25 s; (ii) the actual vehicle position and the velocity history are the most significant input features, where the optimal value of history interval length lies in the range from 30 to 50 s; (iii) the stochastic model have only slightly lower accuracy of predicting the velocity expectation along the receding horizon when compared to the deterministic model (the root mean square error is higher by 2.2%), and it outputs consistent standard deviation prediction.