【アルゴリズム】元の場所に戻らない片道ルート！「始点終点固定型巡回セールスマン問題」｜情報処理問題1000本ノック
すべての地点を回るけれど、出発地とゴール地点が別々に決まっている。巡回（ループ）ではなく、一筆書きの「最短パス」を導き出す最適化アルゴリズムを攻略しましょう。
1. 【 問題 】：グラフ理論と経路最適化（始点・終点制約）
【 問題 】 巡回セールスマン問題（TSP）の派生問題の一つであり、通常のTSPのように「最終的に出発点に戻る（巡回する）」のではなく、あらかじめ指定された異なる「開始地点（始点）」から出発し、すべての訪問先をちょうど1回ずつ経由した上で、同じくあらかじめ指定された別の「最終目的地（終点）」で移動を終了するような、総移動コストが最小となる最短経路（ハミルトンパス）を求める問題を何と呼ぶでしょうか？
① 始点終点固定型巡回セールスマン問題 (Fixed Start-End TSP / オープンTSP)
② 優先順位付き巡回セールスマン問題 (Precedence-Constrained TSP)
③ 時間窓付き巡回セールスマン問題 (Traveling Salesman Problem with Time Windows)
④ 中国人郵便配達問題 (Chinese Postman Problem)
2. 正解：
正解： ① 始点終点固定型巡回セールスマン問題 (Fixed Start-End TSP)
3. 解説：最後の「戻るコスト」を計算に入れない片道パズル
通常の巡回セールスマン問題は、最後に「終点から始点へ戻るための移動距離（コスト）」を足して計算します。しかし、現実のビジネスでは「最後は会社に戻らず、そのまま自宅に直帰する」というケースも多く、その場合は最後の戻り道を計算から除外する始点終点固定型TSPのモデルを使用します。
・数学的な違い：通常のTSPがグラフにおける「ハミルトン閉路（輪っか）」を探すのに対し、この問題は始点と終点が結ばれていない「ハミルトンパス（一本の線）」を探します。 ← ココが問題の正解！
・実務での発生例：観光ツアーの計画で「東京駅（始点）を出発し、都内の観光地をすべて巡って、最終的に羽田空港（終点）で解散する」ルートを作る場合や、工場の配線・穴あけロボットが「待機場所A（始点）から動きだし、基板の全てのポイントを加工して、次の工程の搬出口B（終点）へと抜ける」といった、片道のプロセス最適化にそのまま応用されます。
★ ② 優先順位付き巡回セールスマン問題：前回学びましたね。地点同士に「Aの前に必ずBを回れ」という前後の順序制約がある問題です。最終的には出発点に戻るループ構造が基本です。
★ ③ 時間窓付き巡回セールスマン問題：各地点に「9時〜12時」のような訪問可能な時間帯の縛り（Time Window）がある問題です。
★ ④ 中国人郵便配達問題：すべての「地点（点）」を一筆書きするのではなく、すべての「道路（辺）」を少なくとも1回は通って元の場所に戻る最短ルートを求める、まったく別のグラフ理論問題です。
1. 理解のコツ: 「旅行のドライブ計画」に例えてみましょう。
・自宅を出発して、3つの観光地を巡り、最後にまた自宅へ帰ってくる旅行なら、最後の帰り道も含めて一番安くなるルートを探す通常のTSPです。
・しかし、『自分の家（始点）を出発して、観光地を巡りながらドライブし、今夜泊まる予定の遠くの温泉旅館（終点）へと向かう』という計画の場合、自宅に帰る必要はありません。とにかく旅館に一番早く着く一筆書きのルートを導き出す。これこそが始点終点固定型巡回セールスマン問題です。
2. 試験対策の視点: 「出発点に戻らない」「始点と終点が異なる（固定されている）」という条件があれば「始点終点固定型巡回セールスマン問題」が一択です。基本情報の科目Bや応用情報の午後試験（数理科学・アルゴリズム分野）において、MaaS（モビリティ・アズ・ア・サービス）などの最新のオンデマンド配車や、効率的な配送計画システムを設計する際のアルゴリズムの基礎として頻出するキーワードです。
4. まとめ
「最終地点からスタート地点へと戻る制約を取り払い、指定された2つの異なるポイント（始点・終点）を両端とする、すべての地点を一筆書きで結ぶ最短片道ルート決定問題」。これが始点終点固定型巡回セールスマン問題です。これで通常のループ型、時間窓、優先順位、そして片道型と、実務で使われるTSPの主要な型が完全にコンプリートされましたね！