Heuristic Methods for the Vehicle Routing Problem and Their Application in Car Sharing

Die Anzahl der Personen, die sich ein Fahrzeug teilen – Car-Sharing-Nutzer – stieg in Deutschland seit den letzten 15 Jahren aufgrund sozialer, ökonomischer und ökologischer Ursachen ununterbrochen an. Um das Car-Sharing für Unternehmen attraktiv zu gestalten, müssen diese ihre Fahrzeugflotte bestmöglich ausnutzen.

Diese Arbeit gibt zunächst einen Überblick über das Vehicle Routing Problem und verschiedene mögliche Lösungansätze. Darauf aufbauend wird ein Algorithmus entwickelt, der die Fahrzeuge einer Car-Sharing-Flotte Kunden zuordnet.

Das Vehicle Routing Problem ist ein Graphenproblem, bei dem – vereinfacht dargestellt – eine Zuordnung von Fahrzeugen zu Transportfahrten zwischen Depots und Kunden gesucht wird. Nach der Betrachtung dieses Problems widmen wir uns der Lösung mittels des heuristischen Honey Bees Mating Optimization Algorithm. Dieser wird zunächst vorgestellt und dann für die Verwendung von Elektrofahrzeugen angepasst. Anschließend wird er auf das Zuordnungsproblem von Car-Sharing-Fahrzeugen zu Nutzern angewandt.