[PYTHON] Kombinationsoptimierung - Typisches Problem - Problem mit der Transportroute (Lieferoptimierung)

Typisches Problem und Ausführungsmethode

Problem mit der Transportroute (Lieferoptimierung)

Eine Gruppe von Kunden $ V = \ {0, 1, \ dots, n \} $ (wobei $ 0 $ das Depot darstellt, das der Startpunkt der Route ist) und eine Gruppe von Spediteuren $ M = \ {1, \ dots , m \} $ ist gegeben. Jeder Spediteur verlässt das Depot, liefert um das zugewiesene Kundenset herum und kehrt zum Depot zurück. Für jeden Kunden $ i \ in V $ beträgt die Serviceanforderung $ a_i (\ ge 0) $, jeder Spediteur $ k \ in M $ hat eine maximale Last von $ u (\ ge 0) $ und der Kunde $ Die Kosten für den Wechsel zwischen i $ und Kunde $ j $ betragen $ c_ {ij} (\ ge 0) $. Es wird davon ausgegangen, dass die Nachfrage jedes Kunden durch einen Besuch befriedigt wird. Finden Sie Routen für alle Fluggesellschaften, um die Reisekosten zu minimieren.

Ausführungsmethode

usage


Signature: vrp(g, nv, capa, demand='demand', cost='cost', method=None)
Docstring:
Transportroutenproblem
Eingang
    g:Graph(node:demand, edge:cost)
    nv:Zahl der Fahrzeuge
    capa:Trägerkapazität
    demand:Attributzeichen anfordern
    cost:Kostenattributzeichen
    method:Berechnungsmethode(ex. 'ortools')
Ausgabe
Liste der Apex-Paare für jeden Träger

python


#CSV-Daten
import pandas as pd, networkx as nx
from ortoolpy import vrp, graph_from_table, networkx_draw
tbn = pd.read_csv('data/node1.csv')
tbe = pd.read_csv('data/edge1.csv')
g = graph_from_table(tbn, tbe)[0].to_directed()
networkx_draw(g)
nv, capa = 2, 3 #Anzahl der Fahrzeuge, Fahrzeugkapazität
print(vrp(g, nv, capa))

Ergebnis


[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

vrp.png

python


# pandas.DataFrame
from ortoolpy.optimization import Vrp
Vrp('data/node1.csv','data/edge1.csv',2,3)
car num node1 node2 cost
0 0 0 0 3 10
1 0 1 0 2 10
2 0 2 3 5 1
3 0 3 5 2 1
4 1 0 0 4 10
5 1 1 0 1 10
6 1 2 4 1 1

python


#Beispieldaten
import networkx as nx
from ortoolpy import vrp
nc, nv, capa = 5, 2, 3 #Anzahl der Kunden, Anzahl der Fahrzeuge, Fahrzeugkapazität
g = nx.DiGraph()
g.add_node(0, demand=0)
g.add_nodes_from(range(1, nc + 1), demand=1)
g.add_edges_from([(0, i) for i in range(1, nc + 1)], cost=10)
g.add_edges_from([(i, 0) for i in range(1, nc + 1)], cost=10)
for i, j, t in ((1, 3, 16), (3, 5, 1), (5, 2, 1), (2, 4, 18), (4, 1, 1)):
    g.add_edge(i, j, cost=t)
    g.add_edge(j, i, cost=t)
print(vrp(g, nv, capa))

Ergebnis


[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

Verwendung des Google OR-Tools-Lösers

Bei " method = 'ortools' "wird der Löser (ungefähre Lösung) von Google OR-Tools verwendet.

Hinweis

--Installieren Sie Google OR-Tools mit "pip install or tools".

python


print(vrp(g, nv, capa, method='ortools'))

Ergebnis


[[(0, 1), (1, 4), (4, 0)], [(0, 2), (2, 5), (5, 3), (3, 0)]]

Daten

Recommended Posts

Kombinationsoptimierung - Typisches Problem - Problem mit der Transportroute (Lieferoptimierung)
Kombinationsoptimierung - typisches Problem - Problem der chinesischen Postzustellung
Kombinationsoptimierung - typisches Problem-Rucksack-Problem
Kombinationsoptimierung - typisches Problem - n-dimensionales Packungsproblem
Kombinationsoptimierungstypisches Problem-Minimum-Vertex-Covering-Problem
Kombinationsoptimierung - typisches problemstabiles Matching-Problem
Kombinationsoptimierungstypisches Problem-verallgemeinertes Zuordnungsproblem
Kombinationsoptimierung - typisches Problem beim Packen von Problembehältern
Kombinationsoptimierung - typisches Problem - Maximum-Matching-Problem
Kombinationsoptimierung - typisches Problem - sekundäres Zuordnungsproblem
Problem mit der Codeiq-Milchlieferroute
Kombinationsoptimierung - typisches Problem - Problem mit dem kürzesten Weg
Kombinationsoptimierung - typisches Problem - Kombinationsauktionsproblem
Kombinationsoptimierung - typisches Problem - Maximum-Flow-Problem
Kombinationsoptimierungstypisches Problem-Aggregat-Abdeckungsproblem
Kombinationsoptimierung - typisches Problem-Gewichtsanpassungsproblem
Kombinationsoptimierung - typisches Problem bei der Platzierung von Problemeinrichtungen
Kombinationsoptimierung - typisches Problem-Job-Shop-Problem
Kombinationsoptimierung - typisches Problem - maximales Schnittproblem
Kombinationsoptimierung - typisches Problem - Rundschreiben Verkäufer Problem
Kombinationsoptimierung - typisches Problem bei der Planung der Problemarbeit
Kombinationsoptimierung - typisches Problem - Minimum des Gesamtflächenbaumproblems
Kombinationsoptimierungstypisches Problem-Maximum-Stabil-Set-Problem
Kombinationsoptimierung - typisches Problem - Mindestkostenflussproblem
Kombinationsoptimierung - typisches Problem-Set-Split-Problem
Lösen des N Queen-Problems mit kontinuierlicher / kombinierter Optimierung
Lösen des N Queen-Problems mit Kombinationsoptimierung
Verwenden Sie die Kombinationsoptimierung
Kombinationsoptimierung - Typisches Problem - Problem bei der Platzierung der Einrichtung ohne Kapazitätsbeschränkung
Gruppierung nach Kombinationsoptimierung
Kombinationsoptimierung - Minimum Cut Problem