”車割り”を最適化
”車割り”という作業を競プロ力で自動化→lineのbotで運用 ということをやってみました。
車割り とは
部活の帰りに親切な部員数名が他の部員を最寄駅付近などまで送り届けてあげるとき、どの部員が誰の車に乗るか割り振る というシステムです。
「自分の帰り道から大きく外れる場所を通るのはなるべく避けたいが、できるだけ多くの人数が乗車しているのが望ましい」という考えのもと毎回数人の知恵を結集して割り振りが決められています。
この作業にはかなりの時間がかかるので自動化できれば嬉しいはずです。
車割りを最適化問題に落とす(富本part)
車割り問題は重み付き二部グラフ最大マッチング問題に帰着できます。
まず各車と各部員に対応する頂点を用意し、次に各車に各部員を乗せたときの利益(たとえば送っていける距離)を事前に決めてその利益分の辺を張っていきます。
すると、このグラフは二部グラフとなり、できるだけ利益が大きくなるようにマッチングさせる問題になります。
このままだと各車に一人の部員しかマッチングできませんが、たとえばある車に運転手以外に人が4人乗れる場合は、その車に対応する頂点を4つ用意しておくことで、最大4人の部員をマッチングさせられます。
(実際には頂点を4つ用意するのではなく、後で説明する最小費用流アルゴリズムにおいて張る辺の容量を4にします。)
アルゴリズムの解説 (富本part)
重み付き二部グラフ最大マッチングは最小費用流アルゴリズムを用いると以下のようにして解くことができます。
1. 各車と各部員の頂点のほかに2つの頂点SとTを用意し、十分大きい整数をINFと置く
2. Sから各車に辺(容量:その車に乗れる人数、コスト:0)を張る
3. 各車から各部員に辺(容量:1、コスト:INF-利益)を張る(ただし、利益<0の場合は辺を張らない)
4. 各部員からTに辺(容量:1、コスト:0)を張る
5. SからTにフローを流せるだけ流す
6. 車(Aとする)から部員(Bとする)に張られており(正の)フローが流れているようなすべての辺について、部員Bは車Aに乗ることにする
アルゴリズムをline botに載せる
line botの作成は公式のドキュメントが丁寧なのでそれに従いました。 "サンプルボットを作成する"の項目にあるpythonのtoolkitを使用します。 まず、echobotの例をそのまま実行して動作確認をしました。
次に、実装されたアルゴリズムを組み込んでいきます。 1. 各部員に対して学年、最寄り駅の経度緯度、車に対して乗車可能人数を初期値として持っておきます。
grades = {"name1":1,"name2":2....}
places = {"start1":(000,000),"name1":(000,000),,"name1":(000,000)...}
car = {"name1":4,"name5":3,...}
- 入力に応じて出力を変えるように場合わけをします。 ①割り振り②初期値の更新③初期値の一部確認④helpを想定される入力の様式としてそれ以外は"helpとうって期待する入力形式を確認するように"とエラーを出します。
①割り振り、では 車のスタート地点、割り振られる部員を入力として
@app.route("/callback", methods=['POST'])
def callback():
~~~~
input,has_error = check_input(input)
if has_error:
posst = "入力が違います..."
else:
members,start_place,absent,guest=input
posst = assignment(members=members,start_place=start_place,absent=absent,guest=guest)#重み付き二部グラフ最大マッチング実行
line_bot_api.reply_message(
event.reply_token,
TextSendMessage(text=posst)
)
#>>posst
#out_of_car:[name1,name2,name3, ...]
#name4's car: [name5,name6,name7]
#name8's car: [name9,name10,name11]
#name12's car: [name13,name14,name15]
という出力を得ます。
②初期値の更新、では変数をglobalにすると動きました。
X = ....
@app.route("/callback", methods=['POST'])
def callback():
~~~~
global X
X = new_X
実際には、membersはあらかじめ数個に分かれているgroups(X=[ ],Y=[ ],Z..)のlistを使用することで入力の文字列をできるだけ短くしています。
感想
いままで触ってみたら楽しいかもしれないけれどとっつきにくい、と感じていたflaskやbotに1mmでもタッチできたのは良い経験でした。
競技プログラミングが実生活に役立つ瞬間がみれて感動しました。
最適化の部分はcolabに貼り付けて自分で変数を書き換え→実行すれば動くようになっていましたがほとんど利用されなかったこともあり、休みを利用してlineのbotに載せました。
botの部分はサンプルをいじっただけでしたが、競プロerの力を借りることで巷によるあるbotよりも良さそうなものが作れたのではないかと思います。
参考
https://www.youtube.com/watch?v=jBsvdgFMZtg heroku login:https://qiita.com/WEByamori/items/4cab4be8ce336ed3e4d6
- 前の記事 : Kaggle Tabular Playground Series - Dec 2021
- 次の記事 : 清麗戦の研究:早く負けるが得か?
- 関連記事 :