DROPS

Document

Short Paper

DOI: 10.4230/OASIcs.ATMOS.2023.18

Simple Policies for Capacitated Resupply Problems (Short Paper)

Authors: Mette Wagenvoort, Martijn van Ee, Paul Bouman, and Kerry M. Malone

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract

We consider the Capacitated Resupply Problem in which locations with a given demand rate should be resupplied by vehicles such that they do not run out of stock and the number of vehicles is minimised. Compared to related problems, we consider the scenario where the payload of the vehicles may not suffice to bring the stock level back to full capacity. We focus on the Homogeneous Capacitated Resupply Problem and present both simple policies that provide 2-approximations and an optimal greedy policy that runs in pseudo-polynomial time.

Cite as

Mette Wagenvoort, Martijn van Ee, Paul Bouman, and Kerry M. Malone. Simple Policies for Capacitated Resupply Problems (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 18:1-18:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wagenvoort_et_al:OASIcs.ATMOS.2023.18,
  author =	{Wagenvoort, Mette and van Ee, Martijn and Bouman, Paul and Malone, Kerry M.},
  title =	{{Simple Policies for Capacitated Resupply Problems}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{18:1--18:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.18},
  URN =		{urn:nbn:de:0030-drops-187799},
  doi =		{10.4230/OASIcs.ATMOS.2023.18},
  annote =	{Keywords: resupply problems, periodic schedules, approximation guarantee, greedy policy}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2023.86

Exact and Approximation Algorithms for Routing a Convoy Through a Graph

Authors: Martijn van Ee, Tim Oosterwijk, René Sitters, and Andreas Wiese

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

We study routing problems of a convoy in a graph, generalizing the shortest path problem (SPP), the travelling salesperson problem (TSP), and the Chinese postman problem (CPP) which are all well-studied in the classical (non-convoy) setting. We assume that each edge in the graph has a length and a speed at which it can be traversed and that our convoy has a given length. While the convoy moves through the graph, parts of it can be located on different edges. For safety requirements, at all time the whole convoy needs to travel at the same speed which is dictated by the slowest edge on which currently a part of the convoy is located. For Convoy-SPP, we give a strongly polynomial time exact algorithm. For Convoy-TSP, we provide an O(log n)-approximation algorithm and an O(1)-approximation algorithm for trees. Both results carry over to Convoy-CPP which - maybe surprisingly - we prove to be NP-hard in the convoy setting. This contrasts the non-convoy setting in which the problem is polynomial time solvable.

Cite as

Martijn van Ee, Tim Oosterwijk, René Sitters, and Andreas Wiese. Exact and Approximation Algorithms for Routing a Convoy Through a Graph. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanee_et_al:LIPIcs.MFCS.2023.86,
  author =	{van Ee, Martijn and Oosterwijk, Tim and Sitters, Ren\'{e} and Wiese, Andreas},
  title =	{{Exact and Approximation Algorithms for Routing a Convoy Through a Graph}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{86:1--86:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.86},
  URN =		{urn:nbn:de:0030-drops-186205},
  doi =		{10.4230/LIPIcs.MFCS.2023.86},
  annote =	{Keywords: approximation algorithms, convoy routing, shortest path problem, traveling salesperson problem}
}

Search Results

Documents authored by van Ee, Martijn

Simple Policies for Capacitated Resupply Problems (Short Paper)

Abstract

Cite as

Exact and Approximation Algorithms for Routing a Convoy Through a Graph

Abstract

Cite as

Thanks for your feedback!

Could not send message