In a previous work, the Virtual Network Topology Reconfiguration problem based on Traffic Prediction (VENTURE) was proposed as a means of efficiently adapting core virtual network topology (VNT) to the near-future traffic. Although the benefits obtained by the VENTURE algorithm compared to using a purely reactive VNT reconfiguration approach seems to be clear, margin for improvement still remain and alternative solving methods for the VENTURE problem need to be considered. In this paper, the original VENTURE algorithm is compared against two state-of-the-art metaheuristics for combinatorial network optimization. The two metaheuristics are first presented and then adapted for the VENTURE problem. Finally, the performance of the VENTURE algorithm and the two proposed metaheuristics is numerically evaluated using an exact solving method as reference. © 2018 IEEE.