Branch-and-price: principles and its application to a 2-period vehicle routing problem

We review branch-and-price as an efficient algorithm to solve integer programming problems with huge number of variables. In particular, we discuss column generation algorithm as the main engine in branch-and-price. Implementation of branch-and-price to solve the most basic version of the well-known vehicle routing problem (VRP) is investigated, and some common tricks are introduced. Then, a new extension of VRP is introduced and exploitation of branch-and-price to solve it is discussed. We consider a 2-period vehicle routing problem where each vertex of the network has a positive demand for period 1, 2, or both. Each demand on period 1 can be postponed to period 2 in order to decrease sum of the routing costs on two periods, but it is penalized in the objective function. Similarly, each demand on period 2 can be advanced to period 1, and yet penalized, with the hope of reducing routing costs. We have used many of the classic tricks to implement branch-and-price for solving our 2-period VRP. We have also used new tricks to (1) possibly improve the upper bound during the course of column generation in each node and (2) decrease the computations time to solve pricing problem in column generation.