! Chinese Postman problem,   (CPostman.lng);
! Find the shortest path that covers all arcs
  in a network at least once;
! Euler first described this problem in terms of traversing
the bridges of Koenigsberg.  Kwan Mei-Ko first gave an
explicit method for solving the undirected version;
! Keywords: Chinese postman, Euler, Koenigsberg bridge, Kwan Mei-Ko,
   Tour, Routing;
SETS:
 node;
 arc;
 axnxn( arc, node, node): cij, cji, yij, yji;
ENDSETS
DATA:
! Parameters:
    cij(b,i,j) = cost of going from i to j on arc/bridge b,
    cji(b,i,j) = cost of going from j to i on arc/bridge b.
If an arc is one-way, make its cost for the other way very high;

! The Koenigsberg bridge problem described by Euler,
with costs;
!CaseKng; node = rbank, lbank, isle1, isle2!CaseKng; arc = b1 b2 b3 b4 b5 b6 b7!CaseKng;  
      axnxn       cij cji = 
  b1 rbank, isle1  3   4 
  b2 rbank, isle1  2   1 
  b3 rbank, isle2  5   5 
  b4 lbank, isle1  6   4 
  b5 lbank, isle1  3   2 
  b6 lbank, isle2  3   4 
  b7 isle1, isle2  1   2
;
! Another (undirected) data set;
!Case01   node = node1 node2 node3 node4 node5 node6 node7;
!Case01   arc = a12 a14 a15 a23 a25 a27 a34 a35 a36 a37 a45 a67;
!Case01  
      axnxn       cij cji =
  a12 node1 node2   5   5
  a14 node1 node4   4   4
  a15 node1 node5   1   1
  a23 node2 node3   3   3
  a25 node2 node5   1   1
  a27 node2 node7   1   1
  a34 node3 node4   2   2
  a35 node3 node5   3   3
  a36 node3 node6   1   1
  a37 node3 node7   2   2
  a45 node4 node5   1   1
  a67 node6 node7   3   3;
ENDDATA
SUBMODEL euler:
! Minimize the cost of the arcs traversed;
  min = costot;
   costot = @SUM( axnxn(b,i,j): cij(b,i,j)*yij(b,i,j) + cji(b,i,j)*yji(b,i,j));

! Each arc/bridge b must be traversed at least once in either
   the forward direction i -> j  or the reverse direction j -> i;
  @FOR( axnxn(b,i,j): 
   [cover]  yij( b, i, j) + yji( b, i, j) >= 1;
      );

! Number entries into node k = number of departures from node k;
  @FOR( node( k):
   [flobal] @SUM( axnxn( b, i, k): yij( b, i, k)) + @SUM( axnxn( b, k, i): yji( b, k, i)) =
            @SUM( axnxn( b, k, j): yij( b, k, j)) + @SUM( axnxn( b, j, k): yji( b, j, k)); 
      );
! The yij, yji must be integer;
  @FOR( axnxn( b, i, j):
    @GIN( yij( b, i, j)); @GIN( yji( b, i, j));
      );
ENDSUBMODEL

CALC:
!  @gen( euler);   @SOLVE( euler);

! Write a brief report;
  @WRITE(' Total cost of all arcs travelled= ', costot, @NEWLINE( 1));
  @WRITE('   List of (sub)Tour(s)', @NEWLINE( 1));
  @WRITE(' Arc   From    To  ', @NEWLINE( 1));

! Find an arc that still needs to be traveled;
  more = 1;
  @WHILE( more:
   more = 0;
   @FOR( axnxn(b,i,j) | yij( b, i, j) + yji( b, i, j)  #gt# 0.5:
      more = 1;
      home = i; ! Start a new subroute here;
      curnode = i;
      nunode = 0;
       );
    @while( nunode #ne# home:    ! Trace out the subtour;
! Find an arc that is used and incident to curnode;
       @FOR( axnxn( b, i, j) | ( yij( b, i, j) #gt# 0.5 #and# i #eq# curnode ) 
                          #or# ( yji( b, i, j) #gt# 0.5 #and# j #eq# curnode):
         isv = i;
         jsv = j;
         bsv = b;
           ); 
     @ifc( yij( bsv, isv, jsv) #gt# 0.5 : ! Which direction traversed       @write( ' ', arc( bsv),'   ', node( isv),'   ', node(jsv), @newline(1));
       yij( bsv, isv, jsv) = yij( bsv, isv, jsv) - 1;
       nunode = jsv;
      @else
       @WRITE( ' ', arc( bsv),'   ',node( jsv),'   ', node( isv), @NEWLINE(1));
       yji( bsv, isv, jsv) = yij( bsv, isv, jsv) - 1;
       nunode = isv;
       );
      curnode = nunode;
       );
      );

! To find a complete tour, find any tour starting and returning to node 1.
 If this tour does not cover all arcs, 
    find some node v on the tour that has untraveled arcs,
    find a tour starting and returning to v and splice it in.
Repeat until all arcs are traversed;

ENDCALC