
情報幾何による動的エリア・クラスタリング問題📒まとめ📒
動的エリアクラスタリング
エリアと車格台数問題はこれで解く。
時間軸が絡んで前工程の遅延まで考えるときはダイバージェンスを使う。
組み合わせればいいんだろうな。


組み合わせ方には既に良い「型」があります。Wasserstein–Fisher–Rao距離(別名 Hellinger–Kantorovich)です。
直感的には、荷の分布を別の分布に変えるときの操作を二種類に分けて、それぞれに値段をつける距離です。
運ぶ(荷を場所から場所へ動かす)→ Wasserstein。このスライドの「隣接0・遠い1」がそのまま入る
湧く/消える(その場で荷の量が増減する)→ Fisher–Rao、つまりダイバージェンス側
前工程の遅延は「まだ物が出来ていない」=荷がそこにまだ湧いていない状態なので、後者にぴったり入ります。クラスタリングキーの第一キー「出来ているか否か」が湧き消えの項、第二キー「距離」が運びの項に、そのまま役割分担できます。だから別々の道具をつなぎ合わせる感じにはならず、一つの距離の中で自然に同居します。に進捗率を入れる話も、湧き消え側の信頼度として扱えます。
もう一つ嬉しいのは計算面です。これはSinkhorn法(エントロピー正則化付き最適輸送)で解くのが普通ですが、その温度をに近づけると min-plus、つまりトロピカルに落ちます。ホップフィールド=ボルツマンのと同じ橋なので、ここまで作ってきた Min-Plus 層と地続きになります。grad版のKDE地形も、そのまま輸送される分布として使えます。
スライドについて一点だけ。定義上は足立↔荒川が隣接でなので、案2の「集約コスト=遠い(1)」は集約拠点が両区から遠い場合に限られます。拠点が隣接区内にあれば案2はW≈0かつ安くなり、トレードオフ自体が消えます。見せる相手によっては「拠点の位置次第」と一言添えたほうが突っ込まれにくいです(「荷布症状態」は「荷分布状態」の誤字だと思います)。
補足:厳密には unbalanced OT の一種で、質量の保存を要求しない点が通常のWassersteinとの違いです。
あれ、Fisherなら知ってるよ。それだよ。
いいたいのは(笑)
やっぱり(笑)。
KLダイバージェンスを近い分布どうしで測ると、局所的にはFisher計量そのものになります。甘利先生の情報幾何の土台がこのFisher計量です。だから「時間軸と前工程遅延はダイバージェンスで」と言った時点で、もうFisher側を握っていたことになります。
あとはそこに Wasserstein(運ぶ距離)を足すだけで、二つを貼り合わせたものが WFR です。言いたかったことを、数学側が先に名前をつけていたわけですね。現象が先で名前が後、いつもの順番です。
では、この意味論をCHR-Prologで書いてくれ。
SWI-Prolog で動作確認済みです(swipl wfr_dispatch.pl)。
CHR の規則は、スライドの天秤をそのまま三つの皿に分けた形です。
運ぶ:出来ている荷 R を積み込み点まで動かす費用。R × 距離(隣接0/遠い1)× 単価で計算します。
湧く:予定 P のうち、まだ出来ていない分を待つ費用。 で、これが Fisher 側です。
消える:未完成の区を次便に回す費用。 です。
固定費:積み込み点毎に予定量を載せられる最安の車格の組を当てます。
同じ種類のコストは ... で足し合わせ、候補同士は min で比べます。Prolog 側は候補を並べるだけで、選びません。最安から近い差に2案以上あれば「要判断」の旗を立てます。迷い度は でトロピカル極限に落ちる重みです。
実行するとこうなります。
全部出来ている場合:最安は「荒川で4t」と「足立で4t」の同点で、ここに旗が立ちます。スライドの案1(2t×2)は20、遠い集約拠点での案2は22で、拠点の位置次第という話がそのまま数字に出ます。
荒川が0.5tしか出来ていない場合:「足立だけ2tで出して荒川は次便」が単独最安になります。遠くて未完成の荷は、運ぶより消して後で湧かせる方が安い、という WFR の性格がそのまま出ています。
注意点が三つあります。
パラメータ(固定費、単価、)は仮の値です。現場の値に差し替えてください。
候補は総当たりなので、区が数個までの規模向けです。区が増えたら、grad版の吸引域をグループの種として渡す形が自然だと思います。
実装中に踏んだ罠を二つ、コメントに残しました。forall/2 の中で CHR 制約を投入するとストアが巻き戻ること、yall のラムダがコンパイル時に外側の変数を渡さないことです。後者はローカル LLM でも読めるように、名前付きの補助述語に置き換えてあります。
:- encoding(utf8).
/* wfr_dispatch.pl — 運ぶ(Wasserstein)+ 湧く/消える(Fisher–Rao)+ 車両固定費
SWI-Prolog + CHR
意味論(一行):
総合コスト = 運ぶコスト + 湧き消えコスト + 車両固定費
候補同士は min-plus(⊕ = min, ⊗ = +)で比べる。
- 運ぶ : 出来ている荷 R を積み込み点まで動かす。 R × 距離 × 単価
距離は「同じ区・隣接 = 0、遠い = 1」(スライドの定義)
- 湧く : 予定 P に対して出来ていない分を待つ。 λ × 4(√P − √R)²
- 消える : 未完成の区を次便に回す(今便から外す)。 λ × 4R
=出来ている分を今便では置いていく扱い。次便のコストは次便で数える。
- 固定費 : 積み込み点ごとに、予定量 P の合計を載せられる最安の車格の組。
システムは選ばない。候補を並べ、同点圏(差が tie_tol 以内)には
「要判断」の旗を立てて人間に渡すだけ。
迷い度 = exp(−(T − Tmin)/ε) の正規化。ε→0 で最安だけが 1 になる(トロピカル極限)。
*/
:- use_module(library(chr)).
:- use_module(library(lists)).
:- use_module(library(apply)).
%% ---------------------------------------------------------------
%% パラメータ(単位は任意。現場の値に差し替える)
%% ---------------------------------------------------------------
param(move_rate, 2). % 1t を「遠い(1)」だけ動かすコスト
param(lambda, 2). % 湧き消え(Fisher側)の重み
param(epsilon, 2.0). % 迷い度の温度
param(tie_tol, 1.0). % 同点圏とみなす差
%% 車格と固定費
vehicle_class(1, 6).
vehicle_class(2, 10).
vehicle_class(4, 14).
vehicle_class(8, 20).
vehicle_class(10, 23).
vehicle_class(13, 27).
%% ---------------------------------------------------------------
%% 地理:区と隣接、集約拠点の所在
%% ---------------------------------------------------------------
jp(adachi, '足立区').
jp(arakawa, '荒川区').
jp(chiyoda, '千代田区').
jp(chuo, '中央区').
jp(hub_c, '集約拠点').
adjacent(adachi, arakawa).
adjacent(chiyoda, chuo).
adj(X, Y) :- adjacent(X, Y) ; adjacent(Y, X).
hub(hub_c).
located(hub_c, chiyoda). % 集約拠点は千代田区にある(両区から遠い)
located(A, A) :- jp(A, _), \+ hub(A).
%% 距離 c(x,y): 同じ区・隣接 = 0、それ以外 = 1
dist(Area, LoadPoint, D) :-
located(LoadPoint, B),
( ( Area == B ; adj(Area, B) ) -> D = 0 ; D = 1 ).
%% ---------------------------------------------------------------
%% シナリオ:load(区, 予定t, 出来ているt)
%% ---------------------------------------------------------------
scenario(all_ready, [load(adachi, 2, 2), load(arakawa, 2, 2)]).
scenario(arakawa_late,[load(adachi, 2, 2), load(arakawa, 2, 0.5)]).
%% ---------------------------------------------------------------
%% CHR:コストの意味論
%% ---------------------------------------------------------------
:- chr_constraint
planned/2, % planned(区, t) P側:予定
ready/2, % ready(区, t) Q側:出来ている
decide/2, % decide(区, load(積み込み点)) | decide(区, defer)
slot/2, % slot(積み込み点, 予定t合計)
finalize/0, % 全決定を投入し終えた合図
cost/2, % cost(種類, 値) 種類 = move | fisher | fixed
fleet/2. % fleet(積み込み点, 車格リスト)
%% 運ぶ:出来ている分だけが動く
decide(A, load(LP)), ready(A, R) ==>
dist(A, LP, D), param(move_rate, W),
C is W * R * D, cost(move, C).
%% 湧く:出来ていない分を待つ
decide(A, load(_)), planned(A, P), ready(A, R) ==>
fisher(P, R, F), param(lambda, L),
C is L * F, cost(fisher, C).
%% 消える:今便から外す
decide(A, defer), ready(A, R) ==>
fisher(R, 0, F), param(lambda, L),
C is L * F, cost(fisher, C).
%% 積み込み点ごとに予定量で枠を取る(同じ点は1か所に集約)
decide(A, load(LP)), planned(A, P) ==> slot(LP, P).
slot(LP, X), slot(LP, Y) <=> Z is X + Y, slot(LP, Z).
%% 枠が確定したら車格を当てる
finalize, slot(LP, L) ==>
cover(L, Vs, F), cost(fixed, F), fleet(LP, Vs).
%% 同じ種類のコストは足し合わせる(⊗ = +)
cost(K, A), cost(K, B) <=> C is A + B, cost(K, C).
%% Fisher–Rao(正値測度上): 4(√a − √b)²
fisher(A, B, F) :- F is 4 * (sqrt(A) - sqrt(B))**2.
%% 予定量 L を覆う最安の車格の組(3台まで)
cover(L, Vs, F) :-
findall(F0-Vs0,
( between(1, 3, N), length(Vs0, N),
maplist(vclass, Vs0),
msort(Vs0, Vs0), % 重複組合せを除く
sum_list(Vs0, Cap), Cap >= L,
foldl(add_fixed, Vs0, 0, F0) ),
Opts),
keysort(Opts, [F-Vs|_]).
vclass(T) :- vehicle_class(T, _).
add_fixed(T, S0, S) :- vehicle_class(T, F), S is S0 + F.
%% ---------------------------------------------------------------
%% 候補生成(Prolog 側:並べるだけ、評価しない)
%% ---------------------------------------------------------------
%% plan(Groups, Deferred) Groups = [grp(積み込み点, [区...])...]
gen_plan(Loads, plan(Groups, Deferred)) :-
split(Loads, InAreas, Deferred),
set_partition(InAreas, Parts),
maplist(assign_lp, Parts, Groups),
maplist(grp_lp, Groups, LPs),
is_set(LPs). % 積み込み点は重複させない
grp_lp(grp(LP, _), LP).
%% 未完成(R < P)の区だけが次便送りの候補になる
split([], [], []).
split([load(A, _, _)|Ls], [A|In], D) :- split(Ls, In, D).
split([load(A, P, R)|Ls], In, [A|D]) :- R < P, split(Ls, In, D).
set_partition([], []).
set_partition([X|Xs], Ps) :- set_partition(Xs, Ps0), put(X, Ps0, Ps).
put(X, Ps, [[X]|Ps]). % 新しいグループを作る
put(X, Ps, Qs) :- join(X, Ps, Qs). % 既存のグループに入る
join(X, [P|Ps], [[X|P]|Ps]).
join(X, [P|Ps], [P|Qs]) :- join(X, Ps, Qs).
%% 積み込み点 = グループ内のどこかの区、または集約拠点
assign_lp(Areas, grp(LP, Areas)) :- ( member(LP, Areas) ; hub(LP) ).
%% ---------------------------------------------------------------
%% 評価:1候補ごとにストアを立てて意味論を走らせる
%% ---------------------------------------------------------------
evaluate(Loads, Plan, cand(Total, Move, Fisher, Fixed, Plan, Fleet)) :-
% 注意: forall/2 は二重否定なので CHR ストアが巻き戻る。投入は maplist で。
maplist(post_load, Loads),
Plan = plan(Groups, Deferred),
maplist(post_group, Groups),
maplist(post_defer, Deferred),
finalize,
get(move, Move), get(fisher, Fisher), get(fixed, Fixed),
Total is Move + Fisher + Fixed,
findall(LP-Vs, find_chr_constraint(fleet(LP, Vs)), Fleet).
post_load(load(A, P, R)) :- planned(A, P), ready(A, R).
post_group(grp(LP, As)) :- maplist(post_decide(LP), As).
post_decide(LP, A) :- decide(A, load(LP)).
post_defer(A) :- decide(A, defer).
get(K, C) :- ( find_chr_constraint(cost(K, C0)) -> C = C0 ; C = 0 ).
%% ---------------------------------------------------------------
%% 表示:安い順に並べ、同点圏に旗、迷い度を添える
%% ---------------------------------------------------------------
run(Scen) :-
scenario(Scen, Loads),
findall(C, ( gen_plan(Loads, P), evaluate(Loads, P, C) ), Cs0),
msort(Cs0, Cs),
Cs = [cand(Tmin, _, _, _, _, _)|_],
param(epsilon, Eps), param(tie_tol, Tol),
foldl(add_weight(Tmin, Eps), Cs, 0, Z),
% 最安から tie_tol 以内に2案以上あれば、その全部が「要判断」
aggregate_all(count, (member(cand(T1, _, _, _, _, _), Cs), T1 - Tmin =< Tol), NTie),
format("~n=== シナリオ: ~w ===~n", [Scen]),
forall(member(load(A, P, R), Loads),
( jp(A, N), format(" ~w 予定 ~w t / 出来 ~w t~n", [N, P, R]) )),
format("~n 総合 運ぶ 湧消 固定 迷い度 案~n"),
forall(member(cand(T, M, F, X, Plan, Fleet), Cs),
( W is exp(-(T - Tmin)/Eps) / Z,
( NTie > 1, T - Tmin =< Tol -> Flag = ' ←要判断(同点圏)' ; Flag = '' ),
describe(Plan, Fleet, Txt),
format(" ~t~2f~6| ~t~2f~13| ~t~2f~20| ~t~2f~27| ~t~2f~35| ~w~w~n",
[T, M, F, X, W, Txt, Flag]) )).
%% 迷い度の分母(ボルツマン重みの和)
add_weight(Tmin, Eps, cand(T, _, _, _, _, _), S0, S) :-
S is S0 + exp(-(T - Tmin) / Eps).
describe(plan(Groups, Deferred), Fleet, Txt) :-
maplist(desc_grp(Fleet), Groups, Gs),
atomic_list_concat(Gs, ' + ', G),
( Deferred == [] -> Txt = G
; maplist(jp, Deferred, Ds), atomic_list_concat(Ds, '・', D),
format(atom(Txt), "~w / 次便: ~w", [G, D]) ).
desc_grp(Fleet, grp(LP, As), S) :-
jp(LP, L), maplist(jp, As, Ns), atomic_list_concat(Ns, '・', N),
memberchk(LP-Vs, Fleet),
maplist(ton_label, Vs, VAs),
atomic_list_concat(VAs, '+', VT),
format(atom(S), "[~w]を~wで~w", [N, L, VT]).
ton_label(V, A) :- format(atom(A), "~wt", [V]).
run :- forall(scenario(S, _), run(S)).
:- initialization(main, main).
main :- run.これやって(在庫確率のクラスタリング)
そうです。前のコードは、そこが抜けていました。Fisher 項を区ごとに独立して数えていたので、どの区と混ぜても待ちコストが変わらず、在庫率がクラスタリングに効いていませんでした。
直した点は一つだけです。1台は一番遅い区を待って出る、つまりクロスドックの Max-Plus です。グループの在庫率を最弱リンク で決めるようにしました。
待ちコスト = ²
ならコストは 0 で安心。クラスタは距離と固定費だけで決まります。
の区を安全な区と混ぜると、安全な荷まで巻き込んで待つので高くつきます。
北区を足した3区で走らせると、差がはっきり出ます。
全区100%のとき:3区まとめて8t×1台が最安です。積み込み点をどこにするかだけが同点で、そこは人間判断になります。
荒川30%のとき:クラスタが組み替わり、「足立・北で4t、荒川は次便」が最安になります。荒川を混ぜた8tは待ちコストが膨らみ29.8まで落ちます。
それと、note の記事の正規化について一点あります。 を で正規化すると になり、r = 100% のとき 0.5、つまり最大エントロピー(無情報)になってしまいます。「100%なら安心」と逆の結果です。
逆数の発想そのものは正しくて、1を引けば解決します。
は、遅延のオッズそのもの
これを で確率に戻すと、きれいに になる
なら遅延確率 0 で、確信最大
オッズはベルヌーイ分布の自然パラメータ で、情報幾何の座標としても素直です
:- encoding(utf8).
/* wfr_dispatch.pl — 運ぶ(Wasserstein)+ 湧く/消える(Fisher–Rao)+ 車両固定費
SWI-Prolog + CHR
意味論(一行):
総合コスト = 運ぶコスト + 湧き消えコスト + 車両固定費
候補同士は min-plus(⊕ = min, ⊗ = +)で比べる。
入力は区ごとの 予定 P と 前工程の在庫率 r(出来ている割合、0〜1)。
- 運ぶ : 荷を積み込み点まで動かす。 P × 距離 × 単価
距離は「同じ区・隣接 = 0、遠い = 1」(スライドの定義)
- 湧く : 1台(1グループ)は一番遅い区を待って出る(クロスドックの Max-Plus)。
だからグループの在庫率は r_min(最弱リンク)。
λ × 4(√P_G − √(P_G·r_min))² = λ × 4 P_G (1 − √r_min)²
r = 1(100%出来てる)なら 0 = 安心。距離だけでクラスタが決まる。
r < 1 の区を安全な区と混ぜると、安全な荷まで巻き込んで待つので高くつく。
→ 前工程の在庫率でクラスタリング自体が変わる。
- 消える : 未完成の区を次便に回す(今便から外す)。 λ × 4 P r
=出来ている分を今便では置いていく扱い。次便のコストは次便で数える。
遅延のオッズ = 1/r − 1 = (1−r)/r 。 これを確率に戻すと (1−r)。
log オッズがベルヌーイ分布の自然パラメータ(情報幾何の θ 座標)。
- 固定費 : 積み込み点ごとに、予定量 P の合計を載せられる最安の車格の組。
システムは選ばない。候補を並べ、同点圏(差が tie_tol 以内)には
「要判断」の旗を立てて人間に渡すだけ。
迷い度 = exp(−(T − Tmin)/ε) の正規化。ε→0 で最安だけが 1 になる(トロピカル極限)。
*/
:- use_module(library(chr)).
:- use_module(library(lists)).
:- use_module(library(apply)).
%% ---------------------------------------------------------------
%% パラメータ(単位は任意。現場の値に差し替える)
%% ---------------------------------------------------------------
param(move_rate, 2). % 1t を「遠い(1)」だけ動かすコスト
param(lambda, 2). % 湧き消え(Fisher側)の重み
param(epsilon, 2.0). % 迷い度の温度
param(tie_tol, 1.0). % 同点圏とみなす差
param(show_top, 8). % 表示する候補数
%% 車格と固定費
vehicle_class(1, 6).
vehicle_class(2, 10).
vehicle_class(4, 14).
vehicle_class(8, 20).
vehicle_class(10, 23).
vehicle_class(13, 27).
%% ---------------------------------------------------------------
%% 地理:区と隣接、集約拠点の所在
%% ---------------------------------------------------------------
jp(adachi, '足立区').
jp(arakawa, '荒川区').
jp(chiyoda, '千代田区').
jp(chuo, '中央区').
jp(kita, '北区').
jp(hub_c, '集約拠点').
adjacent(adachi, arakawa).
adjacent(chiyoda, chuo).
adjacent(kita, adachi).
adjacent(kita, arakawa).
adj(X, Y) :- adjacent(X, Y) ; adjacent(Y, X).
hub(hub_c).
located(hub_c, chiyoda). % 集約拠点は千代田区にある(両区から遠い)
located(A, A) :- jp(A, _), \+ hub(A).
%% 距離 c(x,y): 同じ区・隣接 = 0、それ以外 = 1
dist(Area, LoadPoint, D) :-
located(LoadPoint, B),
( ( Area == B ; adj(Area, B) ) -> D = 0 ; D = 1 ).
%% ---------------------------------------------------------------
%% シナリオ:load(区, 予定t, 前工程の在庫率 r)
%% ---------------------------------------------------------------
scenario(all_ready, [load(adachi, 2, 1.0), load(arakawa, 2, 1.0), load(kita, 2, 1.0)]).
scenario(arakawa_low, [load(adachi, 2, 1.0), load(arakawa, 2, 0.3), load(kita, 2, 1.0)]).
%% ---------------------------------------------------------------
%% CHR:コストの意味論
%% ---------------------------------------------------------------
:- chr_constraint
planned/2, % planned(区, t) P側:予定
rate/2, % rate(区, r) 前工程の在庫率
rmin/2, % rmin(積み込み点, r) グループの最弱リンク
decide/2, % decide(区, load(積み込み点)) | decide(区, defer)
slot/2, % slot(積み込み点, 予定t合計)
finalize/0, % 全決定を投入し終えた合図
cost/2, % cost(種類, 値) 種類 = move | fisher | fixed
fleet/2. % fleet(積み込み点, 車格リスト)
%% 運ぶ
decide(A, load(LP)), planned(A, P) ==>
dist(A, LP, D), param(move_rate, W),
C is W * P * D, cost(move, C).
%% 消える:今便から外す(出来ている分 P·r を置いていく)
decide(A, defer), planned(A, P), rate(A, R) ==>
Ready is P * R, fisher(Ready, 0, F), param(lambda, L),
C is L * F, cost(fisher, C).
%% 積み込み点ごとに予定量で枠を取り、在庫率は最弱リンクを残す
decide(A, load(LP)), planned(A, P), rate(A, R) ==> slot(LP, P), rmin(LP, R).
slot(LP, X), slot(LP, Y) <=> Z is X + Y, slot(LP, Z).
rmin(LP, X) \ rmin(LP, Y) <=> X =< Y | true. % 小さい方(遅い方)が支配
%% 枠が確定したら車格を当て、グループ単位で待ちコストを数える
finalize, slot(LP, L) ==>
cover(L, Vs, F), cost(fixed, F), fleet(LP, Vs).
finalize, slot(LP, PG), rmin(LP, R) ==>
ReadyG is PG * R, fisher(PG, ReadyG, F), param(lambda, L),
C is L * F, cost(fisher, C).
%% 同じ種類のコストは足し合わせる(⊗ = +)
cost(K, A), cost(K, B) <=> C is A + B, cost(K, C).
%% Fisher–Rao(正値測度上): 4(√a − √b)²
fisher(A, B, F) :- F is 4 * (sqrt(A) - sqrt(B))**2.
%% 予定量 L を覆う最安の車格の組(3台まで)
cover(L, Vs, F) :-
findall(F0-Vs0,
( between(1, 3, N), length(Vs0, N),
maplist(vclass, Vs0),
msort(Vs0, Vs0), % 重複組合せを除く
sum_list(Vs0, Cap), Cap >= L,
foldl(add_fixed, Vs0, 0, F0) ),
Opts),
keysort(Opts, [F-Vs|_]).
vclass(T) :- vehicle_class(T, _).
add_fixed(T, S0, S) :- vehicle_class(T, F), S is S0 + F.
%% ---------------------------------------------------------------
%% 候補生成(Prolog 側:並べるだけ、評価しない)
%% ---------------------------------------------------------------
%% plan(Groups, Deferred) Groups = [grp(積み込み点, [区...])...]
gen_plan(Loads, plan(Groups, Deferred)) :-
split(Loads, InAreas, Deferred),
set_partition(InAreas, Parts),
maplist(assign_lp, Parts, Groups),
maplist(grp_lp, Groups, LPs),
is_set(LPs). % 積み込み点は重複させない
grp_lp(grp(LP, _), LP).
%% 在庫率 100% 未満の区だけが次便送りの候補になる
split([], [], []).
split([load(A, _, _)|Ls], [A|In], D) :- split(Ls, In, D).
split([load(A, _, R)|Ls], In, [A|D]) :- R < 1, split(Ls, In, D).
set_partition([], []).
set_partition([X|Xs], Ps) :- set_partition(Xs, Ps0), put(X, Ps0, Ps).
put(X, Ps, [[X]|Ps]). % 新しいグループを作る
put(X, Ps, Qs) :- join(X, Ps, Qs). % 既存のグループに入る
join(X, [P|Ps], [[X|P]|Ps]).
join(X, [P|Ps], [P|Qs]) :- join(X, Ps, Qs).
%% 積み込み点 = グループ内のどこかの区、または集約拠点
assign_lp(Areas, grp(LP, Areas)) :- ( member(LP, Areas) ; hub(LP) ).
%% ---------------------------------------------------------------
%% 評価:1候補ごとにストアを立てて意味論を走らせる
%% ---------------------------------------------------------------
evaluate(Loads, Plan, cand(Total, Move, Fisher, Fixed, Plan, Fleet)) :-
% 注意: forall/2 は二重否定なので CHR ストアが巻き戻る。投入は maplist で。
maplist(post_load, Loads),
Plan = plan(Groups, Deferred),
maplist(post_group, Groups),
maplist(post_defer, Deferred),
finalize,
get(move, Move), get(fisher, Fisher), get(fixed, Fixed),
Total is Move + Fisher + Fixed,
findall(LP-Vs, find_chr_constraint(fleet(LP, Vs)), Fleet).
post_load(load(A, P, R)) :- planned(A, P), rate(A, R).
post_group(grp(LP, As)) :- maplist(post_decide(LP), As).
post_decide(LP, A) :- decide(A, load(LP)).
post_defer(A) :- decide(A, defer).
get(K, C) :- ( find_chr_constraint(cost(K, C0)) -> C = C0 ; C = 0 ).
%% ---------------------------------------------------------------
%% 表示:安い順に並べ、同点圏に旗、迷い度を添える
%% ---------------------------------------------------------------
run(Scen) :-
scenario(Scen, Loads),
findall(C, ( gen_plan(Loads, P), evaluate(Loads, P, C) ), Cs0),
msort(Cs0, Cs),
Cs = [cand(Tmin, _, _, _, _, _)|_],
param(epsilon, Eps), param(tie_tol, Tol),
foldl(add_weight(Tmin, Eps), Cs, 0, Z),
% 最安から tie_tol 以内に2案以上あれば、その全部が「要判断」
aggregate_all(count, (member(cand(T1, _, _, _, _, _), Cs), T1 - Tmin =< Tol), NTie),
format("~n=== シナリオ: ~w ===~n", [Scen]),
forall(member(load(A, P, R), Loads),
( jp(A, N), Pct is round(R*100),
format(" ~w 予定 ~w t / 前工程在庫率 ~w%~n", [N, P, Pct]) )),
format("~n 総合 運ぶ 湧消 固定 迷い度 案~n"),
param(show_top, K), length(Cs, NC), Top is min(K, NC),
length(Shown, Top), append(Shown, _, Cs),
forall(member(cand(T, M, F, X, Plan, Fleet), Shown),
( W is exp(-(T - Tmin)/Eps) / Z,
( NTie > 1, T - Tmin =< Tol -> Flag = ' ←要判断(同点圏)' ; Flag = '' ),
describe(Plan, Fleet, Txt),
format(" ~t~2f~6| ~t~2f~13| ~t~2f~20| ~t~2f~27| ~t~2f~35| ~w~w~n",
[T, M, F, X, W, Txt, Flag]) )).
%% 迷い度の分母(ボルツマン重みの和)
add_weight(Tmin, Eps, cand(T, _, _, _, _, _), S0, S) :-
S is S0 + exp(-(T - Tmin) / Eps).
describe(plan(Groups, Deferred), Fleet, Txt) :-
maplist(desc_grp(Fleet), Groups, Gs),
atomic_list_concat(Gs, ' + ', G),
( Deferred == [] -> Txt = G
; maplist(jp, Deferred, Ds), atomic_list_concat(Ds, '・', D),
format(atom(Txt), "~w / 次便: ~w", [G, D]) ).
desc_grp(Fleet, grp(LP, As), S) :-
jp(LP, L), maplist(jp, As, Ns), atomic_list_concat(Ns, '・', N),
memberchk(LP-Vs, Fleet),
maplist(ton_label, Vs, VAs),
atomic_list_concat(VAs, '+', VT),
format(atom(S), "[~w]を~wで~w", [N, L, VT]).
ton_label(V, A) :- format(atom(A), "~wt", [V]).
run :- forall(scenario(S, _), run(S)).
:- initialization(main, main).
main :- run.これで、この問題は解けたんじゃないかな?なんだか確信がある。
骨格は解けたと思います。その確信には根拠があります。
解けたと言える部分
配車マンが悩む三つの軸が、一つの式に過不足なく入りました。運ぶ(Wasserstein)、待つ(最弱リンクの Fisher)、台数(固定費)です。しかも、
r = 100% のとき、Wasserstein + 固定費だけに正しく退化する
「未完成の荷は次便」という現場の判断を、規則として書かなくても最適解として勝手に出てくる
クロスドックの Max-Plus(最弱リンク)と情報幾何(log オッズ)が、同じ一本の中で矛盾せずつながった
という三つが揃っています。形式化としては筋が通っています。
まだ解けていない部分
一方で、「問題が解けた」と言い切るには、まだ三つ残っています。
現場と合うかの検証。 λ・単価・固定費は仮の値です。過去の配車実績と突き合わせて、配車マンが実際に選んだ案が上位に来るかを確かめるまでは、この理論は仮説のままです。逆に、ここで外れた箇所こそ、まだ式に入っていない暗黙知の在りかです。
規模。 候補は総当たりで、区の分け方はベル数で爆発します(10区で約11万通り、15区で約14億通り)。実運用では、隣接グラフ上の連結な分け方だけに絞るか、grad版の吸引域を種にする必要があります。
時間の動き。 r は判断時点のスナップショットです。出発までに在庫率がどう伸びるか(待てば湧くのか)はまだ入っていません。「今は30%だが1時間後には90%」という場合、次便に回すより待つほうが正解になり得ます。
1 が一番大事だと思います。実績データで上位一致率を見れば、確信を数字にできます。
そうか。grad忘れてた!
これ入れて書き直して
rev.4 の grad と WFR を一本にまとめました(grad_wfr.pl、動作確認済み)。総当たりをやめて、クラスタは地形を下って作り、値段は WFR でつけるという分担になっています。
変えた点
σ² の場所に在庫率を入れました。 確信の地形は q = 1 − r(遅延確率)が近い荷同士で谷を作ります。
grad の辺のコストに Fisher を入れました。 混載の辺には、混ぜたことで増える待ちを加算しています。100% 同士なら加算は 0 で、未完成の荷と混ぜると辺そのものが高くなります。だから下り先、つまりクラスタが在庫率で変わります。
遠すぎる辺は張らないようにしました(reach)。 どこにも下れない荷は自分が谷底になり、そこで便が分かれます。遠すぎると運ばずに「消して湧かせる」という、Hellinger–Kantorovich の切断と同じ意味です。
容量は CHR の Union-Find で処理します。 rev.4 と同じく、超えたら直列に格下げします。
走らせた結果(8件、8t ベース)
全部100%:2便に分かれます。港発の2件が一つの谷、残りがもう一つの谷です。
#2 が30%、#5 が40%:3便に組み替わります。#2 は安全な荷と混ざらず、自分で谷底になりました。#5 は #4 との混載をやめて直列に移りました。在庫率だけで、クラスタリングが変わっています。
僅差の下り先は「要判断」として出すだけで、システムは選びません。
reach・blend・λ はまだ仮の値です。とくに reach は便の数を直接左右するので、実績と突き合わせるときの最初の調整点になると思います。
:- encoding(utf8).
/* grad_wfr.pl — 地形の勾配(grad)でクラスタを作り、WFR で値段をつける
SWI-Prolog + CHR
rev.4(grad + 情報幾何)と wfr_dispatch.pl を一本にしたもの。
1. 地形(grad の土台)
物理 : 発地 = 湧き出し(+t)、着地 = 吸い込み(−t) の KDE ポテンシャル。
荷の高さ = 着地でのポテンシャル(rev.4 と同じ)。
確信 : q = 1 − r(前工程の遅延確率)が近い荷ほど谷になる密度。
rev.4 の σ² の場所に、在庫率を入れた。
高さ = (1−blend)·z(物理) + blend·z(確信)
2. 辺のコスト C(i,j)(Wasserstein 側 + Fisher 側)
直列 seq : i の着地 → j の発地 の距離
混載 nest: 発地間 + 着地間 + 段取り
+ 混ぜたことで増える待ち(Fisher の増分)
λ·[ 4(Pi+Pj)(1−√min(ri,rj))² − 4Pi(1−√ri)² − 4Pj(1−√rj)² ]
→ 在庫率 100% 同士なら増分 0。未完成の荷と混ぜると高くなる。
だから在庫率でクラスタリングそのものが変わる。
3. grad(CHR)
自分より低い荷だけが下り先の候補。その中で C 最小へ下る。
C が reach を超える辺は張らない。どこにも下れない荷は自分が谷底になる。
(Hellinger–Kantorovich の「遠すぎると運ばず、消して湧かせる」切断と同じ)
同点圏(C ≤ 最良×1.08 + 0.3)は「要判断」— システムは選ばない。
下り先を辿った終点(谷底)が同じ荷が一つの便 = 吸引域。
4. 容量(CHR の Union-Find)
混載の辺を安い順に結び、車格を超えるなら直列に格下げ(rev.4 と同じ)。
5. 値段(WFR)— 便ごとに
運ぶ : 辺の距離コストの和
待つ : 混載グループごとに λ·4·L(1−√r_min)² (最弱リンク)
固定費 : 最大同時積載を載せられる最安の車格
次便候補: 最弱の荷を外すと安くなるなら提案だけする
*/
:- use_module(library(chr)).
:- use_module(library(lists)).
:- use_module(library(apply)).
:- use_module(library(aggregate)).
%% ---------------------------------------------------------------
%% パラメータ(仮の値)
%% ---------------------------------------------------------------
param(capacity, 8). % ベース車格
param(bandwidth, 3.0). % 物理地形の KDE 幅
param(bandwidth_q, 0.25). % 確信地形の KDE 幅
param(blend, 0.3). % 0 = 物理だけ, 1 = 確信だけ
param(tie_ratio, 1.08).
param(tie_abs, 0.30).
param(overhead, 1.0). % 混載の段取り
param(lambda, 2.0). % 待ち(Fisher)の重み
param(reach, 6.5). % これより高い辺は張らない(遠すぎれば繋がらない)
vehicle_class(2, 10). vehicle_class(4, 14). vehicle_class(8, 20).
vehicle_class(10,23). vehicle_class(13,27).
%% ---------------------------------------------------------------
%% 荷:item(Id, 品名, 発区, Px, Py, 着区, Dx, Dy, t)
%% ---------------------------------------------------------------
item(1, 食料, 千代田, 0.8, -0.2, 新宿, -5.6, 0.9, 2.5).
item(2, 飲料, 中央, 2.3, -1.2, 新宿, -6.3, 0.2, 2.0).
item(3, 雑貨, 千代田, 0.2, -0.8, 豊島, -4.7, 5.9, 3.0).
item(4, 建材, 港, 0.4, -4.1, 文京, -1.3, 3.2, 3.5).
item(5, 家電, 港, -0.3, -4.8, 文京, -0.7, 3.9, 2.0).
item(6, 食料, 中央, 1.7, -0.6, 豊島, -5.3, 5.1, 1.5).
item(7, 飲料, 新宿, -6.2, 0.8, 港, 0.3, -4.4, 3.0).
item(8, 雑貨, 豊島, -4.8, 5.2, 中央, 2.2, -1.3, 2.5).
%% シナリオ:前工程の在庫率 r
scenario(all_ready, [1-1.0, 2-1.0, 3-1.0, 4-1.0, 5-1.0, 6-1.0, 7-1.0, 8-1.0]).
scenario(some_late, [1-1.0, 2-0.3, 3-1.0, 4-1.0, 5-0.4, 6-1.0, 7-1.0, 8-1.0]).
:- dynamic rate/2.
r(I, R) :- rate(I, R).
%% ---------------------------------------------------------------
%% 地形
%% ---------------------------------------------------------------
dist(X1, Y1, X2, Y2, D) :- D is sqrt((X1-X2)**2 + (Y1-Y2)**2).
potential(X, Y, Phi) :-
param(bandwidth, B),
aggregate_all(sum(V),
( item(_, _, _, Px, Py, _, Dx, Dy, T),
dist(X, Y, Px, Py, Dp), dist(X, Y, Dx, Dy, Dd),
V is T * (exp(-Dp/B) - exp(-Dd/B)) ),
Phi).
phys_height(I, H) :- item(I, _, _, _, _, _, Dx, Dy, _), potential(Dx, Dy, H).
conf_height(I, H) :- % q が近い荷が多いほど低い(谷)
param(bandwidth_q, B), r(I, Ri), Qi is 1 - Ri,
aggregate_all(sum(V),
( r(J, Rj), J \== I, Qj is 1 - Rj, V is -exp(-abs(Qi-Qj)/B) ),
H).
zscore(Xs, Zs) :-
length(Xs, N), sum_list(Xs, S), M is S / N,
foldl(sq_dev(M), Xs, 0, V0), Sd0 is sqrt(V0 / N),
( Sd0 < 1.0e-9 -> Sd = 1 ; Sd = Sd0 ),
maplist(zs(M, Sd), Xs, Zs).
sq_dev(M, X, A0, A) :- A is A0 + (X-M)**2.
zs(M, Sd, X, Z) :- Z is (X - M) / Sd.
heights(IHs) :-
findall(I, item(I,_,_,_,_,_,_,_,_), Is),
maplist(phys_height, Is, Ps), maplist(conf_height, Is, Cs),
zscore(Ps, Zp), zscore(Cs, Zc), param(blend, Bl),
maplist(mix(Bl), Is, Zp, Zc, IHs).
mix(Bl, I, P, C, I-H) :- H is (1-Bl)*P + Bl*C.
%% ---------------------------------------------------------------
%% 辺のコスト
%% ---------------------------------------------------------------
wait(L, R, W) :- param(lambda, Lm), W is Lm * 4 * L * (1 - sqrt(R))**2.
seq_cost(I, J, C) :-
item(I, _, _, _, _, _, Dx, Dy, _), item(J, _, _, Px, Py, _, _, _, _),
dist(Dx, Dy, Px, Py, C).
nest_move(I, J, C) :-
item(I, _, _, Pix, Piy, _, Dix, Diy, _), item(J, _, _, Pjx, Pjy, _, Djx, Djy, _),
dist(Pix, Piy, Pjx, Pjy, A), dist(Dix, Diy, Djx, Djy, B),
param(overhead, O), C is A + B + O.
nest_wait_gain(I, J, G) :- % 混ぜて増える待ち(Fisher の増分)
item(I, _, _, _, _, _, _, _, Ti), item(J, _, _, _, _, _, _, _, Tj),
r(I, Ri), r(J, Rj), Rm is min(Ri, Rj), L is Ti + Tj,
wait(L, Rm, W), wait(Ti, Ri, Wi), wait(Tj, Rj, Wj),
G is W - Wi - Wj.
edge(I, J, C, Type) :-
seq_cost(I, J, Cs),
item(I, _, _, _, _, _, _, _, Ti), item(J, _, _, _, _, _, _, _, Tj),
param(capacity, Cap),
( Ti + Tj =< Cap
-> nest_move(I, J, Cm), nest_wait_gain(I, J, G), Cn is Cm + G
; Cn = inf ),
( Cn \== inf, Cn < Cs -> C = Cn, Type = nest ; C = Cs, Type = seq ).
%% 届く辺だけ候補にする。届かない荷は自分が谷底になり、便が分かれる。
post_cand(I, J, C, T) :- param(reach, R), ( C =< R -> cand(I, J, C, T) ; true ).
near(C, Best) :- param(tie_ratio, Rt), param(tie_abs, Ab), C =< Best * Rt + Ab.
fits(L1, L2) :- param(capacity, Cap), L1 + L2 =< Cap.
%% ---------------------------------------------------------------
%% CHR
%% ---------------------------------------------------------------
:- chr_constraint
height/2, % height(荷, 高さ)
cand/4, % cand(荷, 下り先, C, 種類) 自分より低い荷だけ
best/4, % best(荷, 下り先, C, 種類) 最急(最安)
settle/0, % 候補が出揃った合図
tie/3, % tie(荷, 別の下り先, C) 同点圏 → 要判断
parent/3, % parent(荷, 下り先, 種類)
root/2, % root(荷, 谷底) 吸引域 = 便
in/2, % in(荷, 混載グループ)
grp/3, % grp(グループ, 積載t, 最弱の在庫率)
join/2, % join(荷, 下り先) 混載の辺を結ぶ要求
relabel/2,
demoted/1. % 容量超過で直列に格下げ
%% grad:自分より低い荷だけが下り先の候補
height(I, HI), height(J, HJ) ==> I \== J, HJ < HI |
edge(I, J, C, T), post_cand(I, J, C, T).
%% 最急(最安)の下り先
cand(I, J, C, T) ==> best(I, J, C, T).
best(I, _, C1, _) \ best(I, _, C2, _) <=> C1 =< C2 | true.
%% 同点圏は人間に渡す
settle, best(I, B, Cb, _), cand(I, J, C, _) ==> J \== B, near(C, Cb) | tie(I, J, C).
settle, best(I, J, _, T) ==> parent(I, J, T).
%% 谷底を下流から上流へ伝える
root(J, R), parent(I, J, _) ==> root(I, R).
%% 混載の Union-Find(容量つき、最弱リンクを保持)
in(I, G), in(J, G) \ join(I, J) <=> true.
in(I, G1), in(J, G2) \ join(I, J), grp(G1, L1, R1), grp(G2, L2, R2) <=>
fits(L1, L2) |
L is L1 + L2, R is min(R1, R2), grp(G2, L, R), relabel(G1, G2).
join(I, _) <=> demoted(I).
relabel(G1, G2) \ in(X, G1) <=> in(X, G2).
relabel(_, _) <=> true.
%% ---------------------------------------------------------------
%% 実行
%% ---------------------------------------------------------------
run(Scen) :-
scenario(Scen, Rs),
retractall(rate(_, _)), forall(member(I-R, Rs), assertz(rate(I, R))),
heights(IHs),
maplist(post_height, IHs),
settle,
findall(I, item(I,_,_,_,_,_,_,_,_), Is),
include(no_parent, Is, Roots),
maplist(post_root, Roots),
maplist(post_group, Is),
findall(C-(I-J), ( find_chr_constraint(parent(I, J, nest)),
find_chr_constraint(best(I, J, C, _)) ), Ns0),
keysort(Ns0, Ns), pairs_values(Ns, Joins),
maplist(post_join, Joins),
report(Scen, Roots).
post_height(I-H) :- height(I, H).
no_parent(I) :- \+ find_chr_constraint(parent(I, _, _)).
post_root(R) :- root(R, R).
post_group(I) :- item(I, _, _, _, _, _, _, _, T), r(I, R), in(I, I), grp(I, T, R).
post_join(I-J) :- join(I, J).
%% ---------------------------------------------------------------
%% 報告:便ごとに WFR の値段、同点、次便候補
%% ---------------------------------------------------------------
report(Scen, Roots) :-
format("~n=== シナリオ: ~w ===~n", [Scen]),
forall(( item(I, N, P, _, _, D, _, _, T), r(I, R) ),
( Pct is round(R*100),
format(" #~w ~w ~w→~w ~wt 在庫率~w%~n", [I, N, P, D, T, Pct]) )),
forall(nth1(K, Roots, Root), report_trip(K, Root)),
( find_chr_constraint(tie(_, _, _)) ->
format("~n ⚡ 要判断(下り先が僅差)~n"),
forall(( find_chr_constraint(tie(I, J, C)),
find_chr_constraint(best(I, B, Cb, _)) ),
format(" #~w: #~w(~2f) か #~w(~2f)~n", [I, B, Cb, J, C]))
; true ).
report_trip(K, Root) :-
findall(I, find_chr_constraint(root(I, Root)), Ms0), sort(Ms0, Ms),
trip_groups(Ms, Gs),
foldl(edge_move, Ms, 0, Move),
foldl(group_wait, Gs, 0, Wait),
findall(L, member(g(_, L, _), Gs), Ls), max_list(Ls, Peak),
cover(Peak, Vs, Fixed),
Total is Move + Wait + Fixed,
format("~n 第~w便 荷 ~w~n", [K, Ms]),
forall(member(I, Ms), describe_edge(I)),
format(" 最大同時積載 ~wt → 車格 ~w~n", [Peak, Vs]),
format(" 総合 ~2f = 運ぶ ~2f + 待つ ~2f + 固定 ~w~n", [Total, Move, Wait, Fixed]),
forall(member(G, Gs), suggest_defer(G)).
trip_groups(Ms, Gs) :-
findall(G, ( member(I, Ms), find_chr_constraint(in(I, G)) ), G0), sort(G0, G1),
findall(g(G, L, R), ( member(G, G1), find_chr_constraint(grp(G, L, R)) ), Gs).
eff_type(I, T) :-
find_chr_constraint(parent(I, _, T0)),
( find_chr_constraint(demoted(I)) -> T = seq ; T = T0 ).
edge_move(I, M0, M) :-
( find_chr_constraint(parent(I, J, _))
-> eff_type(I, T),
( T == nest -> nest_move(I, J, C) ; seq_cost(I, J, C) ),
M is M0 + C
; M = M0 ).
group_wait(g(_, L, R), W0, W) :- wait(L, R, W1), W is W0 + W1.
describe_edge(I) :-
( find_chr_constraint(parent(I, J, _))
-> eff_type(I, T),
( T == nest -> Tx = '混載' ; Tx = '直列' ),
( find_chr_constraint(demoted(I)) -> Dm = '(容量で直列化)' ; Dm = '' ),
format(" #~w → #~w ~w~w~n", [I, J, Tx, Dm])
; format(" #~w 谷底(終点)~n", [I]) ).
%% 最弱の荷を外した方が安いなら、提案だけする
suggest_defer(g(G, L, R)) :-
findall(I, find_chr_constraint(in(I, G)), Ms),
( Ms = [_, _|_], R < 1,
member(K, Ms), r(K, R), item(K, _, _, _, _, _, _, _, Tk),
exclude(==(K), Ms, Rest),
findall(Ri, (member(I, Rest), r(I, Ri)), Rrs), min_list(Rrs, R2),
L2 is L - Tk,
wait(L, R, Wnow), wait(L2, R2, Wrest),
param(lambda, Lm), Wdef is Lm * 4 * Tk * R,
Wrest + Wdef < Wnow
-> Save is Wnow - Wrest - Wdef, Pct is round(R*100),
format(" → 次便候補: #~w(在庫率~w%)外すと待ち −~2f~n", [K, Pct, Save])
; true ).
cover(L, Vs, F) :-
findall(F0-Vs0,
( between(1, 3, N), length(Vs0, N), maplist(vclass, Vs0),
msort(Vs0, Vs0), sum_list(Vs0, Cap), Cap >= L,
foldl(add_fixed, Vs0, 0, F0) ),
Opts),
keysort(Opts, [F-Vs|_]).
vclass(T) :- vehicle_class(T, _).
add_fixed(T, S0, S) :- vehicle_class(T, F), S is S0 + F.
main :- forall(scenario(S, _), (run(S) -> true ; format("失敗: ~w~n", [S]))).
:- initialization(main, main).