Solving school district organization problems with combinatorial optimization

what is this

Seminar Gurobi Optimizer Solution Seminar 2016 of Optimization held on 12/2 event / 20161021.html), I heard that the school district can be solved as a wide variety minimum cost flow problem, so I actually did it. I tried it.

-Visualization of data by prefecture Use the library japanmap. ――Suppose there is one student in each prefecture, targeting 34 prefectures in Honshu. --There are schools in Aomori, Yamanashi, and Yamaguchi, and the capacity is 7, 21, and 6, respectively. ――The travel time to the neighboring prefecture is 1. —— Each student will attend one of the three schools and will be asked to allocate a school district that will minimize the total travel time for all students.

Way of thinking

--34 Create demand points for prefectures. --The demand for Aomori, Yamanashi, and Yamaguchi is 6, 20, 5, respectively (excluding yourself), and -1 for others. ――Think of three Japans (green Japan, blue Japan, and red Japan) represented by Aomori, Yamanashi, and Yamaguchi, and make them adjacent to each other. (Multi-product network) ――Link to the same prefecture in Japan from the demand points other than the representative points. ――Link to the demand point of the representative point from the same prefecture in each Japan represented by the representative point.

Solve the minimum cost flow problem on this network.

Try it with Python

python3

import numpy as np, networkx as nx
from japanmap import adjacent, pref_code, pref_map
Honshu= np.arange(2,36)
Representative point= {pref_code('Aomori'):7, pref_code('Yamanashi'):21, pref_code('Yamaguchi'):6}
#Graph creation
g = nx.DiGraph()
g.add_nodes_from(Honshu, demand=-1)
for i,d in representative point.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)for j in Honshu if j not in representative points)
    g.add_edges_from(((nwl+j,nwl+k)for j in Honshu for k in adjacent(j)), weight=1)
r = nx.min_cost_flow(g)
#Result display
dc = dict(zip(Representative point,['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)

I solved it as I expected.

development

In reality, there are many factors that need to be considered.

――It is desirable to have the same school district as before. ――I definitely want to divide it in a specific place. --Make the distance, not the number of hops. --The numbers in the group are not perfect.

It seems that it can be done by fixing the formulation.

that's all