LTL freight carriers operate consolidation networks that utilize cross-docking terminals to facilitate the
transfer of freight between trailers and enhance trailer utilization. This research addresses the problem of
determining an optimal schedule for unloading inbound trailers at specific unloading doors using teams of
dock workers. The optimization objective is chosen to ensure that outbound trailers are loaded with minimal
delay with respect to their loading deadlines. Formulating this problem, which is known to be NP-hard, using
a typical time-expanded network often results in an excessively large mixed-integer programming (MIP)
model. To overcome this challenge, we propose an exact dynamic discretization discovery (DDD) algorithm
that iteratively solves MIPs formulated over partial networks. The algorithm employs a combination of
simple time discretization refinement strategy to progressively refine the partial network until a provably
optimal solution is obtained. We demonstrate the effectiveness of the algorithm in solving problem instances
representative of a large L-shaped cross-dock in Atlanta. The DDD algorithm outperforms solving the model
formulated over a complete time-expanded network with a commercial solver in terms of both computational
time and solution quality for practical instances with 180 trailers, 44 unloading doors, and 57 loading doors.
Additionally, we compare the DDD algorithm with a state-of-the-art interval scheduling approach using
instances from a previous study with a different objective function and additional constraints. The DDD
algorithm is computationally faster for most of the small and medium instances and achieves competitive
bounds for the larger instances.
Citation
Ojha, R. & Erera, A. (2023). Cross-Dock Trailer Scheduling with Workforce Constraints: A Dynamic Discretization Discovery Approach.