# Capacitated vehicle routing (MTZ load form)
#
# Routes a fleet from one depot so every customer is visited once and no
# vehicle exceeds its capacity. The load variable does double duty — it
# rules out subtours the way MTZ does for the TSP, and because it
# accumulates demand along the route it enforces capacity at the same time,
# which is why this is the compact CVRP formulation of choice.
#
# Technique: Degree constraints per customer plus load potentials that both
# eliminate subtours and enforce capacity: u_j >= u_i + q_j -
# Q(1 - x_ij).
#
# On this instance the optimum is 25 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Miller, C. E., Tucker, A. W. and Zemlin, R. A. (1960). Integer
# programming formulation of traveling salesman problems. Journal of the ACM
# 7(4), 326–329. doi:10.1145/321043.321046
model m
set V = {1, 2, 3, 4}
set C = {2, 3, 4}
const c = {{0, 1, 10, 12},
{1, 0, 10, 10},
{10, 10, 0, 1},
{12, 10, 1, 0}}, forall i in V, forall j in V
const q = {0, 2, 2, 2}, forall i in V
const lim = 5
const K = 2
bin x, forall i in V, forall j in V
# accumulated load on arrival at each customer
var 0 <= u <= 5, forall i in V
min sum_{i in V}{sum_{j in V setminus {i}}{c_{i,j} * x_{i,j}}}
# every customer entered once and left once
constr sum_{i in V setminus {j}}{x_{i,j}} = 1, forall j in C
constr sum_{j in V setminus {i}}{x_{i,j}} = 1, forall i in C
# the depot dispatches and receives at most K vehicles
constr sum_{j in C}{x_{1,j}} <= K
constr sum_{i in C}{x_{i,1}} <= K
# load accumulates along a route: subtours cannot close, and capacity is
# enforced by u's own upper bound
constr u_{j} >= u_{i} + q_{j} - lim * [1 - x_{i,j}], forall i in C, forall j in C setminus {i}
constr u_{j} >= q_{j}, forall j in C
end
import elytica
Read this through MCP: read with path: "formulations/cvrp-mtz", or resource hlpl://formulations/cvrp-mtz.