Need help with multiple indices variable definition and indice/set domains within constraints (Vehicle Routing Problem)

GAMS
1

Hi,

I am working on a mixed integer programming model for a vehicle routing problem (network), and I was hoping to get some help with GAMS, particulary in defining the indices for my decision variables, and for the domain of the indices within my constraints.

These are my set definitions. As you can see, they make use of sub-sets, so at times, they can share common elements.

 
 Set      n               "set of all nodes"                      /d_start, c1, c2, c3, b1, d_end/
         m(n)            "subset of n without depots"            /c1, c2, c3, b1/
         l(m)            "subset of m, nodes for linehaul"       /c1, c2, c3/
         branch(m)       "subset of m, nodes for backhaul"       /b1/
         NL(n)           "subset of n, From/Launch Nodes (Depot at the beginning)"        /d_start, c1, c2, c3, b1/
         NR(n)           "subset of n, To/Rendezvous Nodes Depot at the end)"      /c1, c2, c3, b1, d_end/;



My Decision Variables are listed below, and they take 2,3,and 4-indice forms. These indices represent the path taken, and the variables are binary, such that they are equal to 1, when the path is taken and zero otherwise.

 
 binary variables
*decision variables
                 x(i,j) truck trip
                 SDV(i,k,j) single drone trip (delivery)
                 MDV(i,l,branch,j) multiple drone trip

In my mathematical model however, I often use different index labels throughout my constraints, and the domain of each index is not restricted to a particular label. While this works logically and mathematically, I am having a hard time translating this to GAMS code.

For example, X(i,j) is just a form, but what is important is that the first label (in this case ‘i’) represents the “from” (source) and the (j) represents the “to” (destination). So in other words, the position of the label in the index is what determines what it means. In my mathematical model, index labels are not mapped to a specific set. For example, there are times wherein the index i is an element of set1, but there are times where it is an element of set2 etc.

Similarly, there are instances wherein I use all three of the decision variables within a single constraint.So there are times when I want the indices to refer to the different sets that have common elements, but refer to distinct or common elements. Mathematically, sometimes I have to introduce new index labels to achieve my logic.

To illustrate this more clearly, here is are a few of the formulations of the constraints

I have tried coding this in gams.

The first time around, this was my code

*Constraint 1a  
lhl(l) .. sum(NL, x1(NL,l)) + sum((NL,NR), SDV(NL,l,NR)) + sum((NL,B,NR), MDV(NL,l,B,NR)) =e= 1 ;

As expected, the output is this:

As you can see, since I do not use the sameas function, it enumerates all combinations of the indices.

Next, I tried using SAMEAS, but I get the following error:

  
  *Constraint 1
lhl(l) .. sum(NL$(NOT SAMEAS(NL,l)), x1(NL,l)) + sum((NL,NR)$(NOT SAMEAS(NL,NR)), SDV(NL,l,NR)) + sum((NL,B,NR)$(NOT SAMEAS(NL,NR)), MDV(NL,l,B,NR)) =e= 1 ;

Result:

What would be the best way to define the variables (and their respective indices) and constraints like this? I was thinking of using alias, but there are times when a single index label can refer to a different set within the context of different constraint equations.

2

Hi gravityman123,

There is a lot to unpack in your post (and this won’t be a complete answer) but one thing that struck me is that your problem has a network in it, but you have not defined a set that describes the arcs in your network. For all sorts of problems it’s a good programming practice to specify a set of nodes and separately define a from/to arc set. This set will be 2D and it will describe the directed graph. This way you don’t get caught off guard with +/- signs for flows etc… helps keep the problem a bit tidier. Once you have this arc set you can use it in a conditional statement to restrict flows only along paths that you want to exist. For example:

SET n /n1*n10/;
SET arc(from,to);
ALIAS(n,nn);

*create the dense network, includes self loops
arc(n,nn) = yes;

*remove self arcs
arc(n,n) = no;

If you use this structure, you might have an easier time with your constraints.