Scientific Program > Talks by Speaker > Baller Annelieke

In the Inventory Routing Problem (IRP) inventory management and route optimization are combined. The Traveling Salesman Problem (TSP) is a special case of the IRP, hence the IRP is NP-hard. We consider special cases of the IRP other than TSP for which it is not clear in advance whether these problems are easy to solve or NP-hard. First, we study cases in which the metric space is a half-line. The problems differ in the number of vehicles, the number of days in the planning horizon and the processing times of the customers. Our main result is a polynomial time dynamic programming algorithm for the case with uniform processing times and a planning horizon of two days. Second, for a family of problems we show that the complexity is comparable to the complexity of the Pinwheel Scheduling Problem which is long-standing open question. Third, NP-hardness is shown for problems with non-uniform processing times. Finally, we study the problem with one vehicle, an infinite planning horizon, uniform processing times and customers located in the Euclidean plane. Instead of computing the routing cost exactly, we approximate the routing cost avoiding immediate NP-hardness via the TSP. We show that with a given route cost approximation this problem is strongly NP-hard.