Milk Run Optimization with Delivery Windows and Hedging Against Uncertainty

Summary Milk runs are an important transportation concept, e.g. in the automotive industry. Trucks start from a depot, pick up goods at different suppliers, and deliver those goods to a single customer. Therefore, milk runs are technically a pick up and delivery problem with multiple pick ups and a single delivery. They make it possible to deliver small lots eficiently and thus lower average inventory levels. Prerequisite is that there are several frequent orders from suppliers that are closely located, otherwise transshipment centers will be used in spite of handling costs. Pickup&Delivery problems calculate routes for single days, sometimes with the additional restriction of time windows for delivery. Models and algorithms for these problems exist and can help in practice as leadtimes are usually very short, in most cases only one day. It has been discussed whether it would be better to allow for delivery windows of a few days so that carriers have more leeway for route optimization (cf. [1]). Now the routing problem is extended with the problem of allocating orders to days. The integrated solution requires vehicles to make multiple trips and is formulated as the VRP with Multiple Trips (VRPM). The VRPM has found only little attention so far: “Although in practice multiple route assignment is common, there is a shortage of papers covering this feature.”[2] It is even more interesting to look at the problem from a dynamic point of view, i.e. to iterate through the days and to assign incoming orders to days without having information on future orders.