This paper introduces an approach for optimal scheduling of external trucks in container terminals. The proposed approach integrates the k-means clustering algorithm with a bi-objective optimization model. The k-means clustering algorithm matches the export and import containers into tuples, reducing the number of empty trips. The optimization model objectives are: minimizing the deviation from the trucking companies’ preferred arrival times and minimizing the total truck turnaround times, while considering several essential aspects, such as yard resources capacity, congestion level, and trucking companies’ preferences. The results depict that the proposed approach reduces the total number of required trips by 31.58% and provides the decision-makers with a tradeoff between the total truck turnaround time and the deviation from the trucking companies’ preferred pickup time window.