Version: 0.1

Author: Andreas Bley

We want to solve the vehicle routing problem (VRP) on a graph \(G = (V,E)\) with \(V = J \cup {d}\), where \(d\) is the depot and the distances are given by the length function \(l_e: E \to R_{\ge 0}\).

Consider the MIP formulation

\[ \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} \]

where \(T_k\) is the set of tours visiting at most \(k\) customers with repetitions of customers allowed and \(a^t_e (a^t_j)\) counts how often edge e (node j) is traversed in \(t \in T_k\). The model contains two types of variables, namely \( x \) which selects tours fractionally and \( y \) which indicates which edges of the graph are in at least one selected tour. Note that it is possible to use an edge as a forward and backward edge in a tour. This is necessary to ensure that a customer \( j \) with \( |\delta(j)| = 1 \) can be served.

Since the number of tours can be exponential in the size of the graph, the algorithm starts with some subset \( \bar{T} \subseteq T_k \) and adds further tours during the solution process. This way it tries to improve the current LP solution.

Let \( \lambda_e \) and \( \gamma_i \) be the dual multipliers for the first and seconds constraint of the MIP and we define the costs of a tour \( T \in T_k \) as:

\[ C(T) := \sum_{e \in E(T)} \lambda_e - \sum_{j \in V(T)} \gamma_j \]

The resulting pricing problem \( \min_{T \in T_k} C(T) \) can be solved with dynamic programming. The algorithm is similar to Dijkstra's shortest path algorithm if we shift the the costs \( \gamma_j \) from the nodes to the edges of \( G \).

Branching decisions on the variables \( y \) modify the pricing problem only slightly. The branch \( y_e = 0\) forbids \( e \) to be contained in a tour which can be easily realized if we remove \( e \) from \( E \). The branch \( y_e \ge 1 \) does not have an impact on the pricing problem.

Further information about the pricing routine and the dynamic program can be found in the documentation of the corresponding files.

The pricer pricer_vrp.cpp shows how to perform column generation in SCIP and how to solve the above described pricing problem which uses an implementation of a priority queue implemented in pqueue.h. In main_vrp.cpp we read the instance, create all necessary data and set up SCIP.

Installation

See the Install file