配送最適化(Vehicle routing problem)とは、１つまたは複数の拠点の荷物を、顧客がいる場所に運ぶ際、移動コストを最小にするような経路を求める問題です。
VRPにはいろいろな種類があります。
CVRP：車両の積載量（数）に上限があるもの
VRPPD：集荷と配送があるもの
VRPTW：配送の希望時間(Time window）が指定されるもの
などなど。（参考：wikipedia https://en.wikipedia.org/wiki/Vehicle_routing_problem）
問題
まずは簡単に、配送センターは１つ、１台の車両で５つの荷物まで一緒に運べる、という条件を考えてみます。
・下図のように、弊社がある五反田駅あたりに（架空の）五反田集配センターがあります。
・その周辺で、20人の顧客宅を緯度経度をランダムにピックアップしました。この20人に荷物を届けます。
・実際は、移動時間をコストにすることが多いと思います。移動時間は地図APIなどを使って求めるのが良いかと思いますが、今回は簡単のため、緯度経度の差から概算しました。
・20人の荷物を、上限5個ずつ車両に載せて運ぶとき、どれとどれをまとめてどのような経路で行けば一番短い時間で済むか、という問題です。
変数１：荷物が通るルートを表す変数
何を変数とするかを考えます。
まずは、20人のそれぞれの荷物を集配センターから顧客宅へ届けなければならないので、それぞれの荷物が通るルートが変数になるようにします。
\( p[i][j][k] \) : 顧客iの荷物がポイントj→ポイントkの間のパスを通る場合1、通らない場合0 とします。
\( i \) は顧客なので1～20を動きます。
\( j,k \) は、集配センターを0＋顧客1～20の0～20を動きます。
変数２：車両が通るルートを表す変数
移動コストは、荷物を運ぶ車両のルートに掛かるので、車両が通るルートが変数になるようにします。
\( c[j][k] \) : 車両がポイントj→ポイントkの間のパスを通る場合1,通らない場合0
制約条件（荷物のルートに関する制約）
まずは、各荷物が通るルートについて立式します。
１．荷物のスタート地点はそのパッケージの集配センター
今回は集配センターは１つのみですので、集配センターのポイント0から出ていくパスが１つだけになるようにします。
$$ \sum_j {p[i][0][j]}=1 \qquad(\forall{i}) $$
２．ルートの終了地点は、顧客宅になります。
そのため、すべての顧客宅iに入るパスは１つ、出ていくパスは0になるようにします。
$$ \sum_j {p[i][j][i]}=1 \qquad(\forall{i}) \\
\sum_j {p[i][i][j]}=0 \qquad(\forall{i}) $$
３．スタート地点、終了地点以外の場所では、すべてのポイントで、入ってくるパスと出ていくパスの数が同じになるようにします。
$$ \sum_{j\backslash0,i}{p[i][j][i]}= \sum_ {j\backslash0,i} {p[i][i][j]} \qquad(\forall{i}) $$
ここまでの立式があっているか確認します。
荷物が通るすべてのパスに、以下のようにコストをかけて、最適化を実行してみます。
$$ minimize \sum_i{\sum_j{\sum_k{p[i][j][k]\cdot (j→kへの移動にかかる時間)}}} $$
当たり前ですが、下図のようにどの顧客にも配送センターから直接荷物を運ぶようなパスになります。回り道もしていないし、一応ここまでは合っていそうです。
制約条件（車両のルートに関する制約）
次に、荷物を５つまで車に載せて運ぶことを考えます。
１．車両には、５つまでの荷物を載せられます。それを式にすると
$$ \sum_i{p[i][j][k] } \leq 5c\qquad(\forall{j,k}) $$
２．車両は、集配センターを出発して荷物を５個ずつ載せて顧客宅を回り、最後に配送センターに帰ってくるものとします。ルートはつながっている必要があり、配送センターには何度か立ち寄る必要があるため、以下のように立式しました。
$$ \sum_{j \backslash 0}{c[j][0]}== \sum_{k \backslash 0}{c[0][k]} \\
\sum_{j}{c[j][k]}==1 \qquad(k=1,\cdots 20) \\
\sum_{k}{c[j][k]}==1 \qquad(j=1,\cdots 20) $$
目的関数
最後に、目的関数を車両の移動にかかるコストに書き換えます。
$$ minimize \sum_j{\sum_k{c[j][k]\cdot (j→kへの移動にかかる時間)}} $$
結果
この立式に基づき、PULPの最小化問題として計算しました。
結果について、それぞれの荷物のルートを下図に示します。下図のように５個までの荷物をまとめて運ぶことができているようです。
車両のルートの方を図示すると以下のようになります。おおよそ効率よく回れているかなと思います。
以上のように、簡単な例ではありますが、配送問題をPULPで解くことができました。
整数計画問題は、立式が楽しいです。
荷物の希望配送時間がある場合や、複数の車両で回る場合、集荷がある問題なども、記事にしたいと思います。
Comments are closed