Wir unterscheiden einen Bus von einem Auto durch GPS-Tracks


    Foto von Artem Svetlov
    Um ein plausibles Korkbild zu erstellen, verarbeitet das Mail.Ru Maps- Projekt eine große Menge an Informationen auf den GPS-Tracks der Verkehrsteilnehmer. Über die Herkunft der Gleise ist oft wenig bekannt, auch aus Sicherheitsgründen. Aber um die wahre Situation auf den Straßen zu bestimmen, wollte ich immer mehr wissen. Zumindest um zu verstehen, wie viel die Geschwindigkeit der Quellmaschine der Geschwindigkeit des restlichen Streams entspricht. Dieser Artikel konzentriert sich auf eine Methode zum Extrahieren von Routenfahrzeugen (Busse, Trolleybusse, Kleinbusse und Straßenbahnen) aus dem rohen GPS-Datenstrom.

    Warum ist das wichtig?

    Routenfahrzeuge bewegen sich meist nicht mit der Geschwindigkeit des restlichen Baches. Natürlich können sie Indikatoren für die Transportsituation sein, aber mit einigen Besonderheiten:
    • Busse und Trolleybusse haben in der Regel einen eigenen Fahrplan mit einer großen Anzahl von Haltestellen auf der Strecke. Dies bedeutet, dass der Bus auf einer freien Straße bewusst langsamer fährt als der Strom und häufig für kurze Zeit anhält. In der Hauptverkehrszeit, wenn die Busse in Intervallen von 7 bis 10 Minuten fahren, können sie eine ausreichende Menge an Informationen über die Abnahme der Durchflussrate im Bereich der Haltestelle senden.
    • Dank der zugewiesenen Fahrspuren kann der Bus schneller fahren als der Strom im Verkehr.
    • Kleinbusfahrer fahren oft gegen alle Regeln.

    Getrennt davon möchte ich die Straßenbahnen beschreiben, die fast immer auf den zugewiesenen Fahrspuren fahren, die in der Nähe oder in der Mitte der Straßen mit dem Autoverkehr vorbeifahren. Daher ist die Straßenbahnschiene praktisch nicht von der Autospur zu unterscheiden.

    Ausgangsdaten

    Ich werde im Voraus reservieren, dass der Zweck des Artikels nicht darin besteht, zu vergleichen, welches der Satellitennavigationssysteme besser ist. Fast alle Client-Geräte verfügen jetzt über Chips, die Daten von allen verfügbaren Systemen empfangen und verallgemeinerte Koordinaten bereitstellen. Um Platz zu sparen, werde ich im Folgenden den mit dem Satellitennavigationssystem erhaltenen Track als GPS-Track bezeichnen.

    Zunächst definieren wir, was ein GPS-Track ist. Ein GPS-Track ist eine Folge von Koordinaten der Position eines Geräts im Zeitverlauf. Leider ist das einzige, was wir über jedes Gerät wissen, das einen Track sendet, seine eindeutige Identifikationsnummer. Dies sind strenge Datenschutzanforderungen.

    Alle Tracks haben einen unterschiedlichen Charakter und stammen von unterschiedlichen Anbietern. In diesem Artikel werde ich den Fall betrachten, in dem das Gerät starr am Fahrzeug befestigt ist und in regelmäßigen Abständen Daten sendet. Diese Vereinfachung wird es mir ermöglichen, die Situation nicht zu berücksichtigen, in der sich das Gerät, das die Spur aufzeichnet, in den Händen von jemandem befand, dann stieg dieser in den Bus und fuhr ein paar Haltestellen ein.

    Der Zweck der Analyse besteht darin, aus der allgemeinen Liste der Tracks diejenigen zu isolieren, die die meiste Zeit entlang derselben Straßensequenzen verlaufen - Routen.

    Lösungsmethode

    Zuallererst muss die anfängliche kontinuierliche Spur in einzelne Fahrten unterteilt werden, die wir miteinander vergleichen werden. Wie bereits beschrieben - physisch an den Maschinen befindet sich ein GPS-Tracker, der alle paar Sekunden seine Koordinaten sendet. Meistens funktioniert der Tracker, wenn die Zündung des Autos eingeschaltet ist, aber es gibt Geräte, die rund um die Uhr funktionieren. Daher benötigt der Auslösetrenner einen langen Zeitraum, in dem die Geschwindigkeit immer 0 war oder das Gerät keine Daten gesendet hat.


    Beispiel für die Aufteilung einer Strecke in Fahrten

    Jetzt haben wir für jedes Fahrzeug eine Reihe von Fahrspuren, die es über einen bestimmten Zeitraum erstellt hat. Darunter befinden sich sowohl echte Fahrten als auch lose gekoppelte Spuren, die durch Fehler bei der Koordinatenbestimmung, Bewegungen innerhalb der Sperrzone des Unternehmens, „Umschiffen“ und ähnlichen Müll verursacht werden. Um keine Rechenressourcen zu verschwenden, filtere ich alle Spuren mit einer Länge von weniger als 400 Metern, einer Anzahl von Punkten von weniger als 10 und einer geografischen Streuung von weniger als 200 Metern für einen Begrenzungsrahmen. Auf diese Weise werden die Sternspuren vermieden, die aufgrund von großen Zufallsfehlern des GPS-Empfängers entstehen.


    Charakteristische Sternspuren

    Die nächste Aufgabe besteht darin, diese Tracks miteinander zu vergleichen und festzustellen, ob sie auf derselben Route verlaufen. Dazu bringe ich als erstes alle GPS-Tracks in einer Form zusammen und verbinde sie mit unserer Straßengrafik. Ich habe in meinem letzten Beitrag über die Arbeit des Binders geschrieben. Seitdem hat er einige Veränderungen erfahren, aber die Grundprinzipien sind dieselben geblieben. Beim Verlassen der Bindung erhalte ich die Spur in Form einer Kette von Paaren (ID der Kante des Graphen, Richtung (vorwärts oder rückwärts)). In diesem Stadium können Sie Strecken herausfiltern, die nicht in unsere Straßengrafik fallen. Dies können Ketten von Flugzeugen / Hubschraubern, Containern im Meer oder Mähdreschern sein. Oder einfach von Autos, die an Orte gefahren sind, an denen wir aus dem einen oder anderen Grund keine Straßengrafik haben. Ich möchte darauf hinweisen, dass hier nur die Spuren gefiltert werden, die überhaupt nicht zum Straßendiagramm passen. Wenn das Auto den Parkplatz verlassen hat, auf dem wir keine Straßengrafik haben, dann lange die Straßen entlang gefahren sind, wo es an der Straßengrafik haftete und am Ende der Straße auf den Parkplatz gefahren ist (wo es keine Straßengrafik mehr gibt), wird eine solche Strecke gezählt.

    Die resultierenden Ketten sind viel einfacher miteinander zu vergleichen. Ich habe mir verschiedene Vergleichsmetriken angesehen und mich schließlich auf die Levenshtein-Metrik konzentriert . Das Alphabet ist in diesem Fall die Menge aller möglichen Kantenrichtungspaare. So hatte ich die Möglichkeit, die „Ähnlichkeit“ von Tracks als die Anzahl der Bearbeitungen der Kanten der Route (Hinzufügen / Entfernen / Ersetzen von Kanten) numerisch zu bestimmen, um eine andere Route von einer Route zu erhalten.

    Der nächste Schritt ist das Gruppieren von Tracks auf Routen. Dieses Problem wird durch Datencluster-Algorithmen gelöst. Da ich bereits eine eindimensionale Metrik der „Ähnlichkeit“ von Spuren habe, habe ich den einfachsten hierarchischen Datencluster-Algorithmus verwendet: Dendrogramm. Ein Baum wird auf der Grundlage der Mindestentfernung von Levenshtein gebaut, und dann werden seine Zweige gebrochen, die sich um mehr als n Kanten unterscheiden. Es war unbedingt erforderlich, das Optimum n gleich 16 zu berechnen.

    Als Ergebnis erhalte ich eine Reihe von Clustern, in denen ähnliche Routen gespeichert sind. Anhand dieser Informationen kann bereits gefolgert werden, ob das Fahrzeug auf einer vorgegebenen Route fährt. Ich hatte die Idee, abhängig von der Anzahl der Kanten in der Route unterschiedliche n zu verwenden, aber diese Verbesserung erhöht nicht die Qualität der Suche, und ich entschied mich, ein festes n zu belassen.

    Anfangs wurde angenommen, dass die meisten Fahrzeuge 2 Routen (von Finale zu Finale) in beide Richtungen haben. Aber wie die Praxis gezeigt hat, kann die Route manchmal kreisförmig sein oder aus mehreren Teilen bestehen.


    Routenfahrzeuge bewegen sich nicht immer entlang der Route. Es gibt Ausflüge in die Garage, Tankstelle usw.

    Tracks von der Route. Ansicht schließen
    Daher haben die meisten Fahrzeuge mindestens einen Cluster, in dem Fahrten zusammengefasst sind, und mehrere Servicefahrten: einmalige oder seltenere Routen (zur Garage, zur Tankstelle usw.). Basierend auf den erhaltenen Daten kann eine weitere Hypothese überprüft werden: Da wir Fahrzeugrouten und Routenvergleichsmetriken haben, können wir Fahrzeuge unterscheiden, die auf derselben Route fahren. Dazu müssen Sie lediglich separate Cluster verschiedener Fahrzeuge nehmen und miteinander vergleichen (zumal die Clustervergleichsfunktion bereits in der hierarchischen Baumimplementierung enthalten ist).




    Zwei verschiedene Busse bewegen sich auf den gleichen Strecken
    , so dass ich die Route und die Gruppenfahrzeuge in Parks klären kann.

    Schlussfolgerungen

    Anonyme GPS-Daten enthalten viele Informationen. Durch die korrekte Analyse dieser Daten können Sie viele zusätzliche Informationen sowohl über das Fahrzeug, mit dem die Strecke erstellt wurde, als auch über die Stadt selbst und ihre Straßen erhalten. Daher sollte der Anwendungsbereich dieser Gleise nicht darauf beschränkt sein, Informationen über Verkehrsstaus zu erhalten, und die Informationen selbst können nicht nur Autofahrern, sondern auch Versorgungsunternehmen und Stadtentwicklungsdiensten zugute kommen. Für die Verarbeitung dieser Spuren ist es jedoch nicht erforderlich, die genauen Daten des Computers zu kennen, auf dem sie erstellt wurden. Alle notwendigen Informationen über das Fahrzeug können die Statistik über seine Bewegungen erzählen. Gleichzeitig sind GPS-Tracks ein ungenaues Werkzeug zur Ermittlung von Informationen. Um ein Ergebnis zu erhalten, muss eine große Datenmenge untersucht werden, was hohe Anforderungen an die Verarbeitungsinfrastruktur stellt.

    Jetzt auch beliebt: