研究紹介

配送計画問題

配送計画問題は，様々な制約条件の下で，複数の車両を用いて全ての客をちょうど一回ずつ訪問するような経路の中で，コストが最小のものを求める問題です．配送計画問題には制約条件などによって様々なタイプの問題がありますが，ここではその中でも時間枠付き配送計画問題を扱います．
車両はデポと呼ばれる地点から出発し，いくつかの客を訪問したのち，デポに戻ってきます．各客はいずれかの車両によってちょうど一度だけ訪問されます．
ここでは，制約条件として次の2つの制約を考慮します．
- 容量制約: 客の需要量の合計が車両の積載容量を超えてはいけない
- 時間枠制約: 客が指定する時間帯(時間枠と呼ばれる)にその客を訪問しなければならない
制約を満たす巡回路の中で総移動距離の最も小さいものを求めることが目的です．

この問題に対する基本的な解法として局所探索法(local search)があります．この方法は，適当な解から始めて，その解に近いもので現在の解より良い解があればそれに置き換える，という操作を反復して，解を改善していく手法です．

以下のGIFアニメーションは局所探索法の実行例です．
上記の例では，容量制約と時間枠制約が厳しくない問題例を使っているので，最終的な巡回路は人間の目からも効率が良さそうに見えます．

局所探索法は，現在の解の近くにより良い解が見つからないとき，現在の解を局所最適解として出力し，終了します．局所探索法などの解法を基本ルーチンとして，さらに良い解を探す手法はメタヒューリスティクスと呼ばれ，様々な研究が行われています．

時間枠制約と容量制約を満たすことが難しい問題例では，以下のように制約を満たすために複雑な（一見，効率の悪そうな）巡回路が得られます．実際に，この巡回路はこれまで知られている最良解です（だったと思います．．．）．

地図データや2地点間の経路探索アルゴリズムがあれば，地図上の配送計画問題を解くこともできます．次の実行例は，都庁を中心にランダムに客を配置して解いたものです．地図の右上のアイコンを操作すれば車両別の巡回路を表示することができます．このページでアルゴリズムを試すことができるので，ご自由にどうぞ．

配置問題とは，配置すべき製品の集合と容器が与えられたとき，製品を容器内に，様々な制約条件のもとで効率よく配置する問題です．