A branch-and-price algorithm for 2-period vehicle routing problems

We consider a Vehicle Routing Problem (VRP) with deterministic orders in two periods from a set of stores. Orders in period 1 (2) can be postponed (advanced) to the other period but any diversion from the initial orders incurs a penalty. From the perspective of a Logistics Service Provider (LSP), such diversions could be beneficial if savings in the routing costs outweigh the penalties. So could they be from a store's view, as the store can set a high enough penalty to compensate the diversion from its own optimal orders. In this paper, we introduce a new model where we seek a better solution for the LSP, compared to solving two independent VRPs with fixed orders, by allowing orders to be fully postponed or advanced. We apply a branch-and-price algorithm to solve this model to optimality. Many cutting-edge techniques are implemented to have an efficient branch-and-price algorithm, and two ideas to possibly improve the upper bound are tested. We draw algorithmic and managerial insights based on our test instances.