[PYTHON] Lösen des Transportroutenproblems (VRP) Gemischte Ganzzahlplanung
Nachdem ich berühmte Probleme im Zusammenhang mit der Logistik studiert habe, denke ich, dass ich sie mit Python lösen werde. Daher werde ich zum ersten Mal versuchen, das Transportroutenproblem mit der ganzzahligen Programmiermethode zu lösen.
Was ist das Problem mit der Transportroute?
Englischer Name Vehicle Routing Problem (VRP). [Problem mit der ORWiki-Transportroute](http://www.orsj.or.jp/~wiki/wiki/index.php/%E9%81%8B%E6%90%AC%E7%B5%8C%E8%B7 % AF% E5% 95% 8F% E9% A1% 8C) enthält eine ausführliche Erklärung. Einfach ausgedrückt ist es ein Problem, die Mindestkosten zu finden, um die Anforderungen mehrerer Kunden zu erfüllen, indem ein Spediteur verwendet wird, der zu einer Basis gehört, die als Depot bezeichnet wird. Wenn es schwer zu verstehen ist, können Sie sich einen Plan überlegen, um die gesamte LKW-Fahrstrecke von Yamato Takkyubin zu minimieren. (Entschuldigung, in ihrem Fall gibt es aufgrund ihrer Abwesenheit eine erneute Lieferung, so dass es äußerst schwierig ist, sie in ein mathematisches Problem zu bringen, oder es ist unmöglich.) Alle Lieferfirmen wollen Systeme mit dem Ziel der Automatisierung einführen, aber eine vollständige Automatisierung ist ziemlich schwierig. Dies liegt daran, dass es plötzliche Bestelländerungen und Produkte gibt, deren Größe unbekannt ist. Der Eindruck, dass die meisten Unternehmen von Handwerkern in Excel erstellt werden.
Problemtyp
- In VRP werden Probleme in Abhängigkeit vom Vorhandensein oder Fehlen der folgenden Bedingungen klassifiziert. Die auf dem Markt erhältliche Software erfüllt die meisten Einschränkungen. Dieses Mal wird nur die Gleiskapazität als Einschränkung betrachtet.
- PickUP and Delivery（VRPPD)
- Mehrere Ladeflächen. Kein einziges Depot.
- LIFO
- Post-In / First-Out-Einschränkungen. Es ist mühsam, das Gepäck auf der Rückseite des Lastwagens und das Gepäck vorne zu entfernen. Wichtig im eigentlichen Transportplan.
- Zeitrahmen (VRPTW)
- Gewünschte Lieferzeitbeschränkungen für jeden Kunden.
- Track-Kapazität (CVRP)
- Track hat Kapazitätsbeschränkungen
Formulierung
Da VRP für NP schwierig ist, verwendet kommerzielle Software die heuristische Lösungsmethode. Nachdem ich diese Zeit studiert habe, werde ich sie mit MIP (Mixed Integer Planning) lösen. Die Erklärung ist in der Quelle. Es tut mir leid, dass ich unfreundlich bin. Ich verwende eine Bibliothek namens Zellstoff, aber wenn Sie nicht damit vertraut sind, werde ich den folgenden Artikel für diejenigen verlinken, die nicht mit der Verwendung von Zellstoff vertraut sind. Einführung in die Lösung linearer Planungsprobleme mit PuLP Übrigens habe ich diesmal die erweiterte Version von DFJ implementiert, die in English Wiki of VRP eingeführt wurde.
Quelle
CVRPwithMIP.py
import pulp
import pandas as pd
import numpy as np
import networkx as nx
import itertools
import matplotlib.pyplot as plt
num_client = 15 #Anzahl der Kunden (id=0,1,2,...Ich denke, es ist 14 nummeriert. Ich würde=0 ist das Depot. )
capacity = 50 #Verfolgen Sie die Kapazität
randint = np.random.randint
seed = 10
#X für jeden Kunden,Erstellen Sie y-Koordinaten und fordern Sie (wie viele Produkte Sie möchten) als DataFrame an
df = pd.DataFrame({"x":randint(0,100,num_client),
"y":randint(0,100,num_client),
"d":randint(5,40,num_client)})
#Der 0. Kunde gilt als Depot (Basis). Also fordern=0,Zum Zeitpunkt der Visualisierung ins Zentrum kommen
#x,y bis 50.
df.ix[0].x = 50
df.ix[0].y = 50
df.ix[0].d = 0
#Kosten ist die Anzahl der Kunden ✖️ Entfernungstabelle der Anzahl der Kunden. np.In Array halten.
cost = create_cost()
#subtours ist ein Depot (id=0)Eine komplette Gruppe von Kunden außer. Ich werde später sehen, was das hilft.
subtours = []
for length in range(2,num_client):
subtours += itertools.combinations(range(1,num_client),length)
#x ist die Anzahl der Kunden ✖️ Binärvariable Array der Anzahl der Kunden. Entspricht der Kostentabelle. Wenn es 1 ist, läuft die Spur zwischen ihnen.
# num_v ist die erforderliche Anzahl von Spurvariablen.
x = np.array([[pulp.LpVariable("{0}_{1}".format(i,j),0,1,"Binary")
for j in range(num_client)]
for i in range(num_client)])
num_v = pulp.LpVariable("num_v",0,100,"Integer")
#Problemdeklaration und Zielfunktionseinstellung. Die Zielfunktion besteht darin, die Gesamtentfernung zu minimieren.
problem = pulp.LpProblem('vrp_simple_problem', pulp.LpMinimize)
problem += pulp.lpSum([x[i][j]*cost[i][j]
for i in range(num_client)
for j in range(num_client)])
#Ausgeschlossen, da keine Möglichkeit besteht, von Kunde 1 zu Kunde 1 zu wechseln
for t in range(num_client):
problem += x[t][t] == 0
#Es geht immer ein Bogen (Spur) aus und ein Bogen (Spur) vom Kunden ein.
for t in range(1,num_client):
problem += pulp.lpSum(x[:,t]) == 1
problem += pulp.lpSum(x[t,:]) == 1
#Depot (hier id=0)Die Anzahl der eingehenden Bögen (Spuren) und ausgehenden Bögen (Spuren) ist immer gleich.
problem += pulp.lpSum(x[:,0]) == num_v
problem += pulp.lpSum(x[0,:]) == num_v
#Das ist die Leber. Mit den oben genannten Einschränkungen wird eine isolierte gesperrte Straße erstellt, die nicht zum Depot zurückkehrt. Was wir hier machen
#Subtour beseitigen Einschränkung. Wir betrachten auch die Nachfrage und fügen hier eine Kapazitätsbeschränkung hinzu. interessiert sein
#Wenn Sie interessiert sind, suchen Sie bitte nach Subtour eliminieren.
for st in subtours:
arcs = []
demand = 0
for s in st:
demand += df_dpsts["d"][s]
for i,j in itertools.permutations(st,2):
arcs.append(x[i][j])
print(len(st) - np.max([0,np.ceil(demand/capacity)]))
problem += pulp.lpSum(arcs) <= np.max([0,len(st) - np.ceil(demand/capacity)])
#Berechnung und Bestätigung der Ergebnisse
status = problem.solve()
print("Status", pulp.LpStatus[status])
for i in range(num_client):
for j in range(num_client):
print(i,j,x[i][j].value())
output_image(G,x)
Visualisierung
Visualisierung der Lösung. Der blaue Punkt ist das Depot und der rote Punkt ist der Kunde (die Zahlen sind nachgefragt)
Es stellt sich heraus, dass fünf Lastwagen benötigt werden. Beachten Sie, dass der Gesamtbedarf für jede gesperrte Straße die LKW-Kapazität (= 50) nicht überschreitet.
Fazit
Gelöst! Die obige Formulierung kann nicht gelöst werden, wenn die Anzahl der Kunden ein wenig zunimmt, insbesondere weil die Anzahl der Einschränkungen für die Beseitigung von Subtouren mit der Anzahl der Kunden explosionsartig zunimmt. Hier gibt es einige Ideen, aber ich werde sie diesmal nicht vorstellen. Nächstes Mal schreibe ich eine heuristische Methode (keine exakte Lösung, aber eine gute Lösung).
Recommended Posts