An exact method for short-term maintenance planning at offshore windfarms

The increasing number of offshore wind farms being installed leads to new scientific and practical challenges in the area of service logistics. In this seminar, a short-term maintenance planning and routing problem and corresponding exact and heuristic solution approaches will be the central topic. In particular, a branch-and-price-and-cut algorithm have been developed and will be discussed in detail. Especially some peculiarities regarding the pulse algorithm (used for solving the pricing problem) that motivates its use, instead of a traditional labeling algorithm, will be discussed. Abstract of the corresponding paper is attached below.

Abstract: A branch-and-price-and-cut algorithm for resource constrained pickup and delivery problems (joint work with Evrim Ursavas and Iris Vis) We study a multi-commodity multi-period resource constrained pickup and delivery problem inspired by the short-term planning of maintenance services at offshore wind farms. To start a maintenance service, different types of scarcely available servicemen need to be delivered to the service locations. We develop resource exceeding route (RER) inequalities, whom are inspired by knapsack cover inequalities, to model the scarcity of servicemen. Besides a traditional separation approach, we present a column-dependent constraint approach to include the RER inequalities in the mathematical formulation. An alternative pricing strategy is developed to correctly include the column-dependent constraints. The resulting approach is broadly applicable for any routing problem that involves a set of scarcely available resources. We present a branch-and-price-and-cut algorithm to compare both approaches of including RER inequalities. The branch-and-price-and-cut algorithm relies on efficiently solving a new variant of the Elementary Resource Constrained Shortest Path Problem, for which a tailored pulse algorithm is developed to solve it. Computational experiments show that the RER inequalities significantly tighten the root node relaxations. The column-dependent constraint approach searches the branch and bound tree more effectively than, and appears competitive with, the traditional separation procedure. Both approaches can solve instances up to 92 nodes over 21 periods to optimality.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.