1.1. Background
Maritime transportation is viewed as the most popular transportation mode for the delivery of cargoes between different continents across the world (Elmi et al., 2022; Rodrigues and Agra, 2022). Approximately 80% of international trade volumes are transported by ships and handled at ports across the globe. Container ships carrying valuable goods are served at marine container terminals (MCTs). There are three major types of MCT operations, including the following (Bierwirth and Meisel, 2010; Bierwirth and Meisel, 2015): (1) seaside operations that mainly focus on the service of arriving ships by sea-to-shore cranes, generally referred to as “quay cranes” (see Figure 1); (2) marshaling yard operations that deal with the storage of containers delivered from the seaside and the landside; and (3) landside operations that entail the pick-up and/or drop-off of the containers delivered by outbound trucks, generally referred to as “drayage trucks”. Berth allocation and scheduling is one of the primary decision problems that have to be addressed by MCT operators when planning seaside operations (Carlo et al., 2015). The berth allocation and scheduling problem (BASP) aims to determine the assignment of arriving ships to the available berthing positions. Furthermore, the service order of arriving ships at each berthing position is determined as a part of the BASP as well. Effective berth allocation and scheduling plans are essential for the MCT performance and timely service of arriving ships.
The solution approaches that have been used for the BASP decision problem can be classified in the following three groups (see Figure 2): (1) exact optimization methods; (2) heuristic methods; and (3) metaheuristic methods. Exact optimization methods (e.g., branch-and-bound, branch-and-cut, CPLEX, MOSEK, GUROBI, BARON, CONOPT, DICOPT, etc.) are able to obtain global optimal solutions for different variations of the BASP decision problem (Issam et al., 2017; Jos et al., 2019; Kallel et al., 2019; Dkhil et al., 2021). The BASP problems generally have high computational complexity, as they can be reduced to the unrelated machine scheduling problem. Due to the computational complexity, exact optimization methods are not able to produce good-quality solutions for large-scale problem instances of the BASP. Therefore, many types of heuristic and metaheuristics have been proposed in the BASP literature. Heuristic algorithms are approximate solution algorithms that do not produce optimal solutions for a given BASP decision problem but can return solutions of a good quality within reasonable computational time. Heuristic algorithms are typically customized for a specific BASP variation (Nishi et al., 2020; Ankita and Mathirajan, 2021; Mnasri and Alrashidi, 2021; Fernández and Munoz-Marquez, 2022).
Figure 1. Berth allocation and scheduling at an MCT
Figure 2. Common solution methods for the BASP decision problem
As an example, Ankita and Mathirajan (2021) proposed a heuristic algorithm for the BASP, which was based on the early-to-finish principle. The heuristic was compared to the exact method (LINGO) and was found to be efficient. In particular, the developed heuristic obtained optimal solutions that were identical to the LINGO solutions for the 7 out of 10 problem instances. More recently, Fernández and Munoz-Marquez (2022) presented several new formulations for the strategic berth template problem at MCTs. A heuristic algorithm was developed to generate feasible solutions for the problem and consisted of three steps, including the following: (a) determine a subset of ships to be served considering the mother-ship constraints; (b) determine the allocation of ships to the berthing positions that satisfies the cycle duration; and (c) develop a ship service sequence at each berthing position.
Similar to heuristic algorithms, metaheuristic algorithms (such as evolutionary algorithms, variable neighborhood search, simulated annealing, grey wolf optimizer, particle swarm optimization, ant colony optimization, lion optimization algorithms, red deer algorithm) are approximate solution algorithms that do not produce optimal solutions for a given BASP decision problem but can return solutions of a good quality within reasonable computational time. However, metaheuristics are generally viewed as a much broader group of algorithms and can be used to different decision problems, not just the BASP decision problem (Bacalhau et al., 2021; Peng et al., 2021; Prencipe and Marinelli, 2021; Barbosa et al., 2022; Wang et al., 2022). For instance, Schepler et al. (2019) studied berth allocation and scheduling in stochastic settings where ship arrival times were not known with certainty. The authors presented a solution approach that was based on the iterated tabu search and dynamic programming. Wang et al. (2019) presented a Levy Flight-based metaheuristic for the BASP with tidal windows. The purpose of introducing a Levy Flight random walk was to prevent the algorithm from converging at one of the local optima. The recent BASP studies explore the potential of new and more advanced forms of metaheuristics. As an example, Dulebenets (2020) and Kavoosi et al. (2020) proposed island-based metaheuristics, where the population individuals were distributed among the islands, and the islands could exchange promising solutions after a certain number of generations.