Setawalk

概要

これは、私がコンピュータサイエンスの学位取得に向けた最終卒業プロジェクトとして、4人のチームで開発したものです。私は主にバックエンドのデータベースと経路探索アルゴリズムを担当し、開発作業の約80％を担いました。

このプロジェクトの目的は、単に目的地への最短ルートを探すのではなく、周辺を探索したい人向けのナビゲーションアプリを作成することでした。

「Setawalk」では、ユーザーは出発地と目的地を選択し、さまざまなカテゴリの観光スポットに対する好みを調整することで、道中で立ち寄って楽しめそうな場所を取り入れた徒歩ルートを生成することができます。

バックエンドでは、PostGIS および pgRouting を備えた PostgreSQL を使用して、地理データを保存し、徒歩ルートを計算しています。

OpenStreetMap のデータを PostgreSQL データベースにインポートし、歩行者ルートネットワークとして処理しました。注目地点は別途保存され、最も近い歩行者ルートノードを指すレコードが割り当てられました。

これらの注目地点を接続するために、デローネイ三角分割を用いてグラフが生成されました。その後、各接続には、ダイクストラのアルゴリズムを用いて pgRouting で計算された徒歩距離が関連付けられました。

これにより、アプリケーションは注目地点を「立ち寄りの候補となる地点のネットワーク」として扱いながら、それらの間の実際の徒歩経路の計算には、基盤となる歩行者ネットワークを引き続き利用できるようになりました。

経路生成アルゴリズムは、一般的な最短経路探索と、ユーザーの好みに基づくPOI（注目地点）の選択を組み合わせています。

出発点と目的地が指定されると、アルゴリズムはまず点Aと点Bの間に「直線距離」の直線を生成します。次に、出発点をナビゲーションネットワーク上の最も近いノードに変換し、進行方向にある各潜在的なPOI接続先へのダイクストラ経路を生成します。

続いて、アルゴリズムは以下の要素に基づいてPOIの立ち寄り先を選択します：

各カテゴリに対するユーザーの嗜好。
各カテゴリの相対的な充足度。
検討対象のPOIと目的地との相対的な角度。
現在のPOIからの距離。
目的地までの残り距離。このアルゴリズムは、ルートの進行に伴い、直線からの許容偏差を徐々に縮小します。これにより、旅の序盤では探索を促進しつつ、最終的には目的地へと戻るルートを確保します。

また、サティエティシステムにより、すでに訪問済みのカテゴリに対する実質的な選好度が低下し、ユーザーの選好に比例して多様な場所をルートに含めるよう促します。

フロントエンドはFlutterを使用して開発され、地図の可視化や位置検索のためにGoogle Mapsと連携しています。

Supabaseを使用してバックエンドと通信し、経路生成のリクエストや、ユーザーの好みを経路生成システムへ渡すなどの処理を行っています。

アプリケーションは、クライアント側で返された経路の座標を処理し、歩行距離、推定所要時間、およびターンバイターンの案内を算出します。方向転換は、経路に沿った方向の変化を分析することで検出されます。

このプロジェクトを通じて、バックエンドとフロントエンドの両方にわたるGISアプリケーションの設計および実装の経験を積むことができました。

空間データベース、PostgreSQL、グラフベースの経路探索、そして従来のナビゲーションを超えたアプリケーションをサポートするために地理データをどのように処理できるかについて、より深い理解を得ることができました。

また、アプリケーションのロジックの大部分をデータベースが担うプロジェクトの開発経験も得ることができました。