Für Kurier-, Express- und Paketdienste (KEP-Dienste) stellt die Gestaltung der logistischen Abläufe einen zentralen Erfolgsfaktor dar. Es ergeben sich vielfältige strategische, taktische und operative Planungsaufgaben. In der taktischen Planung sind u.a. depotbezogen die Tourgebiete für den Nahverkehr zu planen und für den Transport der Sendungen im Fernverkehr ein Linienfahrplan zu erstellen. Diese Arbeit betrachtet die Linienverkehrsplanung. Als Fallstudie liegen die Netze und Sendungsdaten europaweit tätiger KEP-Dienstleister zugrunde. Nach einer Darstellung der Planungsaufgabe wird ein heuristischer Lösungsansatz beschrieben, der zentrale Aspekte der praktischen Fallstudien berücksichtigt und mit geringen Rechenzeiten hochwertige Lösungen erzielt.