Multi-day routes in a multi-depot vehicle routing problem with intermediate replenishment facilities and time windows

We face a multi-depot vehicle routing problem with intermediate replenishment facilities and time windows (MDVRPITW), characterized by a heterogeneous fleet of vehicles. This paper proposes two formulations and an exact algorithm to solve the problem. The first formulation models the set of the intermediate replenishment facilities by an explicit set of nodes. The second formulation introduces replenishment arcs in place of these nodes, if a replenishment occurs between two successive nodes, and adopts standard arcs in case the load of a vehicle is not renewed. By suitable time windows associated with different days, both formulations easily allow the construction of multi-day routes, aimed at minimizing deadhead trips thanks to the possible storage of the freight in the vehicle depots between two consecutive workdays. To solve the problem, we propose a Branch & Price exact approach based on the second formulation. Some numerical experiments on real-type data show significant cost savings considering multi-day routes, compared to the single-day ones with deadhead movements from/to vehicle depots.