NUOPT 事例集 ～タイムウィンドウ付きの Vehicle Routing 問題(CVRPTW)の応用～(株)数理システム
NUOPT を使用して配車計画を立案するという機会がありました．本稿はこの事例について簡単にまとめたものです．

1. 配車計画概要
対象となる計画は 1 日の配車計画です．拠点としては基地(30 箇所前後)・顧客(最大 100 箇所)・仕入所(10 箇所前後)の 3 種類があります．車輌は基地に属しており，各基地は 1 台以上の車輌を所有しています．対象となる車輌は全部で 30 台程度です．仕入所とは配送する品物を車輌に搭載する場所のことです．本配送計画では各車輌は基地を出発する際は最大量の品物を搭載しているとし，基地に帰還する際は直前に仕入所に立ち寄り最大量の品物を搭載しなければならないという決まりがあります．
さらに代表的な制約・規則をあげると以下のようなものがあります．
■顧客の要望・属性
・需要情報(品物と量)・納入時間の指定・納入可能な車輌タイプ(車輌サイズ)
・基地指定・仕入所指定
・納入順番指定(基地を出発後，最初に来てほしいなど)■車輌の制約・属性
・車輌タイプ(車輌サイズ)
・搭載可能品物
・搭載可能容量(品物毎の容量)・平均速度，燃費■仕入所の制約(属性)・仕入れ可能品物
・一日の仕入れ可能量
・仕入れ可能な車輌タイプ(車輌サイズ)■その他，実務的な制約
・需要量の小さな顧客から回る
・各車輌の総労働時間の制約
・各車輌の休憩の制約(連続運転時には休憩を 60 分いれなければならないなど)
・各車輌は可能な限り品物を降ろしてから基地に帰還する
・一般道路，高速道路の利用(一般道路，高速道路ではコスト，平均速度が異なる)■目的関数
・総移動距離最小化
・総コスト最小化
これら制約・規則を鑑みると，本配車計画はタイムウィンドウ付きの Vehicle Routing 問題(CVRPTW)の応用の一種といえます．CVRPTW は NP 困難な二つの部分問題の組み合わせと考えることができますので，組み合わせ的に非常に難しい問題であり，数理計画問題として厳密に定式化ができたとしても大規模な問題では厳密解を求めることは現実的には不可能となります．つまり，厳密解の保証はないがそこそこ良い解(全ての制約を満たしており，目的関数も十分小さい解)をリーズナブルな時間で求めることが本配車計画の目標となります．
このような問題を解くためには一般に 2 通りの方法が考えられます．1 つ目は本配車計画専用の近似解法によるエンジンを 1 から作成するというものであり，2 つ目は本配車計画の基本構造を鑑みることで扱いやすい問題に変形し，既存の信頼できるソルバーを利用するというものです．
本事例では，我々は後者の方法を採用しました．
以下では，本事例の我々のアプローチについて簡単にまとめます．

2. アプローチ
我々は，本配車計画を次の 3 つのフェーズに分けることを考えました．
1. 各車輌毎の意味のある経路(以下，TRIP と呼び，詳細は後述)の列挙
2. TRIP を各車輌へ割り当てるという割り当て問題の求解
3. 後処理第 1 フェーズで，考えられる TRIP を多数列挙し，第 2 フェーズでは第 1 フェーズで列挙された TRIP を車輌に割り当てます．この割り当て問題に対して弊社の数理計画パッケージソ
フトである NUOPT のメタヒューリスティックエンジン WCSP1を使用しました．第 3 フェー
ズでは，第 2 フェーズの割り当て結果を元に，各車輌の細かな時間的なスケジュールを決定し，最終的な配車計画を求めます．
2-1. TRIP の列挙
まず，TRIP の定義をします．
1 つの TRIP とは各車輌がスタート地点である基地を出発して，タイムウィンドウなどの制約を守りながら顧客を回り，再び同じ基地に戻るという一連の経路のことです．
TRIP ： 各車輌の「基地→顧客→．．
．→仕入所→基地」という経路
その際，[配車計画概要]であげた制約・規則のうち以下の項目については列挙時に考慮します．
■顧客の要望・属性
・需要情報(品物と量)・納入時間の指定・納入可能の車輌タイプ(車輌サイズ)
・基地指定
・仕入所指定・納入順番指定(基地を出発後，最初に来てほしいなど)■車輌の制約・属性
・車輌タイプ(車輌サイズ)
・搭載可能品物(一度に搭載できる品物は 1 種類だが，複数の品物を搭載できる場合がある)
・搭載可能容量(品物毎の容量)・平均速度，燃費■仕入所の制約(属性)
1WCSP は，京都大学「問題解決エンジン」開発グループが作成

2

・仕入れ可能品物・仕入れ可能な車輌タイプ(車輌サイズ)■その他，実務的な制約
・需要量の小さな顧客から回る
・各車輌の総労働時間の制約
・各車輌の休憩の制約(連続運転時には休憩を 60 分いれなければならないなど)
・各車輌は可能な限り品物を降ろしてから基地に帰還する
・一般道路，高速道路の利用(一般道路，高速道路ではコスト，平均速度が異なる)
ここでのポイントは，[配車計画概要]であげた制約・規則のほとんどを考慮して TRIP を列挙していることです．このような「制約・規則を満たしている TRIP の列挙」は 2 つの意味で重要です．1 つ目は単純に列挙される TRIP の数を制限できます．特に，本事例では制約・規則が非常にたくさんあるために，TRIP を現実的な数に絞ることができました．2 つ目は，第2 フェーズの割り当て問題を比較的単純なものとして定式化できます．列挙された TRIP はほとんどの制約を満たしているため，第 2 フェーズの割り当て問題は残りの制約を考慮しながら全ての顧客を網羅するような問題を解けばよいことになります．ここには，いわゆる VRP特有の難しい問題はなくなっています．
2-2. 割り当て問題の求解
第 2 フェーズでは第 1 フェーズで列挙した TRIP を車輌に割り当てるという問題を解きます．第 1 フェーズで車輌 c( c  C ，C は車輌集合)に対して TRIP 集合 T が生成されています．
c

ここで 0-1 変数 x c ,t ( t  Tc) を導入することで，割り当て問題のもっと基本となる制約式(各車輌には最大 1 つの TRIP しか割り当てられない)を x 1c ,ttT cと記述することができます．
さらに，本配車計画では全ての顧客を網羅しなければなりません．これを表現するために，顧客が TRIP t 上に存在している場合に 1，存在していない場合に 0 をとるような定数
M t ,k ( k  K ，K は顧客集合)を導入すると，

M xt ,kc ,t1( c ,t ),tT cと記述できます．以上の 2 つの制約式が本割り当て問題の骨子となる制約式です．その他は，■仕入所の制約(属性)・一日の仕入れ可能量■目的関数
・総移動距離最小化・総コスト最小化
をモデルに取り込むことで，定式化は完了します．
NUOPT に搭載されている WCSP というソルバーは，タブサーチによる近似解法で，割り当て問題が得意なことがこれまでの適用経験からわかっています．本事例では上記のように複3雑な制約は，第 1 フェーズに追い出すことで第 2 フェーズでは考慮する必要がないため，非常に効率よく解を求めることができました．
2-3. 後処理
実は各顧客の「納入時間の指定」には幅があります．大きな幅のものでは，6 時間，それ以上のものまであります．これは，TRIP の列挙時に TRIP の開始時刻と終了時刻を 1 つに決めることができないため，TRIP の開始・終了時刻にも幅を持たせる必要があるということを意味しています．すなわち，第 2 フェーズの割り当て問題は，各車輌の顧客を回る順番を求める問題であると言えます．
第 3 フェーズでは，この求まった顧客を回る順番情報を元に，細かい時間の配車計画を作成する処理のことです．細かい配車計画の作成方法は様々ありますが，ここでは時間的に前詰めになるように作成しました．

3. 配車計画結果
本事例において最も重要なフェーズは第 1 フェーズの TRIP 列挙になります．このフェーズで列挙された TRIP の質が悪い場合，第 2 フェーズから得られる解も当然質が悪くなります．
そのため，TRIP 列挙時にどのように列挙するのかが非常に重要です．
今回考慮した点を具体的に列挙します．[配車計画概要]であげた制約・規則と完全に一致しませんが，おおよそ現実的な点を考慮しています．
■車輌の平均速度は 40Km/h■品物を車輌へ搭載，品物を車輌から降ろす速度は 300kg/分■仕入所では品物を搭載する以外に 30 分の固定時間がかかる■顧客先では品物を降ろす以外に 15 分の固定時間がかかる■総移動時間が 8 時間を越える TRIP は列挙しない■総労働時間(総移動時間+総作業時間)が 9 時間を越える TRIP は列挙しない■1 つの TRIP の顧客数が 3 を超えるものは列挙しない■各需要の納入時間の幅を 1 時間分大きくする(納入時間が 9:00 というような需要もあったため)■顧客側の車輌タイプの考慮■車輌の搭載可能品物の考慮■車輌の搭載可能量の考慮■高速道路の利用は考慮していない

4

この前提のもと，第 1 フェーズ，第 2 フェーズを
CPU PentiumD 3.2GHz
メモリ : 4GByte
OS : WindowsXP x64
NUOPT : Ver.9という実行環境で流しました．
第 1 フェーズは 11 秒で列挙が終わり， 13561TRIP が得られました．第 2 フェーズでは 45秒で解の更新がとまり，合計で 45 の TRIP が車輌に割り当てられました(次図)．

4. まとめ本事例で扱った配車計画は，非常に難しい部類の配車計画です．しかし，その難しい部分(難しい制約が多い)を逆手にとることにより，問題を扱いやすい割り当て問題に帰着することができました．
本事例は，正面から取り組むと難しい問題を，別の問題へ変形することで現実的な解を得ることができたというよい例であるとともに，数理計画を適用するにあたって，適用方法により成功・不成功が決まるということも示唆しています．
―以上―

5