受託サービス

経路探索ソフトウェア

概要

ゴーガでは、汎用経路探索ソフトウェアを開発、販売しています。ノード情報およびリンク情報を与え、発地、着地を設定すると、最短経路及び最短から第n位までの経路を算出し、回答することができます。

特長

経路探索ソフトウェアの主な特長は、全経路探索ができることと、そのスピードです。最短経路のみであればダイクストラ法等の既存アルゴリズムで容易に最短経路を計算することができますが、第n位までの経路算出、もしくは全経路算出となるとそのアルゴリズムは非常に複雑になり、また、計算時間やメモリ使用量等の関係で算出が著しく困難になります。

この経路探索ソフトウェアでは独自開発した効率的アルゴリズムにより、非常に短い時間で、第n位までの探索及び全経路探索を提供します。 なお、実用例として弊社が提供するサービス「高速.jp」(http://kosoku.jp)でも使用しており、料金計算と経路算出に威力を発揮しています。

設定可能な項目

この経路探索ソフトウェアでは、ノード及びリンクからなる通常のネットワークの経路探索に加えて、次を考慮した経路探索が可能です。

  • 一方通行の設定
  • 出発ノードの出発方向制限、到着ノードの到着方向制限
  • 3本以上リンクを持つノードについて、経由できない方向の設定

計算事例

1. 高速.jpにおけるNEXCO3社圏内全経路探索 高速.jpにおいては、NEXCO3社範囲の高速道路について全経路(全発地、全着地、全経由経路)を算出しています。

  • 入力データ
    • ノード数 約900点(インター、ジャンクション)
    • リンク数 約900本(インターやジャンクションを結ぶ道路)
    • 経由できない方向の設定 約40件
  • ループ数
    • ループ数 11件
      • ループ経路が多くなると、出現する経路数が著しく増加します。理論上は1つのループ増加につき経路数は2倍になります。
  • 計算時間
    • ご契約日より以降の料金表及び経路表はすべてデータベースサーバーにストックしてありますので、新しい料金に改定になった後も当時の料金表を検索することができます。
      • 全発地、全着地、経路探索
        • 計算時間:31分
          • Core 2 Duo 2.4GHz, メモリ 4GB
        • ファイル出力時間 136分
          • 出力形式を小さくすることで短縮できます。
  • 出力結果サマリー
    • 1つの発着地の組について経路数は約500本~1,000本
    • 1つの発地から、全着地について経路数については約数万~数十万本
      • 浦和インター発:1着地につき約500本、全38,270本
      • 鹿児島インター発:1着地につき約1,000本、全727,256本

その他の事例及びベンチマークについては、現在掲載準備中です。

経路探索ソフトウェアの販売価格

項目 価格
経路探索ソフトウェア(バイナリ形式) 500万円
経路探索ソフトウェアのカスタマイズ導入 お問い合わせ下さい。
経路探索ソフトウェアのソースコード お問い合わせ下さい。