Search Results

Documents authored by Hoogeveen, Han

Document
DOI: 10.4230/OASIcs.ATMOS.2023.14
Scheduling Electric Buses with Stochastic Driving Times

Authors: Philip de Bruin, Marjan van den Akker, Han Hoogeveen, and Marcel van Kooten Niekerk

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

Abstract
To try to make the world more sustainable and reduce air pollution, diesel buses are being replaced with electric buses. This leads to challenges in scheduling, as electric buses need recharging during the day. Moreover, buses encounter varying traffic conditions and passenger demands, leading to delays. Scheduling electric buses with these stochastic driving times is also called the Stochastic Vehicle Scheduling Problem. The classical approach to make a schedule more robust against these delays, is to add slack to the driving time. However, this approach doesn't capture the variance of a distribution well, and it doesn't account for dependencies between trips. We use discrete event simulation in order to evaluate the robustness of a schedule. Then, to create a schedule, we use a hybrid approach, where we combine integer linear programming and simulated annealing with the use of these simulations. We show that with the use of our hybrid algorithm, the punctuality of the buses increase, and they also have a more timely arrival. However, we also see a slight increase in operating cost, as we need slightly more buses compared to when we use deterministic driving times.
Cite as

Philip de Bruin, Marjan van den Akker, Han Hoogeveen, and Marcel van Kooten Niekerk. Scheduling Electric Buses with Stochastic Driving Times. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{debruin_et_al:OASIcs.ATMOS.2023.14,
  author =	{de Bruin, Philip and van den Akker, Marjan and Hoogeveen, Han and van Kooten Niekerk, Marcel},
  title =	{{Scheduling Electric Buses with Stochastic Driving Times}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{14:1--14:19},
  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.14},
  URN =		{urn:nbn:de:0030-drops-187753},
  doi =		{10.4230/OASIcs.ATMOS.2023.14},
  annote =	{Keywords: Electric Vehicle Scheduling Problem, Simulated Annealing, Hybrid Algorithm, Simulation, Stochastic Driving Times}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.12
Personnel Scheduling on Railway Yards

Authors: Roel van den Broek, Han Hoogeveen, and Marjan van den Akker

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

Abstract
In this paper we consider the integration of the personnel scheduling into planning railway yards. This involves an extension of the Train Unit Shunting Problem, in which a conflict-free schedule of all activities at the yard has to be constructed. As the yards often consist of several kilometers of railway track, the main challenge in finding efficient staff schedules arises from the potentially large walking distances between activities. We present two efficient heuristics for staff assignment. These methods are integrated into a local search framework to find feasible solutions to the Train Unit Shunting Problem with staff requirements. To the best of our knowledge, this is the first algorithm to solve the complete version of this problem. Additionally, we propose a dynamic programming method to assign staff members as passengers to train movements to reduce their walking time. Furthermore, we describe several ILP-based approaches to find a feasible solution of the staff assignment problem with maximum robustness, which solution we use to evaluate the quality of the solutions produced by the heuristics. On a set of 300 instances of the train unit shunting problem with staff scheduling on a real-world railway yard, the best-performing heuristic integrated into the local search approach solves 97% of the instances within three minutes on average.
Cite as

Roel van den Broek, Han Hoogeveen, and Marjan van den Akker. Personnel Scheduling on Railway Yards. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vandenbroek_et_al:OASIcs.ATMOS.2020.12,
  author =	{van den Broek, Roel and Hoogeveen, Han and van den Akker, Marjan},
  title =	{{Personnel Scheduling on Railway Yards}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{12:1--12:15},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.12},
  URN =		{urn:nbn:de:0030-drops-131487},
  doi =		{10.4230/OASIcs.ATMOS.2020.12},
  annote =	{Keywords: Staff Scheduling, Train Shunting, Partial Order Schedule}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.3
How to Measure the Robustness of Shunting Plans

Authors: Roel van den Broek, Han Hoogeveen, and Marjan van den Akker

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

Abstract
The general problem of scheduling activities subject to temporal and resource constraints as well as a deadline emerges naturally in numerous application domains such as project management, production planning, and public transport. The schedules often have to be implemented in an uncertain environment, where disturbances cause deviations in the duration, release date or deadline of activities. Since these disruptions are not known in the planning phase, we must have schedules that are robust, i.e., capable of absorbing the disturbances without large deteriorations of the solution quality. Due to the complexity of computing the robustness of a schedule directly, many surrogate robustness measures have been proposed in literature. In this paper, we propose new robustness measures, and compare these and several existing measures with the results of a simulation study to determine which measures can be applied in practice to obtain good approximations of the true robustness of a schedule with deadlines. The experiments are performed on schedules generated for real-world scheduling problems at the shunting yards of the Dutch Railways (NS).
Cite as

Roel van den Broek, Han Hoogeveen, and Marjan van den Akker. How to Measure the Robustness of Shunting Plans. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vandenbroek_et_al:OASIcs.ATMOS.2018.3,
  author =	{van den Broek, Roel and Hoogeveen, Han and van den Akker, Marjan},
  title =	{{How to Measure the Robustness of Shunting Plans}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{3:1--3:13},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.3},
  URN =		{urn:nbn:de:0030-drops-97081},
  doi =		{10.4230/OASIcs.ATMOS.2018.3},
  annote =	{Keywords: robustness, resource-constrained project scheduling, partial order schedule, uncertainty, Monte Carlo simulation, train shunting}
}
Document
DOI: 10.4230/DagSemProc.10071.3
10071 Open Problems – Scheduling

Authors: Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
Collection of the open problems presented at the scheduling seminar.
Cite as

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3,
  author =	{Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.},
  title =	{{10071 Open Problems – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3},
  URN =		{urn:nbn:de:0030-drops-25367},
  doi =		{10.4230/DagSemProc.10071.3},
  annote =	{Keywords: Open problems, scheduling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1591
Integrated Gate and Bus Assignment at Amsterdam Airport Schiphol

Authors: Guido Diepen, Marjan van den Akker, and Han Hoogeveen

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
At an airport a series of assignment problems need to be solved before aircraft can arrive and depart and passengers can embark and disembark. A lot of different parties are involved with this, each of which having to plan their own schedule. Two of the assignment problems that the 'Regie' at Amsterdam Airport Schiphol (AAS) is responsible for, are the gate assignment problem (i.e. where to place which aircraft) and the bus assignment problem (i.e. which bus will transport which passengers to or from the aircraft). Currently these two problems are solved in a sequential fashion, the output of the gate assignment problem is used as input for the bus assignment problem. We look at integrating these two sequential problems into one larger problem that considers both problems at the same time. This creates the possibility of using information regarding the bus assignment problem while solving the gate assignment problem. We developed a column generation algorithm for this problem and have implemented a prototype. To make the algorithm efficient we used a special technique called stabilized column generation and also column deletion. Computational experiments with real-life data from AAS indicate that our algorithm is able to compute a planning for one day at Schiphol in a reasonable time.
Cite as

Guido Diepen, Marjan van den Akker, and Han Hoogeveen. Integrated Gate and Bus Assignment at Amsterdam Airport Schiphol. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{diepen_et_al:OASIcs.ATMOS.2008.1591,
  author =	{Diepen, Guido and van den Akker, Marjan and Hoogeveen, Han},
  title =	{{Integrated Gate and Bus Assignment at Amsterdam Airport Schiphol}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1591},
  URN =		{urn:nbn:de:0030-drops-15918},
  doi =		{10.4230/OASIcs.ATMOS.2008.1591},
  annote =	{Keywords: Gate assignment, airports, integrated planning, column generation, integer linear programming}
}
Document
DOI: 10.4230/DagSemProc.05031.12
Getting rid of stochasticity: applicable sometimes

Authors: Han Hoogeveen and Marjan Van den Akker

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
We consider the single-machine scheduling problem of minimizing the number of late jobs. This problem is well-studied and well-understood in case of deterministic processing times. We consider the problem with stochastic processing times, and we show that for a number of probability distributions the problem can be reformulated as a deterministic problem (and solved by the corresponding algorithm) when we use the concept of minimum success probabilities, which is, that we require that the probability that a job complete on time is `big enough'. We further show that we can extend our approach to the case of machines with stochastic output.
Cite as

Han Hoogeveen and Marjan Van den Akker. Getting rid of stochasticity: applicable sometimes. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{hoogeveen_et_al:DagSemProc.05031.12,
  author =	{Hoogeveen, Han and Van den Akker, Marjan},
  title =	{{Getting rid of stochasticity: applicable sometimes}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.12},
  URN =		{urn:nbn:de:0030-drops-1924},
  doi =		{10.4230/DagSemProc.05031.12},
  annote =	{Keywords: Scheduling , sequencing , single machine , number of late jobs , stochastic processing times , minimum success probability , dynamic programming unreliable machines}
}
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