A variable neighborhood search heuristic for real-time barge scheduling in a river-to-sea channel with tidal restrictions

The scheduling of barge transportation in narrow channels is critical to transportation efficiency, especially when the tide exists and affects the channel navigation of barges. Barge movements in channels are frequently correlated with other activities (e.g., berth allocation) and must thus be considered concurrently. To enhance transportation efficiency, effective scheduling algorithms are required. In this study, we examine the barge scheduling problem arising from a river-to-sea channel with tidal restrictions in the real world, where barges’ loading and unloading operations are placed at both ends of the navigation channel and must be planned and coordinated with their channel movements. To reduce the overall completion time for all barges, we develop a mixed integer linear programming model with several valid inequalities. To satisfy the second-level computational efficiency requirement, a straightforward yet efficient variable neighborhood search algorithm is proposed. Real-world case studies based on a barge transportation project in Boffa, Guinea are conducted. It is demonstrated that the proposed approach is applicable for efficient decision-making and effective in assisting barges to avoid missing feasible tide windows by slightly altering the first-come-first-serve schedule of the barges. With the proposed approach, the size and speed of the barge fleet can be optimized, and the tidal influence is also evaluated quantitatively.