Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons

Qu'est-ce que c'est

Séminaire Gurobi Optimizer Solution Seminar 2016 de Optimization tenu le 12/2 event / 20161021.html), j'ai entendu dire que le district scolaire peut être résolu comme une grande variété problème de flux de coût minimum, alors je l'ai fait. Je l'ai essayé.

• Visualisation des données par préfecture Utilisez la bibliothèque japanmap. ―― Supposons que vous ayez 34 préfectures à Honshu et qu'il y ait un étudiant dans chaque préfecture.
• Il y a des écoles à Aomori, Yamanashi et Yamaguchi, et la capacité est respectivement de 7, 21 et 6. ――Le temps de trajet vers la préfecture voisine est de 1.
• Chaque élève fréquentera l'une des trois écoles et sera invité à attribuer un district scolaire qui minimisera le temps de trajet total pour tous les élèves.

Façon de penser

――34 Créer des points de demande pour les préfectures. ―― La demande pour Aomori, Yamanashi et Yamaguchi est de 6, 20, 5 (à l'exclusion de vous-même) et -1 pour les autres. ―― Pensez à trois Japonais (Japon vert, Japon bleu et Japon rouge) représentés par Aomori, Yamanashi et Yamaguchi, et rendez-les adjacents les uns aux autres. (Réseau multi-produits) ―― Lien vers la même préfecture au Japon à partir des points de demande autres que les points représentatifs. ―― Lien vers le point de demande du point représentatif de la même préfecture de chaque Japon représenté par le point représentatif.

Résolvez le problème de flux de coût minimum sur ce réseau.

Essayez-le avec Python

python3

import numpy as np, networkx as nx
from japanmap import adjacent, pref_code, pref_map
Honshu= np.arange(2,36)
Point représentatif= {pref_code('Aomori'):7, pref_code('Yamanashi'):21, pref_code('Yamaguchi'):6}
#Création de graphes
g = nx.DiGraph()
g.add_nodes_from(Honshu, demand=-1)
for i,d en point représentatif.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)pour j dans Honshu si j pas en points représentatifs)
    g.add_edges_from(((nwl+j,nwl+k)pour j dans Honshu pour k dans adjacent(j)), weight=1)
r = nx.min_cost_flow(g)
#Affichage des résultats
dc = dict(zip(Point représentatif,['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)

Je l'ai résolu comme je m'y attendais.

développement

En réalité, de nombreux facteurs doivent être pris en compte.

――Il est souhaitable d'avoir le même district scolaire qu'auparavant. «Je veux vraiment le diviser dans un endroit précis. --Faites la distance, pas le nombre de sauts.

• Les chiffres du groupe ne sont pas parfaits.

Il semble que cela puisse être fait en fixant la formulation.

c'est tout