TPS (Traveling Salesman Problem)
巡回セールスマン問題。組合せ最適化問題の代表例です。
http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3%83%AB%E3%82%B9%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C
- TravelingSalesmanTour : @PlanningSolution
- List
getVisitList() : @PlanningEntityCollectionProperty @ValueRangeProvider(id = "visitRange") - List
getDomicileRange() : @ValueRangeProvider(id = "domicileRange")
- List
- Visit : @PlanningEntity
- getPreviousStandstill() : @PlanningVariable(valueRangeProviderRefs = {"domicileRange", "visitRange"}, graphType = PlanningVariableGraphType.CHAINED)
- City city
ぐっ、パッと見でピンとこない(英語の語彙的に)。PlanningVariable である Standstill は interface で、実装クラスは Visit と Domicile の2種類がある。Domicile がスタート都市(なので1つ)で、 Visit がその他の訪問する都市の意味。それぞれがクラス City を持っていて、都市間の距離計算は City に委譲する。
"graphType = PlanningVariableGraphType.CHAINED" というのは、今回のように PlanningVariable が連鎖している問題のために特別に用意されているオプション。連鎖の整合性をチェックしてくれるようだ。
TspHelloWorld.java は無い。ていうか XXXHelloWorld.java(コンソール実行アプリ)があるのは NQueens と CloudBalance だけだった。必要なら自分で書いてみよう。
ルールは距離を計算するソフト制約だけなので単純ですね。最後にスタート地点に戻るルールを書くので、別クラス(Domicile)にした方がわかりやすかったのかな。
rule "distanceToPreviousStandstill" when $visit : Visit(previousStandstill != null, $distanceToPreviousStandstill : distanceToPreviousStandstill) then scoreHolder.addConstraintMatch(kcontext, - $distanceToPreviousStandstill); end rule "distanceFromLastVisitToDomicile" when $visit : Visit(previousStandstill != null) not Visit(previousStandstill == $visit) $domicile : Domicile() then scoreHolder.addConstraintMatch(kcontext, - $visit.getDistanceTo($domicile)); end