Warning: include_once(/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php): failed to open stream: No such file or directory in /var/www/html/fields/dbp11/local/config.php on line 4

Warning: include_once(): Failed opening '/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php' for inclusion (include_path='.:/opt/php/lib/php') in /var/www/html/fields/dbp11/local/config.php on line 4

Warning: Cannot modify header information - headers already sent by (output started at /var/www/html/fields/dbp11/local/config.php:4) in /var/www/html/pmwiki-2.2.86/pmwiki.php on line 1250
Datenbankpraktikum SS 2011 - Main - Backend-suche

Optimierung

Zu unseren Aufgaben als Model gehörte außerdem, eine Optimierungsfunktion zu implementieren, die Fahrtgesuche (Requests) und Fahrten (Trips) zueinander in Beziehung bringt und auf Übereinstimmung überprüft. Dabei sollen nicht nur Trips und Requests zusammengeführt werden, die identisch sind, sondern auch solche, die sich nur ähnlich sind, also z.B. nicht exakt denselben Zielort haben. Die Herausforderung besteht hierbei darin, diese "Ähnlichkeit" anhand gewisser Kriterien zu bewerten und die Trips bzw. Requests dann nach dieser Bewertung sortiert auszugeben.

Ablauf einer Suche

Wenn ein User eine Anfrage (Request) stellt, werden folgende Schritte abgearbeitet:

  1. Grobe Selektion:
    1. Nach Start-, Ziel-, Zeitpunkt
    2. Nach Gepäck, Ignorierung
  2. Bewertung der Selektion:
    1. Nach Umweg, Verzögerung
    2. Bewertung des Fahrers
    3. Anzahl Ignorierungen des Fahrers
  3. Sortierung nach Bewertung

Grobe Selektion

Sowohl die Start- als auch die Zieladresse sollen in einem vom Requeststeller vorher festgelegten Umkreis liegen und der Startzeitpunkt in einem vorher ausgewählten Intervall. Weiterhin wird der Wunsch nach Gepäckmitnahme berücksichtigt und Fahrten ignorierter Benutzer werden nicht angezeigt.

Für die Berechnung der Abstände der Start- und Zieladressen verwenden wir die Methode Calculation.distance_between des Geocoders. Diese Methode bekommt zwei Längen- und Breitengrade übergeben und errechnet den Abstand der beiden Koordinaten auf der Erdoberfläche.

Bewertung

Ist die grobe Auswahl erfolgt, werden alle Fahrten, die diese Bedingungen erfüllen näher betrachtet. Unsere Grundidee soll dabei durch folgendes Diagramm veranschaulicht werden:

Wenn es darum geht, einen Trip, der von A nach B führt, bezüglich eines Requests von C nach D zu bewerten, dann wird die Route ACDB berechnet und mit der eigentlichen Route AB des Fahrers verglichen. Wir berechnen also stets den Umweg, den der Fahrer in Kauf nehmen müsste, wenn er den Ersteller dieses Requests mitnehmen will. An dieser Stelle soll betont werden, dass keineswegs vom Fahrer verlangt wird, diesen Umweg tatsächlich zu fahren. Es wird ihm auch nicht angeboten dies zu tun, etwa indem eine Route mit diesem Umweg angezeigt wird. Die Berechnung des Umwegs dient einzig und allein uns als Kriterium für die "Ähnlichkeit" von Trip und Request.

An dieser Stelle wird auch klar, warum wir vor der Bewertung zwangsläufig erst die Auswahl einschränken mussten. Es wird für jeden einzelnen Trip eine Umwegsberechnung mit GoogleMaps oder Bing/Maps durchgeführt. Bereits ab acht Trips liegt die Anfragedauer bei mehr als drei Sekunden, so dass es unzumutbar wäre, alle Trips in der Datenbank in die Berechnung einzubeziehen.

An folgendem Beispiel soll die Berechnung der Bewertung eines Trips demonstriert werden:

Ein User hat einen Trip von Melle zum Flughafen Köln-Bonn angelegt. In der Datenbank werden die Länge und die Fahrtzeit des Trips gespeichert.

Wenn jetzt ein andere User einen Request von Ibbenbüren nach Köln anlegt, dann wird im Hintergrund folgende Route mit den Wegpunkten Ibbenbüren und Köln berechnet, aber nicht angezeigt:

Nun wird der "reine" Umweg berechnet, also die neue Distanz abzüglich der ursprünglichen: Weg_Diff = 259 - 227 = 32 Dieser Wert wird dann durch die ursprüngliche Distanz geteilt und so der relative Umweg berechnet: Weg_rel = 32 / 227 = 0,141 Das gleich geschieht mit der Fahrtzeit: Zeit_Diff = 171 – 128 = 43 und Zeit_rel = 43 / 128 = 0,336

Im günstigsten Fall sind Trip und Request identisch, so dass die beiden Werte Weg_rel und Zeit_rel den Wert 0 haben.

Außerdem sollen noch die bisherige Bewertung des Fahrers sowie die Anzahl der User, die ihn ignorieren beachtet werden. Dazu wird die Durchschnittsbewertung des Fahrers mit 1 subtrahiert und dann durch 5 geteilt. Auf diese Weise erhält man einen Wert zwischen 0 und 1, wobei 0 aus einer Durchschnittsbewertung von 1,0 folgt und 1 aus einer von 6,0. Bei den Ignorierungen wird einfach die Anzahl der User, von denen der Fahrer ignoriert wird, durch die Gesamtzahl der User geteilt. So erhält man wiederum einen Wert zwischen 0 und 1.

Hat in unserem Beispiel der Fahrer des Trips also eine durchschnittliche Bewertung von 2,1 und wird er von 2 Usern ignoriert bei einer Gesamtuseranzahl von 100, so erhalten wir noch die Werte Note_rel = (2,1 - 1) / 5 = 0,22 und Igno_rel = 2 / 100 = 0,02.

Diese vier Relativwerte werden dann nach dem Vorbild der euklidischen Norm verrechnet, so dass man einen aussagekräftigen Wert über die Güte des Trips erhält.


Page last modified on August 19, 2011, at 12:36 PM