OptaPlanner examples その13

OptaPlanner

Traveling tournament problem (TTP)


http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#travelingTournament

各都市の野球チームが、それぞれ都市を訪れ、総当たりでホームアンドアウェイの球場で対戦します。トータルの旅行距離が最小化されるようスケジュールします。

これ「トーナメント（勝ち抜き方式）」じゃなくね？と思ったら、それは日本だけの用法だと知った！ http://ja.wikipedia.org/wiki/%E3%83%88%E3%83%BC%E3%83%8A%E3%83%A1%E3%83%B3%E3%83%88%E6%96%B9%E5%BC%8F

これも最適化界隈ではよく研究対象になる問題のようです。 http://mat.gsia.cmu.edu/TOURN/

  • TravelingTournament : @PlanningSolution
  • Match : @PlanningEntity
    • Day day : @PlanningVariable
    • Team homeTeam
    • Team awayTeam

総当たりなので homeTeam/awayTeam は固定になり、@PlanningVariable は Day だけです。結構単純じゃないですか。ルールもシンプルで分かりやすい。なぜ「Difficult examples」なのか。

localSearch はこんな感じ。

  <localSearch>
    <unionMoveSelector>
      <swapMoveSelector>
        <cacheType>PHASE</cacheType>
        <selectionOrder>SHUFFLED</selectionOrder><!-- TODO with no acceptedCountLimit this should be ORIGINAL -->
        <filterClass>org.optaplanner.examples.travelingtournament.solver.move.factory.InverseMatchSwapMoveFilter</filterClass>
      </swapMoveSelector>
      <moveListFactory>
        <cacheType>STEP</cacheType>
        <selectionOrder>SHUFFLED</selectionOrder><!-- TODO with no acceptedCountLimit this should be ORIGINAL -->
        <moveListFactoryClass>org.optaplanner.examples.travelingtournament.solver.move.factory.MatchChainRotationsMoveFactory</moveListFactoryClass>
      </moveListFactory>
    </unionMoveSelector>
    <acceptor>
      <solutionTabuSize>1500</solutionTabuSize>
      <moveTabuSize>7</moveTabuSize>
    </acceptor>
    <forager>
      <!-- Real world problems require to use of <acceptedCountLimit> -->
    </forager>
  </localSearch>

InverseMatchSwapMoveFilter はホームとアウェイのチームを入れ替えるスワップ。MatchChainRotationsMoveFactory は2日間の対戦組み合わせをぐるっとローテーションさせたり(addDayRotation)、2つのチームをピックアップして、それぞれの Match の対戦相手も含めてローテーションさせたり(addTeamRotation)して、 Move を生成します。この問題ではスワップかローテーションしか、組み替える方法がないからですね。ローテーションはうまく実装しないと、可能な Move を見逃してしまいそうです。

スワップは変化しないので PHASE でキャッシュ。ローテーションは変化するので STEP でキャッシュ。