Googleが無料で提供する「最適化問題」ソルバー
本日は、Googleが無料で公開（Apache License 2.0）している最適化問題ソルバー「Google Optimization Tools」を取り上げます。こちら、昨今話題の pokemon GO でも、このRouting使えるんじゃないか、と（ごく一部の特定層の間で）盛り上がっていたりもします。
Google Optimization Tools （＝or-tools）は、「software suite」と表現されています。「Problem Solver（ソルバー）」の集合体と考えるのが良いかなと思います。※少し長いのですが、以下にOverviewを引用しておきます。（英語です。読み飛ばしてもOKです。）色々書かれてますが、要は「いろんな最適化問題を解く為のソルバーだよ」「簡単に使えて、オープンソースだよ」という感じです。
ちなみに、pokemon GOには言及されていませんが、数独（sudoku）に関しては、引用文の末尾で言及されていますので、ご興味のある方はそのあたりだけでもご一読を。
This site provides an introduction to or-tools, Google’s software suite for combinatorial optimization. The suite contains:
- A constraint programming solver.
- A simple and unified interface to several linear programming and mixed integer programming solvers, includingCBC, CLP, GLOP, GLPK, Gurobi, CPLEX, SCIP, and Sulum.
- Knapsack algorithms
- Graph algorithms (shortest paths, min cost flow, max flow, linear sum assignment)
The or-tools suite is:
- Open source and free. Examples and source code are freely available for download under Apache License 2.0.
- Actively maintained. We release improvements several times per month.
- Documented. In addition to this site, there are many examples available in C++, Python, Java, and C#.
- Portable. The code conforms strictly to Google C++ coding style. Everything is coded in C++ and available through SWIG for Python, Java, and .NET (using Mono on non-Windows platforms). It’s known to compile on:
- Ubuntu 12.04 and up (32- and 64-bit)
- Mac OS X with Xcode 5.x (64-bit, Mac OS X 10.9 and up)
- Microsoft Visual Studio 2013 (32- and 64-bit)
- Efficient. We use it internally at Google, where speed and memory consumption are critical.
- User-friendly. We try to make our code as easy to use as possible (especially in Python and C#).
- Well tested. We use it in mission-critical applications at Google, as do many external developers.
If all you need is mixed integer linear optimization, you have a couple of options other than downloading or-tools:
- Use our mixed integer linear optimizer via Google Sheets.
- Use our mixed integer linear optimizer via Google Apps Script.
On this site you’ll find:
- A general introduction to combinatorial optimization.
- Installation instructions for or-tools.
- Code examples in the navigation bar for particular problems you might want to solve.
If you just want to play Sudoku, fire up Google Sheets and install our Sudoku add-on.
適応領域は、いろいろある（ルート最適化が分かりやすいかも）
複数のソルバーからなるGoogle Optimization Toolsは、解決したい問題の種類によって、活用するソルバーが変わります。代表的な問題として、以下が上げられています。
- Linear Optimization：線形最適
- Integer Optimization：整数問題
- Bin Packing：積載効率最適化
- Scheduling：シフト最適化
- Flow Algorithms：流量最適化
- Routing：経路最適化
- Puzzles：（特定条件に基づいた）パズルを解く
今回は、このうち、現実世界とリンクさせて考えやすい「Routing（ルート最適化）」について取り上げてみます。
ルート最適化問題とは？
ルート最適化問題というのは、別にGoogle Optimization Toolsに限った話ではなく、一般的なお話です。要するに、「いくつかの場所を、どういう順番で回ったら良いか」という「ルート」を考えよう、ということですね。分かりやすい。※これがまさに”Pokemon Go”にヒットする、というわけです。
もっとも代表的なモノが、Traveling Salesman Problem（巡回セールスマン問題）と呼ばれるものです。Wikipediaにも、そのものズバリの項目がありますので、引用しておきますね。
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
Routing＝Traveling Salesman Problem と Vehicle Routing Problem
Google Optimization Toolsでは、このRoutingを（超ザックリいうと）2つの問題に分けて捉えています。
ひとつが、先ほども述べたTraveling Salesman Problem （Google Optimization Tools：TSP）です。一人のセールスマンが、複数の地点（客先）を訪問する際に、最適なルート（即ち、合計距離あるいは所要時間等が”最短・最小”になる訪問順序）を求める、というお話です。
もうひとつが、Vehicle Routing Problem （Google Optimization Tools：VRP）です。これは、配送経路問題と呼ばれます。複数の車両（トラックがイメージしやすいでしょうね）が複数の拠点を訪れる場合の、最適ルート（および、各車両に割り当てるべき拠点）を設定する、ということになります。
Routingにおいて設定可能な制約
このRoutingにおいて、or-toolsでは、以下のような「制約」を設定可能です。
- 回るべき拠点数
- 拠点の順序
- 配送する荷物の総量
- それぞれの拠点に配る量
- 各拠点の受取稼働時間
- 各車の最大積載量
- 各車の回れる最大拠点数
- 各車の最大距離
- 各車の最大稼働時間
一般的に必要と思われる要素は、だいたい入っています。無料でここまでできちゃうの？って感じです。
これ、まぢで無料なの？ってくらいに真っ当に動く
現在（2016年7月時点）、弊社、株式会社ギックスにて検証中の段階なのですが、現時点の感想としては「すごいな、これ」です。既存のルート最適化プレイヤーの牙城を破壊しかねないポテンシャルを秘めていると思います。
無料で、この精度を、この処理速度でだせるのは、はっきりいって想定外です。
もちろん、有償のソリューションと比較すると、できないこともあるのですが、自社のサービスにおいて、どの程度の改善余地がありそうかを見積もるくらいなら、まずはGoogle Optimization Toolsを使ってみることから始めるべきでしょう。それを、ためらう理由はありません。（だって、無料だし・・・）※現状は、情報が英語しかないという問題はありますが、そこは気合と根性でなんとか乗り切っていきましょう。笑
Google Optimization Tools に関しては、継続検証中です。続報は、随時お伝えしていきたいと思います。
関連記事：
