先月組み合わせ最適について整理したが、代表的な組み合わせ問題としての配送計画の最適化を試行してみる。宅配やコンビニなど搬送業者はコスト削減、CO2削減で以下に効率よく配送するかが重要になる。巡回セールスマン問題と同じ類の順序に関する問題だが、複数台のトラックがあるので、順序＋組み合わせの最適化になる。ちょうどGoogleのフリーの最適化ツールOR-toolsにも興味があったので、試してみた。

課題

今回、下記の記事を参考に試行。非常にわかりやすく、コードはほとんどそのまま使わせてもらっている。残念ながら自分自身がOR-toolsの使い方についてこの記事以上にうまく説明はできないので、細かい説明はこの記事を読んでもらうことにする。
https://qiita.com/_jinta/items/3494dff06bee9d85f1e5

横浜市にヤマダ電機は15店舗あり、これらの店舗に商品を配送するにあたってのトラック配送計画を考えてみる。各店舗の場所（緯度と経度）、店舗サイズを調べて地図上にプロットし、青丸が店舗の場所と大きさで店舗のサイズを示している。こうやってみると横浜市のヤマダ電機の各店舗は大きな幹線道路上が多いことがわかる。

データはヤマダ電機の店舗情報から緯度・経度を調べてcsvファイルを作成。店舗の大きさも大凡の目安が記載されているページがあり、その情報を使っている。

課題としては、トラック2台で横浜本店から出発し、トラック2台の総距離が最短になるように、各トラックの配送する店舗と順番を決めてみる。このとき、店舗の大きさ（1: 普通、2: 大型、3: 超大型）に合わせた積載量が必要になり、各トラックの積載量を制限している（店舗の大きさの合計が15を超えないように制限）。

距離の計算は実際の通る道路の長さでなく、2地点間の直線距離になっている。正確性はないが、今回はどういった結果が出るかを見ることが目的で、そこまで追い求めない。

また、横浜市の隣の川崎市の店舗も合わせ、川崎店のトラックを含めた3台のトラックで、総距離がどうなるかを比較してみた。紫色の丸印が川崎市の店舗になる。

実行結果

横浜市のトラック2台の経路は以下のとおりで、総距離は88.762km。横浜市の真ん中から南の方に大きな店舗が集まっているので、積載量が均等になる形で割り振りがされている。北の店舗がそれぞれが距離があるので、北側ルートが非効率になっている感がある。
また川崎市の店舗だけを1台のトラックで回ると、総距離は34.195km。横浜市のトラック2台と川崎市のトラック1台で合計すると122.957km。

今度は川崎市も入れて、トラック3台で最適化した結果は以下の図で、総距離は110.735km。全体で12.2kmの削減、全体で10%ほど、川崎市のトラックが横浜市北部の店舗を回ることでだいぶ効率的になったことがわかる。ちなみに計算時間はほとんどかからず、一瞬で答えを出してくれる。

まとめ

シンプルな配送計画をOR-toolsで試行してみた。使いこなすにはまだまだだけど、台数を増やしたり、トラックごとのスタート地点を変更するなどは今回行えたので、もう少し色々と実験はできそうだ。総距離を実際の道のりから算出したり、制約に総距離と積載量以外にも、例えば工事や渋滞情報など追加するなどを試すとまた見えてくるものはあると思う。アルゴリズムも今回はCPソルバーを使ったが、今読んでいる本（Python コンピュータシミュレーション入門：橋本洋志＋牧野浩二著、オーム社）に遺伝的アルゴリズムの手法も記載されている。

今回の課題の応用先（例えばバスの運行路など）やより複雑な課題にはどのように社会実装が進んでいるかはもう少し調べてみたい。