A VNS-Based Approach for Solving the Manhattan Metric Straddle Carrier Routing Problem With Buffer Areas

Abstract

This paper presents a metaheuristic approach for solving an optimization problem that arises at container terminals where straddle carriers (SCs) transport containers between the stacking areas and the seaside. In such container terminals, operational efficiency depends mainly on SC routing. SCs routes should consider the order in which containers are unloaded and loaded at the quay cranes (QCs), taking into account the limited capacity of the buffer area of each QC where containers are temporarily stored after being handled by a QC or an SC. Besides the precedence relations (i.e., container sequences) and buffer capacities, the solution framework considers safety constraints. Efficient routing of SCs directly contributes to minimizing the idle time of QCs, thereby improving their overall productivity and minimizing the turnaround time of vessels, which is the objective of the problem. Specifically, we present two different variants of the Variable Neighborhood Search (VNS) algorithm. Each variant is initialized in both a greedy and a random manner. These algorithms address the problem by incorporating four LS operators commonly utilized in vehicle routing problems. We perform a comparative analysis of the results of these four approaches against each other and against solutions generated by an exact solver. Our numerical experiments show that the proposed algorithms perform better than the used solver, especially for bigger instances. A comparison with the results from the literature is also given and shows that the proposed VNS-based approach provides competitive results.