Solving Constraint Integer Programs
We want to solve the vehicle routing problem (VRP) on a graph with , where is the depot and the distances are given by the length function .
Consider the MIP formulation
where is the set of tours visiting at most customers with repetitions of customers allowed and counts how often edge e (node j) is traversed in .
with 
, where 
is the depot and the distances are given by the length function 
.![\[ \begin{array}[t]{rll} \min & \displaystyle \sum_{e \in E} l_e y_e \\ & & \\ s.t. & -y_e + \sum_{t \in T_k} a^t_e x_t \leq 0, & \forall e \in E\\ & \displaystyle \sum_{t \in T_k} a^t_j x_t = 1, & \forall j \in J \\ & y(\delta(j)) = 2, & \forall j \in J \\ & y_e \in \{0,1,2\}, & \forall e \in E \\ & x_t \in [0,1], & \forall t \in T_k \end{array} \]](form_4.png)
is the set of tours visiting at most 
customers with repetitions of customers allowed and 
counts how often edge e (node j) is traversed in 
.