Travel-time prediction is a critical component of Intelligent Transportation Systems (ITS), offering vital information for tasks such as accident detection, congestion management, and traffic flow optimisation. Accurate predictions are highly dependent on the selection of relevant features. In this study, a two-stage methodology is proposed which consists of two layers of Optimisation Algorithm and one Data-Driven method (OA2DD) to enhance the accuracy and efficiency of travel-time prediction. The first stage involves an offline process where interconnected optimisation algorithms are employed to identify the optimal set of features and determine the most effective machine learning model architecture. In the second stage, the real-time process utilises the optimised model to predict travel times using new data from previously unseen parts of the dataset. The proposed OA2DD method was applied to a case study on the M50 motorway in Dublin. Results show that OA2DD improves the convergence curve and reduces the number of selected features by up to 50 %, leading to a 56 % reduction in computational costs. Furthermore, using the selected features from OA2DD, reduced the prediction error by up to 29 % compared to the full feature set and other feature selection methods, demonstrating the method's effectiveness and robustness.