  The rolling stock rotation problem with predictive maintenance (RSRP-PdM)
involves the assignment of trips to a fleet of vehicles with integrated
maintenance scheduling based on the predicted failure probability of the
vehicles. These probabilities are determined by the health states of the
vehicles, which are considered to be random variables distributed by a
parameterized family of probability distribution functions. During the
operation of the trips, the corresponding parameters get updated. In this
article, we present a dual solution approach for RSRP-PdM and generalize a
linear programming based lower bound for this problem to families of
probability distribution functions with more than one parameter. For this
purpose, we define a rounding function that allows for a consistent
underestimation of the parameters and model the problem by a state-expanded
event-graph in which the possible states are restricted to a discrete set. This
induces a flow problem that is solved by an integer linear program. We show
that the iterative refinement of the underlying discretization leads to
solutions that converge from below to an optimal solution of the original
instance. Thus, the linear relaxation of the considered integer linear program
results in a lower bound for RSRP-PdM. Finally, we report on the results of
computational experiments conducted on a library of test instances.
