Motivation

Stellen Sie sich vor, Sie sind Eigentümer einer Fluggesellschaft. Ihre Fluggesellschaft muss ihre Flugzeuge mit Sitz in New York zuweisen, um alle anstehenden Linienflüge abzudecken.

Es gibt 10 Flüge und 8 Flugfolgen. Jede Flugsequenz besteht aus mehreren Flügen.

Eine Flugsequenz kann beispielsweise aus Flügen von New York nach Buffalo, von Buffalo nach Chicago und von Chicago nach New York bestehen.

Jede Flugsequenz hat einen bestimmten Preis. Wir müssen eine Teilmenge von Flugsequenzen auswählen, damit es für jeden Flug mindestens ein Flugzeug gibt.

Es gibt viele Möglichkeiten, eine Kombination von Flugsequenzen auszuwählen, sodass für jeden Flug ein Flugzeug zur Verfügung steht. Eine mögliche Kombination sieht so aus:

Eine andere mögliche Kombination sieht so aus:

Und viele mehr.

Welche Kombination von Sequenzen sollte Ihre Fluggesellschaft wählen, damit die Einschränkung erfüllt und die Kosten minimiert werden?

Viele große Fluggesellschaften stehen vor diesem Problem. American Airlines schätzt, dass ihr auf mathematischer Programmierung basierendes System etwa 20 Millionen US-Dollar pro Jahr einspart.

In diesem Artikel erfahren Sie, wie Sie dieses Problem mithilfe von Integer-Programmierung und Python lösen.

Was ist Integer-Programmierung?

Integer-Programmierung bringt Probleme mit Zielen und Einschränkungen mit sich. Einige oder alle Variablen sind auf Ganzzahlen beschränkt.

CVXPY ist ein Python-Tool, das Schnittstellen zu vielen Lösern zur Integer-Programmierung bereitstellt. Geben Sie Folgendes ein, um CXVPY zu installieren:

pip install cvxpy

Daten bekommen

Beginnen Sie mit dem Herunterladen der Daten von Google Drive:

Rufen Sie den Zeitplan, die Kosten und die Stunden jeder Flugsequenz ab.

Verwandle alle positiven Zahlen in 1:

Eingabeparameter

Eingabeparameter definieren:

Entscheidungsvariablen

Definieren Sie Entscheidungsvariablen mit cp.Variable:

Zwang

Es muss mindestens ein Flugzeug pro Flug vorhanden sein. Um beispielsweise sicherzustellen, dass für den Flug New York → Buffalo mindestens ein Flugzeug vorhanden ist, muss die Flugsequenz 1, 4 oder 7 gewählt werden.

Um sicherzustellen, dass für den Flug New York → Cincinnati mindestens ein Flugzeug zur Verfügung steht, muss entweder die Flugsequenz 2 oder 5 gewählt werden.

Für den Flug von New York → Buffalo haben wir also die Einschränkung:

Verallgemeinern Sie diese Einschränkung für alle 10 Flüge, wir haben:

Zielsetzung

Wir wollen die Flugsequenzen wählen, die die Gesamtkosten minimieren.

Das Problem lösen

Jetzt haben wir Einschränkungen und ein Ziel, lasst uns das Problem lösen!

13.0

[1. 1. 1. 0. 0. 0. 0. 0.]

Das bedeutet, dass das Flugzeug fliegen sollte:

• aus New York → Buffalo → Chicago → New York
• aus New York → Cincinnati → Pittsburgh → New York
• aus New York → Chicago → Cincinnati → New York

Lassen Sie uns diese Einschränkung zu unserem Problem hinzufügen und sehen, was passiert.

Einschränkung der Gesamtstundenzahl

Zuerst müssen wir das Array erhalten, das die Anzahl der Stunden für jede Flugsequenz darstellt:

Kombinieren Sie die erste Einschränkung mit der neuen Einschränkung:

Das Problem lösen:

20

Dies liegt daran, dass unterschiedliche Flugfolgen gewählt werden.

Aber warum werden die zweite und dritte Flugsequenz nicht gewählt? Wenn wir uns das Array mit den Stunden genauer ansehen, können wir sehen, dass die Gesamtstunden der ersten 3 Flüge 1700 überschreiten.

Allerdings sind die Gesamtstunden der ersten, fünften und sechsten Flugsequenz kleiner als 1700, was die Einschränkung erfüllt.

Und hier die visuelle Darstellung der neu gewählten Flugsequenzen.

Fazit

Herzliche Glückwünsche! Sie haben gerade gelernt, wie Sie Flugsequenzen auswählen und gleichzeitig die Kosten minimieren. Ich hoffe, dieser Artikel wird Sie motivieren, ähnliche Probleme mit Integer-Programmierung und Python zu lösen.

Zögern Sie nicht, den Code für diesen Artikel in diesem Github-Repository zu forken und zu spielen:

Ich schreibe gerne über grundlegende Data-Science-Konzepte und spiele mit verschiedenen Algorithmen und Data-Science-Tools. Sie können sich mit mir auf LinkedIn und Twitter verbinden .

Star dieses Repo , wenn Sie die Codes für alle Artikel prüfen wollen , die ich geschrieben habe. Folgen Sie mir auf Medium, um mit meinen neuesten Data Science-Artikeln wie diesen auf dem Laufenden zu bleiben:

Referenz

Chen, D.-S., Batson, RG, & Dang, Y. (2010). Angewandte Integer-Programmierung: Modellierung und Lösung . J. Wiley & Söhne.