[PYTHON] Lösen von Problemen bei der Organisation von Schulbezirken durch Kombinationsoptimierung

Was ist das

Seminar Gurobi Optimizer Solution Seminar 2016 von Optimierung am 02.12 event / 20161021.html) habe ich gehört, dass der Schulbezirk als eine Vielzahl von Problemen gelöst werden kann Problem mit dem minimalen Kostenfluss, also habe ich es tatsächlich getan. Ich versuchte es.

• Visualisierung von Daten nach Präfektur Verwenden Sie die Bibliothek japanmap. ―― Angenommen, in jeder Präfektur gibt es einen Studenten, der 34 Präfekturen in Honshu anspricht.
• Es gibt Schulen in Aomori, Yamanashi und Yamaguchi, und die Kapazität beträgt 7, 21 bzw. 6. ――Die Reisezeit in die benachbarte Präfektur beträgt 1.
• Jeder Schüler besucht eine der drei Schulen und wird gebeten, einen Schulbezirk zuzuweisen, der die Gesamtreisezeit für alle Schüler minimiert.

Denkweise

――34 Erstellen Sie Bedarfspunkte für Präfekturen.

• Die Nachfrage nach Aomori, Yamanashi und Yamaguchi beträgt 6, 20, 5 (ohne Sie selbst) und -1 für andere. ――Denken Sie an drei Japaner (grünes Japan, blaues Japan und rotes Japan), die von Aomori, Yamanashi und Yamaguchi vertreten werden, und machen Sie sie nebeneinander. (Netzwerk mit mehreren Produkten) ――Verbindung zur anderen Präfektur in Japan von anderen Nachfragepunkten als den repräsentativen Punkten. ――Verbindung zum Nachfragepunkt des Repräsentantenpunkts aus derselben Präfektur in jedem durch den Repräsentantenpunkt vertretenen Japan.

Lösen Sie das Problem des minimalen Kostenflusses in diesem Netzwerk.

Versuchen Sie es mit Python

python3

import numpy as np, networkx as nx
from japanmap import adjacent, pref_code, pref_map
Honshu= np.arange(2,36)
Repräsentativer Punkt= {pref_code('Aomori'):7, pref_code('Yamanashi'):21, pref_code('Yamaguchi'):6}
#Diagrammerstellung
g = nx.DiGraph()
g.add_nodes_from(Honshu, demand=-1)
for i,d im repräsentativen Punkt.items():
    nwl = i*100
    g.node[i]['demand'] = d-1
    g.add_nodes_from(nwl+Honshu, demand=0)
    g.add_edge(nwl+i,i)
    g.add_edges_from((j,nwl+j)für j in Honshu, wenn j nicht in repräsentativen Punkten)
    g.add_edges_from(((nwl+j,nwl+k)für j in Honshu für k im angrenzenden(j)), weight=1)
r = nx.min_cost_flow(g)
#Ergebnisanzeige
dc = dict(zip(Repräsentativer Punkt,['red','green','blue']))
dc.update({i:dc[j//100]for i, t in r.items() for j, v in t.items() if v and i < 100})
pref_map(Honshu, cols=[dc[i] for i in Honshu], width=4)

Ich habe es wie erwartet gelöst.

Entwicklung

In der Realität müssen viele Faktoren berücksichtigt werden.

――Es ist wünschenswert, den gleichen Schulbezirk wie zuvor zu haben. ――Ich möchte es definitiv an einem bestimmten Ort aufteilen. --Stellen Sie die Entfernung ein, nicht die Anzahl der Sprünge.

• Die Zahlen in der Gruppe sind nicht perfekt.

Es scheint, dass dies durch Fixieren der Formulierung erreicht werden kann.

das ist alles