The multi-trip vehicle routing problem with time windows and unloading queue at depot

Motivated by the practice of urban waste collection, we introduce a new variant of the multi-trip vehicle routing problem with time windows, where vehicles unload cargos collected from customers at a depot that owns a limited unloading capacity, and therefore some vehicles need to wait at a queue once the unloading capacity is fully occupied. Unloading queue at depot significantly compicates this problem since it makes a trip involve traveling, waiting, and unloading stages. We first formulate this problem into a trip-based set partitioning model, which has two sets of mutual exclusion constraints. To solve the model, we propose a branch-and-price-and-cut algorithm (BPC), in which the linear relaxation of the model is solved by column generation, and moreover, the relaxation gap is tightened by incorporating rounded capacity inequalities. Particularly, the mutual exclusion constraints induce a new and challening pricing problem, and we design a novel label-setting algorithm with tailored label structure to solve it. We conduct compuational experiments on a set of random instances generated from the Solomon’s benchmark, and the results demonstrate the effectiveness of the proposed model and algorithm.