A Resource Aggregation Based Label-Correcting Algorithm For The Resource Constrained Shortest Path Problem In A Column Generation Context

In this thesis we investigate the potential benefit of applying resource aggregation strategies in a column generation algorithm used to solve a set-covering problem (SCP) with additional constraints. The corresponding pricing problem is mathematically formulated as a resource constrained shortest path problem (SPPRC) and solved by a dynamic programming approach. The additional resource constraints are incorporated in the problem to take the preferences of the employees into consideration such that a fair distribution of the workload is obtained. We exploit the idea of resource correlation to develop aggregation strategies instead of considering the individual resources in the SPPRC. We develop a framework to solve the pricing problem arising from the application of column generation. The framework consists of a sequence of dynamic programming algorithms based on a generic version of a label-correcting algorithm for solving a shortest path problem. The basic algorithm is adapted such that we can incorporate each of the developed resource aggregation strategies. The proposed resource aggregation strategies are tested on three simulated data instances with a varying degree of correlation, deducted from a part of the actual rail transit network in The Netherlands. The computational results show that some of the developed aggregation strategies perform well for the dataset with medium correlated resources. A reduction of the computation time up to approximately 36% is achieved using a well-chosen parameter setting. Results show that the same parameter setting results in a minimal fairness error according to the used fairness criterion. The use of an aggregation strategy with the well-chosen parameter settings in a column generation context may result in a more efficient approach to incorporate the preferences of employees and increase their happiness and welfare.