set V ; # set of nodes
set A within V cross V; # set of arcs
param k default 3; # number of vehicles
param maxlength default 5; # maximum length of a single vehicle's tour
param c {A} ; # costs (e.g. given by distances) of arcs
param home symbolic in V ; # start and end node of all tours, has a special role for this model
var x {A} binary ; # 1 if arc is chosen for a tour, 0 otherwise
var p {V} in 1..maxlength ; # indicates the position of a node in our sequence (path)
# we can define the maximum length of a single tour (in terms of its number of nodes)
# via upper bounds on p (parameter maxlength).
# objective function: minimize the total cost of arcs used
minimize TotalWeight: sum {(v,w) in A} c[v,w]*x[v,w] ;
# every node is left exactly once, except for the home node
s.t. OutArcs {v in V: v!=home}: sum{(v,w) in A} x[v,w] = 1 ;
# every node is entered exactly once, except for the home node
s.t. InArcs {w in V: w!=home}: sum {(v,w) in A} x[v,w] = 1 ;
# in contrast to the Hamiltonian cycle model, we allow that several arcs leave the home node;
# due to the OutArcs and InArcs constraints, each of those arcs corresponds to a tour
# that eventually has to return to the home node.
# the right hand side of the constraints Out_home and In_home specifies
# the number of tours (e.g. k = 1 gives a Hamiltonian cycle)
s.t. Out_home: sum {(home,w) in A} x[home,w] = k ;
s.t. In_home: sum {(v,home) in A} x[v,home] = k ;
# optional constraint, fixes the position number of the home node
s.t. DefHome: p[home] = 1 ;
# this is the key constraint for eliminating subtours
# it ensures that position numbers strictly increase along arcs
# However, we waive the condition for arcs entering the home node in order to allow closing
# the individual tours for the vehicles
# unintended cycles, that do not use the home node, are prevented
s.t. Connect {(v,w) in A: w != home}:
card(V)*x[v,w] - p[w] + p[v] <= card(V) - 1 ;