TSP Route Planning

巡回セールスマン問題を、実務の道具にする

複数の訪問先を最短で回る順番を求める問題は、巡回セールスマン問題(TSP)として知られています。厳密に解くのは難しい問題ですが、実務では十分に使える近似解が短時間で得られます。

対象: ルート設計を担当する方、配車計画、業務改善、システム選定

巡回セールスマン問題を、実務の道具にする

現在使える範囲と、利用前の確認

何件までルートを計算できますか?

現在、1回に計算できる訪問先は無料・Proとも10件までです。Proの追加画面には30件まで表示されますが、11件以上の計算は完了しません。一括入力の20行/100行は解析の上限で、計算可能な件数とは異なります。

データは外部に送信されますか?

履歴・メモ・写真の保存先は端末内です。一方、地点検索やルート計算では、入力した住所・地点情報・座標を当社のサーバーで処理し、必要な情報を地図サービスに送信します。外部の地図・カレンダーを開く場合も、選んだ地点や予定の情報がリンク先へ渡ります。

Proの購入と無料トライアルについて

ProはiOS・Androidアプリ内で購入できます。Web版では購入できません。地域ごとの価格と7日間無料トライアルの適用可否は、購入画面で確認してください。クラウド同期・チーム管理は現在提供していません。

必ず最短ルートになりますか?

移動時間をもとに訪問順の候補を計算します。滞在時間や出発時刻を設定でき、順番の固定にも対応。必ず最短になる保証や、希望到着時刻に間に合わせる自動調整はありません。希望時刻を超えた場合は結果に警告を表示します。

Pain Points

手作業での順番決めが抱える限界

  • ! 訪問先が増えると組み合わせが爆発的に増える
  • ! 担当者の経験に依存し、精度がばらつく
  • ! 道路距離ではなく直線距離で判断してしまう
  • ! 滞在時間を含む予定と希望到着時刻を照合しにくい

Solution

実務で成立させる考え方

  • ✓ 厳密な最適解ではなく、実用上十分な近似解を短時間で求める
  • ✓ 地図サービスの推定移動時間で順番を評価する
  • ✓ 滞在時間から予定を作り、希望到着時刻は超過の警告に使う
  • ✓ 出発地と「出発地に戻る」の有無を指定し、必要な訪問順を固定する

Workflow

ぐるーとでの扱い

1

訪問先と条件を入力

住所に加えて、出発地・滞在時間・希望到着時刻を指定します。

2

訪問順を計算

移動時間を評価しながら、実用的な順番を短時間で求めます。

3

結果を業務に落とす

到着予定時刻を確認し、区間ごとにナビへ引き継いで実行します。

Why It Works

厳密解を求めない理由

ぐるーとは、ナビそのものより前の「訪問順を決める」「保存する」「記録する」工程を短くするためのアプリです。

訪問先が増えると厳密解の計算量は現実的でなくなります

実務では数分の差より、すぐ結果が出ることの価値が上回ります

道路状況や滞在時間の変動があるため、過度な精緻化は意味を持ちにくいです

FAQ

よくある質問

巡回セールスマン問題とは何ですか?

複数の地点をすべて1回ずつ訪問して出発地に戻る、最短の順路を求める問題です。地点数が増えると組み合わせが急激に増え、すべてを調べて最短を選ぶ方法は現実的でなくなります。

厳密な最適解でなくても問題ありませんか?

多くの業務では問題ありません。実際の移動時間は交通状況で変動し、滞在時間にも幅があります。数パーセントの差を追うより、条件変更のたびにすぐ計算し直せることの方が実務では有用です。

出発地と戻る場所を指定できますか?

出発地を指定できます。業務の実態に合わせて、回り方の起点を固定した計算が可能です。

順番の計算を、アプリに任せる

訪問先を入力するだけで、実務で使える訪問順が求まります。