Approach A はビームサーチを使いました。B は貪欲法を使いました。

A
  • 最初の頃MLEになったので、Double-Ended PQ(hogloidさんの4PQ) を使いました。
  • 幅 : 約300
  • 枝狩り : 同じ頂点で次の注文までの時間が800以内ならまとめる
  • 枝狩り : 距離が25以下のところまたは店に移動する
  • スコア : 待ち時間の2乗引くのが本当のスコアだが、貪欲法の気持ちになると、足した方が良いと思って、やってみたら良かった。


B
  • 注文が来たら、巡回セールスマン問題をGuided Local Searchで解いて、店に早く戻ってくるのを繰り返す(スコア : 1410...)
  • 頂点数が400の時、巡回セールスマン問題は戻ってくるまで1200以上かかるが、同じ頂点からの注文は平均600ほどで来る。A では注文をまとめた(後回しにする)けど、逆に早く店に戻るのが良いと分かる。巡回セールスマン問題自体は頑張って解いていて、これより大幅に早く戻ることはできないので、途中で店に寄り道するしかない。(スコア : 1414...)
  • 途中で戻ってくる巡回路を作るために、最初から頂点を2、3のグループに分けた。(スコア : 14169...)
  • 途中で戻ってきたときに、注文が分かるのでその情報を使う。(スコア : 実装間に合わなかった)


感想というか失敗したこと

スコアを合わせるのに時間がかかったけど、上位とは配達できた注文で圧倒的に差がついてたし、A もB も無視して結局本当のスコアを使わなかった。