Massively parallel sequencing, a popular and efficient sequencing method, produces a tremendous number of sequences from multiple individual samples. Labeling sequences with barcodes (tags) prevents them from being unrecoverable or confused during sequencing, replication, and oligonucleotide synthesis. In view of DNA barcode set design, we propose a tabu variable neighborhood search (TVNS) to design DNA barcode sets. We propose using sequences with the maximum sum of edit distances as the basis for building the neighborhood structures of TVNS. We adopt an exhaustive search to complete local searches built from these structures. The algorithm switches between neighborhoods built from different seed data. Compared with previous designs, our proposed algorithm is effective for designing DNA barcode sets and improving the lower bound of DNA barcode sets.