Separating constraints in the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) is a classic optimization problem. In the CVRP a set of customers needs to be satisfied in their demand by vehicles with limited capacity. Augerat et al. (1998) describe the cutting plane algorithm to obtain lower bounds for the CVRP. This algorithm iteratively solves linear relaxations and adds violated capacity constraints. Our research is mainly concerned with investigating heuristic methods to identify violated capacity constraints. We implement the methods described in Augerat et al. (1998) and also design our own advanced tabu and simulated annealing methods. Finally we investigate a variant of the CVRP which has emission zones where only electric vehicles are allowed to come. We develop constraint sets and identification heuristics to obtain lower bounds for this variant of the CVRP.