Our main goal in this work is to study permutation codes in the Levenshtein metric which can correct multiple deletions. Permutation codes in the Levenshtein metric are known to have a close relationship with those in Ulam and generalized Kendall-tau metrics. In this work, we present a new connection between different kinds of distances over two permutations, including Hamming, Levenshtein, Ulam, and generalized Kendall-tau distance. From this new connection and some known permutation codes in the Hamming metric, we obtain new permutation codes in Levenshtein, Ulam, and generalized Kendall-tau metrics with better size. In particular, we show that there exist permutation codes of length $n$ for correcting $t$ deletions with at most $(3t+1) \log n+o(\log n)$ bits of redundancy. Furthermore, we present the construction of our permutation codes for correcting $t$ deletions with a specific decoding process.