Cross-Dock Trailer Scheduling with Workforce Constraints: A Dynamic Discretization Discovery Approach

Less-than-truckload (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 target loading due dates. 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 a 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. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0406 .