Rounded Capacity Cuts

Rounded Capacity Cuts, referred to as RCCs, are a type of cutting plane used in capacity constrained vehicle routing problems to improve the lower bound of the linear programming (LP) relaxation.

In this section, we will discuss the RCC package used in RouteOpt. It provides the following functionalities:

  1. Easy call CVRPSEP.

    RouteOpt does not implement the RCC separation package itself, but instead calls the CVRPSEP package [Lysgaard et al., 2004], which is a C library for solving the Capacitated Vehicle Routing Problem (CVRP) using cutting planes.

  2. Updating the reduced cost (RC) associated with RCCs during the labeling algorithm.

  3. Calculating the coefficients of the constraint matrix associated with RCCs.

The following are details of the functionalities provided by the RCC package. I highly recommend reading the rest of this page before going through the following sections to understand how to use the package.

Definition

The following formulas describe the general form of the RCC:

  1. Basic Constraint for a Set \(S\):

\[x(S:S) \leq |S| - k(S)\]

  • \(x(S:S)\) represents the total flow that starts and ends within the customer set \(S\).

  • \(|S|\) denotes the total number of customers in \(S\).

  • \(k(S)\) is the lower bound on the number of vehicles required to serve the customers in \(S\).

  1. Constraint for the Complement Set \(\bar{S}\):

\[x(\bar{S}:\bar{S}) + \frac{1}{2}\,x(\{0\}:\bar{S}) - \frac{1}{2}\,x(\{0\}:S) \leq |\bar{S}| - k(S)\]

  • \(x(\bar{S}:\bar{S})\) represents the total flow among customers within the complement set \(\bar{S}\).

  • \(x(\{0\}:\bar{S})\) denotes the flow from the depot (represented by 0) to customers in \(\bar{S}\).

  • \(x(\{0\}:S)\) denotes the flow from the depot to customers in \(S\).

  1. Strengthened Constraint in the Enumeration State:

\[\sum_{p \in P} I\{(|p \cap S| \geq 1)\}\, x_p \geq k(S)\]

  • \(\sum_{p \in P}\) indicates summation over a set of routes.

  • \(I\{(|p \cap S| \geq 1)\}\) is the indicator function that equals 1 if path \(p\) includes at least one customer from \(S\), and 0 otherwise.

  • \(x_p\) is the decision variable associated with path \(p\).

Further Reading

For more detailed information, please refer to:

[LLE04]

Jens Lysgaard, Adam N Letchford, and Richard W Eglese. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100:423–445, 2004.