Solved

# Example model of VRP

• 100 views

• Enthusiast
• 3 replies

I have downloaded the example model of VRP and going through it.

I was not completely able to interpret the Subset code.

I have few questions as specified below

1. what the while loop is doing.

CurrentSubset(CurrentPosition) := 1;
CurrentSubset(c | CurrentPosition < c) := 0;

1. Finally in the if statement  line     SubsetIndicator(comb, c) := CurrentSubset(c);
icon

Best answer by luispinto 16 December 2021, 11:42

View original

Userlevel 4
+5

Hello Sudheer,

To answer your questions, we should start off by understanding what is objective of the procedure itself. Since we are running the VRP with the Subtour elimination option, this specific procedure is taking care of generating all possible subtours in the VRP.

In order to do this, we need to create all possible combinations of customers in our problem (eg. customers 1 and 2; customers 1 and 3; customers 1, 2 and 3, etc.). Basically our loops are setup in order to produce all possible permutations. I strongly suggest you debug the procedure and observe how CurrentSubset, SubtourCombinations and SubsetIndicator(s,i) are updated as they go.

Quick reminder:

CurrentSubset (parameter) - Used locally, it is selecting customers that will be then added as a subtour

SubtourCombinations (set) - Just the list of subtours that were encountered.

SubsetIndicator(s,i) (paramter) - Defines which customers (the i index) is selected for each subtour (the s index).

Finally, the procedure is just copying the CurrentSubset paramter to the SubsetIndicator when it has correctly identified that there are at least two customers in the local parameter.

1. what the while loop is doing.

This is loop is seeking out a customer that is currently not in the CurrentSubset parameter.

Customers are integers, so at the start of every repeat loop the CurrentPosition is set to the customer (line 9) and then we start moving back until we find a customer that is currently not selected.

CurrentSubset(CurrentPosition) := 1;

We are selecting the customer from the while loop (CurrentPosition) by setting the the CurrentSubset for that customer.

CurrentSubset(c | CurrentPosition < c) := 0;

After this, we are eliminating all customers that have a greater value than the current one. This is a smart trick to be able to create all permutations. If we never eliminate customers previously selected, then we will never have combinations without the last customers.

1. Finally in the if statement  line     SubsetIndicator(comb, c) := CurrentSubset(c);

This statement is in the if condition. At this point we know that CurrentSubset contains at least 2 customers and that they are a unique combination of customers and form a subset of all of the customers. So, we copy this parameter to the SubsetIndicator to “keep” the information and use it in the model.

1 2 3 4 5 6 7 8 9 10 11 12 13
1                       1 1
2                     1   1
3                     1 1
4                     1 1 1
5                   1     1

This is what the first 5 lines of the SubsetIndicator looks after running this procedure. Every line corresponds to a subtour and you’ll see how it is creating all possible permutations.