Recoverable robustness for train shunting problems

Recoverable robustness for train shunting problems

0.00 Avg rating0 Votes
Article ID: iaor200970869
Country: Canada
Volume: 4
Issue: 2
Start Page Number: 102
End Page Number: 116
Publication Date: Jun 2009
Journal: Algorithmic Operations Research
Authors: , , , ,
Keywords: vehicle routing & scheduling
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.

Reviews

Required fields are marked *. Your email address will not be published.