The important issue for intra-city vehicle scheduling is to measure and store actual vehicle travel speeds between customer locations. Travel speeds(and times) in nearly all metropolitan areas change drastically during the day because of congestion in certain parts of the city road network. We propose three models for estimating departure time-dependent travel speeds between locations that relieve much burden for the data collection and computer storage requirements. Two of the three models use a least squares method and the rest one employs a neural network trained with the back-propagation rule. On a real-world study using the travel speed data collected in Seoul, we found out that the neural network model is more accurate than the other two models.