Heuristische Optimierung der globalen Zielfunktion im dynamischen Ridesharing

LOUD ist ein Ridesharing-Algorithmus, welcher Fahrtanfragen zu dem Zeitpunkt, an dem sie eintreffen, in die Route eines Fahrzeuges aus einer begrenzten Menge an Fahrzeugen einfügt. Dafür betrachtet LOUD den Umweg, den ein Fahrzeug machen muss, um die Fahrtanfrage abzuarbeiten. Dem Fahrzeug, welches den kleinsten Umweg für die Fahrtanfrage machen muss, weist LOUD die Fahrtanfrage zu. Dadurch soll eine globale Zielfunktion, die durchschnittliche Gesamtfahrzeit eines Fahrzeuges, minimiert werden. LOUD berücksichtigt dabei nicht, ob ein Fahrzeug von Bedeutung für zukünftige Fahrtanfragen ist, aber durch die Zuweisung der aktuellen Fahrtanfrage an das Fahrzeug für die zukünftige Fahrtanfrage nicht mehr zur Verfügung steht. ... mehrIn dieser Arbeit befassen wir uns mit der strategischen Planung für das Ridesharing-Problem. Dabei bestimmen wir heuristisch die Fahrzeuge, die von Bedeutung für zukünftige Fahrtanfragen sind und benachteiligen diese bei der Auswahl eines Fahrzeuges für eine Fahrtanfrage. Dadurch sollen die Fahrzeuge derart positioniert werden, dass sich der Umweg, welches ein Fahrzeug für eine zukünftige Fahrtanfrage machen muss verringert und damit die globale Zielfunktion weiter minimiert werden kann. Wir konnten zeigen, dass mit diesem Ansatz die durchschnittliche Gesamtfahrzeit, sowie die Reisezeit der Fahrgäste im 95%-Quantil reduziert werden kann.

LOUD is a ridesharing algorithm that inserts ride requests into the route of a vehicle from a limited set of vehicles at the time they arrive. To do this, LOUD considers the detour that a vehicle has to make in order to process the ride request. LOUD assigns the ride request to the vehicle with the smallest detour for the ride request. This aims to minimize a global objective function. Therefor we use the average total trip time of a vehicle. LOUD does not take into account whether a vehicle is important for future requests, but is no longer available for future ride requests due to the assignment of the current ride request to the vehicle. ... mehrIn this thesis, we address strategic planning for the ridesharing problem. We heuristically determine the vehicles that are important for future ride requests and penalize them when selecting a vehicle for a ride request. This should position the vehicles in such a way that the detour that a vehicle has to make for a future ride request is reduced and the global objective function can thus be further minimized. We were able to show that this approach can reduce the average total trip time as well as the trip time of the passengers in the 95%-quantile.