Ich arbeite an einer Flugplanungs-App (Disclaimer: es ist für ein College-Projekt, also bitte keine Code-Antworten). Bitte lesen Sie diese Frage mit einiger Aufmerksamkeit, bevor Sie antworten, denn sie hat viele Besonderheiten: (
Zuerst einige Terminologieprobleme:
Sie haben Flugzeuge und Flüge, und Sie müssen sie paaren. Der Einfachheit halber nehmen wir an, dass ein Flugzeug frei ist, sobald der Flug, der es benutzt, landet.
Flüge werden als Aufgaben angesehen:
Flugzeuge können als Ressourcen angesehen werden, die von Aufgaben (oder Flügen, in unserer Terminologie) verwendet werden.
Bei Flügen wird eine bestimmte Art von Flugzeug benötigt. z.B. Flug 200 benötigt ein Flugzeug vom Typ B. Flugzeuge sind offensichtlich von nur einem bestimmten Typ, z. B. Flugzeug Airforce One ist vom Typ C.
Ein "Projekt" ist die Menge aller Flüge einer Fluggesellschaft in einem bestimmten Zeitraum.
Die erforderliche Funktionalität ist:
Den kürzest möglichen finden Dauer für ein besagtes Projekt
Das früheste und spätest mögliche Start für eine Aufgabe (Flug)
Die kritischen Aufgaben, basierend auf zur Verfügung gestellte Daten, komplett mit Bezeichner vorhergehender Aufgaben.
Flüge automatisch zusammenlegen und Flugzeuge, um alle Flüge zu bekommen gepaart mit einem Flugzeug. (Beachten Sie das Dauer der Flüge ist festgelegt)
Erhalte ein Gantt-Diagramm mit den Projekten Planung, in der alle Flüge Beginnen Sie so früh wie möglich und zeigen Sie alle zuvor genannten Daten grafisch (Abhängigkeiten, Zeitinformationen, usw.).
Die Frage ist also: Wie in der Welt erreiche ich das? Besonders:
Wenn Sie uns auch einige Algorithmen vorschlagen könnten, wäre das großartig.
Hier ein paar Vorschläge.
Im Prinzip können Sie ein Diagramm haben, bei dem jeder Knoten ein Flug ist und es eine Kante von Flug A zu Flug B gibt, wenn B von A abhängt, d. h. B kann nicht starten, bevor A gelandet ist. Sie können dieses Abhängigkeitsdiagramm verwenden, um die kürzest mögliche Dauer für das Projekt zu berechnen --- finden Sie den Pfad durch das Diagramm mit der maximalen Dauer, wenn Sie die Dauer aller Flüge auf dem Pfad zusammenaddieren. Dies ist der "kritische Pfad" Ihres Projekts.
Die Tatsache, dass Sie Flugzeuge koppeln müssen, macht es jedoch schwieriger, insbesondere. wie ich vermute, wird angenommen, dass die Flugzeuge nicht ohne Passagiere fliegen dürfen, d. h. ein Flugzeug muss von der gleichen Stadt starten, in der es zuletzt gelandet ist.
Wenn Sie über eine zu große Anzahl von Flugzeugen verfügen, kann die Zuordnung zu den Flügen sehr wahrscheinlich mit einem kombinatorischen Optimierungsalgorithmus wie Simulated Annealing erfolgen. Wenn der Plan sehr eng ist, d. H. Sie haben keine überschüssigen Flugzeuge, könnte es ein schweres Problem sein.
Um die tatsächlichen Startzeiten für Ihre Flüge festzulegen, können Sie zum Beispiel die erlaubten Zeitpläne als lineares Programmierproblem oder als halbdefiniertes / quadratisches Programmierproblem formulieren.
Hier einige Referenzen:
Beginnen Sie mit dem Zeichnen eines Domänenmodells (Klassendiagramm) und machen Sie eine klare Trennung zwischen:
PlaneType , Plane , Flight , FlightBeforeFlightConstraint , ... PlaneToFlightAssignment
Umschließen Sie alle Instanzen in der Klasse Project (= eine Lösung).
Dann definieren Sie eine Score-Funktion (AKA-Fitness-Funktion) für eine solche Lösung. Wenn es beispielsweise 2 PlaneToFlightAssignments gibt, die mit einem FlightBeforeFlightConstraint (= Flugabhängigkeit) nicht in Ordnung sind, dann senken Sie die Punktzahl.
Dann ist es nur eine Frage, die Lösung mit dem besten Ergebnis zu finden, indem Sie die PlaneToFlightAssignment Instanzen ändern. Es gibt verschiedene Algorithmen , mit denen Sie arbeiten können finde die beste Lösung. Wenn Ihr Datensatz wirklich sehr klein ist (etwa 10 Ebenen), können Sie möglicherweise brute force verwenden.
Tags und Links algorithm graph scheduling gantt-chart