OptaPlannerで百名山最短経路で制覇を妄想する

こんにちは。年末になり、今年は仕事でもプライベートでもチャレンジングな事があまり無くて、ぱっとしない一年だったなぁと振り返り中のレッドハット長谷川です。

はてさて、仕事はさておき、プライベートでチャレンジングな事があまり無かった理由の1つは、去年から始めたばかりのチャレンジングな山登りに、今年はたった4回しか行けなかったからだと勝手に考えています。

ということで、今年の山行回数に物足りなさを感じる私は、仕事中の得意技である妄想を発動して、このvoidを埋めようとしています。先日、「あーあ、1年くらい休みとって、百名山制覇とか、やってみたいわー」と妄想していると、ふと、1つの疑問が。

「1年で百名山制覇となると、最短経路で百名山を移動しないとなぁ、でも、最短経路ってどんなんだい?」

はい、後付け的前振りは、ここまで。
OptaPlannerに私の妄想を深掘りしてもらいましょう!!
# 私の妄想を文章化してるだけですが、一応、赤帽エンジニアAdvent Calendar 2018の25日目の記事です。

OptaPlanner

f:id:yhasegaw:20181225122125p:plain

OptaPlannerとは、私の理解で言い表すと、「膨大な組み合わせの中から最適解を見つける為に、良さ気な組み合わせを沢山自動で作って、その組み合わせを自分の好きな様に評価して、最適解を導出する」Javaソフトウェアです。
# Red Hat Decision Managerにバンドルさてれいます。

例えば、今回の百名山最短移動経路を求めたい場合、考えられる経路(=組み合わせ)の数は、100の階乗となり、とてつもない桁の数になってしまい、このような膨大な組み合わせの中から1つ1つの組み合わせを調べて最適解を見つけるのは、とてつもない時間がかかってしまう。そこで、ちょっと工夫して何とか良さ気な最適解をより短時間で見つけよう、というのが、OptaPlannerの実現する価値となります。

経路探索だけではなく、OptaPlannerでは、シフト表作成、ジョブスケジューリング等、組み合わせ数が膨大になる問題を解決出来ちゃうようになります。

では、OptaPlannerでは、どんな工夫をして最適解を導出しているのか? 色々と工夫点はあるのですが、今回は、メインとなるLocal Searchの説明をしたいと思います。

Local Search

Local Searchは、日本語訳では局所探索法となり、1つのたたき台となる組み合わせ(=初期解)をベースに、異なる組み合わせを生成、評価し、良さ気な組み合わせを見つける。そして、この良さ気な組み合わせを新たな初期解として、このサイクルを繰り返すことにより、最適解を効率良く見つけようとする手法です。

はい、文章だと自分でもよく分からないので、百名山最短移動経路の場合を例に、私の脳内イメージをダンプしてみます。

最初に、何かたたき台となる初期解経路を用意します。初期解は、OptaPlannerのConstruction Heuristicsを使用することにより求めることが出来ますが、説明していると25日中に記事をpublish出来ないので、後日紹介したいと思います。今すぐ知りたいという方は、OptaPlannerのドキュメントをご参照下さい。

その初期解経路を元に、異なる組み合わせを生成します。例えば、下の図でいうと、A→B →C→Dという初期解経路があったとすると、AをCの後にMove(移動)させてみたり、AとCをSwap(入れ替え)してみたりすることで、異なる経路をOptaPlannerの機能により自動生成します。

f:id:yhasegaw:20181225110851j:plain

次に、生成された経路を評価します。評価は、経路をスコアとして数値化することで行います。どのように数値化するかは、Java or Drools Rule Languageで自由に実装出来るので、好きな制約を適応することが可能です。

例えば、百名山最短移動経路の場合、私は、2つの制約条件をスコア化することにしました。

山と山の間の移動距離が最小であること
最後に訪れる山が、家から一番近いこと(とっとと帰宅したいので)

今回、私の妄想に使用したスコア計算Javaコードは以下になります。やっていることのイメージだけ把握して頂ければと思うので、細かい説明は省きますが、やっていることは、山の位置情報(Location)を緯度経度で持たせておき、そのLocation情報からOptaPlannerが生成した経路の各山間の距離の和をdistanceに格納し、HardSoftLongScoreというスコアを格納するオブジェクトにマイナスのdistance値を設定しています。マイナスのdistance値にするのは、距離が長くなるほど、悪いスコアとする為です。また、1000を乗じているのは、緯度経度の精度を小数点第3位まで考慮する為です。
# 地球の丸みとか、そんなところに道はねーよ、とかは、私の妄想では考慮外なので、あしからず。

public class ScoreCalculator implements EasyScoreCalculator {

@Override
public HardSoftLongScore calculateScore(MountainRoutingSolution solution) {
    double distance = 0;

    RoutingPoint routingPoint = solution.getHomes().get(0);

    while (routingPoint.getNextMountain() != null) {
        distance += getDistanceDouble(routingPoint.getLocation(), routingPoint.getNextMountain().getLocation());
        routingPoint = routingPoint.getNextMountain();
    }

    double goHomeASAP = getDistanceDouble(routingPoint.getLocation(), solution.getHomes().get(0).getLocation());

    return HardSoftLongScore.of(-(long) goHomeASAP, -(long) (distance * 1000));

}

生成された経路にスコア付けが完了したら、次に、スコアをベースに良さそうな経路を選定アルゴリズムが決定し、この経路を新しい初期解経路とします。そして、このLocal Searchの最初に戻って、最適解探索を繰り返し実行していきます。

f:id:yhasegaw:20181225111500j:plain

さて、この選定アルゴリズムが個人的には面白いところで、OptaPlannerでは、Tabu Search、Simulated Annealing、Late Acceptance等の選定アルゴリズムが使用可能です。これらの選定アルゴリズムの何が重要かというと、Local Optimumに嵌ってしまう問題を回避することです。

はい、私の嫌いな小難しい用語です。私の理解で言い表すと、「井の中の蛙問題を回避する」ってところでしょうか。私の脳内イメージは、以下です。
# 図がショボい。。。

f:id:yhasegaw:20181225111537j:plain

Local Searchは、その名前が示すように近傍(=Local)を探索する方式ですので、近傍により良いスコアを持つ解が見つからない場合、その近傍ばかりをグルグル探索して結局、上図の左側のわーいと言っている人の様に、今のベストスコアの解に戻ってしまう可能性があります。しかし、これ、井の中の蛙になっている可能性もあり、より視野を広げて遠方を探索すれば、より良いスコアの解が見つかる可能性もあります。OptaPlannerでは、より視野を広げて遠方を探索する為に、これらの選定アルゴリズムを用いており、ちゃんとより良い解を求める工夫がなされています。

はい、以上、Local Searchの基本イメージを説明しました。1つのたたき台となる組み合わせ(=初期解)をベースに、異なる組み合わせを生成、評価し、良さ気な組み合わせを見つける。そして、この良さ気な組み合わせを新たな初期解として、このサイクルを繰り返すことにより、最適解を見つけようとする手法というのが、イメージ出来てもらえるとありがたいです。が、むずい、と良く言われるので、詳細説明が必要でしたら、Red Hatにご相談下さいませー。Red Hatのルールのお兄さんかセーラームーンが対応してくれる筈!!

で、妄想結果は?

本当は、もっともっと説明したいことがあるのですが、今回は、結果だけ。ついでに、OptaPlannerが出力した経路を、LeafletとOpenStreetMapを使用して可視化してみました。東京恵比寿からスタートするキレイな時計回りの経路が得られてますね、パット見、最短っぽいです。(javascript埋め込み見えるかな?)