With the rise of network virtualization, network slicing is becoming a hot research topic. Indeed, network operators must deal with capacity-limited resources while insuring an extreme availability of services. Several approaches exist in the literature to tackle such a problem, some of them converge quickly to a local minimum, while others are not explainable and therefore do not provide the necessary guarantees for their deployment in a real network. In this context, we propose a new approach for Virtual Network Embedding (VNE) based on the Greedy Adaptive Search Procedure (GRASP). Using the GRASP meta-heuristic ensures the robustness of the solution to changing constraints and environments. Moreover, the proposed realistic approach allows a more efficient and directed exploration of the solution space, in opposition to existing techniques. The simulation results show the potential of the proposed method for solving services' placement problems and its superiority over existing approaches.