Public Class HalteStellenComparer
    Implements IComparer(Of String)
 
    Public Function Compare(ByVal x As String, ByVal y As String) As Integer _
        Implements System.Collections.Generic.IComparer(Of String).Compare
        Return (GetComparableString(x).CompareTo(GetComparableString(y)))
    End Function
 
    Private Function GetComparableString(ByVal hs As String) As String
        Dim stb As New System.Text.StringBuilder(hs.ToUpper.Trim)
        stb.Remove(0, 10)
        If stb(0) = "_"c Or stb(0) = "-" Then stb.Remove(0, 1)
        stb.Replace("Ä", "AE")
        stb.Replace("Ö", "UE")
        stb.Replace("Ü", "UE")
        Return stb.ToString
    End Function
End Class

Dim enc As System.Text.Encoding = System.Text.Encoding.UTF7 'oder ?
Dim lines() As String = IO.File.ReadAllLines(<Pfad/Name der _
  Haltestellendatei>, enc)
Array.Sort(lines, New HalteStellenComparer)