解説
数理計画の理論と実装

容量制約付き車輪経路選択問題の解法
LeslieE．Trotter，大山 達雄
Ill川‖州Illl…………………ll…………‖‖＝‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖‖‖＝‖‖‖‖‖‖＝‖＝‖‖‖＝‖‖＝‖‖＝‖＝‖‖‖‖＝‖＝‖＝‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖＝………llに対応する．この間題の整数計画問題による定式化は，1．はじめに以下のように与えられる．

1959年にDantzigら（Dantzig−Ramser［10］）にMinimize z＝∑cexee∈E

よって最初に提起された車輌経路選択問題（VehicleRouting Problem（VRP））の解法について考える．
顧客の集合をⅣ＝（1，…，乃）とし，それぞれの顧客オは何らかの単一品種物資に対する需要め（整数値）を有するとする．このとき，々台の同一容量Cを有する車輌を用いて，すべて中央に位置するデポ（0）から出発するという条件下で，それぞれの顧客の物資需要を最小の総輸送費用でまかなうような配送計画を作成するにはどうすればよいか，というのが事柄経路選択問題である．顧客オから顧客ノへの移動コスト値をCゎ≧0とするとき，すべての顧客の需要をまかなうという条件下において車輌の総移動コストが最小となるような配送計画を作成することが必要とされる．ここでcぴ＝Cノ∫が成立するとき，コストは対称であるといい，さらに同一顧客間の移動コストはc打＝0とする．
車輌経路選択問題を組合せ論的に述べると，集合Ⅳを々個の経路（凡，…，月々）に分割するに際して，それぞれが∑J∈肘あ≦C，オ＝1，2，…，々を満たすように，そしてそれぞれの経路に対しては配送順序を与える順列（ツアと呼ぶ）のを求める問題であるということができる．またこの間題をグラフ論的に述べると，項点集合Ⅳ∪（0），枝集合E，そして枝（オ，ノ）∈E上の移動コストを有する完全無向グラフに対して，デポ頂点を共通の頂点とする々個の閉路の和集合を解とするものを求める問題となる．ここで，それぞれの閉路は々台の車輌の各々が物資の配送を実施するルート

Subjecttoe＝｛｝∈E∑ ∬e＝2 ∀才∈Ⅳg＝H，Jl∈g∑：こ払≧2∂（5）∀5⊂Ⅳ，151＞1（3）し−∴・∴−ごご0≦Je≦1∀e＝（オ，ノ）∈E，グ，ノ≠0 （4）0≦∬e≦2 ∀e＝（0，力∈E∬e：整数 ∀e∈且．

顧客集合Sの需要を満たすのに必要とされる車輌台数の下限値∂（5）＝「（∑f∈5dど）／Clを定義するより強力な不等式は，容量Cを有するビンに集合5の需要を満たすという，いわゆるビンパッキング問題（BinPacking Problem（BPP））に対する解を計算することによって得られる．制約条件（1）と（2）は次数制約と呼ばれる．容量制約（3）は行商人問題（Traveling Sales−man Problem（TSP））に対するサブツア削除制約の一般化であると見なすことができる．これらの制約は解の連結性，そしてまたルート上の総需要がCを超えないようにするためのものである．

VRPがBPPとTSPという二つの難しい組合せ問
題と密接に関連していることは明らかである．C＝∞のとき，多重行商人問題（MultipleTravelingSales−man Problem（MTSP））の問題例が得られるが，MTSPは項点0と付随する枝をk−1個追加することによって等価なTSPの問題例に変換することができる（々個のデポの間には枝が存在しないことに注意されたい）．他方，与えられたVRPの問題例に対して

レスリー・E・トロッター

実行可能解が存在するか否かという問題はBPPの問

SchoolofOR／IE，CollegeofEngineering
Corne11University，Ithaca，NY14853U．S．A．

題例である．この間題の決定変数は，概念的には，任おおやま たつお
政策研究大学院大学〒162−8677新宿区若松町2−2

等価である（すべての実行可能解は最通解である）．

924（48）意のオ，ノに対してcむ＝0であるようなVRPモデルと全体問題に対する実行可能解はTSPの（拡大グラフ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

（5）

（6）

における）ツアであって，々個のデポを連結するセグ

では，これらの制約条件（すなわち∂（5）＝（∑∫∈∫di）／

メントに沿っての総需要はCを超えることはない．

C）の小数形式が多項式時間で分離可能であることがBPPとTSPという二つのモデルの間には相互関連示されている．この方法は，式（3）の制約条件を満たさがあるために，VRPの問題例は実際に解くのが非常ないものを識別する発見的解法として利用することがに難しくなっている．このことは，コスト構造がルーできる．

ティングの順番に大きく依存するため，それらをまと前述のモデルではTSPは拡張グラフ上のVRPのめること（パッキング）の重要性が低下していること緩和形であると見なすことができるが，TSPツアは，によるものである．したがって，ルーティングとパッBPPに対する実行可能解となる場合にはVRPの実キングという二つの条件が競合することも時々あるた行可能解にもなり得る．そこですべてのTSPツアのめ，これらのモデルの一方あるいはもう一方を緩和す付随ベクトルの凸包であるTSP多面体をT，VRPるという分割型最適化を用いることも必要となる．この実行可能解に対応するツアの付随ベクトルによってこで，TSP多面体上で最適化を行うという既知の手生成される多面体をβと表すと，斤⊆rであって，法を用いることによってBPP構造からTSP部分のさらに斤の端点がrの端点に含まれることが分かる．

みを抽出するという方法について調べてみよう．この

枝カット探索木のある項点において，LPソルバー

ことは容量制約あるいは他の妥当不等式制約のクラスによってLP緩和問題に対する最適解￡が得られたに対する分離ルーティンを実施することに相当し，ことする．このとき上のまに対応する支持グラフあるの分離手法は，二つのモデル間の共通部分に対応する

いは分数グラフを，枝集合麿＝（e：烹e＞0）を有するような組合せ最適化問題に対してもより一般的に適用

グラフe＝（Ⅳ∪（0），眉）と定義する．いままが整数可能な手法である．

値であるとすると，倉≠Tのとき，次数制約がLP緩以下にこのアプローチの概略を紹介し，応用ソフト

和問題の中に明示的に含まれているので，グラフeのSYMPHONY構成（SYMPHONYについてはは非連結となる．この場合，デポを含まないようなグ

User，sGuide［19］あるいは文献［13］を参照されたい）

ラフeの任意の連結成分の項点集合は容量制約を満を用いて行った並行枝，カット，コストに対する数値たさないので，われわれはCUT操作を実行すること実験の計算結果を示す．

によって，この不等式をLPに追加した後，再び最適化を実行する．他方，ま∈rの場合，ま∈点か否か2．容量制約の分離を考慮し，そうでない場合にはまに対応するツアのVRP多面体に対する妥当な不等式の多くのクラス

デポ間ルート中にある項点によって導出される容量制についてはいろいろな文献［1，4〜7，9，14〜16］た報約を烹が満たさなくなるので，CUT操作を実行する．

告されているが，分離問題はほとんどの既知のクラス

最後に，ま∈斤のとき，￡はVRPに対する実行可能に対しても解くのが困難とされている．有効に分離が解を与えるので，現在の探索項点の操作は終了する．

行われるようなクラスでも枝とカットに関しては有効

このようにしてまが整数値でない場合の処理を行うとならない場合が多い．ここでは容量制約（3）を用いたことになる．

VRP多面体から任意の分数点を分離するという問題2．1発見的解法に注目する．このような制約に対する分離問題は分離問題は解くのが難しいため，解烹が滴たさなHarche，Rinaldi（文献［5］参照）によってJW一完全い容量制約を決定するためにいくつかの単純な発見的であることが示されたが，ここに示した定式化のLP解法を通用する．これらの発見的方法は支持グラフ緩和問題も構造的に刃P−完全であることが分かる．

eに対して適用されるが，ここではグラフeは連結分離問題を解くのは非常に難しいため，制約条件を効率的に分離するための発見的解法をどのようにして構築すればよいかという問題に対する研究努力がこれまでかなり活発に行われてきた．しかしながら，
Augeratetal．［5］による論文が現れるまで，ほとんどの既知の解法は容量制約を満たさないような条件を識とし，成分が紺e＝烹eによって定義されるような枝の重みを有するベクトル紺∈〟？磨を有するとする．
紺（F）＝∑紺g，F⊆麿（7）∂（5）＝（（オ，ノ）∈磨：オ∈S，ノ≠S），5⊆Ⅳ∪（0）．（8）
連結成分発見的解法では，デポを除去した後に支持グラフの成分を一つずつ考慮する．いまSは，この別するのに有効とはいえないものであった．文献［4］2003年12月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（49）925

ような連結成分の項点集合であるとしよう．￡がSた順番に従って1より重みの小さい枝に対して実行さによって決定される容量限定制約を滴たさないときは，れる．縮退型発見的解法の場合と同様にして，それぞCUT操作を実行する．そうでない場合には，除去後れの枝は容量制約を満たさなくなるかどうかを決定すに制約が満たされなくなりそうな項点〃∈5を用いてるために縮約する前にチェックされる．枝が選ばれる

S←5＼（〃）を実行する（特に占（Cf＼（わ）＝占（Cf）と順番は各カットの重みが 小さい 順になっているのu）（8（Ci＼（u）））−2b（C＼（v））＜u）（8（Ci））−2b（Ci））を満で，このアルゴリズムでは，他の発見的解法では発見たすような項点〃∈Cどを利用する）．このような手順されないような容量制約を見出すことが可能となる．

は，頂点が見つからなくなるまで繰り返し実行される．

上記の発見的解法が，容量制約を満たさないものを不等号条件がすべて満たされたとすると，支持グラフ見出せない場合には，食欲縮退型発見的解法を通用すの次の連結成分について考慮する．この方法の一つのればよい．この解法では，任意に選択されるか，ある変形版として2連結成分発見的解法があるが，この解いはまた何らかの発見的規則に従って選択されるよう法ではデポの除去後に2一枝連結成分（少なくとも2な，小さな項点集合Sから出発する．それぞれの反本の枝を除去して初めて非連結となるようなグラフ成復において，集合Sに∑吋（ど，ノ〉。E：f。5〉∬eが最大（した分）から手順を開始する．

がって∑e∈∂（5）∬gが最小）となるような項点ノ≠Sを縮退型発見的解法では，デポに隣接していない支持追加することによって，Sを大きくしていく．この戦

グラフの任意の枝の二つの頂点がまによって容量制略と，大きな初期集合が同様の規則を用いて縮退され約が満たされない枝（すなわち，S＝（オ，ノ）が容量制るという連結成分発見的解法に基づく戦略とを対照さ約を満たさないと仮定しよう）に対応するとき，せて見てほしい．

CUT操作を実行する．そうでない場合は，デポに隣2．2 分割アルゴリズム接していない杖e＝（オ，力が紺e≧1せ満たすとしよう．

上述の発見的解法が容量制約を満たさないものを見

この場合，両端点を重ね合わせることによって枝e出すことができなかっ▲た場合，文献［18］に最初に提示を縮退，あるいは縮約し，その結果得られた枝に対応された分割アルゴリズムを適用するJあるLP緩和問する紺の成分を加え合わせる．このようにして得ら題に対する小数解烹が与えられたとき，まをツアのれた縮約グラフにおいて，同一化された二つの端点は付随ベクトルの凸包として表すことによって烹が多Ⅳの部分集合からなる超項点を形成することになる．

面体rの内部に存在するか否かを決定する．より厳この新たな超項点に対応する需要は，それに含まれる密には，列ベクトルがrの端点を表すような行列T各項点の需要の総和となる．この縮退操作が容量制約に対してを満たさなくなる操作と矛盾しないこ七は容易に証明

max（0り：71＝烹，1り＝1，ス≧0）できる．すなわちSが容量制約を満たさない場合，グ，が有限な最適解を有するか否かを求めることが必要と

ノ∈5′またはダニノ≠S′のいずれかを満たす集合5′がなる．まをこのようなツアベクトルの凸結合として存在しなければならないことを示せばよい．このよう分割可能な場合には，Carath60doryの定理によってにして，発見的解法では，紺e≧1を滴たす杖eを縮rの列の一部分のみが必要とされることが分かる．

退させる操作と両端の項点が容量制約を滴たさか−か言うまでもないことであるが，行列Tを作成するこどうかを調べる操作を交互に反復的に実行する．制約とは容易ではなく，・どのようにしてこれを実行するかが満たされない場合はCUT操作を実行し，そうでなという問題については，読者はもう少し待ってほしい．

いときは，すべての枝eがデポに隣接しているか，まがツアベクトルの凸結一合でありながら，容量制あるいは祝侵＜1を満たすようになるまで反復操作を約を満たさない場合には，ある種の分割もまた同じ制繰り返す．縮退グラフにおいては，ある枝eに対し約を満たさないことになる．このようにして，烹にて，抑e＞1となることが可能であることに注意された

対する凸結合が与えられたとき，容量制約を満たさなしヽいようなものを求めるためには，ツアの中のデポから修正縮退型発見的解法はNagamochi−Ibaraki［17］デポへのそれぞれの部分を調べることになる．この手による最小カットアルゴリズムに基づいており，基本続きが成功すると，滴たされなかった不等式に対する的には縮退型発見的解法に類似している．この修正版

CUTを作成する．この子続きがうまくいかない場合

では，縮退操作は文献［17］のアルゴリズムに定められには，すなわちま（したがって烹∈r）の凸分割が存

926（50）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ（9）在して，さらに制約を満たさないものが存在しない場

2．3 拡張合には，分離が失敗したことになるので，BRANCH

文献［11］に示された分割アルゴリズムの効率性の改善方法について述べる．rの列を多面体P′の端点の操作を実行しなければならない．
まの凸分割が存在しない場合には，烹≠rとなり，みに限定する効果について考えてみよう．まず最初に，ファルカスの定理によって烹をrから分離する超平分割を見出すことができない場合には，われわれの目面が得られる．特に，rの各行′に対してα巨≧αで的が達成されないように思えるかも知れない．しかしあって，しかもα烹＜αとなるようなベクトルαとスながら，われわれが分割を見出せない場合に生成されカラーαが存在しなければならない．この不等式はたファルカスのカットを用いることによってまをP′

式（9）に定義されたLP問題を解く際の基底逆行列に対から分離することができ，さらにCUT操作としても応するので，ただちに得られる．

利用することができる．この基本的なアプローチは，行列Tの処理に関しては2種類の方法が存在する．

一つは行列rの列集合を限定することである．烹の文献［2］にあるTSPに対する妥当な不等式を生成する場合にも利用することができる．

凸結合であるツア′はすべて烹に適合していなけれ次にコストが現在の上界値に等しいか，それより小ばならない．すなわち′は，まe＝1のときはいつもJe

さい場合の解の付随ベクトルの凸包として定義される＝1，烹e＝0のときはfe＝0を満たさなければならな多面体P′′について考えてみよう．P′′⊆P′はただちい．このようにして，これらの規定がrのすべてのに待られるが，さらにmin（cx：X∈P，）＝min（cx：X列に対して成立することが必要となる．烹の分数支∈P′′）も容易に得られる．このようにして，われわれ持部分である，0＜烹e＜1を満たすような枝集合は要は数え上げ操作をコストが現在の上界値より小さいよ

素数が少ないので，深さ優先探索法を用いてrを明うな列のみに限定した場合にも，妥当なファルカスの示的に生成することによってすべてのツアを数え上げ不等式を生成することができる．

rが空集合になる場合に，数え上げが点に限定さることが可能となる．この方法の短所は，ファルカス取り出され なければならず，しれるとどうなるかを考えてみよう．この場合，アルゴかもそれは計算上かなり困難であるということである．

リズムによって，コストが現在の上界値より小さいともう一つのアプローチは，列生成法を用いてrをきには現在の分数解と適合するような実行可能解が存暗示的に処理するということである．ここでrは最在しないことが証明される．したがってこの場合には，初はツアの部分集合族のみからなるため，アルゴリズ

次のような非列カット（no−COlumns cut）を導入す

ムは前と同様に進行し，烹がrの列の凸結合であるる．の不等式がすべてか否かを求めることになる．凸表現がrの列の中に求められた場合，ツアの一部分が容量制約を満たさないかどうかを調べる．容量制約を満たさない場合にはCUT操作を実行する．前と同様にして，既知のツアを用いて￡の凸結合が存在しない場合には，ファルカスの定理によって，Tの各列fに対してα巨≧αであって，しかもα烹＜αとなる組（α，α）が得られる．

ここでTSP最適化手法を用いてコストベクトルαに関してr上で最小化操作を行う．′＊が最適ツアの付∑∴‰−∑∬e≦凪ト1．

（10）

e：烹g＝1 （ヲ：ゴビ＝0

これらのカットは文献［5］にある仮想ツア（hypo−tours）の特別なケースである．実行可能性とコストの両者に基づく列生成を行うと，常にこれらの不等式の一つを生成することができる．このことを確かめるには，rが多面体P′′の端点のみからなるとしよう．
このとき，これらの各列によって新たな上界値を得ることができ，さらにそれをrから削除し，rを空集合にすることが可能となる．

随ベクトルであるとしよう．このとき，α′＊＞αならば，最小化操作によってα∬≧αがまをrから分離するため，この不等式がCUT操作に用いられる．また
αf＊＜αの場合には，J＊はrの列には存在しないため，′＊がTに追加され，烹の凸分割がrの列から得られるか否かを再び求めることになる．この手順は分割が見つかるか，または烹≠rが証明されるまで

3．計算結果分離ルーチンはRalphs［18］，Lad畠nyi［12］らによる遺伝的並行分岐カットによって構成されたSYM−PHONYの中に組み込まれている．この方法の実施
結果については文献［13］に示されている．われわれのテスト集合はTSPLIB［20］から取られた中規模の繰り返される．
2003年12月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）92丁VRP問題とAugerat［3］による問題からなる．この［8］N．Christ6desandS．Eilon：AnAlgorithmforthe

論文に用いられた完全なテスト集合とソースプログラ

Vehicle Dispatching Problem，（砂emtionalReseanh

ムのコードはhttp：／／www．branchandcut．org／VRP

勧研如動20，pp．309−318，1969．

［9］G．Cornu6joIsandF．Harche：PolyhedralStudyofから得られる．

この集合にある10個の問題は文献［8］のChristofidesとEilonによって用いられたもので

theCapacitatedVehicleRoutingProblem，Mathemati−∽JP和好用∽∽Z刀g，60，pp．21−52，1993．

［10］G．B．Dantzig and R．H．Ramser：The TruckTSPLIBにあるVRP問題例にも含まれている．また

DispatchingProblem，Mandgement Science，6，pp．80−

3題（E−n76−k7，E−n76−k8，E−nlOl−k8）は80台91，1959．のプロセッサによるIBMSP2並列コンピュータ上で［11］L．Kopman：A NewGenericSeparation Routine

SYMPHONYの並列版を用いて最初に解かれたもの

andItsApplicationinaBranchandCutAlgorithmforである．最近BlasumとHochstattlerは追加的カッthe Vehicle Routing Problem，Ph．D．Dissertation，

ト平面法［6］を用いて単一プロセッサ上でE−n76−k7
and E−n76−k8を解いた．われわれもE−n76−k7を直列的に解いたが，より大きなツリーを必要とした．
われわれが知っている最小の問題例で未解決の問題がB−n50−k8であることは重要であろう．われわれはトラック容量が150に増加した場合のこのモデルを解

Field of Operations Research，CornellUniversity，
Ithaca，NY，USA，1999．

［12］L．Ladanyi：ParallelBranch and Cut andIts
ApplicationtotheTravelingSalesmanProblem，Ph．
D．Dissertation，FieldofOperationsResearch，Cornell
University，Ithaca，NY，USA，1996，［13］L．Lad畠nyi，T．K．Ralphs，and L．E．Trotter：
Branch，Cut，and Price：Sequentialand Para11el，

いたが，原問題については未解決である．

ComputationalCombinatorialOptimization，D．Nad−
参考文献

defandM．Junger，eds．，Springer，Berlin，pp．223L260，

2001．
［1］）．R．Araque，L．Hall，andT．Magnanti：Capacitat−［14］G．LaporteandY．Nobert：Comb．Inequalitiesfor
edTrees，CapacitatedRoutingandAssociatedPolyhe−dra，Discussionpaper9061，CORE，LouvainLaNueve， theVehicleRoutingProblem，Methods〆（砂eYations
斤どぶgα汀ゐ，51，pp．271−276，1981．

1990．

［15］G．Laporte，Y．Nobert，andM．Desrochers：Opti−［2］D．Applegate，R．Bixby，Ⅴ．Chvまtal，andW．Cook：
malRoutingwithCapacityandDistanceRestrictions，
TSP CutsWhich Do Not Conform to the Template
Paradigm，CompuiationalCombinatoYial（砂timization，（砂g和才わ乃5月β5gα汀ゐ，33，pp．1050−1073，1985．

［16］A．N．Letchford，R．W．Eglese，andJ．Lysgaard：
D．Naddef and M．Jtinger，eds．，Springer，Berlin，pp．
Multistars，PartialMultistars and the Capacitated

26ト303，2001．

［3］P．Augerat：VRPprobleminstances，Availableat
http：／／www．branchandcut．org／VRP／data／，1995．

VehicleRoutingProblem，TechnicalReportavailable
at http：／／www．lancs．ac．uk／staff／1etchfoa／pubs．htm，［4］P．Augerat，J．M．Belenguer，E．Benavent，A．Corber− 2001．
an，andD．Naddef：SeparatingCapacityConstraints［17］H．Nagamochiand T．Ibaraki：Computing Edge
intheCVRPUsingTabuSearch，Euプ1坤eanJoumal〆（砂β和才わ乃5月β5βαⅣゐ，106，pp．546−557，1998．

ConnectivityinMultigraphsandCapacitatedGraphs，ぷA〟ノ0〟γ犯αJ〆βゐc柁′βルね′ゐe椚α′gα，5，pp．54−66，［5］P．Augerat，J．M．Belenguer，E．Benavent，A．Corber− 1992．
［18］T．K．Ralphs：ParallelBranchandCutforVehicle
まn，D．Naddef，andG．Rinaldi：ComputationalResults
With a Branch and Cut Code for the Capacitated
Vehicle Routing Problem，Research Report949−M，UniversiteJosephFourier，Grenoble，France，1995．

［6］u．BlasumandW．Hochstattler：ApplicationoftheBranchandCutMethodtotheVehicleRoutingProb−Routing，Ph．D．Dissertation，Field of Operations

Research，CornellUniversity，Ithaca，NY，USA，1995．
［19］T．K Ralphs：SYMPHONY Version2．8User
SYMPHONY，2001．

1em，Zentrum ftir AngewandteInformatik，K81n， ［20］G．Reinelt：TSPLIB，A traveling salesman prob−
1emlibrary，ORSAJoumalon Con4）uting，3，376−384．
TechnicalReportzpr2000−386，2000．

［7］Ⅴ．Campos，A．Corberan，andE．Mota：Polyhedral
Results for a Vehicle Routing Problem，助rt4）ean

Update available at http：／／www．iwr．uni−heidelberg．
de／iwr／comopt／software／TSPLIB95／，1991．

ノb〟7ⅥαJ〆（砂g和才わ紹5月彷gαⅣゐ，52，pp．75−856，1991．

928（52）sGuide，Available at http：／／www．branchandcut．org／© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ