【アルゴリズム】「何時までに届けろ」の制約を守れ！「時間窓付き巡回セールスマン問題」｜情報処理問題1000本ノック
ただ最速で回るだけでは、ビジネスの現場では役に立たない。顧客が指定した「約束の時間」をすべてクリアする超リアルな巡回アルゴリズムを攻略しましょう。
1. 【 問題 】：グラフ理論と数理最適化の制約問題
【 問題 】 巡回セールスマン問題（TSP）の派生問題の一つであり、各訪問先（都市や顧客）に対して「何時から何時の間に訪問しなければならない」という受け入れ可能な時間帯（制約条件）が設定されており、その制限をすべて満たしながら、全体の移動距離や所要時間を最小にする最適なルートを求める問題を何と呼ぶでしょうか？
① 時間窓付き巡回セールスマン問題 (TSPTW / Traveling Salesman Problem with Time Windows)
② 部分巡回セールスマン問題 (Orienteering Problem)
③ 中国人郵便配達問題 (Chinese Postman Problem)
④ 動的経路計画問題 (Dynamic Routing Problem)
2. 正解：
正解： ① 時間窓付き巡回セールスマン問題 (TSPTW)
3. 解説：「距離の短さ」と「時間の約束」を同時に解く難問
標準的な巡回セールスマン問題は、距離や時間が最短になる順番をパズルのように解くだけですが、そこに「午前中指定」「14時〜16時」といった実務の縛りを組み込んだのが時間窓付き巡回セールスマン問題（TSPTW）です。
・「時間窓（Time Window）」とは：各地点に設定された「ここから（開始時刻）ここまで（終了時刻）」という訪問許可時間のことです。 ← ココが問題の正解！
・計算の複雑さ：もし、ある家に指定時間より早く着きすぎてしまったら、その時間（時間窓の開始）になるまでその場で「待機」しなければなりません。逆に、ルートを効率化しようとするあまり1分でも遅れると、制約違反（大クレーム）になります。地理的に隣にある家であっても、時間の指定がバラバラだと効率的なルートが全く組めなくなるため、通常のTSPよりも遥かに計算が難しく、組み合わせが爆発します。
★ ② 部分巡回セールスマン問題：以前学んだ問題です。時間や予算などの限られた資源の範囲内で、すべての都市ではなく、価値や得点が高い重要な地点を「厳選」して巡回し、スコアを最大化する問題です。
★ ③ 中国人郵便配達問題：すべての「地点（点）」ではなく、すべての「道路（辺）」を少なくとも1回は通って元の場所に戻る最短ルートを求める問題です。
★ ④ 動的経路計画問題：移動中にリアルタイムで発生する「渋滞情報」や「急な集荷依頼」などに応じて、その都度ルートを柔軟に再計算して変更していく問題です。
1. 理解のコツ: 「ネット通販の宅配ドライバーのルート作成」に例えてみましょう。
・地図だけを見て、15軒の家を一番一筆書きで綺麗に回れるルートを作るのが通常の巡回セールスマン問題です。
・しかし現実には、Aさんは『午前中指定（9時〜12時）』、Bさんは『夜間指定（19時〜21時）』という約束（時間窓）があります。Aさんの家に11時50分に滑り込み、その後他の家を回り、ちょうど19時過ぎにBさんの家に到着するよう、時間軸のパズルを完璧に組み立てるのが、この時間窓付き巡回セールスマン問題です。物流業界（ヤマト運輸やAmazonの配送網など）のルート自動生成システムでは、毎日このアルゴリズムが裏側でフル稼働しています。
2. 試験対策の視点: 「訪問時間に制限がある」「時間窓（タイムウィンドウ）」というキーワードがあれば「時間窓付き巡回セールスマン問題」が一択です。基本情報や応用情報の午前試験、さらには高度試験（システムアーキテクト等）において、物流DXや自動配車システムの数理モデル、あるいはAIによるスケジューリング最適化の文脈で、最も実用的かつ難度の高いアルゴリズム問題として注目されています。
4. まとめ
「移動距離のミニマム化という空間的なパズルに、各地点の『時間指定（時間窓）』という厳格な時間軸の制約を掛け合わせた、現代の物流システムを支える最重要の数理最適化問題」。これが時間窓付き巡回セールスマン問題です。これで巡回セールスマン問題の派生形も完璧に網羅できましたね！