—The problem of transport optimization is of great importance for the successful operation of distribution companies. To successfully find routes, it is necessary to provide accurate input data on orders, customer location, vehicle fleet, depots, and delivery restrictions. Most of the input data can be provided through the order creation process or the use of various online services. One of the most important inputs is an estimate of the unloading time of the goods for each customer. The number of customers that the vehicle serves during the day directly depends on the time of unloading. This estimate depends on the number of items, weight and volume of orders, but also on the specifics of customers, such as the proximity of parking or crowds at the unloading location. Customers repeat over time, and unloading time can be calculated from GPS data history. The paper describes the innovative application of machine learning techniques and delivery history obtained through a GPS vehicle tracking system for a more accurate estimate of unloading time. The application of techniques gave quality results and significantly improved the accuracy of unloading time data by 83.27% compared to previously used methods. The proposed method has been implemented for some of the largest distribution companies in Bosnia and Herzegovina.