フリーペーパーの「配送計画問題」に見る、「局所探索法」の基本的な考え方：リクルート事例で分かる数理最適化入門（4）

リクルートにおける数理最適化の応用事例を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介する連載。今回は、フリーペーパーの「配送計画問題」をどう解決したかを解説する。

[濱田賢吾, 棚橋耕太郎，リクルート]

　本連載「リクルート事例で分かる数理最適化入門」では、リクルートでの数理最適化の応用事例を通して、数理最適化がどのようにビジネスに応用できるのかを紹介します。連載第4回の本記事では、前回に引き続き、リクルート各サービスにおける数理最適化の応用事例を紹介します。

　今回は、「フリーペーパーの配送計画の策定」の事例を紹介します。この事例では、「扱う問題が汎用（はんよう）の数理最適化ソルバーが苦手とするタイプの問題である」という難しさがありました。

　前回までで紹介した事例では、汎用の数理最適化ソルバーを用いた求解を行いましたが、全ての問題が汎用ソルバーで効率的に解けるわけではありません。本記事で紹介するアプローチが、読者の皆さんがそのような問題に直面した際の解決の一助になれば幸いです。

概要

　リクルートでは、「タウンワーク」「ホットペッパービューティー」など、複数のフリーペーパーを全国の駅やコンビニエンスストアなどのラックに配置しています。各ラックへのフリーペーパーの配送は、複数の配送会社に委託しています。

　配送会社は複数のトラックで多くのラックを巡るので、その配送ルートを効率化することは重要な問題です。従来は人手によってトラックの配送ルートを決めていましたが、より効率的なルートを提案するために数理最適化を用いました。

ビジネス課題の理解

　ここでは、もう少し詳細に問題設定を説明します。

　トラックは配送会社の拠点から出発し、ラックを巡って、また拠点に戻ってきます。この際、全てのラックをいずれかのトラックで訪問する必要があります。

　下図は配送ルートのイメージです。

　決めるべきものは、次の2点です。

1. どのトラックがどのラックを担当するか
2. 各トラックはどのようなルートでラックを巡るか

　ルートはできるだけ効率的なもの、すなわち、総移動時間が短くなるものが望ましいです。なお、ラック間の移動時間は入力データとして与える必要があります。

　さらに、次に挙げた項目などを含む多くの実務的な制約を守る必要があります。

• ドライバーの稼働時間
• トラックの積載量
• ラックを設置している店舗への訪問可能時間

　ここまでに説明した問題設定をまとめると、下図のようになります。

　このような複雑な問題を人間が考える大変さは想像に難くありません。しかし、人手だからこそ調整できる細かな要件があることも、また事実でしょう。現場の方に使っていただくために、「どれだけ現実に即した解を提案できるか」が本取り組みの肝といえます。

数理最適化によるアプローチ