$Title  Handlungsreisendenproblem
$Ontext

Vorlesung: Distributionslogistik
Abschnitt: 3.3 Handlungsreisendenprobleme
Problemstellung: Ermittlung einer kuerzesten (knotenorientierten) Rundreise in einem Digraphen

 - Model -

Author: Rui Guo
Date: 23/10/2019

$Offtext

$eolcom//

$include tsp_data.gms

variables
   zeit    Gesamte Fahrzeit
   x(i,j)  Haeufigkeit mit der Strecke i-j auf der Rundreise durchfahren wird
   pi(i)   Stufenindex von Knoten i auf der Rundreise bei Indizierung mit pi(i0) gleich 0 ;

integer variable x, pi ;

equations
   def_zeit           Definition der Fahrzeit
   flusserhaltung(i)  Flusserhaltungsbedingung fuer Knoten i
   fluss_min(i)       Mindestflussstaerke durch Knoten i
   kurzyklen(i,j)     Miller-Tucker-Zemlin-Bedingung zur Vermeidung von Kurzzyklen ;

   def_zeit..                                zeit =e= sum((i,j)$a(i,j), c(i,j)*x(i,j)) ;
   flusserhaltung(i)..                       sum(j$a(i,j), x(i,j)) =e= sum(j$a(j,i), x(j,i)) ;
   fluss_min(i)..                            sum(j$a(i,j), x(i,j)) =g= 1 ;
   kurzyklen(i,j)$(a(i,j) and (ord(i)>1))..  pi(j)-pi(i) =g= card(i)*(x(i,j)-1)+1 ;

model tsp / all / ;

options mip = cplex
        optcr = 0
        reslim = 60 ;

solve tsp minimzing zeit using mip ;

display zeit.l, x.l ;