Solving the Inter-Terminal Truck Routing Problem for Delay Minimization Using Simulated Annealing with Normalized Exploration Rate

Abstract

The growth in containerized shipping has led to the expansion of seaports, resulting in the emergence of multiple terminals. While multi-terminal systems increase port capacity, they also pose significant challenges to container transportation, particularly in inter-terminal movements. Consequently, the transportation delay of containers in inter-terminal operations demands crucial attention, as it can adversely affect the efficiency and service levels of seaports. To minimize the total transportation delays of the inter-terminal truck routing problem (ITTRP), we introduce simulated annealing with normalized acceptance rate (SANE). SANE improves the exploration capability of simulated annealing (SA) by dynamic rescaling of the transportation delay objective to modify the acceptance probability. To validate the quality of solutions provided by SANE, we have developed a mathematical model that provides a set of linear formulations for ITTRP constraints, avoiding the known set-partitioning alternative. Experimental results showed that for small-scale ITTRP instances, SANE achieved a solution close to the optimal. In larger instances with 100–120 orders, SANE found feasible suboptimal solutions within 15–21 seconds, which is unattainable using the exact solver. Further comparison with baselines indicates that SANE provides considerable improvements compared to both SA and Tabu search in terms of the objective value.

Keywords

• inter-terminal transport
• inter-terminal truck routing
• simulated annealing
• tabu search
• mixed integer programming