Jeder will auf der optimalsten Route an sein Ziel kommen. Im Straßenverkehr hilft uns dafür ein Navi die besten Straßen zu finden. Für Fabriken gibt es das noch nicht. Wie Sie in 3 einfachen Schritten selber zu optimalen Routen kommen, zeige ich Ihnen in diesem Artikel.
Inhaltsverzeichnis
- Warum sind optimale Routen wichtig?
- Wie ermittelt man eine optimale Route?
- Realisierung mit Excel
- Fahren wir heute schon optimal?
- Ausblick
- Download
Warum sind optimale Routen wichtig?
Kennen Sie die optimalen Routen für den Transport von Materialien und Produkten innerhalb der Fabrik, können Sie Zeit und Ressourcen sparen. Sie haben dann die Möglichkeit einer effizienteren Nutzung von Arbeitskräften und Transportmitteln. Kürzere Transportwege durch optimale Routenplanung tragen auch dazu bei, die Betriebskosten zu senken. Dies kann sich in Form von reduzierten Treibstoffkosten, geringerem Verschleiß von Fahrzeugen und einer besseren Ressourcenauslastung für Sie auswirken.
Optimale Routen in einer Fabrik sind damit ein entscheidender Stellhebel. Bleibt aber die Frage übrig: Was sind eigentlich optimale Routen in Ihrem konkreten Fall?
Wie ermittelt man eine optimale Route?
Die Ermittlung einer optimalen Route kann je nach Anwendungsfall, und den zur Verfügung stehenden Ressourcen, unterschiedliche Methoden erfordern. In Spezialfällen reicht das bis zum Einsatz von Geographischen Informationssystemen, GPS-Systemen oder KI.
Im Fabrik Alltag trifft man meistens auf den Klassiker: die manuelle Planung. Das ist zugleich der einfachste Ansatz und beinhaltet die manuelle Planung einer Route auf Grundlage von Fabrik-Layouts. Die Auswahl der optimalen Route erfolgt durch Erfahrung und Wissen des Planers.
Für kleine Bereiche ist das gut zu bewältigen. Im größeren Maßstab oder für viele Untersuchungen reicht es aber nicht aus.
Das ist auch nicht weiter problematisch, denn für optimale Routen reichen im Grunde 3 einfachen Schritte, um diese selber im Unternehmen zu ermitteln.
- Geodaten zusammenstellen
- Algorithmus zur Streckenberechnung anwenden
- Ergebnis visualisieren
1. Schritt: Geodaten zusammenstellen
Ohne Geodaten ist heute keine Navigation im Straßenverkehr möglich. Jedes Navigationsgerät benötigt Punkte mit Geodaten, welche über ein Routennetz mit Entfernungen verbunden sind. Es entsteht ein riesiger gerichteter und gewichteter Graph. Dasselbe gilt für die Fabrik. Eine optimale Route kann, wie beim Navi, nur über ein Routennetz – den Fabrik-Graph – gefunden werden.
Jede Abzweigung oder jeder mögliche Zielort muss als Knoten im Fabrik-Layout bekannt sein. Mögliche Wege werden durch Verbindungen der Knoten dargestellt. Eine Verbindung kann nur in jeweils eine Richtung (Einbahnstraße) oder in beide Richtungen möglich sein.
2. Schritt: Algorithmen zur Streckenberechnung anwenden
Sicher finden Sie optimale Routen in der Fabrik nur über Algorithmen. Hier gibt es eine Vielzahl von Möglichkeiten. Heuristische Algorithmen basieren auf Regeln oder Strategien, um Routen schrittweise zu optimieren, ohne alle möglichen Kombinationen auszuprobieren. Für komplexere Routing-Probleme können mathematische Optimierungsalgorithmen oder lineare Programmierung eingesetzt werden. Diese Algorithmen berücksichtigen alle möglichen Routen und finden die beste Lösung unter Berücksichtigung von Zielfunktionen, wie minimale Entfernung, minimale Zeit oder minimale Kosten.
Die Wahl des besten Ansatzes hängt von der Komplexität des Problems, den verfügbaren Daten und den spezifischen Anforderungen ab.
Komplexität ist in einer Fabrik zweifelsfrei vorhanden. Sie ist aber nicht mit der Komplexität eines Straßennetzwerks vergleichbar. Deswegen lassen sich gut einfache Algorithmen einsetzen, die alle möglichen Lösungen untersuchen und nach der Zielfunktion „Entfernung“, die Beste Route auswählen, um von einem Knoten (z. B. einem Arbeitsplatz) zu einem anderen zu navigieren.
Gängige Algorithmen sind die Algorithmen von Dijkstra, A* oder von Floyd-Warshall.
3. Schritt: Ergebnis visualisieren
Ein Algorithmus präsentiert sein Ergebnis direkt in einer Matrix. Würde ein Navi so vorgehen, hätte sicherlich jeder von uns viel Freude damit. Deswegen geht es nicht ohne Visualisierung. Das Ergebnis muss mit Hilfe des Streckennetzes verständlich visualisiert sein.
Realisierung mit Excel
Jetzt wissen wir, wie vorzugehen ist. In diesem Abschnitt setzen wir ein Beispiel mit Microsoft Excel selber um. Sie können sich davon inspirieren lassen und es sehr einfach auf Ihren Anwendungsfall anpassen.
Wie kommt das Streckennetz in den Rechner?
Je nach Anforderungen an die Genauigkeit kommen verschiedene Techniken zum Einsatz: CAD-Zeichnungen, OpenStreetMap, Spezialsoftware. Was allen Varianten gemein ist, sie brauchen in irgendeiner Form Geodaten.
Da die Berechnungen mit Microsoft Excel durchgeführt werden, sollen auch die Geodaten dort erfasst werden. In Punkto Genauigkeit muss also etwas Abstriche gemacht werden. Dafür wird eine Analyse für fast jeden Excel-Nutzer möglich.
Formen mit mittigem Kontaktpunkt
Wie sieht nun die Erfassung des Streckennetzes in Excel aus? Basis ist ein Layout Ihrer Fabrik. Das wird als Bild auf einem Arbeitsblatt in Excel positioniert.
Über dieses Bild müssen die Transportwege und Zielorte erkennbar sein, denn diese müssen im nächsten Schritt definiert werden. Für den Algorithmus sind das die einzelnen Knoten des Fabrik-Graphen.
Damit spätere Anpassungen möglich sind und die Positionierung einfach gelingt, verwende ich dafür die Formen in Excel.
Am besten eignet sich die Form „Flussdiagramm: Zusammenstellen“. Sie ist die einzige Form, welche in der Form-Mitte einen Kontaktpunkt hat.
Über diesen Kontaktpunkt wird die Verbindung (Kante) zwischen den Knoten zueinander hergestellt. Dafür eignen sich die Excel Verbindungspfeile perfekt. Sie lassen sich an den Kontaktpunkt andocken und mit einem Pfeil können Sie eine definierte Fahrtrichtung mitgeben oder mit einem Doppelpfeil eine beidseitige Befahrung zulassen.
Für jeden möglichen Abzweigungspunkt fügen Sie einen Knoten ein und schieben die Excel Form (Shape) an die richtige Stelle im Fabrik-Layout.
Die Layoutposition nutzt später der Algorithmus zur automatischen Berechnung der Entfernungen zwischen den Knoten.
Achtung:
Jeder eingefügte Knoten muss einen eindeutigen Namen haben
Über die Namen wird später die Route berechnet und ausgegeben. Deswegen muss der Name eindeutig sein. Zugewiesen wird der Name in der Bearbeitungsleiste von Excel nach Anklicken einer Form (Shape). Im Bild ist dem Shape der Name Knoten-42 zugewiesen.
Knoten mit Verbindungspfeilen direkt einfügen
Noch praktischer und innerhalb weniger Minuten geht der Aufbau eines Streckennetzes mit einer eigenen Einfügeprozedur. Mit VBA lässt es sich leider nicht realisieren, dass das richtige Shape gleich direkt am Mauszeiger hängt. Aber über den Umweg, das Shape auf ein anderes – ein Ablage-Shape – zu positionieren, gelingt das trotzdem gut.
Dafür braucht es eine globale Variable, in der das letzte eingefügte Shape gespeichert wird. Zu diesem erzeugt die Prozedur automatische eine Doppelpfeil-Verbindung an dem mittleren Kontaktpunkt (Nr. 2).
Sub InsertNode() 'Hotkey Strg+Y
Dim shpNode As Shape
Dim shpEdge As Shape
Set shpNode = ActiveSheet.shapes.AddShape(msoShapeFlowchartCollate, 100, 100, 28, 28)
shpNode.Name = NODE_PREFIX & CStr(NextNodeNumber(ActiveSheet.Name))
Call FormatNode(shpNode)
If lastNode Is Nothing = False Then
Set shpEdge = ActiveSheet.shapes.AddConnector(msoConnectorStraight, 100, 100, 100, 100)
shpEdge.Line.BeginArrowheadStyle = msoArrowheadTriangle
shpEdge.Line.EndArrowheadStyle = msoArrowheadTriangle
shpEdge.ConnectorFormat.BeginConnect lastNode, 2
shpEdge.ConnectorFormat.EndConnect shpNode, 2
Call FormatEdge(shpEdge)
End If
If ExistsShape(S_LAYOUT, "InsertNewNodePanel") = True Then
shpNode.Left = Sheets(S_LAYOUT).shapes("InsertNewNodePanel").Left + (Sheets(S_LAYOUT).shapes("InsertNewNodePanel").Width - shpNode.Width) / 2
shpNode.Top = Sheets(S_LAYOUT).shapes("InsertNewNodePanel").Top + (Sheets(S_LAYOUT).shapes("InsertNewNodePanel").Height - shpNode.Height) / 2
End If
Set lastNode = shpNode
End Sub
Der große Vorteil liegt darin, auch automatisch ein eindeutiger Knotenname generiert wird und die Ablage des neuen Shapes immer mittig in das Shape InsertNewNodePanel erfolgt. Damit können Sie in größeren Layouts die Einfügeposition immer in die Nähe Ihres Arbeitsbereiches schieben und schneller arbeiten.
Das Streckennetz im Beispiel aufzubauen dauerte nur wenige Minuten. Auf diese Art lassen sich auf größere Fabrik-Graphen sehr schnell verwirklichen.
Wie einfach und schnell das funktioniert, können Sie sich in diesem kurzen Video anschauen.
Streckennetz auswerten
Als nächstes müssen die Knoten und Kanten des Streckennetzes für den Algorithmus verwendbar gemacht werden.
Die Subroutine FindNodes durchläuft alle Shapes des Arbeitsblatts. Beginnt der Name des Shapes mit „Knoten-“, wird nachgeschaut, ob es Verbindung zu anderen Shapes hat. Gibt es welche wird es als Knoten gewertet und in eine Liste aufgenommen. Damit diese sichtbar für Sie ist, trägt sie die Routine in das Tabellenblatt Knoten ein.
Das Kriterium muss aber nicht der Name sein. Sie können auch andere Bedingungen nutzen, wie beispielsweise abfragen, ob es sich um einen bestimmten Shape-Typ handelt.
Private Sub FindNodes()
Dim sheet As Worksheet
Dim shp As Shape
Dim i As Integer
Dim k As Integer
Dim kmax As Integer
Dim s As String
kmax = 0
Set sheet = Sheets(S_LAYOUT)
'Anzahl ermitteln
i = 1
For Each shp In sheet.shapes
If Left$(shp.Name, Len(NODE_PREFIX)) = NODE_PREFIX And HasEdges(shp.Name) = True Then
i = i + 1
End If
Next
i = i - 1
Call ClearSheet(S_NODES)
Sheets(S_NODES).Cells(1, 3) = "Knoten": Sheets(S_NODES).Cells(1, 2) = i
Sheets(S_NODES).Cells(4, 1) = "Name"
i = 0
For Each shp In sheet.shapes
k = CountEdges(shp.Name)
If k > kmax Then kmax = k
If Left$(shp.Name, Len(NODE_PREFIX)) = NODE_PREFIX And k > 0 Then
Sheets(S_NODES).Cells(i + NODES_DY, 1) = shp.Name
i = i + 1
End If
Next
End Sub
Geht es nur um das Finden der optimalen Route reicht es aus, alle Knoten korrekt miteinander zu verbinden. Ist auch die Entfernung wichtig, muss eine Umrechnung in den Maßstab des Fabrik-Layout Bildes erfolgen. Als Hilfsmittel fügen Sie ein beliebiges Shape in das Tabellenblatt ein und benennen es mit dem Namen layout_scale. Dann schieben Sie es an eine Stelle im Fabrik-Layout und vergrößern es horizontal auf eine Länge, die Sie vom Layout her kennen.
Den realen Wert, hier 10 Meter, hinterlegen Sie im Quellcode für die Längenberechnung:
Private Function CalcEdgeResistor(shpNameFrom As String, shpNameTo As String) As Double 'Berechnet den Widerstand von einem Knoten zum anderen, hier die Entfernung Const realScaleLength = 10 '10m ...
Dort liegt auch die Ungenauigkeit dieser Variante. Eine genaue Positionierung ist nur schwer möglich und hängt von Ihren Fähigkeiten ab, die Knotenpunkte exakt zu positionieren und die Länge des Hilfsmaßstabs festzulegen.
Vorbereiten der Matrizen
Das so erzeugte Streckennetz ist die Ausgangsbasis für den Algorithmus. Es muss nur noch in eine Matrix überführt werden. Der Floyd Algorithmus verlangt eine Matrix in der Form: von Quelle (Zeilen) zur Senke (Spalten). Es muss für jede vorhandene Verbindung zwischen zwei Knoten ein Widerstand zum Überwinden der Strecke berechnet sein. Gibt es keine Verbindung ist der Widerstand unendlich. Als Widerstand gilt für mein Beispiel die Entfernung. Es können aber genauso Fahrzeiten, Transportkosten oder andere Kriterien sein.
HÄSSIG hat 1979 eine Vorgänger-Matrix eingeführt. Mit dieser lässt sich elegant die Route aus der Floyd Optimierung herauslesen.
Vorgängermatrix(i,j) = 1, falls i=j oder i direkt benachbart mit j
Vorgängermatrix(i,j) = 0, in jedem anderen Fall
Umsetzen des Floyd Algorithmus in VBA
Der Floyd-Warshall Algorithmus ist der Einfachste in der Umsetzung. Deswegen ist er Teil meines Umsetzungsbeispiels.
Die grundlegende Idee des Floyd-Warshall-Algorithmus besteht darin, die kürzesten Wege zwischen allen Knoten schrittweise zu aktualisieren, indem er alle möglichen Pfade zwischen den Knoten überprüft. Der Algorithmus verwendet eine iterative Vorgehensweise, bei der die Widerstandsmatrix (hier Entfernungsmatrix) schrittweise aktualisiert wird, bis die kürzesten Wege für alle Knotenpaare gefunden wurden.
Umgesetzt ist der Floyd Algorithmus in wenigen Zeilen Quellcode. Auch die Rechenzeit spielt heute fast keine Rolle mehr. Die größte Zeit benötigt das Auslesen des Streckennetzes.
Private Sub FloydAlgorithem()
Dim h As Double
Dim k As Integer
Dim i As Integer
Dim j As Integer
Dim smax As Integer
Dim w() As Double
Dim v() As Integer
smax = NodesCount()
ReDim w(smax, smax)
ReDim v(smax, smax)
For i = 1 To smax
For j = 1 To smax
w(i, j) = matrixResistor(i, j)
v(i, j) = matrixPredecessor(i, j)
Next
Next
For k = 1 To smax
For i = 1 To smax
For j = 1 To smax
If w(i, k) = INFINITE_DOUBLE Or w(k, j) = INFINITE_DOUBLE Then
h = INFINITE_DOUBLE
Else
h = w(i, k) + w(k, j)
End If
If h < w(i, j) Then
w(i, j) = h
v(i, j) = v(k, j)
End If
Next
Next
Next
...
End Sub
Als Ergebnis entsteht eine Matrix mit allen Knoten und den jeweils kürzesten Verbindungen zwischen den Knoten. Wollen Sie eine Entfernung zwischen Knoten-10 und Knoten-8 wissen, starten Sie in der Zeile 11 in Spalte A. Dort steht der Ausgangspunkt Knoten-10. Gehen Sie jetzt in dieser Zeile nach rechts bis in Spalte I Ihr Zielpunkt Knoten-8 steht. Dieser Wert ist die kürzeste Entfernung zwischen den beiden Knoten, hier 9,59 Meter.
Visualisierung von beliebigen Routen
Parallel dazu wird auch die Vorgänger-Matrix generiert. Über sie lassen sich Routen rekonstruieren. Die Route wird rückwärts ausgehend von dem Zielknoten zum Startknoten ermittelt. Suchen Sie sich die Zeile des Startpunktes aus. Gehen Sie dann in die Spalte des Zielknotens. Die Zahl an beiden Punkten gibt Ihnen die Spaltennummer (+1) des nächsten Wegepunktes an. Das wird solange wiederholt, bis Sie am Ausgangspunkt angekommen sind.
In der VBA Umsetzung ermittelt dieser Code die Routen von Start- zum Zielknoten.
Function FloydRoute(shpNameFrom As String, shpNameTo As String) As String
Dim result As String
Dim i As Integer
Dim x As Integer
Dim y As Integer
Dim smax As Integer
Dim route() As Integer
Dim routeNodes As Integer
Dim distance As Double
Dim source As Integer
Dim destination As Integer
source = -1: destination = -1: distance = 0
smax = NodesCount(): ReDim route(smax)
For y = 1 To smax
If shpNameFrom = Sheets(S_ROUTE).Cells(y + 1, 1) Then source = y
If shpNameTo = Sheets(S_ROUTE).Cells(y + 1, 1) Then destination = y
Next
If source = -1 Or destination = -1 Then
FloydRoute = ""
Exit Function
End If
routeNodes = 1: route(routeNodes) = destination
'Route von Ziel zur Quelle
Do While destination <> source And routeNodes <= smax
destination = Sheets(S_ROUTE).Cells(1 + source, 1 + destination).Value 'Nächsten Routenpunkt gefunden
routeNodes = routeNodes + 1
route(routeNodes) = destination
Loop
If destination = source Then 'Route ist fertig, an Quelle angekommen
result = ""
For i = 1 To routeNodes
result = Sheets(S_ROUTE).Cells(route(i) + 1, 1) + ";" + result
Next
If Right$(result, 1) = ";" Then result = Left$(result, Len(result) - 1)
FloydRoute = result
Else
FloydRoute = ""
Debug.Print "Keine Route gefunden: " & shpNameFrom & "-" & shpNameTo
End If
End Function
Die Funktion ist als normale Excel-Funktion nutzbar. Nach Eingabe von Start- und Zielknoten lassen sich die Routenpunkte und die Entfernung direkt ausgeben.
Da das Layout mit Streckennetz jetzt aber vorliegt, ist es viel praktischer die Route visuell anzuzeigen. Das funktioniert über die Funktion VisualizeRoute.
Private Sub VisualizeRoute(shpNameFrom As String, shpNameTo As String)
Dim s As String
Dim route() As String
Dim shpName As Variant
Dim last As String
s = FloydRoute(shpNameFrom, shpNameTo)
route() = Split(s, ";")
last = ""
For Each shpName In route
If last <> "" Then
Call VisualizeEdge(last, CStr(shpName))
End If
last = shpName
Next
End Sub
Private Sub VisualizeEdge(shpNameFrom As String, shpNameTo As String)
Dim shp As Shape
Dim shp1 As Shape
Dim shp2 As Shape
Dim art As Integer
On Error Resume Next
If shpNameFrom = shpNameTo Then Exit Sub
For Each shp In Sheets(S_LAYOUT).shapes
If shp.AutoShapeType = -2 Then 'Connector
If shp.ConnectorFormat.BeginConnected And shp.ConnectorFormat.EndConnected Then
Set shp1 = shp.ConnectorFormat.BeginConnectedShape
Set shp2 = shp.ConnectorFormat.EndConnectedShape
If ((shp1.Name = shpNameFrom) And (shp2.Name = shpNameTo)) Or ((shp1.Name = shpNameTo) And (shp2.Name = shpNameFrom)) Then
'Verbindung gefunden
'welche Art ist es?
'0=keine 1=nur ausgehend von VON 2=nur ausgehend von NACH 3=beide Richtungen
If (shp1.Name = shpNameFrom) And (shp2.Name = shpNameTo) Then
art = 0
If shp.Line.BeginArrowheadStyle = 2 Then art = 2 'nach
If shp.Line.EndArrowheadStyle = 2 Then 'von
If art = 2 Then
art = 3
Else
art = 1
End If
End If
Else
art = 0
If shp.Line.EndArrowheadStyle = 2 Then art = 2 'nach
If shp.Line.BeginArrowheadStyle = 2 Then 'von
If art = 2 Then
art = 3
Else
art = 1
End If
End If
End If
If art = 2 Then art = 0
If art = 1 Or art = 3 Then 'Hervorgeben der Route
shp.Line.ForeColor.RGB = RGB(0, 150, 0)
shp.Line.Weight = 10
End If
End If
End If
End If
Next
End Sub
Im Layout integriert sieht das so aus:
Fahren wir heute schon optimal?
Nachdem Sie jetzt wissen, wie eine optimale Route in Ihrer Fabrik aussieht, fehlt der Abgleich, wie nahe Sie bereits an dieser Lösung in der realen Fabrik schon dran sind.
Das geht natürlich nur, wenn Sie nachschauen. Also raus und Augen auf.
Ausblick
Insgesamt ist das Fabrik-Streckennetz eine wertvolle Ressource, die Unternehmen dabei unterstützt, ihre Produktionsabläufe zu optimieren, Kosten zu senken, die Effizienz zu steigern und die Umweltauswirkungen zu minimieren. Es dient als Grundlage für eine Vielzahl von betrieblichen Entscheidungen und Aktivitäten.
Interessant ist es diese Daten zusammen mit einerVerbindung zur Materialflussanalyse, für die Berechnung von Transportintensitäten zu verwenden. Wenn Sie das interessiert schauen Sie gerne wieder auf diese Seite oder melden sich im Newsletter an.
Download
Hier finden Sie das „Plus an Sourcecode“ für diesen Artikel für Sie zum Download: das lauffähige Beispielprojekt mit dem vollständigen Sourcecode zum Nachschauen und Experimentieren.
