0
$\begingroup$

In many routing problems, it is fairly common to include a constraint that ensures all vehicles follow an elementary path, meaning that no vertices are repeated.

However, when an elementary path is NOT required, then it is fairly common to include a constraint that ensures there are no subtours meaning that there are no isolated tours that do not start at, and return to, the specified depot.

From my understanding, it would never be necessary to include both of these constraints. However, in some cases I have seen both of these constraints, for example here: https://par.nsf.gov/servlets/purl/10074741

Problem Description MILP In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint?

EDIT I've found another resource which highlights my intuition: In this book it describes a similar problem, the vehicle routing problem with time windows. And, in its MILP formulation (shown below), it does not have subtour elimination constraints, and explicitly mentions the classical VRP subtour elimination constraints become redundant. Now, I would have expected this to be the same reason why the image 2 would not need the subtour elimination constraints, since in both cases, the direction of traversal is indicated by denoting $(i,j)$.

MILP_VRPTW subtour_redundant

The difference between these two MILP formulations and problem statements might help me understand what you guys are getting at. Is the only difference that one of them imposes a unique direction?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ In the cited example, what are you interpreting as an elementary path constraint? If it is (4), keep in mind that (4) ensures (a) that every node is visited at least once and (b) that no two vehicles visit the same node. $\endgroup$
    – prubin ♦
    Sep 23 at 19:41
  • $\begingroup$ I'm not seeing how (4) can be interpreted that way. There is a summation over all the vehicles $\Sigma_k$. So, to me it says "Each vertex can be visited once and by only one vehicle (except for the depot)". Furthermore in the description below it says "(4) ensure that each node is visited exactly once. $\endgroup$
    – IsalanOnkar
    Sep 24 at 6:34
  • 1
    $\begingroup$ The necessary part of (4) is the $\ge$ from the $=$ which is not in the subtour elimination constraint. Without it, the solution is just to visit nothing $\endgroup$
    – fontanf
    Sep 24 at 7:07
  • $\begingroup$ @fontanf To me, (4) says "exactly one incoming arc for each vertex in $V^+$. Is that right? I don't understand what you mean by $\ge$. Constraint (4) is an equality, and the subtour elimination constraint is $\le$. Do you mind being more explicit? $\endgroup$
    – IsalanOnkar
    Sep 25 at 22:10
  • $\begingroup$ I editted the question with another problem formulation I've seen where the subtour elimination constraints are redundant. Maybe that will help me see what you're talking about? $\endgroup$
    – IsalanOnkar
    Sep 26 at 6:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.