毎朝、物流センターの前では、トラック数台が荷物を積んで出発を待っています。今日届ける先は数十か所あり、どのトラックがどの家を担当し、どんな順番で回るかを決めなければなりません。同じ荷物を同じ家に運ぶのでも、ルートをどう組むかによって、一日に走る距離や燃料代、ドライバーの退勤時間が大きく変わります。
車両経路問題（Vehicle Routing Problem）とは、簡単に言えば「複数の車両が倉庫から出発し、複数の顧客を分担して訪ね、戻ってくるとき、全体のコストが最も少なくなる経路の組み合わせを探す問題」のことです。1959年にジョージ・ダンツィグ（George Dantzig）とジョン・ラムザー（John Ramser）が、ガソリンスタンドへガソリンを運ぶトラックの配車問題として初めて紹介し、今日では宅配や流通物流の基本的な計算になっています。
この資料では、車両経路問題の基本構造から、場合の数が爆発する理由、現実が加えるさまざまな条件、そして答えを見つける方法まで、順に見ていきます。
トラック複数台のルートを一度に組む計算
車両経路問題の基本構造
車両経路問題は、いくつかの要素を決めるだけで、その姿がはっきりします。
（1）倉庫と車両
すべての車両は一か所の倉庫、つまり出発拠点から出て、仕事を終えたらまたそこへ戻ります。車両が何台あるか、各車両がどれだけ積めるかは、最初から決まっています。
（2）顧客と需要
配送先ごとに位置と、受け取るべき荷物の量があります。すべての顧客は必ず一度ずつ、しかも一台の車両からだけ荷物を受け取ります。
（3）移動コスト
二地点間を行き来するのにかかる距離や時間、費用をあらかじめ計算しておきます。実際の道路網で最短の道を求めておけば、地点間のコストを一枚の表のように扱えます。
（4）目標
最も一般的な目標は、全体の移動コストを減らすことです。場合によっては、車両の台数を最小にしたり、車両ごとの仕事の量を均等に分けたりすることを目標にすることもあります。
場合の数が爆発する理由
トラック一台がすべての家を一周する最も短い順序を探す問題を、巡回セールスマン問題（Traveling Salesman Problem）といいます。車両経路問題はこの巡回セールスマン問題を複数台の車両に広げたものなので、少なくともそれと同じだけ難しい問題です。
訪問先が10か所なら、回る順序だけで約362万通りになります。20か所になると、その数は約243京通りにふくらみます。さらにどの車両がどの顧客を担当するかまで決めなければならないため、すべての場合を一つひとつ調べる方法はすぐに限界にぶつかります。
数学では、このような問題をNP困難（NP-hard）問題に分類します。顧客の数が増えるにつれて、正確な答えを求めるのにかかる時間が、手に負えないほど急に増えるおそれがあるという意味です。そのため現場では、完璧な答えよりも、十分によい答えを素早く見つける方を選ぶことが多くあります。
現実が加える条件
実際の配送の現場は、教科書の中の問題よりずっと複雑で、条件が加わるたびに新しい変形問題が生まれます。
- 積載容量の制約（Capacitated Vehicle Routing Problem）：車両ごとに積める重さや体積に限りがあり、それを超えないように顧客を分けなければなりません。
- 時間枠の制約（Vehicle Routing Problem with Time Windows）：顧客ごとに荷物を受け取れる時間帯が決まっていて、その中に到着しなければなりません。
- 集荷と配送（Vehicle Routing Problem with Pickup and Delivery）：ある場所で荷物を積み、別の場所で降ろす仕事を一緒に処理します。
- 複数倉庫（Multi-Depot Vehicle Routing Problem）：車両が出発して戻る倉庫が複数あります。
- 電気自動車の経路問題（Electric Vehicle Routing Problem）：バッテリーで走れる距離と、充電する場所もあわせて考えます。
このほかにも、車両が倉庫に戻らなくてもよい場合や、一日に何度も倉庫を行き来する場合など、現場の事情の数だけさまざまな変形が研究されています。
答えを見つける方法
車両経路問題を解く方法は、大きく、正確な答えを求める方向と、よい答えを素早く求める方向に分かれます。
厳密解法
整数計画法という数学的なモデルで問題を立て、可能な場合をうまくふるい落としながら、最もよい答えを探します。答えの質は確実ですが、顧客が増えると計算時間が大きく増えるため、主に規模の小さい問題に使われます。
セービング法
1964年にクラーク（G. Clarke）とライト（J. W. Wright）が提案した方法です。最初は顧客ごとにトラックを一台ずつ別々に送ると仮定し、二人の顧客を一つの経路でつないだときに減る距離、つまり節約量が大きい組から順に合わせていきます。計算が簡単で結果も使えるため、今でも広く使われています。
メタヒューリスティクス
遺伝的アルゴリズム、タブーサーチ、焼きなまし法のように、最初に作った経路を少しずつ直しながら、よりよい答えに近づいていく方法です。最近の優れた方法は、数百から数千か所に及ぶ問題でも、最適な答えとの差を1パーセント前後まで縮められると知られています。
車両経路問題は、地図の上に線を引く作業のように見えますが、その裏には、コストと時間、人の労働をともに減らそうとする計算があります。経路計画ソフトを作る企業が5〜30パーセントのコスト削減をうたっているのも、この計算の力を示しています。
同じ荷物をより短い道で運ぶために、経路を絶えず見直すこと。それが効率的な配送の第一歩です。
