A Tabu Search Heuristic for the Vehicle Routing Problem with Two-Dimensional Loading Constraints

This thesis evaluates the paper of Gendreau et al. (2008), where the well-known Capacitated Vehicle Rout- ing Problem (CVRP) is addressed. They incorporate in this problem, which usually only depends on weight constraints, two-dimensional loading constraints. The CVRP minimizes the transportation costs resulting from delivering demanded goods to customers, carried out by a fleet of vehicles from a single depot. Since we now want a load of items to fit two-dimensionally in a vehicle, a feasibility check of the two-dimensional packing (2L) is executed for every vehicle. In the paper a Tabu Search heuristic is proposed for solving the combined problem, denoted as 2L-CVRP, since it is NP-hard and particularly hard to solve in practice. The effectiveness of the heuristic is evaluated with computational experiments.