Cross-Dock Trailer Scheduling with Workforce Constraints: A Dynamic Discretization Discovery Approach
研究了在交叉码头中，利用工人团队为卸货拖车安排最优卸货门调度，以最小化出站拖车延迟，并提出一种精确的动态离散化发现算法来高效求解该NP难问题。
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 .