Vehicle routing in a wood waste pickup system

In this paper, we analyze a new vehicle routing problem, the Prize Collecting Vehicle Routing Problem with Service Restrictions (PCVRPsr), which arises in wood-waste collection. It is a problem with a homogeneous fleet and a unique depot, in which the visit to some clients is not compulsory, but conditioned by the total needs of waste. We propose a formulation for this problem, which comes from a three-index vehicle flow formulation for the Vehicle Routing Problem. To optimize the plan, we explore methods based on decomposition. We analyze, in particular, the Dantzig–Wolfe decomposition applied to this formulation, and a branch-and-price scheme to find integer solutions. An algorithm was developed to obtain the computational results discussed at the end of the paper. In the branch-and-price tree, we applied a method for deriving lower bounds for the bin-packing problem, based on dual feasible functions, that makes the process more efficient.