CVRP Exact Formulation Comparison

Author: WGM

Three exact formulations for the Capacitated Vehicle Routing Problem (CVRP), implemented in Python with IBM CPLEX (via docplex / native API).

Since CPU time is generally strongly correlated to, amongst other factors, the capacity utilisation of each vehicle, these instances and scripts are specifically designed to test how computational effort scales and how different formulations handle tight capacity constraints.

The Formulations

These beautiful formulations are credited to and inspired by the following original sources, with a notable mention to Toth & Vigo (2002), where these models are comprehensively described:

• DFJ: DFJ with branch-and-cut | Dantzig, Fulkerson & Johnson (1954)
• Flow: Single-commodity flow | Gavish & Graves (1978)
• MTZ: Miller–Tucker–Zemlin | Miller, Tucker & Zemlin (1960)

Requirements

• Python 3.8+
• IBM CPLEX (with docplex; DFJ B&C additionally requires the native cplex Python API)
• NumPy, Matplotlib

Usage

Configure instance parameters (seed, n, K, Q, UTIL_TARGET) at the top of any script and run directly:

python CVRP_Flow.py