apps/route/optimizers/route_opt.mzn

   1
   2 % Number of nodes
   3 int: N;
   4     % Start node
   5 0..N-1: Start;
   6     % End node
   7 0..N-1: End;
   8     % Number of edges (directed arcs)
   9 int: M;
  10     %  The actual edges
  11 set of int: Edges = 1..M;
  12     % Edge lengths
  13 array[Edges] of int: L;
  14     % Edge start node
  15 array[Edges] of 0..N-1: Edge_Start;
  16 array[Edges] of 0..N-1: Edge_End;
  17
  18     % Variable indicating if edge is used
  19 array[Edges] of var 0..1: x;
  20
  21 constraint
  22     forall( i in 0..N-1 ) (
  23         if i = Start then
  24                 % outgoing flow
  25             sum(e in Edges where Edge_Start[e] = i)(x[e]) -
  26                 % incoming flow
  27             sum(e in Edges where Edge_End[e] = i)(x[e])
  28             = 1
  29         elseif i = End then
  30             sum(e in Edges where Edge_Start[e] = i)(x[e]) -
  31             sum(e in Edges where Edge_End[e] = i)(x[e])
  32             = -1
  33         else
  34             sum(e in Edges where Edge_Start[e] = i)(x[e]) -
  35             sum(e in Edges where Edge_End[e] = i)(x[e])
  36             = 0
  37         endif
  38     );
  39
  40
  41 solve minimize sum(e in Edges)( L[e] * x[e] );
  42 %solve satisfy;
  43
  44 output ["Length: ", show(sum(e in Edges)(L[e] * x[e])), "\n"] ++
  45        ["Start : ", show(Start), "\n"] ++
  46        ["End   : ", show(End), "\n\n"] ++
  47        ["Edges in shortest path:\n"] ++
  48        [ if   fix(x[e]) = 1
  49          then show(Edge_Start[e]) ++ " -> " ++ show(Edge_End[e]) ++ "\n"
  50          else ""
  51          endif | e in Edges
  52        ];
  53