大学で情報工学を専攻されたかたはTSP（traveling salesman problem）を学んだことがあるだろう。計算複雑度を学ぶ題材としても有名な問題だ。

しかし大学を卒業し、学問の場から離れ社会を見渡すと、現実的には巡回セールスマン問題を解くセールスマンはおそらくいない（もちろん学生が扱う多くの問題が社会のどこに適用されているか知ることはあまりない）。これにはいくつかの原因が考えられる。

では、巡回セールスマン問題は学問の場にしか役に立っていないのだろうか？実は巡回セールスマン問題の応用であるVRP（vehicle routing problem）として世界中で役に立っている。

VRPはその名の通り、車のルートを求めるものだ。TSP同様、１つのスタート地点、１つのゴール地点、複数の目的地を効率的に回るルートを計算する。TSPとの違いは複数人（複数のドライバー）で回るという点だ。

運送業のルート、宅配便のルート、仕出し弁当配布のルート、飲食店向け食品小売業のルートなど現実的な問題に近づいた。

さらに現実の問題では以下のような制約を考慮に入れることが多い

主な要件：

すでにこのような制約を解決しようとするサービスは世の中にいくつか提供されている。仮に上記の制約を満たす最適なルートを現実的な時間で計算できたとしても、ドライバーは配達中に多くの課題に直面する。

課題：

このような課題を解決するため、システムには以下の要件が加わる

追加要件：

前述の通りVRPを解くシステムがある。

一部のルート最適化システムは佐川急便が採用するなど、運送業への導入が進められている。巡回セールスマン問題は今やVRPソルバーとして、多くの配送業のため、そして我々一般消費者のために役立てられている。