3 Search Results for "Bouman, Paul"

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-dev.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/OASIcs.ATMOS.2020.6
A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling

Authors: Paul Bouman, Alexander Schiewe, and Philine Schiewe

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
When evaluating the operational costs of a public transport system, the most important factor is the number of vehicles needed for operation. In contrast to the canonical sequential approach of first fixing a timetable and then adding a vehicle schedule, we consider a sequential approach where a vehicle schedule is determined for a given line plan and only afterwards a timetable is fixed. We compare this new sequential approach to a model that integrates both steps. To represent various operational requirements, we consider multiple possibilities to restrict the vehicle circulations to be short, as this can provide operational benefits. The sequential approach can efficiently determine public transport plans with a low number of vehicles. This is evaluated theoretically and empirically demonstrated for two close-to real-world instances.
Cite as

Paul Bouman, Alexander Schiewe, and Philine Schiewe. A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bouman_et_al:OASIcs.ATMOS.2020.6,
  author =	{Bouman, Paul and Schiewe, Alexander and Schiewe, Philine},
  title =	{{A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{6:1--6:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.6},
  URN =		{urn:nbn:de:0030-drops-131422},
  doi =		{10.4230/OASIcs.ATMOS.2020.6},
  annote =	{Keywords: Vehicle Scheduling, Timetabling, Integrated Planning}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.15
Vehicle Scheduling Based on a Line Plan

Authors: Rolf N. van Lieshout and Paul C. Bouman

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
We consider the following problem: given a set of lines in a public transportation network with their round trip times and frequencies, a maximum number of vehicles and a maximum number of lines that can be combined into a vehicle circulation, does there exist a set of vehicle circulations that covers all lines given the constraints. Solving this problem provides an estimate of the costs of operating a certain line plan, without having to compute a timetable first. We show that this problem is NP-hard for any restriction on the number of lines that can be combined into a circulation which is equal to or greater than three. We pay special attention to the case where at most two lines can be combined into a circulation, which is NP-hard if a single line can be covered by multiple circulations. If this is not allowed, a matching algorithm can be used to find the optimal solutions, which we show to be a 16/15-approximation for the case where it is allowed. We also provide an exact algorithm that is able to exploit low tree-width of the so-called circulation graph and small numbers of vehicles required to cover single circulations.
Cite as

Rolf N. van Lieshout and Paul C. Bouman. Vehicle Scheduling Based on a Line Plan. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanlieshout_et_al:OASIcs.ATMOS.2018.15,
  author =	{van Lieshout, Rolf N. and Bouman, Paul C.},
  title =	{{Vehicle Scheduling Based on a Line Plan}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{15:1--15:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.15},
  URN =		{urn:nbn:de:0030-drops-97204},
  doi =		{10.4230/OASIcs.ATMOS.2018.15},
  annote =	{Keywords: Vehicle scheduling, integrated railway planning, (fractional) matching, treewidth}
}
  • Refine by Author
  • 2 Bouman, Paul
  • 1 Bouman, Paul C.
  • 1 Malone, Kerry M.
  • 1 Schiewe, Alexander
  • 1 Schiewe, Philine
  • Show More...

  • Refine by Classification
  • 3 Applied computing → Transportation
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 1 (fractional) matching
  • 1 Integrated Planning
  • 1 Timetabling
  • 1 Vehicle Scheduling
  • 1 Vehicle scheduling
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact