Multi-Period Multi-Resource Stochastic Generalized Assignment Problem: model and exact approach

In this setting, over-assignment of an agent is allowed, but a reassignment cost is considered. In the literature, stochastic models assume unitary job sizes, a single type of resource, and only consider a single period. However, recent applications, especially in emerging digital platforms, require a more generic setting. For example, a ride-sharing platform, aiming to maximize total profit, can consider sequential multi-resource services for a set of passengers who may cancel their rides at the last minute. Yet no existing stochastic assignment model supports this level of generality. 

This paper aims to fill this gap by introducing the Multi-Period Multi-Resource Stochastic Generalized Assignment Problem, which considers a multi-period setting, multiple resource types, and integer resource consumption. After developing the mathematical model, we propose an exact Nested Logic-Based Benders Decomposition algorithm and tailored pruning conditions to reject master solutions that will not improve the best bound. A Large Neighborhood Search algorithm is also developed to find good solutions in a limited time frame. Computational experiments are presented to show the algorithms’ performance and the necessity of tight pruning conditions for the exact method to speed up convergence time. Finally, we perform a sensitivity analysis to assess the quality and the structure of the solutions.

About the speaker

Duarte Medeiros is a PhD candidate at TU Delft focusing on matching models for shippers and transport operators to promote more sustainable freight logistics. He holds an MSc in Statistics and Operations Research and a BSc in Applied Mathematics from the University of Lisbon. His work aims to optimize capacity across transport modalities for cleaner, more efficient transportation.

Coordinators

Ruben van Beesten