巡回セールスマン問題
大学で情報工学を専攻されたかたはTSP（traveling salesman problem）を学んだことがあるだろう。計算複雑度を学ぶ題材としても有名な問題だ。
しかし大学を卒業し、学問の場から離れ社会を見渡すと、現実的には巡回セールスマン問題を解くセールスマンはおそらくいない（もちろん学生が扱う多くの問題が社会のどこに適用されているか知ることはあまりない）。これにはいくつかの原因が考えられる。
- そもそも巡回セールスマン問題をしらない
- 知っているが、計算が面倒だし、最適解を知りたいわけではない
- 最適解と経験上得られる解に大した差がないと考えている
- 顧客とはアポを取っているから、アポの時間に行けばいい
- 等々
現実世界への適用
では、巡回セールスマン問題は学問の場にしか役に立っていないのだろうか？実は巡回セールスマン問題の応用であるVRP（vehicle routing problem）として世界中で役に立っている。
VRPはその名の通り、車のルートを求めるものだ。TSP同様、１つのスタート地点、１つのゴール地点、複数の目的地を効率的に回るルートを計算する。TSPとの違いは複数人（複数のドライバー）で回るという点だ。
運送業のルート、宅配便のルート、仕出し弁当配布のルート、飲食店向け食品小売業のルートなど現実的な問題に近づいた。
さらに現実の問題では以下のような制約を考慮に入れることが多い
主な要件：
- 終業時間（勤務の開始/終了時間、休憩の開始/終了時間）
- 訪問先の順序制約（倉庫や弁当工場に行った後、配達先に向かうなど）
- 法令による勤務時間ルール（〇時間以上働く場合は〇分以上休憩をとるなど）
- 荷量による制約（小さなトラックは一度に詰める荷物の量に厳しい制約がある）
すでにこのような制約を解決しようとするサービスは世の中にいくつか提供されている。仮に上記の制約を満たす最適なルートを現実的な時間で計算できたとしても、ドライバーは配達中に多くの課題に直面する。
課題：
- 顧客に急に呼び出され計画が乱れた
- 配達先にお客様がおらず再配達となった、〇分待ってほしいといわれ、計画が乱れた
- 道路状況により計画から遅れが発生した
- 追加の荷物が当日に増えた
このような課題を解決するため、システムには以下の要件が加わる
追加要件：
- 新しく加わった訪問先と未訪問の目的地とを含めたルートの再計算ができる
- 現実的な時間で計算が終わらなくてはいけない（1度の計算で数分は待てない）
VRPソルバー
前述の通りVRPを解くシステムがある。
- Loogia
- LYNA自動配車クラウド
『巡回セールスマン問題』は誰のため？
一部のルート最適化システムは佐川急便が採用するなど、運送業への導入が進められている。巡回セールスマン問題は今やVRPソルバーとして、多くの配送業のため、そして我々一般消費者のために役立てられている。