We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

Approximation algorithms for replenishment problems with fixed turnover times / Bosman, Thomas; van Ee, Martijn; Jiao, Yang; Marchetti-Spaccamela, Alberto; Ravi, R.; Stougie, Leen. - STAMPA. - 10807:(2018), pp. 217-230. (Intervento presentato al convegno 13th Latin American Symposium tenutosi a Buenos Aires; Argentina) [10.1007/978-3-319-77404-6_17].

Approximation algorithms for replenishment problems with fixed turnover times

Marchetti-Spaccamela, Alberto;
2018

Abstract

We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.
2018
13th Latin American Symposium
Theoretical Computer Science; Approximation algorithms; Traveling salesman
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Approximation algorithms for replenishment problems with fixed turnover times / Bosman, Thomas; van Ee, Martijn; Jiao, Yang; Marchetti-Spaccamela, Alberto; Ravi, R.; Stougie, Leen. - STAMPA. - 10807:(2018), pp. 217-230. (Intervento presentato al convegno 13th Latin American Symposium tenutosi a Buenos Aires; Argentina) [10.1007/978-3-319-77404-6_17].
File allegati a questo prodotto
File Dimensione Formato  
Bosman_Postprint_Approximation-Algorithms_2018.pdf

Open Access dal 02/06/2019

Note: https://link.springer.com/chapter/10.1007/978-3-319-77404-6_17
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 442.59 kB
Formato Adobe PDF
442.59 kB Adobe PDF
Bosman_Approximation-Algorithms_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 330.01 kB
Formato Adobe PDF
330.01 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1140645
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact