【アルゴリズム】「Aの前に必ずBに立ち寄れ」！「優先順位付き巡回セールスマン問題」｜情報処理問題1000本ノック
一筆書きの美しさよりも、業務の順番（段取り）が最優先。地点同士の「前後関係の縛り」をクリアしながら最短ルートを導き出す、実務直結の最適化アルゴリズムを攻略しましょう。
1. 【 問題 】：グラフ理論と順序制約の最適化問題
【 問題 】 巡回セールスマン問題（TSP）の派生問題の一つであり、特定の訪問先（都市や顧客）の間に「地点Aを訪問する前に、必ず地点Bを訪問していなければならない」といった、訪問順序に関する制約条件（先行制約・優先順位）があらかじめ設定されており、その順序をすべて守りながら全体の移動コストを最小にするルートを求める問題を何と呼ぶでしょうか？
① 優先順位付き巡回セールスマン問題 (Precedence-Constrained TSP)
② 時間窓付き巡回セールスマン問題 (Traveling Salesman Problem with Time Windows)
③ 部分巡回セールスマン問題 (Orienteering Problem)
④ 容量制約付き車両配送問題 (Capacitated Vehicle Routing Problem)
2. 正解：
正解： ① 優先順位付き巡回セールスマン問題 (Precedence-Constrained TSP)
3. 解説：「最短ルート」をへし折る、業務のタスク順序
標準的な巡回セールスマン問題は、すべての地点を一番効率よく回るだけの「空間的なパズル」ですが、そこに「タスクの順序」という制約を足したのが優先順位付き巡回セールスマン問題です。
・本質：地点同士に「矢印（順序関係）」のネットワークが組み込まれます。 ← ココが問題の正解！
・ビジネスでの発生例：荷物の「集荷と配達（ピックアップ＆デリバリー）」が典型です。当たり前ですが、倉庫や顧客Aの家で荷物を「集荷（先）」しなければ、顧客Bの家に「配達（後）」することはできません。また、工場の組み立てロボットの移動経路であれば、「部品Aを取り付ける（先）」前に「ネジBを締める（後）」ことはできない、といった物理的な順序（優先順位）がルートを縛ります。これによって、見た目の距離がどんなに近くてもその順番でしか進めなくなるため、探索空間が制限され、効率的な解を見つけるアルゴリズムが非常に複雑になります。
★ ② 時間窓付き巡回セールスマン問題：前回学びましたね。順序ではなく「9時〜12時の間」のように、各地点に設定された特定の「時間帯の縛り（Time Window）」を守る問題です。
★ ③ 部分巡回セールスマン問題：時間やコストの制限内に、すべての地点ではなく、価値（スコア）が高い地点を「厳選」して巡回し、得点を最大化する問題です。
★ ④ 容量制約付き車両配送問題（CVRP）：1人ではなく「複数台のトラック」を使い、それぞれのトラックの積載重量（容量）を超えないように荷物を小分けにしながら、複数の顧客を効率よく回るルートを設計する、さらに大規模な物流最適化問題です。
1. 理解のコツ: 「ネットオークションの商品の受け渡し」に例えてみましょう。
・地図を広げて、出品者の家、落札者の家、郵便局、自分の家を一番短距離で回るルートを考えるのが通常の巡回セールスマン問題です。
・しかし現実には、『まず出品者の家で商品を預かり（先）、次に郵便局で専用の箱を買い（先）、それを自分の家で梱包し（先）、最後に落札者の家に届ける（後）』という、絶対にひっくり返せない順番があります。距離が近いからといって、最初に落札者の家に行っては元も子もありません。この仕事の段取り（優先順位）を破らずに、なおかつ全体の移動を一番無駄なく組み立てるのが、この優先順位付き巡回セールスマン問題です。
2. 試験対策の視点: 「ある地点は先に、ある地点は後で」「順序に関する制約条件」「優先順位（先行制約）」という文脈があれば「優先順位付き巡回セールスマン問題」が一択です。基本情報の科目B（アルゴリズムの思考力）や、応用情報の午前試験、さらにはシステムアーキテクトや高度な応用数学系の試験において、物流DXの配車管理、製造業の生産工程（スケジューリング）最適化のロジックとして非常によく注目されるホットな問題です。
4. まとめ
「距離や時間を短縮するという地理的な効率性に、『このタスクを終わらせてから次へ進め』という厳格な業務順序（優先順位）の縛りを融合させた、実社会のプロセス設計に直結する数理最適化問題」。これが優先順位付き巡回セールスマン問題です。これで「時間窓」と「優先順位」という、現場で使われる2大巡回アルゴリズムが完全に揃いましたね！