配車計画を難しくする「バース制約」とは

From:朴成浩

NHKスペシャル、見ましたか？

「天使か悪魔か 羽生善治 人工知能を探る」

個人的には、一番の驚きはGoogle囲碁開発者のハサビスさんと将棋の羽生さんとのチェス勝負でした。あの羽生さんと一勝一敗、全くの互角ですよ！？

世の中にはまったくすごい人がいるものです。「何でもできる」のレベルが違い過ぎます。もし、ハサビスさんが真剣に自動配車を作ったら一体、どんなことになってしまうのか！？かなり見てみたいです。

ハサビスさんの目標は、何でもできる人工知能を開発することだそうなので、もしその夢が叶う日が来たなら是非、私たちの「最適配車しかできない」専用アルゴリズムと対戦させて頂きたいです。

どっちがより良い配車を組めるのか？いわば、「AI vs コンピューター」対決です。

はたして汎用の人工知能は、困難な組み合わせ最適化問題においてもコンピューターにさえ勝てるのか！？

ちょっと何言ってるの？？という感じですが、このワクワク感を理解してくれる人がいたら是非、飲みながら語りましょう！

「バース制約」とは

さて、いきなり話を戻しますが、、

前回は、配送計画を難しくする運行パターンの例として「宵積み」を挙げました。宵積みできる車両とできない車両が混在する状況にうまく対処できるようにするのは、私たちも非常に苦労しましたが、実はもっと難しい配送条件があります。

それが「バース制約」です。バースとはトラックバースのこと。簡単に言えばトラックが積み降ろしを行う場所のことですね。

たとえば、こんな状況を想像してみてください。車100台の配送計画を組むとしましょう。このとき、もし100台のトラック全てが朝8:00に一斉にセンターにやってきて積み込みを始めようとしたらどうなるでしょうか？

このとき、たとえばこのセンターにはバースが20台分しかなかったとしましょう。すると、最初の20台の積み込みが終わるまで残りの80台は待たないといけない、ということになってしまうわけです。

たとえば積み込みに30分かかるとしましょう。すると、8:00～8:30の間に20台が荷積みをし、8:30～9:00の間に次の20台が荷積みをし・・・というように、100台の車は20台ずつ時間をずらしながら荷積みを行っていくことになりますね。

このように、1カ所のセンターや配送先で同時に積み降ろしできるトラックの台数に制限がある状況、これが「バース制約」です。

なお、便宜的に「バース制約」と呼んでいますが、一度に積み降ろしできる台数を制限するのは必ずしもバース数だけではありません。たとえば、倉庫側の作業者の人数やピッキング能力といった、センター側の出荷能力の関係から１時間当たり○○個の荷物しか入出庫できない、ということもよくあります。そのような条件も「バース制約」の一種です。

バース制約が入ると、はっきり言って配送計画はめちゃくちゃ難しくなります。超超超・・・と「超」を10個くらい付けたくなるほど難しくなるのです。

「バース制約」が厄介な理由

たとえば、先ほどの単純な例では、100台のそれぞれの出発時間は次のような感じになりますよね。

8:30 1～20号車が出発

9:00 21～40号車が出発

9:30 41～60号車が出発

10:00 61～80号車が出発

10:30 81～100号車が出発

最初に出発する車両と最後に出発する車両では2時間もの時間差があるわけです。となると、行ける範囲にしてもコース組みにしても、1号車と100号車ではできることが全然、違ってきてしまうわけです。

つまり、ルートを考えると同時に、各拠点や配送先でどの車両に先に積み降ろしをさせてどの車両を後回しにするか、というバースの使用順までも一緒に計画しないといけないのです。

このようにバース制約では、宵積み同様、ルート以外の要素にも複雑な組み合わせ要素が入ってくるので、めまいがするほど検討すべき組み合わせが大きくなってしまいます。しかし、バース制約が配車計画を難しくする理由はそれだけではありません。バース制約が入ると、常に解全体のことを考えないといけなくなってしまうのですね。

たとえば、あるルートに変更を加えたとしましょう。通常、バース制約がない場合はその影響は変更したルートにだけ及びます。つまり、何か改善したい部分がある場合はその部分だけに注目して、もっと良いルートに改善できないかな？と考えれば良いわけです。

ところが、バース制約があると、あるルートに対する変更の影響はそのルートだけに留まりません。そのルートと訪問先が重なる全てのルートに影響は及びます。たとえば、あるルートを変えるとセンターを出発すべき時刻や荷積みにかかる時間が変わってきますから、場合によっては同じセンターに着発する他のルートとバースがかぶってしまうというようなことが起こるわけです。

何というか、難しいプラモデルとかレゴとかを作っているような感じです。端っこの方を取り付けていると、反対側の端っこが外れてくる、みたいな感じです。誰か反対側抑えといて！とか手がもう１本欲しい！とか言いたくなるヤツですね。（と言っても、こんなたとえ分かる人いますか？）

こんな風に、バース制約は「ルート組み」と「バースの利用順」という２つの難しい組み合わせ最適化問題を同時に解かないといけないので、まっとうに挑むと手が何本あっても足りない、というか、計算時間がいくらあっても足りないのです。

私たちもいろいろがんばってはいるのですが、バース制約を考慮しながら、なおかつ私たちの他の配送計画と同じくらい高速に解くということは残念ながら、現状ではまだ実現ができていません。大きな課題の一つですね。さらに良い配車のためにまだまだがんばります！

＋＋朴成浩