5
$\begingroup$

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 TSR 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 important problems such as TSP should be tags themselves.

$\endgroup$
  • 4
    $\begingroup$ Could you please define VRP? Equivalently, which vehicle routing problem? $\endgroup$ – Jeffε Sep 19 '12 at 16:01
  • $\begingroup$ 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. $\endgroup$ – Yixin Cao Sep 19 '12 at 16:27
  • $\begingroup$ @JɛffE 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 en.wikipedia.org/wiki/Vehicle_routing and mansci.journal.informs.org/content/6/1/80.short $\endgroup$ – sma Sep 20 '12 at 0:32
  • $\begingroup$ @Yixin Cao see the above comment $\endgroup$ – sma Sep 20 '12 at 0:32
  • $\begingroup$ i think vrp is equivalent to multiple travelling salesman where all salesman have the same starting location $\endgroup$ – sma Sep 20 '12 at 9:17
4
$\begingroup$

The Vehicle Routing Problem was introduced in G. B. Dantzig and J. H. Ramser, The Truck Dispatching Problem, 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 salesman 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, precedence relations between points.

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.

For what regards "It seems relatively easy to model TSR 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 it requires other intermediate reductions).

$\endgroup$
  • $\begingroup$ I have the same conclusion as your summarized difference. $\endgroup$ – sma Mar 17 '14 at 19:22
  • $\begingroup$ 'probelm'->'problem' ; it's below 6 char and I can't submt an edit $\endgroup$ – BlueWizard May 19 '18 at 8:35
2
$\begingroup$

In the year 1959, Dantzig and Ramser, the authos of "The truck dispatching problem" described how the Vehicle Routing Problem (VRP) may be considered as a generalization of the Travelling Salesman 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", and access an attempt to compile all of those at: VRP-REP.ORG

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.