会議室割当と運搬車スケジューリング

配送計画問題が運搬車経路問題 (vehicle routing problem)と呼ばれるのに対して，運搬車「スケジューリング」は，時間に焦点を当てたモデリングを行うことを意味する．特に，顧客の訪問時刻が，決められた時刻である場合は，時刻が決められていない（もしくは時間枠として与えられている）配送計画問題と比べて，自由度が減るので，求解が容易になる．

運搬車の台数を最小にする問題は，実は会議室割当の問題と同じ構造だ．

私の後輩が顧問している会社にデモがあった．

オンラインデモ&チュートリアル - Amplify - 量子アニーリングと共に進化するクラウド

実は多項式時間で簡単に解ける．タスク（会議の場合はミーティング）を点として，あるタスクの後に別のタスクが実行できる場合に有向枝をはる．このグラフ上で，始点から終点への独立パス（同じ点を通過しないパス）ですべてのタスクを表す点をちょうど 1 回づつ 通過するものを求める．実は，最小のパスの本数（運搬車の台数）は， Dilworthの定理とよばれるグラフ理論の結果から，同時に処理できないタスクの最大値と一致することが知られている．

タスクをあらわす点を両端点として無向２部グラフを作って，上で作ったグラフの有向枝に対してだけ，右から左に枝をはる．このグラフ上でマッチンゴを求めれば，最小台数（会議室数）の解が求まる．

上のサイトではアニーリングを８つの会議に割り当てていたが，最適解は５つだ．かなりスカスカなスケジューリングを結構時間をかけて出している．

ちなみにマッチングはSciPyにハンガリー法があるので，ものすごく速く計算できる．もちろん，普通にnetworkxのマッチングを使っても良い．こんなかんじで書くことができる．

G = nx.Graph()
for i in D.nodes():
   G.add_node(str(i)+"L")
   G.add_node(str(i)+"R")
for (i,j) in D.edges():
   G.add_edge(str(i)+"R", str(j)+"L")
   
matching = nx.algorithms.matching.max_weight_matching(G, maxcardinality=True)
edges =[]
for m in matching:
   (i,j) = m
   if i[-1]=="R":
       edges.append((i[:-1],j[:-1]))
   else:
       edges.append((j[:-1],i[:-1]))

他の例題（タクシーの割当）も割当問題なので，多項式で解ける．４色問題も簡単だ．数分割問題も増えていたが，小さい整数の問題例はものすごく簡単だ．大きな整数を入れて300個くらいの問題例を入れてみたら，解が出なかった．差分法を使えば 一瞬で最適解が得られるものだ．

まともな問題としては巡回セールスマンが入っていたが，大きいので試すとたまに交差する．Euclidean TSPは交差していたら論外だ．雰囲気だと最適解の5%ましより悪そうだ．