Models, Solutions and Relaxations of the Asymmetrical Capacitated Vehicle Routing Problem

In this thesis, we take a look at the Asymmetrical Capacitated Vehicle Routing Problem (ACVRP). We will take a look at different possible formulations for the problem and choose one based on the ease of implementation, the computation speed of solving it, and the available relaxations. The problem, and its relaxations, will be modeled and solved using AIMMS, a commercial modeling software. Using the methods described above, we model different cases and instances of the problem using a Two-Index Vehicle Flow formulation. We apply an Assignment Problem relaxation and a Linear Programming relaxation to each of the instances. We find that the problem is easiest to solve when all customers are relatively close to each other (as opposed to being placed in separate clusters that are relatively far from each other), and that the LP relaxation gives bounds with a fairly good quality in short periods of time.Electrical Engineering, Mathematics and Computer ScienceDelft Institute of Applied MathematicsOptimizatio