Convenience store chains are many people’s top choice for dining and leisure and have logistics procedures that involve each store receiving multiple deliveries because of the varying delivery periods and suitable temperatures for different goods. The estimated arrival time for each delivery has a huge impact on the route arrangement and convenience store preparation for dispatchers to schedule future deliveries. This study collected global positioning system travel data from a fleet of one of the top convenience store chains in Taiwan between April 2021 and March 2022 and proposed machine learning to establish a model to predict travel times. For unavailable data, we proposed the nonlinear regression equation to fill in the missing GPS data. Moreover, the study used the data between April 2022 and September 2022 with mean absolute percentage error to validate the prediction effects exceeding 97%. Therefore, the proposed model based on historical data and the machine learning algorithm in this study can help logistics fleets estimate accurate travel times for their scheduling of future delivery tasks and arranging routes.