I am failing to understand subtour elimination constraint.

[V12DBS]

Can someone help me understand it? Also will a subtour elimination constraint required for a multi depot VRP with backhaul?

[gergely_batho]

If your model is a direct extension of a "classical" TSP model or a "classical" VRP moddel, then yes.

Without those constraints the solution will contain subtours: circular paths, that have no connections to the depot(s).

Of course a depot-node should not be part of such a constraint, becasuse a circle containing a depot is a valid tour.

[V12DBS]

Thanks very much for the reply Gergely. If I have a decision variable X(i,j) where i != j, then how will I have circular paths even if I do not have a sub tour elimination constraint?

[RobPratt]

You might find the following three documentation examples useful because they all demonstrate subtour elimination:

SAS/OR(R) 13.2 User's Guide: Mathematical Programming

SAS/OR(R) 13.2 User's Guide: Mathematical Programming Examples

SAS/OR(R) 13.2 User's Guide: Mathematical Programming Examples

[V12DBS]

Hi Rob,

Thanks for the reply. The examples are great but are a bit overwhelming since I do not understand the fundamentals of subtour. I feel like I am chasing tail when I try to understand the concept. (just like the circular route without subtours)

How would you explain subtours to a person who is struggling to understand the concept? Like I said how would I have a circular route without going to a depot if my decision variables do not have i = j?

[RobPratt · Accepted solution]

Suppose the depot is node 0 and your solution satisfies x[2,5] = 1, x[5,8] = 1, and x[8,2] = 1.  Then this solution contains a subtour of length 3.  Disallowing x[i,j] with i = j eliminates only subtours of length 1 but allows longer subtours.  So you need constraints to eliminate them.

The pictures in the first (TSP) example should help solidify the concept.  You want a single connected tour that contains each node exactly once.  But the first several iterations of the algorithm yield a collection of disjoint subtours that together contain each node exactly once.  The subtour elimination constraints prevent such subtours from arising, and these constraints are added to the problem dynamically.  Once you get a solution that is a single tour, you terminate the algorithm.

[V12DBS]

Rob,

Thanks a ton for being patient with me and a very big thanks. Pointing me to the picture and the word "disjoint" absolutely nailed it. This is exactly what I was seeking.

Now I will enjoy reading more about subtours and implement it in my model.