Line Messaging API × Google Maps API × pulpによる数理最適化で旅行プラン提案LINEBotを作る

自己紹介

普段は趣味でUnityを使ったゲームを作っています。
今回紹介するのは、先日たまたま参加したハッカソンで作ったLINE Botについてです。

普段は開発して途中で投げちゃうことも多いのですが、たまたま頭にインスピレーションがびびっと来て我ながらいいアイディアだと思ったのと、ちょうどLINE BOOT AWARDSというイベントもあったので完成まで頑張ることにしました。

作ったものについて

QRコード

旅程提案Bot「旅のおとも」

旅のおともくん(エントリーページ)

スクリーンショット

なにができるの？

暇な休みにちょっと遠出したい！けど計画を立てるのは面倒、、、というときに「旅のおともくん」にLINEのメッセージを送ると怠惰なユーザーの代わりに旅行のプランを考えてくれます。
伝えるメッセージはほんの数文で
「旅行行きたい！大阪！五時間くらい！」

これくらいです。メッセージを送ると一瞬~数十秒で「旅のおともくん」がイイ感じに旅行のプランを提案してくれます。うーん、イマイチというときにプランを再度提案してもらうことも可能です。

また、旅行のプラン提案とは別に自分のお気に入りスポットと「旅のおともくん」に覚えてもらうことが可能です。覚えてもらったスポットは以降の旅行プランの提案の際に参考にされます。

なぜ作ったの?

まず、なんでLine BotなのかというとLINE Botを作ってみようという感じのハッカソンに参加したからです。

じゃあなんでこのアイディアにしたかというと、
もともと、自分の専攻が数理最適化で整数計画問を利用したサービスが作りたかったってのがあり、なんとか数理最適化使えないかなーと考えているときに

1. 自分は旅行に行くのは好きだが、予定を立てるのはキライ
2. 旅行先のスポット、スポット間の経路はGoogleMapのAPIとかでなんとかなりそう
3. スポットとスポット間の経路があるなら、グラフの経路計画問題みたいなのができるんじゃね？

と閃いたからです。昔にPython+PuLPによるタダで仕事に使える数理最適化といったpythonで数理最適化を扱う記事をQiitaで見ていてなんかできそう...!!と思ったのも理由です。

一押しポイント

とにかく手軽に使えるということを意識しました。旅行において個人が重視することなんて個人差がありすぎるので、各人に対する最適なプランを自動で提案することはぶっちゃけ厳しいです。というかそれができたら旅行代理店とかの存在意義がなくなります。

また、今の世の中でLINEかなり多くの人が日常的に利用しており、似たようなサービスがWebサービスとしてあったとしても、手軽さ、とっつきやすさLINEが勝るんじゃないかなーと思います。

とりあえずLINEを開いてBotに一言二言つぶやくだけでなんかいい感じのプランが返ってくる。この手軽さがこのサービスの強みです。

採用した技術

全体構成

バックエンド環境としてとりあえずHerokuにPythonのFlaskフレームワークを載せています。
ユーザから[行きたい県,時間]のリクエストが来ると、まずDBから対象の県にある旅行スポットを取り出します。次にその旅行スポットの緯度経度、評価情報がNullの場合はGooglePlacesAPIを叩き、上記の3つの情報を取得します。
次に、リスト化したスポット間を移動する際にかかる時間をGoogleDirectionsAPIを用いて計算します。
以上の操作により,スポット(点)とスポット間の移動時間(辺)情報が得られるため、これらをグラフとしてみなした数理最適化問題をpythonのパッケージであるpulpを用いて記述し、数理ソルバーであるCOINを使って処理しています。計算した結果はまたpythonを用いて取得し、LINE Messaging APIのflex messageを用いて整形し出力します。

LINE messaging API

だいたい以下の記事を参考にさせていただきました。
- LINE Messaging API でできることまとめ【送信編】
- 1時間でLINE BOTを作るハンズオン (資料+レポート) in Node学園祭2017 #nodefest

Google Maps API

参考になったのは以下の記事です。Direction APIについてあんまり記事がないなーと思っていたら2日前に2つ目の記事ができていたみたいです。もう少し早く書いてくれたら...（他力本願）
- Google Map Directions API で日本国内の路線検索はできない
- Directions API(Google Maps Platform) をコールしてルート間の距離と所要時間をPythonで取得する
今回はテキスト検索による位置特定、レーティング値の取得をPlaceAPIを使って取得し、二点間を移動する際の所要時間をDirectionsAPIを用いて取得しました。

import requests
import urllib
import json
import APIkey
import re


# 位置座標クラス
class MapCoordinate:

    def __init__(self, latitude, longitude):
        self.latitude = latitude
        self.longitude = longitude

    def position(self):
        return "{0},{1}".format(self.latitude, self.longitude)
# ルートクラス
class MapRoute:
    mode_driving = "driving"
    mode_walking = "walking"
    mode_bicycling = "bicycling"
    mode_transit = "transit"

    def __init__(self, src, dest, mode):
        self.src = src
        self.dest = dest
        self.mode = mode
        self.lang = "ja"
        self.units = "metric"
        self.region = "ja"



def getGoogleMapDirection(route):
    # Goolge Map Direction API トークン
    api_key = APIkey.googleAPIkey
    # Google Maps Direction API URL
    url = "https://maps.googleapis.com/maps/api/directions/json"

    try:
        q = {
            'origin': route.src.position(),    # 出発地点
            'destination': route.dest.position(),  # 到着地点
            'travelMode': 'driving',  # トラベルモード
            'key': api_key
        }

        s = requests.Session()
        r = s.get(url, params=q)
        json_o = r.json()
        print(url)
        return json_o

    except Exception as e:
        raise e

def getPathromGoogleAPI(fromplace,toplace):
    src = MapCoordinate(fromplace[0], fromplace[1])
    dest = MapCoordinate(toplace[0], toplace[1])
    route = MapRoute(src, dest, MapRoute.mode_transit)

    direction_json = getGoogleMapDirection(route)
    duringtime = direction_json['routes'][0]['legs'][
        0]['duration']["value"]  # これで２点間を車移動したときの秒数が入る

    return duringtime


def getPointFromGoogleAPI(PlaceName):
    place_url = 'https://maps.googleapis.com/maps/api/place/textsearch/json'
    query = {'query': PlaceName,
            'language': 'ja',
            'key': APIkey.googleAPIkey}
    s = requests.Session()
    s.headers.update({'Referer': 'www.monotalk.xyz/example'})

    r = s.get(place_url, params=query)
    json_start = r.json()

    if (json_start['status'] == 'ZERO_RESULTS'):
        return None,None,None
    # print(json.dumps(json_start,ensure_ascii=False, indent=2))

    location = json_start["results"][0]["geometry"]["location"]
    return float(location["lat"]),float(location["lng"]),float(json_start["results"][0]["rating"])

数理最適化

• pythonで数理計画問題を扱うために参考にしたのは以下の記事です。
• Python+PuLPによるタダで仕事に使える数理最適化

数理最適化では、なにかの入力から出力を得るために、求めたい値(決定変数)、判断評価基準(目的関数)、守るべき条件(制約条件)の3つを定める必要があります。

例えば、非常に簡単な二変数の二次関数を使って数理最適化を行う場合以下のようになります。

要素	式(変数)
決定変数	$$ x , y \in \mathbb{R} $$　0-1のbinary型,整数値,実数値が主に利用される
目的関数	$$ x^2 +y^2 $$を最大化する。最小化する場合もある
制約条件	$$ 0 \leq x \leq 1 , 0 \leq y \leq 1 \ x,y \in \mathbb{R} $$ 問題によって制約の数や形はことなる

定式化

maximize x^2 +y^2 \\
0 \leq x \leq 1 \\
0 \leq y \leq 1 \\
x,y \in \mathbb{R}

今回は,旅行先スポットとスポット間の移動距離がグラフ$$G=(N,A)$$として与えられたときにひとつながりの旅行パスを出力したいので、決定変数と目的関数は以下のようにしました。

要素	式(変数)
決定変数	$$ x_{i,j}\in { 0,1 } $$　旅行スポットiからjへ,もしくはその逆に移動するとき1になる変数$$ y_{i}\in { 0,1 } $$　旅行スポットiへ訪れるなら1になる変数
目的関数	$$ \sum_{i=0}^{location} v_{i}y_{i} $$訪れるスポットに評価値をかけたものの和を最大化

定式化

以上の表記を用いた定式化は以下になります。

maximize \sum_{i=0}^{location} v_{i}y_{i} \\

\sum_{i=0}^{location}\sum_{j=0}^{location}x_{i,j}movetime_{i,j} + y_{i}stayTime
\leq travelTime  \\

x_{i,j} + x_{j,i} \leq 1\\
x_{i,j}  == 0 \\

\sum_{j=0}^{location}x_{j,i} - \sum_{k=0}^{location}x_{i,k} \geq 0 \\

\sum_{j=0}^{location}x_{j,i} \leq y_{i} \\
\sum_{j=0}^{location}x_{i,j} \leq y_{i} \\
\sum_{i=0}^{location}y_{i} - \sum_{i=0}^{location}\sum_{j=0}^{location}x_{i,j}movetime_{i,j} == 1 \\
x_{i,j},y_{i} \in \{0,1\}

movetime,syayTime,travelTimeはパラメータで,それぞれ二点間の移動にかかる時間,スポットに滞在する時間,旅行全体の時間を表しています。

式一つ一つについての説明は今回は省かせていただきますが、大雑把にいうと
$$x_{i,j}movetime_{i,j}$$がスポット間の移動距離、$$y_{i}stayTime$$がスポットの滞在時間で、この和が旅行の予定時間であるtravelTimeを超えないように、一筆書きで、評価が高くなるよう$$x_{i,j}$$の組み合わせを選ぶ組み合わせ最適化問題みたいな問題が上の式になります。

定式化は、pythonのpulpパッケージを使うことでリストや内包表記を用いて簡単に書くことができます。また完成した定式化は同じくpulpを使って内蔵している数理ソルバーのCOINにわたすことで、COINが内点法(シンプレックス法)とかを用いて計算してくれます。計算結果は同じくpython内でオブジェクトとして受け取ることが可能です。

pulpによる定式化

参考までに、以下に実データを用いた定式化と出力を載せます。見やすくするために,2頂点1辺が与えられた場合の定式化となっています。

def calcPath(location, e, c, time, stayTime):
    # 最適化問題を解く
    problem = pulp.LpProblem('sample', pulp.LpMaximize)
    # -------------------------------------------
    # 決定変数定義
    # -------------------------------------------   
    x = { (i, j) :pulp.LpVariable("x({:},{:})".format(i, j), 0, 1, pulp.LpInteger) for i in location for j in location}
    y = { i : pulp.LpVariable("y({:})".format(i), 0, 1, pulp.LpInteger) for i in location}
    # -------------------------------------------
    # 目的関数設定
    # -------------------------------------------   
    problem += pulp.lpSum(c[i] * y[i] for i in location), "TotalCost"
    # -------------------------------------------
    # 制約式
    # -------------------------------------------   
    # 全体時間制約
    problem += sum(x[i, j] * e[i,j] for i in location for j in location) + \
        sum(y[i] * stayTime for i in location) <= time, "Constraint_leq"
    # 単方向制約
    for i in location:
        for j in location:
            problem += sum(x[i, j] + x[j, i]) <= 1, "Constraint_leq_{:}_{:}".format(i, j)
    # 自身パス除去制約
    for i in location:
        problem += x[i, i] == 0, "Constraint_node_eq{:}".format(i)
    # 接続制約
    for i in location:
        problem += sum(sum(x[j, i] for j in location) - sum(x[i,k]  for k in location)) >= 0, "Constraint_node_{:}".format(i)
    # y起動制約
    for i in location:
        problem += sum(x[i, j] for j in location) <= y[i], "Constraint_node_y_{:}".format(i)
    for i in location:
        problem += sum(x[j, i] for j in location) <= y[i], "Constraint_node_y_r_{:}".format(i)
    # 部分巡回路除去制約
    problem += sum(y[i] for i in location) - sum(x[i, j] for i in location for j in location) == 1, "Constraint_eq2"

    # -------------------------------------------
    # pulpを用いた求解
    # -------------------------------------------  
    status = problem.solve()
    print("Status", pulp.LpStatus[status])
    print(problem)

    for i in location:
        for j in location:
            print (x[i,j], x[i,j].value())

    for i in location:
        print (y[i], y[i].value())


    return x, y

テキスト出力した式

 MAXIMIZE
 8.5*y(井の頭恩賜公園) + 8.6*y(国立科学博物館)

 SUBJECT TO
 2683 x(井の頭恩賜公園,国立科学博物館) + 2683 x(国立科学博物館,井の頭恩賜公園)
 + 3600 y(井の頭恩賜公園) + 3600 y(国立科学博物館) <= 18000

 x(井の頭恩賜公園,井の頭恩賜公園) <= 1
 x(井の頭恩賜公園,国立科学博物館) + x(国立科学博物館,井の頭恩賜公園) <= 1
 x(井の頭恩賜公園,国立科学博物館) + x(国立科学博物館,井の頭恩賜公園) <= 1
 x(国立科学博物館,国立科学博物館) <= 1

 x(井の頭恩賜公園,井の頭恩賜公園) = 0
 x(国立科学博物館,国立科学博物館) = 0

 x(井の頭恩賜公園,井の頭恩賜公園) + x(井の頭恩賜公園,国立科学博物館) + x(国立科学博物館,井の頭恩賜公園) >= 0
 x(井の頭恩賜公園,国立科学博物館) + x(国立科学博物館,井の頭恩賜公園) + x(国立科学博物館,国立科学博物館) >= 0

 x(井の頭恩賜公園,井の頭恩賜公園) + x(井の頭恩賜公園,国立科学博物館) - y(井の頭恩賜公園) <= 0
 x(国立科学博物館,井の頭恩賜公園) + x(国立科学博物館,国立科学博物館) - y(国立科学博物館) <= 0
 x(井の頭恩賜公園,井の頭恩賜公園) + x(国立科学博物館,井の頭恩賜公園) - y(井の頭恩賜公園) <= 0
 x(井の頭恩賜公園,国立科学博物館) + x(国立科学博物館,国立科学博物館)- y(国立科学博物館) <= 0

 - x(井の頭恩賜公園,井の頭恩賜公園) - x(井の頭恩賜公園,国立科学博物館) - x(国立科学博物館,井の頭恩賜公園) - x(国立科学博物館,国立科学博物館) + y(井の頭恩賜公園) + y(国立科学博物館) = 1

解の出力

 x(井の頭恩賜公園,井の頭恩賜公園) 0.0
 x(井の頭恩賜公園,国立科学博物館) 1.0
 x(国立科学博物館,井の頭恩賜公園) 0.0
 x(国立科学博物館,国立科学博物館) 0.0
 y(井の頭恩賜公園) 1.0
 y(国立科学博物館) 1.0

今後の展望

今回作成したLINEBotについて、最終的には旅行プランに関する総合プラットフォームを目指しています。とりあえず今後実装予定の機能としては以下を予定しています。
- 市,町単位の検索
- 移動手段に徒歩を追加
- スポットの羅列で旅行プランを提案可能に
- 旅行プランの登録と登録したプランを提案
- 「大阪旅行 by tomotan」 みたいなタイトルで
- ユーザーによる滞在時間の設定
- スポットと旅行プランの☆評価(1日一回とか)
- 現在地を考慮した旅行プランの提案
- LINEのリッチメニューの実装

最後に

なにかいいアイディアとか、間違っているところがあれば指摘の方をお願いします。