Vehicle routing problems (VRP) and Container Loading Problems (CLP) have been studied for decades. However, the combination of the two deserves more attention than in the literature to date. When solving VRP problems, computed routes must be checked for feasibility. Among the feasibility checks to perform, we need to guarantee that the load plan is feasible, namely that all the assigned products fit inside the truck. This involves solving a CLP. Since the check of load plan feasibility is performed frequently, a short computational time is important. Hence, the load plan feasibility check is usually performed using approximation methods. Having rapid and reliable load plan feasibility estimations is crucial to reduce computational times when solving the VRP problem. However, if these estimations are conservative, the obtained routes are inefficient routes; if the estimations are opportunistic, the resulting load plans can turn out to be infeasible. This work explored to what extent supervised Machine Learning (ML) methods can be used to rapidly yet accurately classify whether load plans will be feasible or not. These predictions can then be exploited in VRP algorithms to improve efficiency and computation time. Several ML methods are considered and benchmarked on synthetic data and real data from a major company in the beverage sector. Extended experiments in different settings are performed, to check the effectiveness of ML in providing reliable load plan estimations and to extract insights on how load plan characteristics affect load feasibility. Results suggest the effectiveness of applying ML models, with Random Forest models reaching an accuracy above 91.5% on all different experiments considered. Also, compared to the current estimations used for load feasibility checking, Random Forest models decreases computation time with 54.9%.