One of the main challenges for service providers when they try to deploy Network Function Virtualization based networks is to efficiently make use of substrate network resources to facilitate the design, delivery and operation of network services in a dynamic and scalable manner. This challenge is known as Network Function Virtualization Resource Allocation, which can be addressed in two stages called Service Function Chain Composition and Service Function Chain Embedding. The main objective of the first stage is to compose an optimized chain of Virtual Network Functions, which offers a complete network service. The second stage is responsible for the embedding of such network service onto a physical infrastructure based on virtualization technologies. In this paper, we propose a metaheuristic algorithm to face the scalability challenges of exact approaches, when solving the composition stage. The performance of our metaheuristic approach shows that large, complex and heterogeneous service requests can be processed in reasonable running times, finding better results compared with existing heuristics in the state of the art.