----------------------------------------------------
発表者：浦田
論文：
Fukasawa, R., Longo, H., Lysgchoa, E., Werneck, RF. : Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Mathematical Programming, Vol. 106, No.3, pp. 491-511, 2006.
(配送経路の最適化)
----------------------------------------------------

■はじめに
何がロバスト？
もともと1959年からvehicle routing problemの問題は取り扱われている．この論文
では2004年に登場したbranch-and-cut-and-priceの解き方を少し変えたもの
ブランチ=枝をどう分割するか
カット=グラフ理論における分割集合
プライス=ラグランジュの未定乗数法でλを求めて重みづけ

■条件設定
センターのデポから出発してデポに帰っていく．
ネットワークG=(V,E)，車の数，頂点Vの数(エッジE)，需要，キャパシティデータを
与えて14経路を最適化．
切れるというのがポイント．

今泉：
あらかじめ通らないといけない経路があって，それを制約条件に組み込めば使えそ
う．
羽藤：
l_e*x_eが維持管理コストだからどう設定するか．

■column generation
上位問題：K台の選択ルートの距離の最小化
下位問題：距離の短いルート群の生成
・容量cを横軸，頂点を縦軸にとった行列Mで頂点vまでの道とその際の総需要dを表
す．
・DPで道を形成していく
w(vの近傍点)をvの次に追加するかどうかを判断して加えていく．
行列の中の点の数がnc個なのでnc回繰り返せば道が1本できる．ルートの本数はn本で
きるのでcn^2回で計算可能．


■column generationの高速化：
削除：通過点を記憶して閉路となっているかを判断
○ヒューリスティック加速
sparsification：1つのグラフを5つに分割し，Spanning treeをあらかじめ設定す
る．

■Cut generation
カットセットの辺の数を置いていたが，そのカットセットの生成を行う．
周回容量制約に最適化計算の制約条件ではなく，別途アルゴリズムを設定する．
切断集合に属するための条件・Mが与えられた時のS,yを抽出する条件を制約条件とし
て出入りの辺の数を最小化する．

■質疑
藤垣：
車両数は外生的に与えているのか．
浦田：
与えている．ただ車両数を5,6,7..のように変えたときの比較を行うことは可能．
仲西：
結果としてどのくらい違うのか気になる．
羽藤：
OR系の場合はどういう風に計算するかというのが受ける．
今泉：
容量の固定が前提だが，本当は色々あって，各車両のルートの最適化は行えるのか．
浦田：
複数台でも計算可能．今泉の場合は大きいところは大きい車両で，小さいところは小
さい車両でというように分けることを考えている．
羽藤：
首都圏で解くにしろ，神戸で解くにしろ，解法の特徴はおさえておくといい．
伊藤：
デポが複数になったらどうなるのか．圏域内で回るのが最適なのか他の圏域に移るの
が最適なのか．
浦田：
デポが複数の場合も存在する．ただあまりORではやられていない．
伊藤：
容量が100から10になった時に何回もまわることはあるがそうした問題はあるのか．
羽藤：
台数が少ないときにどう会員を集めるか．
浦田：
multi-commodityだと複数のルートを回った方が最適であるという結果が出ている．
羽藤：
問題を出すのは我々の分野では必要．今泉と若林はお互いに確認し合った方がいい．
羽藤：
避難は現状分析までしかできていないのでオペレーションを考えることはDaganzoの
ように新しい．
仲西：
社会基盤では内村さんとかがやっていた．
藤垣：
spaning treeは大学院の授業で貞広先生がやっていた．
羽藤：
ORみたいな話を都市に適用する場合，誰でもわかるようなレベルまで落として説明し
ながらも，このアルゴリズム萌えるよねみたいな話ができるといい．実装結果を見せ
るのが分かりやすい．