A machine learning based branch-cut-and-Benders for dock assignment and truck scheduling problem in cross-docks

摘要

In this work, we study the dock-door assignment and truck scheduling problem in cross-docks with an intraday planning horizon. This timeframe allows us to view the problem as a repeating operation with a frequency of 24 h. In practice, this repeating process follows a certain distribution, which is largely sustained even if we extend the horizon. While several modeling approaches and efficient solution algorithms have been proposed for various problem variations, the utilization of decomposition techniques in exact mathematical programming methods has been the most effective. Surprisingly, none of these techniques have taken advantage of the repeating patterns inherent in the problem. We start with a recently proposed compact model that is well-designed and can be exploited in a primal (Benders) decomposition technique, although it cannot be directly used to solve a practical-sized problem. We show that its modeling deficiencies can be fixed and propose a Benders decomposition framework together with several Alternative Objective Functions (AOFs) to generate customized Benders cuts, along with other valid inequalities that can be identified and separated. A classifier is trained to identify the most efficient AOF to use at different stages of the Benders iterations, to help avoid saturation of the master problem with dominated Benders cuts. Our extensive computational experiments confirm the significant performance improvement in the comparable decomposition framework.