Complexity of inventory routing problems when routing is easy

Research output: Contribution to JournalArticleAcademicpeer-review

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, of 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.

Original languageEnglish
JournalNetworks
DOIs
Publication statusAccepted/In press - 2020

Fingerprint

Traveling salesman problem
Hardness
Planning
Dynamic programming
Computational complexity
Scheduling
Polynomials
Costs

Keywords

  • approximation
  • computational complexity
  • dynamic programming
  • inventory routing
  • periodic replenishment
  • pinwheel scheduling

Cite this

@article{6e1946ae956c47ec83c5abf62b2af100,
title = "Complexity of inventory routing problems when routing is easy",
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, of 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.",
keywords = "approximation, computational complexity, dynamic programming, inventory routing, periodic replenishment, pinwheel scheduling",
author = "Baller, {Annelieke C.} and {van Ee}, Martijn and Maaike Hoogeboom and Leen Stougie",
year = "2020",
doi = "10.1002/net.21908",
language = "English",
journal = "Networks",
issn = "0028-3045",
publisher = "Wiley-Liss Inc.",

}

Complexity of inventory routing problems when routing is easy. / Baller, Annelieke C.; van Ee, Martijn; Hoogeboom, Maaike; Stougie, Leen.

In: Networks, 2020.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Complexity of inventory routing problems when routing is easy

AU - Baller, Annelieke C.

AU - van Ee, Martijn

AU - Hoogeboom, Maaike

AU - Stougie, Leen

PY - 2020

Y1 - 2020

N2 - 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, of 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.

AB - 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, of 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.

KW - approximation

KW - computational complexity

KW - dynamic programming

KW - inventory routing

KW - periodic replenishment

KW - pinwheel scheduling

UR - http://www.scopus.com/inward/record.url?scp=85074029467&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074029467&partnerID=8YFLogxK

U2 - 10.1002/net.21908

DO - 10.1002/net.21908

M3 - Article

JO - Networks

JF - Networks

SN - 0028-3045

ER -