Data allocation problem (DAP) is of great importance in distributed database systems (DDS). Minimizing the total cost of transactions and queries is the main objective of DAP which is mostly affected by the volume of transmitting data through the system. On the other hand, the volume of transmitting data depends on the fragment-to-site allocations method. DAP as a Np-hard problem has been widely solved by applying soft computing methods like evolutionary algorithms. In the continuation of our previously published research, this paper proposes a novel hybrid method based on Simulated Annealing Algorithm (SA) and Variable Neighborhood Search (VNS) mechanism for Solving DAP. To increase the performance, VNS mechanism is embedded into SA method in the proposed hybrid method. Technically speaking, in order to discover more promising parts of search space, the proposed method (VNSA) explores the search space via SA and fulfills more exploitation by applying neighborhood search mechanism. Moreover, due to the fact that both are a single solution-based method, they explore the search space faster than population-based methods. Performance of the proposed VNSA is experimentally evaluated using well-known benchmarks reported in state-of-the-art literature, and evaluation outcomes prove the robustness and fastness of the proposed hybrid method (VNSA). Furthermore, the results exhibit that VNSA outperforms its competitors and achieves better results in majority of test proble