Wie wir Fracht für Spediteure ausgewählt haben

Guten Tag. Unser Name ist Ilya Bashtanov (Entwickler, Tochka-Tochka ) und Tatyana Voronova (Datenanalystin, 2M Center ). Und wir möchten über die technische Umsetzung der Aufgabe der Warenauswahl für den Transport sprechen.

Das Wesentliche des Problems ist wie folgt. Es gibt Waren im Lager, die von Stadt A nach Stadt B transportiert werden müssen. Wir können davon ausgehen, dass nur das Gewicht der Waren berücksichtigt wird und ihre Größen mehr oder weniger Standard sind (Euro-Paletten). Ein Spediteur, der eine vorbeifahrende Fracht nehmen möchte, möchte so viel wie möglich befördern, ist jedoch durch das Gewicht und die Anzahl der Pakete begrenzt. Es ist notwendig, für ihn mehrere Varianten der Lose aus den im Lager verfügbaren Waren zu formen.

Gelöste Aufgaben für Unternehmen in diesem Fall:

1. Beladen Sie Fahrzeuge so effizient wie möglich und steigern Sie so die Transporteinnahmen.
2. Lösung des Lieferproblems in einer für den Benutzer akzeptablen Zeit (einschließlich des FIFO-Prinzips).

Das Projekt schien sofort attraktiv. Zunächst aus mathematischer Sicht: Es wurde vorgeschlagen, einen Algorithmus zur Lösung des klassischen kombinatorischen Optimierungsproblems zu implementieren. Zweitens wurde PostgreSQL als DBMS vorgeschlagen, dessen Popularität in den letzten Jahren aufgrund einer Vielzahl von Funktionen, Zuverlässigkeit und guten Leistungsmerkmalen stetig zugenommen hat. Und natürlich wurde auch die Bedeutung der praktischen Aufgabe und der Umfang des Projekts, an dem viele verschiedene Teilnehmer beteiligt waren, zu einem großen Anreiz.

Algorithmus

Diese Aufgabe ist eine Variante des klassischen Rucksackverpackungsproblems . Das Rucksackproblem ist NP-vollständig . Solche Probleme können nicht in Polynomzeit gelöst werden, obwohl dies mathematisch noch nicht bewiesen ist. Dies bedeutet, dass exakte Algorithmen wie die umfassende Suche nach Varianten oder deren optimierten Sorten in der Praxis nicht funktionieren, da sie komplex sind$$$O(2^n)$. Ungefähre Methoden bieten Lösungen für die beste Zeit. Zum Beispiel geht der Greedy-Algorithmus davon aus, dass das maximale Gewicht so lange wie möglich im Rucksack liegt. Seine Komplexität überschreitet nicht die Komplexität der Sortierung$$$(O(n * log n))$, aber das Ergebnis kann weit vom Optimum entfernt sein. Es gibt auch eine Klasse genetischer Algorithmen, die in einer begrenzten Zeit gute Ergebnisse liefern, aber nicht deterministisch sind. In unserem Fall würde dies zu unterschiedlichen Optionen für die Ausgabe bei wiederholten Anrufen führen. Es wäre schwierig, dies dem Kunden und den Spediteuren zu erklären. Infolgedessen fiel die Wahl auf ungefähre Methoden , die das Ergebnis mit garantierter Genauigkeit in der Polynomzeit liefern.

Also haben wir:

• Gewichte mit Gewichten $$$w_1,w_2,... , w_n$
• Begrenzung des Gesamtgewichts der Ware $$$W_\max$
• Frachtlimit $$$Q_\max$

Es ist erforderlich, eine Teilmenge von Waren mit einem maximalen Gesamtgewicht zu finden, das die Einschränkungen erfüllt.

Die Idee ist, die Vielfalt der Waren durch Vergröberung ihrer Gewichte zu reduzieren und den Greedy-Algorithmus anzuwenden. In diesem Fall wird die ungefähre Lösung in einer vollständig polynomiellen Zeit gefunden, dh einer Lösung mit garantierter Genauigkeit$$$1- \varepsilon$ erhalten mit Komplexität als Polynom in $$$n$und $$$\varepsilon$.

Bei der Eingabe des Algorithmus haben wir eine Platte, die die gerundeten Gewichte der Waren und die Anzahl der Sitze für jedes Gewicht enthält. Mit einem gierigen Algorithmus versuchen wir, Styling-Optionen für die Gesamtgewichte zu erhalten$$$W_\max,$ $$$W_\max-1,$$$$W_\max-2,$$$$…,$$$$0$. Nachdem wir das Zielgesamtgewicht festgelegt haben, wählen wir in einem Zyklus aus den verbleibenden Lasten die Last des Maximalgewichts aus, um das Zielgesamtgewicht nicht zu überschreiten. Wenn der maximal zulässige Betrag erreicht ist$$$Q_\max$endet der Zyklus. Die resultierenden Kombinationen werden in einem temporären Array gespeichert.

Die Anzahl der möglichen Kombinationen kann groß sein, und es ist für den Benutzer bequem, aus einer kleinen Anzahl von Optionen zu wählen, aber gleichzeitig sollte es immer noch eine Auswahl geben. Eine zusätzliche Aufgabe ergibt sich aus der Auswahl bevorzugter Kombinationen. Um dies nicht zu komplizieren, haben wir uns entschlossen, nach Möglichkeit immer zwei Optionen anzugeben. Für ein Lager ist es zunächst ratsam, die schwersten Lasten zu versenden, daher ordnen wir die Kombinationen in absteigender Reihenfolge nach dem größten Gewicht der Ladung. Wenn die Kombinationen mit dem maximalen Maximalgewicht mehr als zwei sind, geben wir zwei aus: mit der größten und der geringsten Warenmenge.

Tests

Zum Testen haben wir zwei Implementierungen des betrachteten Algorithmus ausgewählt, die sich in unwesentlichen Details unterscheiden: eine in Java, die andere in PL / pgSQL, der prozeduralen Sprache des PostgreSQL-DBMS. Es sollte sofort beachtet werden, dass die endgültige Auswahl nicht nur von den Testergebnissen, sondern auch von architektonischen Überlegungen, Benutzerfreundlichkeit und anderen Faktoren beeinflusst wurde. Zunächst bestand die Aufgabe darin, eine von zwei Implementierungen auszuwählen.

Es wurden zwei Testumgebungen verwendet: ein Desktop zum Testen der Entwicklung und ein Server zum Testen unter ähnlichen Bedingungen wie bei realen.

• Entwickler : HP Probook 4740s Client Station + 32-Bit 2 x Pentium® Dual-Core-CPU E5300 bei 2,60 GHz und 4 GB RAM, Ubuntu Linux 16.04, PostgreSQL 10.3.
• test: 64-bit 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz 14 , CentOS Linux 7.4, PostgreSQL 10.3

In der PostgreSQL-Datenbank wurde eine Testtabelle erstellt, die 7000 Ladungen mit zufälligen Gewichten von 20 bis 800 kg enthielt. Zum Testen verwendeten wir das Standarddienstprogramm pgBench von PostgreSQL, das während des Tests 500 Transaktionen (10 Verbindungen mit jeweils 50 Transaktionen) ausführte. Bei jeder Transaktion wurde der Algorithmus mit zufälligen Parametern aufgerufen (Gewichtsbeschränkung von 10 auf 1000 kg und Anzahl der Waren von 1 auf 50 Stück). Alle Zufallsvariablen sind gleichmäßig verteilt.

Für den ersten Algorithmus startete jede Transaktion eine Java-Maschine und übergab ihr ein JAR-Archiv mit dem Algorithmuscode zur Ausführung. Die Haupt-Java-Klasse, die über den JDBC-Treiber mit der Datenbank verbunden ist, hat Testdaten aus der Tabelle empfangen und den Algorithmus auf diese angewendet.

Für den zweiten Algorithmus rief jede Transaktion die gespeicherte Funktion der PostgreSQL-Datenbank auf, die Testdaten aus der Tabelle las und den Algorithmus anwendete.

Tabelle 1. Ergebnisse des Haupttests



Zusätzlich zum Haupttest, dessen Ergebnisse in Tabelle 1 gezeigt sind, wurde ein zusätzlicher Test von Algorithmus 2 durchgeführt, bei dem verschiedene Optionen zum Erhalten der Anfangsdaten verglichen wurden: aus einer Datenbank, aus einer Datei, zufällige Array-Erzeugung. Es stellte sich heraus, dass das Übertragen von Daten von einem DBMS zu einem lokalen Array für 7000 Ladevorgänge mehr Zeit erfordert als der eigentliche Stapelalgorithmus.

Ergebnisse.

1. In unserer Aufgabe hing die Leistung mehr von der Architektur des Systems und der Geschwindigkeit der Interaktion mit der Datenbank ab als vom verwendeten Algorithmus. Dies wird durch einen zusätzlichen Test von Algorithmus 1 bestätigt, bei dem die Auswahl von Daten aus der Datenbank den größten Teil der Zeit in Anspruch nahm.
2. Option 2 lässt sich etwas besser skalieren, anscheinend aufgrund geringerer RAM-Anforderungen (temporäre Datenbanktabellen werden zum Speichern von Zwischenergebnissen verwendet).

Als Ergebnis wurde der zweite Algorithmus gewählt, der mit geringfügigen Änderungen für das zweite Jahr verwendet wurde. Infolgedessen wird eine Lösung mit akzeptabler Genauigkeit mit einer durchschnittlichen Transaktionszeit von weniger als 1 Sekunde gesucht.

Ausbeutung

Wie immer nahm das Leben Anpassungen vor und ich musste die Implementierung optimieren.

In Wirklichkeit reserviert der Spediteur die Sendung in einer Yankee-Auktion mit einem variablen Preis. Genau genommen ist diese Option des Auktionsverkaufs nicht, aber dies ist das Thema eines separaten Gesprächs an einem anderen Standort. Zusätzlich zum maximalen Frachtgewicht und der maximalen Menge legt der Spediteur zwei Städte (Anfang und Ende der Route) und die gewünschte Ladezeit fest. Danach filtert das Auswahlverfahren für jedes Lagerpaar (in der Abfahrts- und Zielstadt) Ladungen nach verschiedenen Kriterien heraus, insbesondere unter Berücksichtigung der Arbeitszeit des Lagers und der maximalen Transportkosten, zu denen die Kosten noch vom Absender getragen werden, und überträgt ihre Gewichte auf den Stapelalgorithmus. Am Ausgang des Algorithmus wird eine Liste von Gewichten erhalten, nach denen Sätze spezifischer Waren ausgewählt werden, die als Auktionsangebote ausgegeben werden.

Anfangs wurden die Gewichte auf Werte aufgerundet, die ein Vielfaches von 10 kg sind. Während des Betriebs wurde deutlich, dass die Genauigkeit spürbar leidet und die Ergebnisse dem gesunden Menschenverstand zu widersprechen beginnen. Beispielsweise kann das System bei Waren mit einem Gewicht von 12 und 19 kg die erste auswählen. Warehouse-Skalen liefern Daten mit einer Genauigkeit von 1 kg, und für das aktuelle Volumen und die aktuelle Last erwies sich die Leistung des Algorithmus für ganzzahlige Werte der Skalen als recht akzeptabel, sodass sie die Rundung abgelehnt haben. In Zukunft ist mit zunehmender Anzahl von Sendungen geplant, auf Werte zu runden, die ein Vielfaches von 5 kg sind.

Der Aufwand für den Betrieb des Stapelalgorithmus mit dem aktuellen Datenvolumen und der Abfrageintensität ist nicht kritisch. In der Phase der Ladungsauswahl sowie für andere Systembetriebsprozesse werden erheblich mehr Ressourcen benötigt.

Geschäftsergebnisse

Die Mission des Point-Point ist ein effektiver Logistikprozess, insbesondere die optimale Nutzung des Fahrzeugs im Hinblick auf Staus: beim Transport eines Minimums an Hohlräumen.

Die globalen Ziele der Lösung von Optimierungsproblemen im Güterverkehr: Das Einsparen von Ressourcen trägt zum Wirtschaftswachstum bei, schafft zusätzliche Möglichkeiten für kleine und mittlere Unternehmen und verbessert die Umwelt.

Die Spezialisten von Center 2M und Tochka-Tochki fanden eine softwaremathematische Lösung, die für alle Teilnehmer am Transportprozess geeignet ist. Es kann für das Bundesnetz verwendet werden, von dem an jedem Punkt 7 Tausend Paletten (entsprechend der Größe des Fußballfeldes) von 500 Transportunternehmen angefordert werden und das Ergebnis in weniger als 1 Sekunde erzielt wird.

Autoren des Artikels: Ilya Bashtanov (i-bash), Tatyana Voronova (tvoronova)