TSP Traveling Salesman Problem - Avoiding Short Cycles

[Goo.Gle]

Hello,
I am a newbie in AIMMS and just starting to play around with it. So,
Implementing the TSP so far is not a problem but I am wondering how to
avoid short cycles in a efficient manner.
I am goint to implement:

sum(i element Q) sum (j element V \ Q) x(i,j) >=1
Q is the powerset of all destinations.

Can you give me a guidance how to implement those two subsets?

Regards
Goo.Gle

[Pim]

Hi,

TSP is a difficult type of problem, and avoiding short cycles/subtours
in an efficient manner is one of the difficult parts. You want your
constraint to hold for all subsets of your 'locations', and those are
many: two to the power of your number of locations. If you don't have
many locations this simple mip approach works, but if you do, you
might better look at alternatives. There is a lot of literature about
TSP. In the Traveling Salesman example that comes with AIMMS you can
also see the implementation of some algorithm.

If you have a small set of locations and want to continue with your
approach below, you could generate the subsets the following way. The
procedure below generates a set LocationSubsets with an element for
each possible subset. The procedure walks through the numbers 1.. 2^n
(with n=card(locations)-1) and stores in the numerical parameter
LocationInLocationSubset which elements belong to a certain
LocationSubset.

MaxCounter := Power(2, card(Locations))-1;
Counter := 1;

while counter < MaxCounter do

SetElementAdd( LocationSubsets, LocationSubSet, FormatString( "%i",
Counter ) );
ElementCheck := card(Locations);
LeftToConvert := Counter;

while ElementCheck > 0 do

ElementCheck -= 1;

if power( 2, ElementCheck ) <= LeftToConvert then

LocationInLocationSubset( LocationSubset, element( Locations,
ElementCheck+1 ) ) := 1;
LeftToConvert -= power( 2, ElementCheck )

endif;

endwhile;

Counter += 1;

endwhile;

There are probably easier and more efficient ways to do this, but it
does the trick. With lss an index in LocationSubset and i and j
indices in Locations you can have a constraint like
EliminateSubTours( lss )
sum( ( i,j ) | LocationInLocationSubset( lss, i ) and not
LocationInLocationSubset( lss, j ), x(i,j) ) >= 1

Regards
Pim Beers
AIMMS Specialist

[Goo.Gle]

Hi Pim,

thank you for your help.
I will try it. Choosing this way avoiding short cycles is to get
familiar with AIMMS.

Best regards
Goo.Gle

[f.wag...@gmail.com]

Hi,

I am trying to implement your suggested solution. I therefore created a procedure and created the identifiers, but i receive a error message stating:

"The second argument of intrinsic procedure "SetElementAdd" is not a scalar element parameter into the set "KnotenSubsets" (or another set with the same root set)."

DECLARATION SECTION Subtours_Declaration

    PARAMETER:
       identifier :  MaxCounter ;

    PARAMETER:
       identifier :  Counter ;

    SET:
       identifier :  KnotenSubsets ;

    SET:
       identifier :  KnotenSubSet
       subset of  :  KnotenSubsets ;

    PARAMETER:
       identifier :  KnotenInKnotenSubset ;

    PARAMETER:
       identifier :  ElementCheck ;

    PARAMETER:
       identifier :  LeftToConvert ;

  ENDSECTION  ;

  PROCEDURE
    identifier :  Subtours
    body       :  
      MaxCounter := Power(2, card(Knoten))-1;

      Counter := 1;
     
      while counter < MaxCounter do

     
         SetElementAdd( KnotenSubsets, KnotenSubSet, FormatString( "%i",
      Counter ) );
         ElementCheck := card(Knoten);

         LeftToConvert := Counter;
     
         while ElementCheck > 0 do
     
            ElementCheck -= 1;
     
            if power( 2, ElementCheck ) <= LeftToConvert then

     
               KnotenInKnotenSubset( KnotenSubsets, element( Knoten,

      ElementCheck+1 ) ) := 1;
               LeftToConvert -= power( 2, ElementCheck )
     
            endif;
     
         endwhile;
     
         Counter += 1;
     
      endwhile;

How can I fix this error?

Thanks,
Florian

[Guido Diepen]

Hi Florian,

the SetElementAdd function requires an element parameter as the second parameter. It will store the element that it just created in this element parameter. You are currently supplying a subset as the second argument, which this function does not accept.

To see what kind of arguments you should provide to internal AIMMS functions, you can right-click on the function in the IDE then select "Help on" from the context menu and then select the name of the function. This will open the AIMMS Function Reference on the page for the given function.

Guido Diepen

AIMMS Specialist

[f.wag...@gmail.com]

Hi Guido,

thanks for your response. My problem is in declaring the sets "KnotenSubSets" and "KnotenSubSet" I guess.
KnotenSubSets is the set containing all elements of type "KnotenSubSet", and KnotenSubSet contains elements of the type "Knoten".

But I get the following error message now: "This implementation of AIMMS does not provide feature "Passing (slices of) indexed sets as function/procedure arguments" in the line of "SetElementAdd(...)".

Thanks for any help in advance, Florian

DECLARATION SECTION Subtours_Declaration

    PARAMETER:
       identifier   :  MaxCounter ;

    PARAMETER:
       identifier   :  Counter ;

    SET:

       identifier   :  KnotenSubSets
       index domain :  Iss
       subset of    :  Knoten ;

    SET:
       identifier   :  KnotenSubSet
       subset of    :  Knoten

       index        :  Iss ;

    PARAMETER:
       identifier   :  KnotenInKnotenSubset
       index domain :  (Iss,i)
       range        :  binary ;

    PARAMETER:
       identifier   :  ElementCheck ;

    PARAMETER:
       identifier   :  LeftToConvert ;

  ENDSECTION  ;

  PROCEDURE
    identifier :  Subtours
    body       :  
      MaxCounter := Power(2, card(Knoten))-1;
      Counter := 1;
     
      while counter < MaxCounter do

     
         SetElementAdd( KnotenSubSets, KnotenSubSet, FormatString( "%i",

      Counter ) );
         ElementCheck := card(Knoten);
         LeftToConvert := Counter;
     
         while ElementCheck > 0 do
     
            ElementCheck -= 1;
     
            if power( 2, ElementCheck ) <= LeftToConvert then

     
               KnotenInKnotenSubset( KnotenSubSets, element( Knoten,

      ElementCheck+1 ) ) := 1;
               LeftToConvert -= power( 2, ElementCheck )
     
            endif;
     
         endwhile;
     
         Counter += 1;
     
      endwhile;

  ENDPROCEDURE  ;

[f.wag...@gmail.com]

I figured out the error,  KnotenSubSet has to be defined as a parameter within the declaration of KnotenSubSets. Now it works fine. Thanks for the input!

Florian

 DECLARATION SECTION Subtours_Declaration

    PARAMETER:
       identifier   :  MaxCounter ;

    PARAMETER:
       identifier   :  Counter ;

    SET:
       identifier   :  KnotenSubSets

       index        :  kss
       parameter    :  KnotenSubSet ;

    PARAMETER:
       identifier   :  KnotenInKnotenSubset
       index domain :  (kss,i)

       range        :  binary ;

    PARAMETER:
       identifier   :  ElementCheck ;

    PARAMETER:
       identifier   :  LeftToConvert ;

  ENDSECTION  ;

  PROCEDURE
    identifier :  Subtours
    body       :  
      MaxCounter := Power(2, card(Knoten))-1;
      Counter := 1;
     
      while counter < MaxCounter do
     
         SetElementAdd( KnotenSubSets, KnotenSubSet, FormatString( "%i",
      Counter ) );
         ElementCheck := card(Knoten);
         LeftToConvert := Counter;
     
         while ElementCheck > 0 do
     
            ElementCheck -= 1;
     
            if power( 2, ElementCheck ) <= LeftToConvert then

     
               KnotenInKnotenSubset( KnotenSubSet, element( Knoten,

[Guido Diepen]

Hi Florian,

declaring the knotensubset as a parameter in the attributes of the KnoteSubSets identifiers, means you are introducing it as an element parameter with knotenSubSets as the range. Alternatively, you can also declare a separate element parameter identifier in the model tree and set its range to KnotenSubSets to achieve the same.

Guido Diepen

AIMMS Specialist

[f.wag...@gmail.com]

Hi Guido,

thanks for the input.

The subtour elimination works fine under the consumption I have one time period and all nodes have to be visited.
In my model I have d time periods over a planning horizon. Based on the visit frequency only a subset of the nodes have to be visited during a time period d.

My question now is how can I assure the subtour elimination for every tour of a vehicle. E.g. Vehicle 1 is chosen to by the optimization algorithm to drive the tour 0-3-4-5-0 . To eliminate the subtour I would now have only the set [0,3,4,5] to create my powerset for (within the subtour elimination algorithm).

How could I implement this in AIMMS?

Happy Easter and thanks,
Florian

[f.wag...@gmail.com]

I solved the problem now by using the following constraint instead of the algorithm:

 CONSTRAINT:
       identifier   :  EliminiereSubtour2
       index domain :  (K,d,i,j) | Subtour2Aktiv
       text         :  "Subtour Eliminierung in einer Zeile"
       definition   :  subtour_counter(j,K,d) >= subtour_counter(i,K,d) + 1 - 50*(1-Transport(i,j,d,K))  ;

Thanks for the support.