Recoverable Robustness for Train Shunting Problems

Authors

  • Serafino Cicerone University of L’Aquila
  • Gianlorenzo D'Angelo University of L’Aquila
  • Gabriele Di Stefano University of L’Aquila
  • Daniele Frigioni University of L’Aquila
  • Alfredo Navarra University of Perugia

Keywords:

robustness, recoverability, robust algorithm, shunting problem

Abstract

Several attempts have been done in the literature in the last years in order to provide a formal definition of the notions of robustness and recoverability for optimization problems. Recently, a new model of recoverable robustness has been introduced in the context of railways optimization. The basic idea of recoverable robustness is to compute solutions that are robust against a limited set of disturbances and for a limited recovery capabilities. The quality of the robust solution is measured by its price of robustness that determines the trade-off between an optimal and a robust solution. In this paper, within the recoverable robustness model, we emphasize algorithmic aspects and provide definitions of robust algorithm and price of robustness of a robust algorithm as a measure to evaluate its performance. A robust algorithm provides a solution that maintains feasibility by possibly applying available recovery capabilities in the case of changes to the input data. We study various settings in the context of shunting problems, i.e. the reordering of train cars over a hump yard. The considered shunting problems can be seen as the reordering of an integer vector by means of a set of available stacks with the further constraint that the pull operation does not involve only the element on top of a stack, but all the elements contained in the stack. We provide efficient robust algorithms concerning specific shunting problems. In particular, we study algorithms able to cope with disturbances, as temporary and local unavailability and/or malfunctioning of key resources that can occur and affect planned operations. Various scenarios are considered, and robustness results are presented.

Downloads

Published

2009-09-16

How to Cite

Cicerone, S., D’Angelo, G., Di Stefano, G., Frigioni, D., & Navarra, A. (2009). Recoverable Robustness for Train Shunting Problems. Algorithmic Operations Research, 4(2), Pages 102 – 116. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/10471

Issue

Vol. 4 No. 2 (2009)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.