  The Burrows-Wheeler Transform (BWT) is a string transformation technique
widely used in areas such as bioinformatics and file compression. Many
applications combine a run-length encoding (RLE) with the BWT in a way which
preserves the ability to query the compressed data efficiently. However, these
methods may not take full advantage of the compressibility of the BWT as they
do not modify the alphabet ordering for the sorting step embedded in computing
the BWT. Indeed, any such alteration of the alphabet ordering can have a
considerable impact on the output of the BWT, in particular on the number of
runs. For an alphabet $\Sigma$ containing $\sigma$ characters, the space of all
alphabet orderings is of size $\sigma!$. While for small alphabets an
exhaustive investigation is possible, finding the optimal ordering for larger
alphabets is not feasible. Therefore, there is a need for a more informed
search strategy than brute-force sampling the entire space, which motivates a
new heuristic approach. In this paper, we explore the non-trivial cases for the
problem of minimizing the size of a run-length encoded BWT (RLBWT) via
selecting a new ordering for the alphabet. We show that random sampling of the
space of alphabet orderings usually gives sub-optimal orderings for compression
and that a local search strategy can provide a large improvement in relatively
few steps. We also inspect a selection of initial alphabet orderings, including
ASCII, letter appearance, and letter frequency. While this alphabet ordering
problem is computationally hard we demonstrate gain in compressibility.
