A pulse algorithm for column generation for a generalized vehicle routing formulation

In this thesis we describe the use of an exact algorithm to solve a pricing problem arising from applying column generation in the context of the capacitated vehicle routing problem. A generalization of the vehicle flow and set covering formulations is used, known as the p-step formulation. This causes the corresponding pricing problem to be modeled as an elementary resource constrained shortest path problem, where the number of customers on a path is restricted. To solve this pricing problem, we utilize an exact algorithm, known as the pulse algorithm. In particular, we use it to quickly identify negative reduced cost variables which can be added to the linear relaxation of the p-step formulation. Four pruning strategies are used which are mostly adapted to be specifically applicable to our pricing problem. The performance is tested using known benchmark problem instances in the literature and compared to a labeling algorithm. The results show that the pulse algorithm is able to partially outperform the labeling algorithm in terms of both bounds and computation times. For one particular instance, a tighter bound can be obtained while requiring 41 times less computation time. However, when the allowed number of customers on a path increases to its maximum, the computation times of the pulse algorithm become intractable in contrast to the labeling algorithm. This suggests that multiple pricing algorithms might be required in order to obtain the overall best performance.