Problems with looping and indices

Problems with modeling
SvenTH
User
User
Posts: 6
Joined: 4 years ago

Problems with looping and indices

Post by SvenTH »

Hi all,

i am new to GAMS and try to implement a complex vehicle routing problem. I did quite well but one thing isn't working at all:

There is routing variable x(i,j,t) which has location indices i and j, and index for time period t. Later in my code I want to add a vehicle index v to this, so i have parameter xt(i,j,t,v). Every location can be at least met once per period and every delivering tour has to start and end in depot 'i1'. With this knowledge every tour can be identified even without index v. As an example tour1 can look like i1 - i2 - i3 - i5 - i1 and tour2 like i1 - i4 - i6 - i1.

To add vehicle index v I have to tell GAMS these tours and try to do this by adding variable nexti, while nexti equals ord(j), and looping over i and j. With the code attached I get the (exact) xt(i,j,t,v) for tour1 which then looks like:

INDEX 1 = v1

t1

i1.i2 1.000
i2.i3 1.000
i3.i5 1.000
i5.i1 1.000

In the next loop iteration, tour i1 - i2 - i3 - i5 - i1 should be "ignored" but I didn't get that. I think every xt(i,j,t,v) is filled with data from tour1 until my abort criterion stops the loop. How can I tell GAMS to ignore x(i1,i2,t) and take x(i1,i4,t) with which the loop should generate the exact xt(i,j,t,v) for tour2?

Obviously my break statement is wrong even, but I don't know better.. Hope you understand what I am trying to do and can help me!

Thanks a lot in advance.
Sven


Note: In my original code I x(i,j,t) is a variable but in this reduced example I created it as a parameter.

Code: Select all

*---------------------------------------------------------------------------
*---------------------------------------------------------------------------
*Data
*---------------------------------------------------------------------------
*---------------------------------------------------------------------------

Sets i   'locations'     / i1 * i6 /
     v   'vehicles'      / v1 * v3 /
     t   'time period'   / t1 /;

Alias (i,j);

Set nextv(v);

Parameter
  x(i,j,t)       '1 if location i immediately precedes location j on a delivery route; 0 otherwise'
  xt(v,i,j,t)    '1 if location i immediately precedes location j on a delivery route; 0 otherwise'
  touren(t)      'number of vehicles leaving depot i1 in period t'
  count          'parameter to count in loop'
;

touren(t) = 0;

Variable nexti  'faces following location in delivering route'
;

*---------------------------------------------------------------------------
*---------------------------------------------------------------------------
*Random Delivery Routes
*---------------------------------------------------------------------------
*---------------------------------------------------------------------------

x('i1','i2',t) = 1;
x('i1','i4',t) = 1;
x('i2','i3',t) = 1;
x('i3','i5',t) = 1;
x('i5','i1',t) = 1;
x('i4','i6',t) = 1;
x('i6','i1',t) = 1;


*---------------------------------------------------------------------------
*---------------------------------------------------------------------------
*Count number of vehicles leaving depot i1 in period t
*---------------------------------------------------------------------------
*---------------------------------------------------------------------------

loop(t,
  loop((i,j),
    if(x(i,j,t)$(ord(i) = 1) = 1,
      touren(t) = touren(t)+1;
    );
  );
);

*---------------------------------------------------------------------------
*---------------------------------------------------------------------------
*Tour must start in depot i1 and end in depot i1, each vehicle v can do at
*least one tour per period t
*Goal: Assign index v to every tour
*---------------------------------------------------------------------------
*---------------------------------------------------------------------------

loop(t,
  nexti.l = 1;
  count = 1;
  nextv(v)=no;
  nextv('v1')=yes;

      loop(i$(Ord(i)=nexti.l),
        loop(j,
          if(x(i,j,t) = 1,
            xt(nextv,i,j,t) = x(i,j,t);
            nexti.l = ord(j);

*when following location equals i1 (depot), then use next vehicle v
              if(nexti.l=1,
              nextv(v) = nextv(v-1);
              count = count+1;
              );

            break;
          );
        );
      );
);

display xt;

In the end, parameter xt should look like:

INDEX 1 = v1

t1

i1.i2 1.000
i2.i3 1.000
i3.i5 1.000
i5.i1 1.000

INDEX 1 = v2

t1

i1.i4 1.000
i4.i6 1.000
i6.i1 1.000

Thank you!
User avatar
Renger
Posts: 639
Joined: 7 years ago

Re: Problems with looping and indices

Post by Renger »

Hi Sven

I simplified the problem a little bit to find the solution, but I assume you can add the complexity back again.

Here is a solution

Code: Select all

Sets i   'locations'     / i1 * i6 /;

alias (i,j);

set trips /1*2/;
parameter xt(i,j,trips), x(i,j);

variable nexti;

x('i1','i2') = 1;
x('i1','i4') = 1;
x('i2','i3') = 1;
x('i3','i5') = 1;
x('i5','i1') = 1;
x('i4','i6') = 1;
x('i6','i1') = 1;

loop(trips,
    NEXTI.L = 1;
    loop(i$(ord(i) = NEXTI.L),
        LOOP(j$(x(i,j) = 1),
            xt(i,j,trips) = 1;
            x(i,j) = 0;
            NEXTI.L = ord(j);
            break;
        );
    );
);
display xt;
which gives:

Code: Select all

----     30 PARAMETER xt  

                1           2

i1.i2       1.000
i1.i4                   1.000
i2.i3       1.000
i3.i5       1.000
i4.i6                   1.000
i5.i1       1.000
i6.i1                   1.000
Hope this helps

Renger
____________________________________
Enjoy modeling even more: Read my blog on modeling at The lazy economist
SvenTH
User
User
Posts: 6
Joined: 4 years ago

Re: Problems with looping and indices

Post by SvenTH »

Hi Renger,

works perfectly, thanks a lot!

Regards
Sven
SvenTH
User
User
Posts: 6
Joined: 4 years ago

Re: Problems with looping and indices

Post by SvenTH »

Hi all,
Hi Renger

at least, there is still a little issue. If my delivering route is not in a sorted row like i1 - i2 - i3 - i5 - i1 but maybe i1 - i2 - i5 - i3 - i1 then Parameter xt looks like:

INDEX 1 = v1

t1

i1.i2 1.000
i2.i5 1.000

This apparently is because nexti (in this case 'i3') is smaller than the actual examined 'i5' and the loop then isn't considering index 'i3' anymore.

Do you have an idea how to solve this issue? Maybe with another loop, this is what I try right now.

Thanks in advance,
Sven
User avatar
Renger
Posts: 639
Joined: 7 years ago

Re: Problems with looping and indices

Post by Renger »

Hi Sven
Although the last part is not very elegant, it seems to do the job as wanted

Code: Select all

Sets i   'locations'     / i1 * i6 /;
alias (i,j);

set trips /1*2/;

parameter xt(i,j,trips), x(i,j);

variable nexti;

x('i1','i2') = 1;
x('i1','i4') = 1;
x('i2','i5') = 1;
x('i5','i3') = 1;
x('i3','i1') = 1;
x('i4','i6') = 1;
x('i6','i1') = 1;

xt(i,j,trips) = 0;

parameter acti, actj;
loop(trips,
    NEXTI.L = 1;
    loop(i$(ord(i) = NEXTI.L),
        acti = ord(i);
        loop(j$(x(i,j) = 1),
            actj = ord(j);
            xt(i,j,trips) = 1;
            x(i,j)        = 0;
            NEXTI.L       = ord(j);
            if(actj = 1, xt(i,j,trips) = 1; break);
            if(ord(j) > ord(i), break);
        );
* Break out of the i loop if we move to a prior node and start i loop again
        if(actj < ord(i) and actj NE 1 , break);
    );
);   

parameter
    nnodes(trips) number of nodes per trip,
    count, lastnode(i,j,trips);

nnodes(trips) = sum((i,j), xt(i,j,trips));
 
* Assign the missing last node if we jumped back to a prior node
loop(trips,
    count = 0;
    loop(i,
        loop(j$xt(i,j,trips),
            count = count  + 1;
            if(ord(j) NE 1 and count = nnodes(trips),
                actj = ord(J);
                lastnode(i,j,trips) = actj;
            );
        );
    );
);

loop((i,j,trips)$lastnode(i,j,trips),
    xt(j,"i1",trips) = 1;
);
    
display xt, nnodes, lastnode;
Let me know if you manage to add the last loop into the original one.
Cheers
Renger
____________________________________
Enjoy modeling even more: Read my blog on modeling at The lazy economist
SvenTH
User
User
Posts: 6
Joined: 4 years ago

Re: Problems with looping and indices

Post by SvenTH »

Hi all,
Hi Renger,

thank you very much for your reply! This code works well if I just jump back once, but I need to jump back for several times. I copied one of these trips in your code but didn't manage to get the right xt by now. Do you have an idea how to solve this issue?

My trip looks like i1 - i2 - i6 - i3 - i5 - i9 - i4 - i1. The code gives me the following xt:

---- 62 PARAMETER xt

1

i1.i2 1.000
i2.i6 1.000
i3.i1 1.000
i6.i3 1.000

but it should look like:

---- 62 PARAMETER xt

1

i1.i2 1.000
i2.i6 1.000
i3.i5 1.000
i4.i1 1.000
i5.i9 1.000
i6.i3 1.000
i9.i4 1.000

Thanks again in advance for your great help,
Sven

Code: Select all

Sets i   'locations'     / i1 * i9 /;
alias (i,j);

set trips /1*2/;

parameter xt(i,j,trips), x(i,j);

variable nexti;

x('i1','i2') = 1;
x('i2','i6') = 1;
x('i6','i3') = 1;
x('i3','i5') = 1;
x('i5','i9') = 1;
x('i9','i4') = 1;
x('i4','i1') = 1;

xt(i,j,trips) = 0;

parameter acti, actj;
loop(trips,
    NEXTI.L = 1;
    loop(i$(ord(i) = NEXTI.L),
        acti = ord(i);
        loop(j$(x(i,j) = 1),
            actj = ord(j);
            xt(i,j,trips) = 1;
            x(i,j)        = 0;
            NEXTI.L       = ord(j);
            if(actj = 1, xt(i,j,trips) = 1; break);
            if(ord(j) > ord(i), break);
        );
* Break out of the i loop if we move to a prior node and start i loop again
        if(actj < ord(i) and actj NE 1 , break);
    );
);

parameter
    nnodes(trips) number of nodes per trip,
    count, lastnode(i,j,trips);

nnodes(trips) = sum((i,j), xt(i,j,trips));

* Assign the missing last node if we jumped back to a prior node
loop(trips,
    count = 0;
    loop(i,
        loop(j$xt(i,j,trips),
            count = count  + 1;
            if(ord(j) NE 1 and count = nnodes(trips),
                actj = ord(J);
                lastnode(i,j,trips) = actj;
            );
        );
    );
);

loop((i,j,trips)$lastnode(i,j,trips),
    xt(j,"i1",trips) = 1;
);

display xt, nnodes, lastnode;
User avatar
Renger
Posts: 639
Joined: 7 years ago

Re: Problems with looping and indices

Post by Renger »

Hi Sven

Just replace the = sign by "<" and subtract 1 from NEXTI.L:

Code: Select all

...
 loop(i$(ord(i) > NEXTI.L-1),   
... 
Solution

Code: Select all

----     62 PARAMETER xt  

                1           2

i1.i2       1.000
i2.i6       1.000
i3.i1       1.000
i3.i5                   1.000
i4.i1                   1.000
i5.i9                   1.000
i6.i3       1.000
i9.i4                   1.000
Cheers
Renger
____________________________________
Enjoy modeling even more: Read my blog on modeling at The lazy economist
SvenTH
User
User
Posts: 6
Joined: 4 years ago

Re: Problems with looping and indices

Post by SvenTH »

Hi all,
Hi Renger,

thanks again for your help. At least, your soultion is close, but not exactly what I want to do. Index 'trips' should only increase, if there is another trip starting in node 'i1'. In this case, there should only be one trip which is i1 - i2 - i6 - i3 - i5 - i9 - i4 - i1. Hope you can help.

Thanks again in advance,
Sven
User avatar
Renger
Posts: 639
Joined: 7 years ago

Re: Problems with looping and indices

Post by Renger »

Try this one (you don't need the loop for the last node trip anymore:

Code: Select all

parameter acti, actj;
loop(trips,
    NEXTI.L = 1;
    loop(i,
        loop(j$(x(i,j) = 1),
            actj = ord(j); acti = ord(i);
            xt(i,j,trips) = 1;
            x(i,j)        = 0;
            NEXTI.L       = ord(j);
            if(actj < acti and actj NE 1, break);
        );
        
    );
);
gives:

Code: Select all

i1.i2       1.000
i2.i6       1.000
i3.i5       1.000
i4.i1       1.000
i5.i9       1.000
i6.i3       1.000
i9.i4       1.000

____________________________________
Enjoy modeling even more: Read my blog on modeling at The lazy economist
SvenTH
User
User
Posts: 6
Joined: 4 years ago

Re: Problems with looping and indices

Post by SvenTH »

Hi all,
Hi Renger,

this is even closer, but index 'trips' doesn't count up if there is another tour starting in 'i1'. I just took a second tour in your code:

Code: Select all

Sets i   'locations'     / i1 * i9 /;
alias (i,j);

set trips /1*2/;

parameter xt(i,j,trips), x(i,j);

variable nexti;

x('i1','i2') = 1;
x('i2','i6') = 1;
x('i6','i3') = 1;
x('i3','i5') = 1;
x('i5','i9') = 1;
x('i9','i4') = 1;
x('i4','i1') = 1;

x('i1','i8') = 1;
x('i8','i7') = 1;
x('i7','i1') = 1;

xt(i,j,trips) = 0;

parameter acti, actj;
loop(trips,
    NEXTI.L = 1;
    loop(i,
        loop(j$(x(i,j) = 1),
            actj = ord(j); acti = ord(i);
            xt(i,j,trips) = 1;
            x(i,j)        = 0;
            NEXTI.L       = ord(j);
            if(actj < acti and actj NE 1, break);
        );

    );
);


display xt;
which gives me:

Code: Select all

                1

i1.i2       1.000
i1.i8       1.000
i2.i6       1.000
i3.i5       1.000
i4.i1       1.000
i5.i9       1.000
i6.i3       1.000
i7.i1       1.000
i8.i7       1.000
i9.i4       1.000
Thanks for your help!
Cheers Sven
Post Reply