<p>In the year 1959, Dantzig and Ramser, the authos of "<a href="https://pubsonline.informs.org/doi/abs/10.1287/mnsc.6.1.80" rel="nofollow noreferrer">The truck dispatching problem</a>" described how <strong>the Vehicle Routing Problem (VRP) may be considered as a generalization of the Travelling Salesman Problem (TSP)</strong>. They described the generalization of the TSP with multiple salespeople (supposedly riding a single vehicle each), and called this the “Clover problem”. 
You can read more about the VRP and its many variants in "<a href="http://dx.doi.org/10.4236/iim.2012.43010" rel="nofollow noreferrer">A Survey on the Vehicle Routing Problem and its Variants</a>", and access an attempt to compile all of those at: <a href="http://www.vrp-rep.org/variants.html" rel="nofollow noreferrer">VRP-REP.ORG</a></p>

CC BY-SA 4.0
2018-06-26T10:41:37.237Z
2018-06-26T10:41:37.237Z
Alfonso F R
<p>My explanation is TSP is VRP with the condition that only 1 truck is in operation or only 1 salesman. In other word, the VRP solution can have many routes but TSP solution has only 1 route. TSP is the simplest problem of VRP. </p>

CC BY-SA 3.0
2014-09-03T08:44:10.497Z
2014-09-03T08:44:10.497Z
Boontariga K.
<p>The Vehicle Routing Problem was introduced in G. B. Dantzig and J. H. Ramser, <a href="http://andresjaquep.files.wordpress.com/2008/10/2627477-clasico-dantzig.pdf" rel="nofollow noreferrer">The Truck Dispatching Problem</a>, Management Science Vol. 6, No. 1 (Oct., 1959), pp. 80-91.</p>
<p>The authors underline the differences with TSP in this way:</p>
<blockquote>
... The "truck dispatching problem" formulated in this paper may be considered as a <em>generalization</em> of the TSP ...<br><br>
<p>... The salesman may be required to return to the &quot;terminal point&quot; whenever he has contated <span class="math-container">$m$</span> of the <span class="math-container">$n-1$</span> remaining points, <span class="math-container">$m$</span> being a divisor of <span class="math-container">$n-1$</span>. For given <span class="math-container">$n$</span> and <span class="math-container">$m$</span> the problem is to find loops such that all loops have a specified point in common and total loop length is a minimum. Since the loops have one point in commom, this problem may be called the &quot;Clover Leaf Problem&quot;...<br><br></p>
<p>... The TSP may also be generalized by imposing the condition that specified deliveries <span class="math-container">$q_i$</span> be made at every point <span class="math-container">$P_i$</span> (excepting the terminal point). If the capacity of the carrier <span class="math-container">$C$</span> is greater than <span class="math-container">$\sum_i q_i$</span>, the probelm is formally identical with the TSP in its original form since the carrier can serve every delivery point on one trip which links all the points...</p>
</blockquote>
<p>In the simplest VRP formulation, all trucks (vehicles) have the same capacity and only one product is to be delivered to each point <span class="math-container">$P_i$</span>. Other common constraints are: time constraints (or total length of each route), time windows, and precedence relations between points.</p>
<p>To summarize: the main difference between a TSP and VRP is that the salesman must return to the starting location after some points have been visited.</p>
<p>For what regards &quot;<em>It seems relatively easy to model TSP in the form of VRP and likewise inversely.</em>&quot;: the reduction from TSP to VRP is immediate, the opposite direction VRP <span class="math-container">$\leq_m^p$</span> TSP is surely more complex (and probably requires other intermediate reductions).</p>

CC BY-SA 3.0
2014-03-17T19:22:08.013Z
I have the same conclusion as your summarized difference.
sma
CC BY-SA 4.0
2018-05-19T08:35:56.530Z
'probelm'->'problem' ; it's below 6 char and I can't submt an edit
BlueWizard
CC BY-SA 4.0
2014-03-17T10:45:46.973Z
2024-04-09T20:27:39.287Z
2024-04-09T20:27:39.287Z
Marzio De Biasi
<p>Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSP in the form of VRP and likewise inversely. So what is the essential point to make VRP a different problem from TSP?</p>
<p>p.s. I cannot find appropriate tags for this question. I think there should be tags for important problems such as TSP.</p>

CC BY-SA 3.0
2012-09-19T16:01:55.747Z
Could you please define VRP?  Equivalently, _which_ vehicle routing problem?
Jeffε
CC BY-SA 3.0
2012-09-19T16:27:38.717Z
TSP might deserve a tag, but VRP definitely deserves a definition/explanation.  This problem is not that famous out of operation research community, at least, not commonly mentioned in CS courses.  The real difference might be something similar as ``serial computation and parallel computation''.  With the formulation of VRP, it is easy to impose more realistic constraints, e.g. number of vertices by each vehicles, total distance of each vehicles.
Yixin Cao
CC BY-SA 3.0
2012-09-20T00:32:09.027Z
@JɛﬀE in its simplest form, VPR is to visit a number of locations with a fixed number of vehicle and minimizes the total travel distance. see http://en.wikipedia.org/wiki/Vehicle_routing and http://mansci.journal.informs.org/content/6/1/80.short
sma
CC BY-SA 3.0
2012-09-20T00:32:34.050Z
@Yixin Cao  see the above comment
sma
CC BY-SA 3.0
2012-09-20T09:17:40.667Z
i think vrp is equivalent to multiple travelling salesman where all  salesman have the same starting location
sma
CC BY-SA 3.0
2012-09-30T14:57:30.727Z
In the vehicle routing, you also need to assign the locations to the vehicles.  If you fix an assignment, you would say the problem reduces to the traveling salesman problem.  But an assignment is not a trivial task.
Yoshio Okamoto
CC BY-SA 3.0
2017-06-09T11:10:53.427Z
Can anyone say where are we on VRP, where we reached and how much we are able to solve VRP or/and TSP?
yuen shi
<cc.complexity-theory><np-hardness><tsp>
what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?
sma
# what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

(Asked by: username_0 on 2012-09-19)

Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSP in the form of VRP and likewise inversely. So what is the essential point to make VRP a different problem from TSP?

p.s. I cannot find appropriate tags for this question. I think there should be tags for important problems such as TSP.

**Tags:** cc.complexity-theory, np-hardness, tsp

> **Comments:**
> **username_1**: Could you please define VRP?  Equivalently, _which_ vehicle routing problem?  
> **username_2**: TSP might deserve a tag, but VRP definitely deserves a definition/explanation.  This problem is not that famous out of operation research community, at least, not commonly mentioned in CS courses.  The real difference might be something similar as ``serial computation and parallel computation''.  With the formulation of VRP, it is easy to impose more realistic constraints, e.g. number of vertices by each vehicles, total distance of each vehicles.  
> **username_0**: @JɛﬀE in its simplest form, VPR is to visit a number of locations with a fixed number of vehicle and minimizes the total travel distance. see http://en.wikipedia.org/wiki/Vehicle_routing and http://mansci.journal.informs.org/content/6/1/80.short  
> **username_0**: @username_2  see the above comment  
> **username_0**: i think vrp is equivalent to multiple travelling saleusername_0n where all  saleusername_0n have the same starting location  
> **username_3**: In the vehicle routing, you also need to assign the locations to the vehicles.  If you fix an assignment, you would say the problem reduces to the traveling saleusername_0n problem.  But an assignment is not a trivial task.  
> **username_4**: Can anyone say where are we on VRP, where we reached and how much we are able to solve VRP or/and TSP?  

---

## 3 answers

### Answer by username_7 on 2014-03-17. Score: 7 | Accepted answer

The Vehicle Routing Problem was introduced in G. B. Dantzig and J. H. Ramser, [The Truck Dispatching Problem](http://andresjaquep.files.wordpress.com/2008/10/2627477-clasico-dantzig.pdf), Management Science Vol. 6, No. 1 (Oct., 1959), pp. 80-91.

The authors underline the differences with TSP in this way:

> ... The "truck dispatching problem" formulated in this paper may be considered as a *generalization* of the TSP ...  
>   
>
> ... The saleusername_0n may be required to return to the "terminal point" whenever he has contated $m$ of the $n-1$ remaining points, $m$ being a divisor of $n-1$. For given $n$ and $m$ the problem is to find loops such that all loops have a specified point in common and total loop length is a minimum. Since the loops have one point in commom, this problem may be called the "Clover Leaf Problem"...
>
> ... The TSP may also be generalized by imposing the condition that specified deliveries $q\_i$ be made at every point $P\_i$ (excepting the terminal point). If the capacity of the carrier $C$ is greater than $\sum\_i q\_i$, the probelm is formally identical with the TSP in its original form since the carrier can serve every delivery point on one trip which links all the points...

In the simplest VRP formulation, all trucks (vehicles) have the same capacity and only one product is to be delivered to each point $P\_i$. Other common constraints are: time constraints (or total length of each route), time windows, and precedence relations between points.

To summarize: the main difference between a TSP and VRP is that the saleusername_0n must return to the starting location after some points have been visited.

For what regards "*It seems relatively easy to model TSP in the form of VRP and likewise inversely.*": the reduction from TSP to VRP is immediate, the opposite direction VRP $\leq\_m^p$ TSP is surely more complex (and probably requires other intermediate reductions).

> **Comments:**
> **username_0**: I have the same conclusion as your summarized difference.  
> **username_8**: 'probelm'->'problem' ; it's below 6 char and I can't submt an edit  

---

### Answer by username_5 on 2018-06-26. Score: 3

In the year 1959, Dantzig and Ramser, the authos of "[The truck dispatching problem](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.6.1.80)" described how **the Vehicle Routing Problem (VRP) may be considered as a generalization of the Travelling Saleusername_0n Problem (TSP)**. They described the generalization of the TSP with multiple salespeople (supposedly riding a single vehicle each), and called this the “Clover problem”.
You can read more about the VRP and its many variants in "[A Survey on the Vehicle Routing Problem and its Variants](http://dx.doi.org/10.4236/iim.2012.43010)", and access an attempt to compile all of those at: [VRP-REP.ORG](http://www.vrp-rep.org/variants.html)


---

### Answer by username_6 on 2014-09-03. Score: 0

My explanation is TSP is VRP with the condition that only 1 truck is in operation or only 1 saleusername_0n. In other word, the VRP solution can have many routes but TSP solution has only 1 route. TSP is the simplest problem of VRP.


---

