エアブラシによる着色の順序は、同じパーツを2色以上で塗り分ける場合に制約がかかる。基本的に奥まったところを塗ってからそれ以外を塗る必要があるため。しかし、エアブラシで色を変える作業は結構手間なので、なるべく1つの色は一度にすべて塗りたい。これはアルゴリズムで最適化できる問題。
— 西田和史(k.bigwheel) 開発基盤EM @ Speee ⌨️🖊️ (@k_bigwheel) 2022年7月9日
から始まる問題の解き方を考える。
まずは問題としてのモデル化から入る。
モデル化
問題のモデル化のセオリーがわからないため、NP困難な問題の中で一番有名な巡回セールスマン問題との違いをまとめることから始める。
- 距離はない (あとでつけたい気もするが一旦なしで考える)
- 点Aより後に点Bを通る必要がある、という制約
- なるべくたどる点の数を少なくしたい
調べると、かなり近い(というかほぼまんま)の先行研究がいくつか見つかった。
- 巡回セールスマン問題 順序 制約 - Google 検索
- ある種の順序制約付きTSPと多項式オーダー解法について | 文献情報 | J-GLOBAL 科学技術総合リンクセンター (タイトルしか見てない)
特に 順序付き巡回セールスマン問題について - Qiita はやりたいことをほぼやっている。 ただ、モデルとして循環するような制約を除外しているようなので、循環を許容して点の通過回数2回以上を許容するような問題設定が必要になる。 たぶん、
- Sequential Ordering Problem
- TSP (Traveling Salesman Problem ) Order Constraint
などがクエリとして良さそう。
あと[難問]複雑な制約付きの巡回セールスマン問題（TSP）もしくはジョブショッ... - Yahoo!知恵袋の人が話題に出しているJSPの問題にも似ている。この人はセールスマンが複数いる場合の問題だけど、塗装の問題はセールスマンが1人のTSP+JSP複合問題と言えるかもしれない。
プリント基板の電気検査における数理計画法に基づくシステム最適化
そこで，カメラによるアライメント撮像を考慮 した最短検査経路を求める問題が，先行順序制約付き巡回セールスマン問題の中で も特に集荷配送巡回セールスマン問題として定式化が可能であることを示し，その 上で，小規模問題に対しては，数理計画ソルバーを用いて厳密解を求解可能である ことを示している。
お、これもかなり参考になりそう。そうか、順序制約はより一般的な用途だと集荷配送と近いのか。
先行順序付き合流可能運搬経路問題に対する局所探索法 (最適化手法の深化と広がり)
これもと期待問題にかなり近いが、verhicleが複数であるのがちょっと違う。 ここは1台でいい。
いくつかキーワードとそれらしい論文は出てきているが、これと言ったものがない。というより、こちらに理解の土壌がない気もする。
おそらく、僕が求めているものは
- The Precedence Constrained Traveling Salesman Problem
- 先行順序制約付き一般化巡回セールスマン問題
がほぼそれなんじゃないかと思う。 前者の論文をちゃんと読めばそれで問題は解決するかも。
もろもろ考えると論文読んで実装するのはつらそう。 googleのツールとか見るに組み合わせ問題として問題を得として、その概要を学び、solverの適用方法を調べて適当なsolover(library)を使うのが最短距離っぽいとわかった。
2022/08/08
移動中勉強していたが、
全体戦略は見えた。
— 西田和史(k.bigwheel) 開発基盤 / SRE ⌨️🖊️ (@k_bigwheel) 2022年8月7日
次は定式化だ。塗装順の問題は一般的なものではないから、自分で定式化を考える必要がある。 https://t.co/eM9dOSH8hl
という感じ。 vercelにpythonのAPIをデプロイできることもあり、google製のortoolsを使うつもりでいる。
