Shoeisha Technology Media

EnterpriseZine(エンタープライズジン)

EnterpriseZine(エンタープライズジン)

テーマ別に探す

【第八回】経路探索(前編) アルゴリズムとビジネスへの適用

2015/06/29 14:30

 今回より2回にわたって、経路探索を紹介していきます。今回は経路探索アルゴリズムの概要とビジネスにおける応用例を中心に、次回はR言語を用いた経路探索の実現方法を、実際の地図データを使って説明します。

1.経路探索について

 経路探索問題とは、どのように移動すれば出発地から目的地まで、時間、通行料金、環境負荷など様々な観点で最適なルートとなるのかをコンピュータ上で計算するという問題です。

 身の回りで用いられている例は幅広く、例えば倉庫で複数の棚から荷物を取って運ぶ時、どんなルートをたどれば効率が良いのか、あるいは徒歩で駅から目的地へ移動するとき、どのようなルートをたどれば歩く距離が少ないのか等を計算する際に用いられています。カーナビやスマホアプリのルート案内サービスなどでも使われていますので、皆さんが目にする機会も多いと思います。

 一般的に出発地から目的地まで到達する経路は無数に存在しますが、経路探索では探索したいルートの中から何らかの基準(時間、通行料金、環境負荷など)で最も望ましい経路を選ぶことで、最終的に経路を1つに絞り込みます。ここでの経路選択基準は、どのような経路を探したいかによって様々です。

 例えば、車を運転するときには距離の短い経路、あるいは所要時間の短い経路が望ましいですが、電車の乗り換えの際には料金を重要視することもあります。

 表1ではいくつの応用事例を挙げますが、様々な目的で経路探索が利用されていることがご覧いただけると思います。

表1.身の回りでアルゴリズムによる経路探索が行われている例
  経路探索が用いられる例 概要
1 電車の乗り換え案内アプリにおける経路の探索 目的地までの膨大な経路の組み合わせの中から、所要時間が最小の経路や、料金や乗り換え回数が最小の経路を探索
2 インターネットでのルーティング Webサイトを閲覧する際、ネットワーク全体で負荷が分散されるように、ネットワーク上の通信経路を探索
3 コンピュータゲームにおけるキャラクターの移動経路計算 コンピュータが操作するキャラクターの移動について、プレイヤーの所在場所やキャラクター同士の相互関係を考慮したうえで、より自然に見える移動ルートを計算
4 コンビニの商品配送ルートの決定 複数のエリアのコンビニを巡回するトラックに対し、配送時間帯等の制限を考慮しながら効率の良い配送順序を決定
5 災害時の避難ルートの生成 危険な場所を避けて通るための制約を加味し、経路の安全性および目的地への到達性の高いルートを速やかに選択

※この続きは、会員の方のみお読みいただけます(登録無料)。


著者プロフィール

  • 工藤 卓哉 (クドウ タクヤ)

    Accenture Data Science Center of Excellence アクセンチュア アナリティクス 日本統括 マネジング・ディレクター 慶應義塾大学を卒業しアクセンチュアに入社。コンサルタントとして活躍後、コロンビア大学国際公共政策大学院で学ぶため退職。同大学...

  • 保科 学世(ホシナ ガクセ)

    アクセンチュア株式会社 デジタル コンサルティング本部 マネジング・ディレクター 慶應義塾大学大学院理工学研究科博士課程修了 理学博士。アクセンチュアにてAFS[Accenture Fulfillment Service]、ARS[Accenture Recommend Serv...

  • 佐伯 隆(サエキ タカシ)

    アクセンチュア株式会社 デジタル コンサルティング本部 アクセンチュア アナリティクス シニア・マネジャー  アクセンチュア アナリティクスにおいて、金融機関の合併に伴うデータ統合管理方針策定、通信事業者向けのビッグデータを活用したマーケティング促進システムの構築、公益事業会社向けデータ...

  • 飯澤 拓 (イイザワ ヒラク)

    アクセンチュア株式会社 デジタル コンサルティング本部 シニア・マネジャー  福島大学 経済学部卒業。 SAPなどを活用した大規模基幹システム開発から、ビッグデータを取り扱う分析基盤に至るまで、インフラ・アーキテクチャの設計と実装を専門とする。近年は通信事業者における位置情報データ活用プロジェ...

  • 党 聡維(ダン コンウェイ)

    アクセンチュア株式会社 デジタル コンサルティング本部 コンサルタント 東京大学大学院 情報理工学研究科 博士号取得。大手電気通信会社にて交通運輸分野における研究開発とシステム構築に従事。その後、アクセンチュアに入社し、ビッグデータアナリティクス分野に取り組む。

  • 田内 真惟人(タウチ マイト)

    アクセンチュア株式会社 デジタル コンサルティング本部 コンサルタント 京都大学大学院 人間・環境学研究科修士課程修了後、㈱構造計画研究所を経てアクセンチュア入社。アクセンチュア アナリティクスにおいて、主に小売業、製造業に対するコンサルティング、アナリティクス案件に従事。

バックナンバー

連載:意志決定のためのデータサイエンス講座

もっと読む

All contents copyright © 2007-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5