Network virtualization allows the service providers (SPs) to divide the substrate resources into isolated entities called virtual data centers (VDCs). Typically, a VDC comprises multiple cooperative virtual machines (VMs) and virtual links (VLs) capturing their communication relationships. The SPs often re-embed VDCs entirely or partially to meet dynamic resource demands, balance the load, and perform routine maintenance activities. This paper proposes a genetic algorithm (GA)-based effective VDC re-embedding (GAMap) framework that focuses on a use case where the SPs relocate the VDCs to meet their excess resource demands, introducing the following challenges. Firstly, it encompasses the re-embedding of VMs. Secondly, VL re-embedding follows the re-embedding of the VMs, which adds to the complexity. Thirdly, VM and VL re-embedding are computationally intractable problems and are proven to be NP-Hard. Given these challenges, we adopt the GA-based solution that generates an efficient re-embedding plan with minimum costs. Experimental evaluations confirm that the proposed scheme shows promising performance by achieving an 11.94% reduction in the re-embedding cost compared to the baselines.