Subtour Elimination Constraint VRP

[MS]

I'm trying to implement a Vehicle Routing Problem in AIMMS. Now I want to implement the subtour elimination constraint in this way:



So I defined W as a Subsetof of V\{0}. Now I want to implement the SubtourEliminationConstraint but now I don't know how to implement the absolut value of W (|W|).

Thank you a lot in advance for your help!!!

[Marcel Hunting]

Hi,

The |W| does not refer to the absolute value but instead refers to the cardinality of the set W. The cardinality of a set in AIMMS can be obtained using the Card function. However, that will not help you much as you cannot loop (directly) over subsets of a set in AIMMS.

It is not trivial to find all subsets W in V and to generate the corresponding subtour elimination constraints. On paper it looks easy but if you try to implement that in AIMMS (or in any other modeling language) then that turns out to be quite tricky. I just updated the CVRP example on our website by adding a second formulation that generates all subtour elimination constraints. This example can be downloaded from here.

Please note that generating all subtour elimination constraints is not very efficient for larger problems. For 30 customers you need (a little less than) 2^30 subtour elimination constraints which is a very large number. This example also contains a second formulation (Miller-Tucker-Zemlin) which uses a much smaller amount of constraints.

Best regards,

Marcel Hunting

AIMMS Optimization Specialist