配送計画
配送計画とは、荷物の集積所から各顧客、あるいは小売店などにトラックを使って物を配送するときに、どのトラックがどの顧客をどういう順番で回れば一番良い、つまり、コストが安くなるかを求める問題です。集積所から顧客、あるいは顧客間の移動時間は地図から計算できるので、各トラックがどういう順番でどの顧客を回るかを決めれば、どの程度時間がかかるか、どの程度コストがかかるかがわかりますから、かかる時間をなるべく少なく、また使うトラックをなるべく少なくするな配送ルートを見つける、という問題です。分かりやすく解説するために、図1の例を見てください。
この例では、真ん中に倉庫が一つ、お店が５、トラックが2台あります。この2台のトラックを使って店に荷物を配送する、配送ルートで、もっともコストの安いものを見つけましょう、という問題です。今、時間の関係で、1台のトラックは３つまでしか店を回れないとします。移動時間は、店と店の、図の中での距離で表されるとします。そうすると、もっとも時間がかからない配送ルート (最適解、といいます) はこのようになります。
この例のように、店、あるは顧客が少数しかない場合は、図を見ればすぐに答えがわかります。しかし、図3のように、たくさんの店がある場合はどうでしょう？しかも、この他にいろいろな条件が付いていたりしたら。たぶん、一番良いルート（かかる時間が少ない、あるいは使用するトラックの台数が少ない）を見つけるのは大変です。こういった、ある程度大きな問題（店舗数が大きな問題）を、コンピューターを使って高速に解こう、というのが、配送計画問題です。
工場から店に配送を行う場合、通常は、いろいろな条件があります。例えば、トラックが1日に走れる距離と時間。あるドライバーだけが残業をたくさんするような答えが出てくると困りますからね。その他に、各店への到着時間。店員がいない時間にトラックが到着すると困るので、トラックが来ても良い時間帯を指定します。トラックの積荷の上限もあります。この他、場面場面でいろいろな制約条件が出てきます。これらの条件を満たすように、あるいはなるべく満たすような配送ルートを作る必要があります。これらの制約条件がついた配送計画問題の一例を見てみましょう。
現実の場面で現れる条件はどのようなものがあるのか、それをコンピューターで扱わせるためにはどうすればいいのか、はたまた、そのような条件を満たし、コストがなるべく少なくなるような最適配送ルートを、コンピューターで機械的に見つけるにはどうすればいいか、そういったことを研究するのが、配送計画の研究なのです。
配送計画は、通常大きな問題になることが多いようです。このような大きな問題に対しては、人間が直感や手計算で最適ルートを求めることは、ほぼ不可能です。コンピューターで最適化を行う必要があるわけです。また、得られた解は、配送ルートの細かい部分、つまり、この店を先に回ったほうが、信号でつっかえないから早く済むとか、そういった部分については人間の経験のほうが優れているのですが、全体的な計画に関しては、人間が解いたものより優れているようです。1割から3割程度、コストの安い配送ルートが得られるという報告もされています。年間の配送コストが10億円程度であれば、1億から3億円のコスト削減につながる可能性があるわけです。
配送計画は、スケジューリング問題と同じく。正確な最適解、つまり、他のどの解もこれ以上良くならないような保証がある解を見つけるには、膨大な時間がかかります。だいたい、店舗の数が50ぐらいの問題が限界です。おおよそですが、パソコンを使って解いても、1日くらいかかるでしょう。問題によって、それこそ1分程度で解けるものもありますが、運が悪ければ、1日2日ではすまなくなります。
実際に、宅急便会社や配送業者などが解きたい問題は、それこそ、店なりお客の数が1000以上になります。このような問題に対して、真の最適解を求めるのは、ほぼ不可能です。そこで、近似解法といって、限られた時間、5分〜10分程度で、誤差が5%くらいであろうと思われるような解を求める、という作戦に基づいた方法が、ずいぶん研究されてきています。数多くの方法が発明されていて、それぞれ、長所短所があります。ですが、どの方法にも共通して言えることは、とても運が悪ければ、悪い答えが出るかもしれないけれど、たくさんの問題例に対して実験してみた結果、そんなに悪いものは出ない、ということです。このような方法を用いれば、客の数が3000くらいまで増えても何とかなります。
普通、このような、計画、あるいはプランを決める問題では、問題を解きたい人が欲しいと思っているような答えをコンピューターがそのまま出してくれることはありません。条件や目的を数値化しているので、どうしても、人間の考えている条件と、コンピューターが理解した条件との間にギャップができてしまうからです。そこで、通常は、コンピューターの出した答えを人間がチェックして、「この部分は良いがこの部分はよろしくない」という点を探し出し、そういった解を出さないよう、条件を新たに付加してコンピューターに問題を解かせなおす、といった方法が行われます。こうして、コンピューターと対話して、人間の、あいまいな条件をコンピューターに理解させていくのです。そのためには、一回の問題を解く時間が、1分程度になる必要があります。一回解くのに10分も20分もかかるようでは、対話している人間がいらいらしてしまいます。
計算の高速化のためには、アルゴリズムの改良やデータ構造の工夫が不可欠です。このような、対話型の近似解法に対しても、アルゴリズムの改良が、計算時間を10倍にも100倍にもする可能性があります。実際、データ構造を用いて、10000店もの大規模な問題が、2-3分で解けるようにもなってきています。今後研究を進めれば、各種の配送計画がそれこそ瞬く間に解けるようなものが、開発されていくでしょう。