# Google Colab の場合は2行目のコメントを外して実行: ライブラリインストール(1回だけ)
# !pip install pulp matplotlib networkx

import pulp
import matplotlib.pyplot as plt
import networkx as nx

# 経路データ: N[j-1] が経路j の通過ノード列、f[j-1] が経路j の交通量 [人/日]
N = [[1, 2], [2, 3], [3, 4], [4, 5], [2, 4]]
f = [120, 150, 80, 100, 60]

I = sorted(set(sum(N, [])))     # 経路上に現れるノードの集合
J = list(range(1, len(N) + 1))  # 経路の番号
p = 2                           # 設置する施設数

print(f'ノード集合 I = {I}')
print(f'経路数: {len(J)}, 設置数 p = {p}')

ノード集合 I = [1, 2, 3, 4, 5]
経路数: 5, 設置数 p = 2

# 最大化問題として宣言
prob = pulp.LpProblem('FCLM_example', pulp.LpMaximize)

# 変数
x = pulp.LpVariable.dicts('x', I, cat='Binary')  # ノードへの施設設置
y = pulp.LpVariable.dicts('y', J, cat='Binary')  # 経路の捕捉

# 目的関数: 捕捉した交通量の合計
prob += pulp.lpSum(f[j - 1] * y[j] for j in J)

# 制約1: 捕捉の判定(経路j の通過ノードに施設がなければ y_j = 0)
for j in J:
    prob += pulp.lpSum(x[i] for i in N[j - 1]) >= y[j]

# 制約2: 施設数の指定
prob += pulp.lpSum(x[i] for i in I) == p

print(prob)

FCLM_example:
MAXIMIZE
120*y_1 + 150*y_2 + 80*y_3 + 100*y_4 + 60*y_5 + 0.0
SUBJECT TO
_C1: x_1 + x_2 - y_1 >= 0

_C2: x_2 + x_3 - y_2 >= 0

_C3: x_3 + x_4 - y_3 >= 0

_C4: x_4 + x_5 - y_4 >= 0

_C5: x_2 + x_4 - y_5 >= 0

_C6: x_1 + x_2 + x_3 + x_4 + x_5 = 2

VARIABLES
0 <= x_1 <= 1 Integer
0 <= x_2 <= 1 Integer
0 <= x_3 <= 1 Integer
0 <= x_4 <= 1 Integer
0 <= x_5 <= 1 Integer
0 <= y_1 <= 1 Integer
0 <= y_2 <= 1 Integer
0 <= y_3 <= 1 Integer
0 <= y_4 <= 1 Integer
0 <= y_5 <= 1 Integer

prob.solve(pulp.PULP_CBC_CMD(msg=0))
print('求解結果:', pulp.LpStatus[prob.status])
print('捕捉交通量の最大値:', int(pulp.value(prob.objective)), '[人/日]')
print('設置ノード:', [i for i in I if x[i].value() == 1])
print('捕捉された経路:', [j for j in J if y[j].value() == 1])

求解結果: Optimal
捕捉交通量の最大値: 510 [人/日]
設置ノード: [2, 4]
捕捉された経路: [1, 2, 3, 4, 5]

# ネットワークと解の可視化(この例では各経路が1本の辺に対応する)
G = nx.Graph()
for Nj in N:
    G.add_edge(Nj[0], Nj[-1])
pos = {1: (0, 0), 2: (1, 0), 3: (2, 0.6), 4: (3, 0), 5: (4, 0)}

captured = [j for j in J if y[j].value() == 1]
chosen = [i for i in I if x[i].value() == 1]

plt.figure(figsize=(8, 3))
for j in J:
    u, v = N[j - 1][0], N[j - 1][-1]
    color = 'red' if j in captured else 'lightgray'
    nx.draw_networkx_edges(G, pos, edgelist=[(u, v)], edge_color=color, width=2.5)
nx.draw_networkx_edge_labels(
    G, pos, edge_labels={(N[j - 1][0], N[j - 1][-1]): f[j - 1] for j in J}, font_size=9)
nx.draw_networkx_nodes(G, pos, node_size=320, node_color='white', edgecolors='black')
nx.draw_networkx_nodes(G, pos, nodelist=chosen, node_size=320, node_color='red',
                       edgecolors='black')
nx.draw_networkx_labels(G, pos, font_size=10)
plt.axis('off')
plt.tight_layout()
plt.show()

def solve_fclm(N, f, p):
    I = sorted(set(sum(N, [])))
    J = list(range(1, len(N) + 1))
    prob = pulp.LpProblem('FCLM', pulp.LpMaximize)
    x = pulp.LpVariable.dicts('x', I, cat='Binary')
    y = pulp.LpVariable.dicts('y', J, cat='Binary')
    prob += pulp.lpSum(f[j - 1] * y[j] for j in J)
    for j in J:
        prob += pulp.lpSum(x[i] for i in N[j - 1]) >= y[j]
    prob += pulp.lpSum(x[i] for i in I) == p
    prob.solve(pulp.PULP_CBC_CMD(msg=0))
    return int(pulp.value(prob.objective)), [i for i in I if x[i].value() == 1]

for p_test in [1, 2, 3]:
    z, chosen = solve_fclm(N, f, p_test)
    print(f'p = {p_test}: 捕捉交通量 = {z} [人/日], 設置ノード = {chosen}')

p = 1: 捕捉交通量 = 330 [人/日], 設置ノード = [2]
p = 2: 捕捉交通量 = 510 [人/日], 設置ノード = [2, 4]
p = 3: 捕捉交通量 = 510 [人/日], 設置ノード = [1, 2, 4]

import numpy as np

# 道路網の読み込み(描画用。road_network.ipynb と同じ手順)
edgs = np.loadtxt('../road-network/links_ud.csv', delimiter=',')
G = nx.Graph()
G.add_weighted_edges_from([(int(e[0]), int(e[1]), e[2]) for e in edgs])
pos = {}
for e in edgs:
    pos[int(e[0])] = [e[3], e[4]]
    pos[int(e[1])] = [e[5], e[6]]

# 経路データの読み込み
N = []
with open('../road-network/N.csv', 'r') as fp:
    for row in fp.readlines():
        N.append([int(v) for v in row.strip().split(',') if len(v) > 0])
f = [int(v) for v in np.loadtxt('../road-network/f.csv')]

I = sorted(set(sum(N, [])))
J = list(range(1, len(N) + 1))
print(f'経路数: {len(J)}, ノード数 |I| = {len(I)}')
for j in J:
    print(f'経路{j}: f_{j} = {f[j - 1]}, N_{j} = {N[j - 1]}')

経路数: 7, ノード数 |I| = 26
経路1: f_1 = 120, N_1 = [1, 2, 3, 4, 5, 6]
経路2: f_2 = 100, N_2 = [25, 26, 27, 28, 29, 30]
経路3: f_3 = 90, N_3 = [1, 7, 8, 14, 20, 26, 25]
経路4: f_4 = 80, N_4 = [6, 12, 18, 24, 30]
経路5: f_5 = 150, N_5 = [3, 9, 15, 21, 27]
経路6: f_6 = 60, N_6 = [13, 14, 15, 16, 17, 18]
経路7: f_7 = 70, N_7 = [11, 12, 18, 24]

z2, chosen2 = solve_fclm(N, f, 2)
print('p = 2 の最大捕捉交通量:', z2, '[人/日]')
print('設置ノード:', chosen2)

p = 2 の最大捕捉交通量: 480 [人/日]
設置ノード: [3, 18]

from itertools import combinations

def captured_value(open_nodes):
    return sum(fj for Nj, fj in zip(N, f) if set(Nj) & set(open_nodes))

best = max(captured_value(cb) for cb in combinations(I, 2))
print('全列挙による p = 2 の最大捕捉交通量:', best)
print('数理モデルの解と一致:', best == z2)

全列挙による p = 2 の最大捕捉交通量: 480
数理モデルの解と一致: True

# 可視化: 赤い実線 = 捕捉された経路、青い破線 = 捕捉されない経路
captured = [j for j in J if set(N[j - 1]) & set(chosen2)]

plt.figure(figsize=(8, 6))
nx.draw_networkx_edges(G, pos, edge_color='lightgray')
for j in J:
    if j not in captured:
        nx.draw_networkx_edges(G, pos, edgelist=list(zip(N[j - 1][:-1], N[j - 1][1:])),
                               edge_color='steelblue', style='dashed', width=2)
for j in J:
    if j in captured:
        nx.draw_networkx_edges(G, pos, edgelist=list(zip(N[j - 1][:-1], N[j - 1][1:])),
                               edge_color='red', width=2)
nx.draw_networkx_nodes(G, pos, node_size=170, node_color='white', edgecolors='gray')
nx.draw_networkx_nodes(G, pos, nodelist=chosen2, node_size=300, node_color='red',
                       edgecolors='black')
nx.draw_networkx_labels(G, pos, font_size=7)
plt.axis('equal')
plt.axis('off')
plt.tight_layout()
plt.show()

for p_test in [1, 2, 3]:
    z, chosen = solve_fclm(N, f, p_test)
    print(f'p = {p_test}: 捕捉交通量 = {z} [人/日], 設置ノード = {chosen}')

p = 1: 捕捉交通量 = 270 [人/日], 設置ノード = [3]
p = 2: 捕捉交通量 = 480 [人/日], 設置ノード = [3, 18]
p = 3: 捕捉交通量 = 670 [人/日], 設置ノード = [1, 18, 27]

名前	説明
$I$	ノードの集合(経路上に現れるノード全体、この例では1〜5)
$J$	経路の集合(この例では5本)
$N_j$	経路 $j$ が通過するノードの集合
$f_j$	経路 $j$ の交通量
$p$	設置する施設数(この例では2)
$x_i$	ノード $i$ に施設を設置するなら1、そうでなければ0
$y_j$	経路 $j$ が捕捉されるなら1、そうでなければ0

フロー捕捉型施設配置問題(FCLM)入門¶

1. はじめに¶

2. 前提知識と学習目標¶

学習目標¶

3. 問題設定と定式化¶

3.1 問題の具体例¶

3.2 数学的な定式化¶

3.2.1 定数および決定変数の定義¶

3.2.2 数理モデル¶

3.2.3 目的関数の意味¶

3.2.4 制約条件の意味¶

4. Python + PuLP による実装¶

4.1 準備¶

4.2 モデル構築¶

4.3 求解および結果の解釈¶

4.4 可視化¶

4.5 感度分析: 施設数を変える¶

5. 道路ネットワークへの適用¶

6. 発展: 実データへの適用と研究紹介¶

7. 参考文献¶

8. 注意事項¶

9. 卒業研究概要への手引き¶

1章はじめに(文章量の比率: 15%)¶

2章 FCLM(文章量の比率: 30%)¶

3章実験(文章量の比率: 40%)¶

3.1節概要¶

3.2節結果と考察¶

4章おわりに(文章量の比率: 15%)¶

参考文献¶

経路 $j$	通過ノード $N_j$	交通量 $f_j$ [人/日]
1	1, 2	120
2	2, 3	150
3	3, 4	80
4	4, 5	100
5	2, 4	60

フロー捕捉型施設配置問題(FCLM)入門¶

1. はじめに¶

2. 前提知識と学習目標¶

学習目標¶

3. 問題設定と定式化¶

3.1 問題の具体例¶

3.2 数学的な定式化¶

3.2.1 定数および決定変数の定義¶

3.2.2 数理モデル¶

3.2.3 目的関数の意味¶

3.2.4 制約条件の意味¶

4. Python + PuLP による実装¶

4.1 準備¶

4.2 モデル構築¶

4.3 求解および結果の解釈¶

4.4 可視化¶

4.5 感度分析: 施設数を変える¶

5. 道路ネットワークへの適用¶

6. 発展: 実データへの適用と研究紹介¶

7. 参考文献¶

8. 注意事項¶

9. 卒業研究概要への手引き¶

1章 はじめに(文章量の比率: 15%)¶

2章 FCLM(文章量の比率: 30%)¶

3章 実験(文章量の比率: 40%)¶

3.1節 概要¶

3.2節 結果と考察¶

4章 おわりに(文章量の比率: 15%)¶

参考文献¶

1章はじめに(文章量の比率: 15%)¶

3章実験(文章量の比率: 40%)¶

3.1節概要¶

3.2節結果と考察¶

4章おわりに(文章量の比率: 15%)¶