RCSPPの改善計画

実務と並行して行っているアカデミック分野でのお話です。 

数理ソルバで鍵となるのる部品の一つは、RCSPPです。Resource Constraint Shortest Path Problem、(制約付き最短パス問題)です。数理ソルバでは、必須の部品になりますが、こちらの改善に手をつけることにしました。Shortest Pathについては、ダイクストラのアルゴリズムが有名ですが、NSPの場合は、一般にこれにリソース制約が加わることになります。カーナビで言えば、単なる最短距離に、コストや、時間といったリソースに制約が追加された問題ということになります。

これによりINRC2での記録更新を狙います。数か月レベルの作業となります。

関連する作業としては、

１）改善RCSPPの定式化　６月

２）Branching　改善　７-8月

３）整数化改善　9月

です。ペアに纏わる部分は、Branchingによるしかないだろうと思っていますが、もしかしたら何か手はあるかもしれません。数理ソルバは、この部分がネックであることが分かっていて、再度トライしてみます。整数化では、今回開発したAL5を使用予定です。

当初より、大幅に遅れ記録更新は、10月を予定しています。

INRC2の後のTargetは、SchedulingBenchmarksのInstance23に挑みます。

COPTのアカデミックライセンスを１年間得て、バリアソルバにより記録更新を狙います。インスタンス23に関しては、恐らく行けると見ていますが、インスタンス24はメモリがネックになる可能性が大で及ばないかもしれません。