New savings based algorithms for time constrained pickup and delivery of full truckloads

In this paper we deal with the pickup and delivery of full truckloads under time window constraints. Our objective function is to minimize empty vehicle movements, as these use resources without directly adding value to the products transported. We first give an exact formulation of the problem. After that we present a relaxed problem formulation based on network flows, which can be used to calculate a lower bound to the solution value. Furthermore, we propose four different savings based heuristics for the problem. Our results show that these heuristics find very good solutions quickly. We also perform a sensitivity analysis by studying the impact of time window tightness on the performance of our heuristics.