A Sampling Procedure for Real-Life Rich Vehicle Routing Problems

In this paper we address a rich variant of the vehicle routing problem which occurs in real-life applications. Among other aspects we take into consideration time windows, simultaneous delivery and pick-up at customer locations, multiple use of vehicles, and timely allocation of vehicles to loading bays at the depot. In order to solve practical instances of the resulting real-life rich vehicle routing problem, efficient methods are required. For this reason, we present a sampling procedure, which is a multi-start algorithm that executes in each call a substantial extension of the well-known savings algorithm. Using a set of suitable benchmark instances, we assess the performance of the proposed sampling procedure.