Emmomi

2024年3月20日 @アクトシティ浜松 テーマ 高専カンファレンスin浜松 [15分枠] 土建折衷 市営船の最適化について考えてみた 鳥羽商船 専攻科 えもみ (後援) #kosenconf151_hamamatsu

自己紹介 • • • • • えもみ 豊田(NITTC)→鳥羽(NITTC) Blenderとかやってる人 Twitter @Emmomi1 情報系っぽい見た目をしてる が電気の人だったりする

Q.情報系の人間が土木・建築の話をするの？？？ A.どうやらそうらしいですね

そもそも土木の範囲って？ ■ 地盤系 ■ 構造・材料系 ■ 水工系 ■ 測量系 ■ 計画系 ■ 交通系 ■ 衛生系 どうやら自分はここにヒットしたらしい (って土木の大学院生に言われた)

と言うことで… 交通計画(市営船)の最適化について話してくぞー

最適化とは？ 目的関数𝑓(𝑥)の 最大値 or 最小値 を出してくれる𝑥を頑張っ て見つけるお仕事 𝑓(𝑥) 𝑥 どっちかを見つける

(鳥羽市の)市営船 • 鳥羽市と近くの島を運航している 船 • 鳥羽市が運営してるらしい • 赤字がいっぱい出てるらしい

市営船の赤字を最も少なくしよう～ ここが最適化

1つ目の最適化の手法 便の数を減らす

鳥羽の市営船の運航表 1~数時間に一本 流石に便を減らしたら住民に 刺されるかもしれない…

2つ目の最適化の手法 (本題) 便の割り当て方を変える

どう言うことだってばよ？？ 船1 それぞれの運航便を別々 の船で担当している 船1 (回送中) 船2 船2 (回送中) 船3 回送分がコストになる

どう言うことだってばよ？？ 経由便として1つの船が担 当する 回送分のコストが減る (まぁ燃料だったりメンテナンス だったりは置いといて…)

モデル化 目的関数𝑓(𝑥)&制約式を実際に数式にするお仕事 とある屋台で例えると… max(𝑥 + 𝑦) 𝑥,𝑦 ൞ 𝑥 + 𝑦 = 20 2𝑥 + 4𝑦 = 30 〇川焼き 大△焼き 小麦粉 1円 1円 餡 2円 4円

モデル化 xsn ∈ 0,1 , n ∈ N, s ∈ S ෍ xsn = 1 , n ∈ N xsn1+xsn2 s∈S ≤ 1, AT n1 > DT n2 ∧ DT n1 < AT n2 , n1 ∈ N, n2 ∈ N, s ∈ S ෍ xsn1 × xsn2 = 1,∀n2 , ∀n1 , DH(n2)=AH(n1), DH(n2)−AH(n1) < 𝑚 s∈S ?

モデル化 船s x ns ∈ 0,1 , n ∈ N, s ∈ S 便 nに船 sを割り当てるかを示す変数 xsn = 1 ൝ n xs = 0 割り当てる 割り当てない A港 12:00 発 B港 12:10 着 便n

モデル化 船s σs∈S xns = 1 , n ∈ N 便 nには船舶を1つ割り当てなければならない A港 12:00 発 B港 12:10 着 便n

モデル化 12:00 n2 x n1 +x s s ≤ 1, AT n1 > DT n2 ∧ DT n1 < AT n2 , n1 ∈ N, n2 ∈ N, s ∈ S 運行時間が被っている便同士は同じ船舶を 割り当てられない 12:10 12:20 便n1 12:30 便n2

モデル化 船s n2 σs∈S x n1 × x s s = 1, ∀n2 , ∀n1 , DH(n2 )=AH(n1 ), DH(n2 )-AH(n1 )< 𝑚 船s 到着した船舶の折り返し便の出発港は到着した港 と同じでなければならない 便n1 便n2 A港 12:00 発 B港 12:13 発 B港 12:10 着 C港 12:20 着

2次式の制約式があると計算量が洒落 にならんくなる…(っ◞‸◟c) 解決策として1次式に変換すると言う手もあるが…

面倒くせぇ それに1次式にしたところでオーバーフロー起こして 一緒に起動してたアプリ全部落とすしPC破壊しかけ るしなんならBlenderの10倍重くなったりするし…

船s ところで… さっきの制約は便同士の 「繋がり」の制約でした 船s 便n1 便n2 A港 12:00 発 B港 12:13 発 B港 12:10 着 C港 12:20 着

「繋がり」が表現できれば行けるのでは？？？

それが出来るのがグラフ(ネットワークと言ったりもする)です このグラフって子は実は行列でも表現できたり するのでとっても便利

便n1 便n2 A港 12:00 発 B港 12:13 発 B港 12:10 着 C港 12:20 着 この条件を満たす便同士を 結ぶ有向グラフを作れば 行列を見るだけで良くなる！！

モデル化が終わったら 複数の解を出して 目的関数に入れてって 𝕩 𝑛 x𝑠11 = 0 𝕩 𝑛 x𝑠11 =1 𝑛 x𝑠33 = 1 𝑛 x𝑠22 = 0 𝑛 x𝑠33 = 0 𝑛 x𝑠22 = 1 𝑓 𝕩 = 赤字 最も赤字が少なく なる𝕩を探す

実際に 最適化 自動生成が出来るプログラムを置いておき ました https://github.com/Emmomi/EconoNav

• https://github.com/Emmomi/EconoNav

宣伝 コミケ104にサークル申し込みしました 古市庭(ふるいちば)ってサークルで出ます ウマ娘のお出かけ本を出します