NP困難の近似最適化について。

質問

整数計画問題で、あるネットワーク中の配送量を最大化する問題です。
小規模ではGLPKというソフトを使って最適値を出すことができました。
しかし、大規模になるとやはり無理でしたので、近似最適化手法を使おうと考えています。

今まで、スケジューリング問題や輸送経路問題でGAやSA、タブサーチなどを使っていますので、その辺のメタ戦略系は少し分かります。

スケジューリングなどはコレとコレを入れ替えるなど、近傍が分かりやすかったのですが、
配送量問題では、拠点１から拠点２の配送量を２０から２１に増やして、拠点４から拠点３の配送量を１８から１７に減らすなど、輸送機器の積載量の制限などがあっても、異常な組み合わせが発生してしまうように感じます。

配送量を１ずつ増やしたり減らしたりする近傍で最適化しようとすると全列挙しているように思えるので、配送量問題でよく使われる近傍というものを教えていただければ嬉しいです。

ちなみに簡単に問題を示しますと、
目的関数：　max　Σ(i→n)Σ(i→n)Σ(k→K)Pijk　（Pijk：輸送機器kが拠点iからjに運ぶ配送量）
制約条件：　Pijk＜Ck　（C：輸送機器kの積載量制限）
　　　　　　Σ(k→K)Pijk＜Dij　（Dij：拠点iから拠点jに運びたい在庫量）
　　　　　　Pijk＞0　（非負制限）
決定変数はPijkです。
簡単に言えばこんな感じですが、本当は少し違います。目的関数以外の項にEjjkというもう一つの決定変数が足されます。
（Pijkはiからjに運びたいと思っている在庫量Dijを運ぶような感じで、Eijkはiからjに運びたいとは思っていないが、別の拠点に運んでおけば次期に運びやすいため運んでしまおうという、目的関数の配送量が増えない配送量です。ここでは１期間で定式化していますが本当は多期間です）

回答No.1

goma_2000

誰も解答していないようなので。参考程度ですが。。。

恐らく、タブサーチ等のヒューリスティクスな手法で、連続値を取り扱うのは無理かと思います。これらの手法は基本的に組み合わせ最適問題に適した手法です。

どうしてもこれらの手法で、という場合に使うトリッキーな方法は、例えば、配送量の桁数がわかっている場合に、それぞれの桁の数値を0-9の離散値だと思い、組み合わせ問題としてとくということを行います。