The number of vehicles on the roads worldwide is increasing each year. The consequence is that the travel-time of the trips is changing each year. It is very frustrating when you discover during the trip that the travel-time gotten from the available services on the internet or other vendors is very unrealistic. In this paper, we propose solution where we calculate travel-times that are more reliable. In order to achieve this we are using a data that is recorded with a GPS (Global Position System) equipped vehicles. We are using this data to discover historical speed patterns, and then these patterns are used to determine the travel-times. In addition, we propose several fallback methods, which handle the cases where we do not have enough data for some parts of a road network. Our solution can be used in domain of the traffic analyses and planning. We can provide the reports with the speed patterns for the parts of the road network. We use in our implementation the shortest travel-time path to verify that our solution can be also used in the navigation and the route planning.