Complexity of inventory routing problems when routing is easy

Journal Article

Abstract 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 investigate how other aspects than routing influence the complexity of a variant of the IRP. We first study problem variants on a point and on the half‐line. The problems differ in the number of vehicles, the number of days in the planning horizon and the service times of the customers. Our main result is a polynomial time dynamic programming algorithm for the variant on the half‐line with uniform service times and a planning horizon of 2 days. Second, for nearly any problem in the class with nonfixed planning horizon, we show that the complexity is dictated by the complexity of the pinwheel scheduling problem, for which the complexity is a long‐standing open research question. Third, NP‐hardness is shown for problem variants with nonuniform servicing times. Finally, we prove strong NP‐hardness of a Euclidean variant with uniform service times and an easily computable routing cost approximation, avoiding immediate NP‐hardness via the TSP.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.