OptaPlanner examples その3

OptaPlanner

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")
  • 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 が連鎖している問題のために特別に用意されているオプション。連鎖の整合性をチェックしてくれるようだ。

http://docs.jboss.org/optaplanner/release/6.1.0.Final/optaplanner-javadoc/org/optaplanner/core/api/domain/variable/PlanningVariableGraphType.html#CHAINED

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