An event-based model and hybrid genetic search algorithm for an inland multi-size container transportation problem

Abstract

This paper addresses a complex multi-size Container Drayage Problem (CDP) in the hinterland of a seaport, where a fleet of identical trucks is used to transport containers between customer locations, a container terminal, and a depot, and in which the repositioning of empty containers is also considered. Each truck can carry either one 40-ft container or two 20-ft containers simultaneously. The main target of the CDP is to determine the trucking schedule that satisfies all transport demands while minimizing the total cost. The problem is described using an event-based graph that considers capacity, pairing, precedence, and time-window constraints implicitly, based on which a compact Mixed-Integer Linear Programming (MILP) model is proposed. To reduce the model scale and enhance computational efficiency, we introduce tailored model enhancement methods to eliminate infeasible event nodes and arcs based on time window feasibility checks. The results of numerical experiments prove that the event-based model can solve small-scale instances effectively. For large-scale instances, we develop a Hybrid Genetic Search (HGS) algorithm that incorporates a Dynamic Programming (DP)-optimized enumeration method to handle multi-size container loading schemes and time-window constraints effeciently. Extensive computational experiments show that our proposed algorithm significantly outperforms the commercial solver CPLEX on large-scale instances, demonstrating its scalability for real-world applications.