1日あたり26,000食の配送ですか?
この規模の配送ロジスティクスは困難です。当団体のボランティアドライバーには、1回あたり15食の配給(つまり1回の配送で30食)を処理できるものと想定し、それぞれに最適化された配送ルートを割り当てています。それでも、1回の配送完了には約1.5〜2時間かかり、ボランティアにとって週2〜3回このペースを維持できると考えています。
当団体の場合、26,000食は13,000食の配給に相当します。これは、1地点あたり約2食の配給として計算すると、約7,000回の停車を意味します。ボランティアドライバーと一般乗用車を使用して配送する場合、毎日700台の車両が必要となり、実際には(毎日運転するボランティアは限られるため)約2,000人のドライバーが必要になります。
食料の供給元を管理できる場合(当団体は食料を作っていないため、その点では難しいですが)、ドライバー間で住所リストを分割し、各ルートを最適化すれば済みます。当団体の配送量は yours よりもはるかに少ない(1日2,000〜3,000食、yours の1/10程度)ため、住所リストの自動分割は行っていません。各配送先は地域に割り当てられ、配送担当者によって地域ごとに手動でリストを分割しています(これは単純なスプレッドシートのソートです)。その後、AWS上で動作するWebサーバーを通じて各ドライバーのルートを最適化し、各ドライバーに最適化された配送ルート(単純な巡回セールスマン問題のアルゴリズム)を提供しています。
住所リスト全体の自動分割も検討しましたが、まだ必要なく、資金も限られているため、AWSやGoogle Maps APIの利用コストを低く抑えたいと考えています
複数の車両を対象とした一般的な配送経路最適化問題(VRP)に対しては、シンプルなアルゴリズム的解決策が存在します。例えば、こちらをご覧ください:
ただし、これほどの数の配送がある場合、非常に広大な地理的エリアをカバーしていると思われます。そのため、ドライバーの自宅住所も考慮する必要があるかもしれません。これにより、通常のVRPからは外れます。単純なヒューリスティック手法で、ドライバーのグループと配送先住所をサブ問題に分割し、配送先とドライバーが同じ地理的エリア内にあるようにすることで、再び標準的なVRPソリューションを利用できる可能性があります。
余談ですが、当団体ではGMapの移動時間を点対点の距離として使用しています。