今回より2回にわたって、経路探索を紹介していきます。今回は経路探索アルゴリズムの概要とビジネスにおける応用例を中心に、次回はR言語を用いた経路探索の実現方法を、実際の地図データを使って説明します。
1.経路探索について
経路探索問題とは、どのように移動すれば出発地から目的地まで、時間、通行料金、環境負荷など様々な観点で最適なルートとなるのかをコンピュータ上で計算するという問題です。
身の回りで用いられている例は幅広く、例えば倉庫で複数の棚から荷物を取って運ぶ時、どんなルートをたどれば効率が良いのか、あるいは徒歩で駅から目的地へ移動するとき、どのようなルートをたどれば歩く距離が少ないのか等を計算する際に用いられています。カーナビやスマホアプリのルート案内サービスなどでも使われていますので、皆さんが目にする機会も多いと思います。
一般的に出発地から目的地まで到達する経路は無数に存在しますが、経路探索では探索したいルートの中から何らかの基準（時間、通行料金、環境負荷など）で最も望ましい経路を選ぶことで、最終的に経路を１つに絞り込みます。ここでの経路選択基準は、どのような経路を探したいかによって様々です。
例えば、車を運転するときには距離の短い経路、あるいは所要時間の短い経路が望ましいですが、電車の乗り換えの際には料金を重要視することもあります。
表1ではいくつの応用事例を挙げますが、様々な目的で経路探索が利用されていることがご覧いただけると思います。
| 経路探索が用いられる例 | 概要 | |
|---|---|---|
| 1 | 電車の乗り換え案内アプリにおける経路の探索 | 目的地までの膨大な経路の組み合わせの中から、所要時間が最小の経路や、料金や乗り換え回数が最小の経路を探索 |
| 2 | インターネットでのルーティング | Webサイトを閲覧する際、ネットワーク全体で負荷が分散されるように、ネットワーク上の通信経路を探索 |
| 3 | コンピュータゲームにおけるキャラクターの移動経路計算 | コンピュータが操作するキャラクターの移動について、プレイヤーの所在場所やキャラクター同士の相互関係を考慮したうえで、より自然に見える移動ルートを計算 |
| 4 | コンビニの商品配送ルートの決定 | 複数のエリアのコンビニを巡回するトラックに対し、配送時間帯等の制限を考慮しながら効率の良い配送順序を決定 |
| 5 | 災害時の避難ルートの生成 | 危険な場所を避けて通るための制約を加味し、経路の安全性および目的地への到達性の高いルートを速やかに選択 |
この記事は参考になりましたか？
- 意志決定のためのデータサイエンス講座連載記事一覧
-
- 【第九回】経路探索(後編) R言語と地図データによる実行
- 【第八回】経路探索(前編) アルゴリズムとビジネスへの適用
- 【第七回】クラスタ分析 (後編) 「R」を使ったクラスタ分析
- この記事の著者
-
工藤 卓哉 （クドウ タクヤ）
Accenture
Data Science Center of Excellence
アクセンチュア アナリティクス 日本統括
マネジング・ディレクター慶應義塾大学を卒業しアクセンチュアに入社。コンサルタントとして活躍後、コロンビア大学国際公共政策大学院で学ぶため退職。同...※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
-
保科 学世（ホシナ ガクセ）
アクセンチュア株式会社 デジタル コンサルティング本部
マネジング・ディレクター
慶應義塾大学大学院理工学研究科博士課程修了 理学博士。アクセンチュアにてAFS［Accenture Fulfillment Service］、ARS［Accenture Recommend Service］など、アナリ...※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
-
佐伯 隆（サエキ タカシ）
アクセンチュア株式会社 デジタル コンサルティング本部
アクセンチュア アナリティクス シニア・マネジャー
アクセンチュア アナリティクスにおいて、金融機関の合併に伴うデータ統合管理方針策定、通信事業者向けのビッグデータを活用したマーケティング促進システムの構築、公益事業会社向けデータ...※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
-
飯澤 拓 （イイザワ ヒラク）
アクセンチュア株式会社 デジタル コンサルティング本部 シニア・マネジャー
福島大学 経済学部卒業。 SAPなどを活用した大規模基幹システム開発から、ビッグデータを取り扱う分析基盤に至るまで、インフラ・アーキテクチャの設計と実装を専門とする。近年は通信事業者における位置情報データ活用プロジェクトや、...※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
-
党 聡維（ダン コンウェイ）
アクセンチュア株式会社 デジタル コンサルティング本部 コンサルタント
東京大学大学院 情報理工学研究科 博士号取得。大手電気通信会社にて交通運輸分野における研究開発とシステム構築に従事。その後、アクセンチュアに入社し、ビッグデータアナリティクス分野に取り組む。※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
-
田内 真惟人（タウチ マイト）
アクセンチュア株式会社 デジタル コンサルティング本部 コンサルタント
京都大学大学院 人間・環境学研究科修士課程修了後、㈱構造計画研究所を経てアクセンチュア入社。アクセンチュア アナリティクスにおいて、主に小売業、製造業に対するコンサルティング、アナリティクス案件に従事。※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
この記事は参考になりましたか？
この記事をシェア
