Dock assignment and truck scheduling problem; consideration of multiple scenarios with resource allocation constraints

摘要

The notion of 'resource' plays an important role in the overall efficiency and performance of most cross-docks. The processing time can often be described in terms of the resources allocated to different trucks. Conversely, for a given processing time, different combinations of resources can be prescribed. We study the problem of truck scheduling and dock assignment in the presence of resource constraints. In the absence of a closed -form (or well-defined) linear formulation describing the processing times as a function of resources, expert' knowledge has been mobilized to enable modelling of the problem as an integer linear model. Two cases are taken into account: In the first one, the expert believes in his/her estimation of the processing time for every truck and only proposes a different combination of resources for his/her estimation, while in the second one the expert proposes a limited number of resource deployment scenarios for serving trucks, each of which has a different combination of resources and different processing times. We propose a novel compact integer programming formulation for the problem, which is particularly designed with an embedded structure that can be exploited in dual decomposition techniques with a remarkably computationally efficient column generation approach in this case. The case in which a scenario with invariant processing time is considered and modelled as a special case of the proposed model. Since a direct application of commercial solvers such as CPLEX to solve instances of this problem is not realistic, we propose a branch-and-price framework and, moreover, several classes of valid inequalities. Our extensive computational experiments confirm that the proposed exact solution framework is very efficient and viable in solving real-size instances of the practice and in a reasonable amount of time.