A New Memetic Approach to Solve the Strategic Berth Template Problem

Introduction

Nowadays, Containerization provides an optimal freight management solution, reducing both the transport cost and vessels handling time at the port. The huge number of containers ships that demand handling service at container terminals needs an optimal planning of seaside operations (Meisel, 2009) to grant their smooth movement and avoid terminal congestion. The Berth Allocation Problem (BAP) consists in assigning the best position at an ideal berthing time for each calling ship with the objective of minimizing their waiting and their handling time at the port. This problem is addressed at three different planning levels (Imai et al., 2014), namely, the tactical, operational and strategic planning horizon. In tactical level, the decision to assigning ships to berth for their berthing is realized at a long term with a fixed time horizon (Imai et al., 2014). While, in the operational level, the decision is taken at a short term with an open time horizon. Finally, at the strategic level the berth planning is similarly to tactical level but the difference lies in the fact that, at tactical level all ships calling at the port for handling service are accepted which can contribute to port congested. However, at the strategic level, it’s possible to refuse some ships to be served at the port to avoid the congestion. Many works on BAP had tended to focus on operational or tactical level rather than strategic level. In this paper, we present SBTP with the consideration of the dynamic arrival of ships (i.e. when the time planning starts, it’s necessary to take into account the vessels which have already arrived and not yet arrived at the port) and discrete berth layouts where the quay is divided into a specified number of berth (Issam et al., 2018). When ships request a berth at a container port, ship-owners should negotiate a contract with port operators to provide them with services at the port during the contract duration. The contract in general is long and the arrival of ships during this contract is cyclical (i.e. the same day of each week).Therefore, this allows the operators to prepare a long-term a berth template for ships called strategic berth template. On the other hand, at strategic level, it is possible to reject some calls to avoid congestion and maximize terminal performance. The fact that not all calling ships are accepted to be served at the port is what makes the difference between the SBTP and BAP at operational or tactical level (Imai et al., 2014).

In this work, the main objective of the SBTP is getting a berthing position for each selected ship with minimization of their waiting time and the reduction in the numbers of rejected ships. In addition, another particularity of this problem is the consideration of a cylinder time horizon where the length of the time horizon is fixed. However, the starting and the ending of this horizon is a variable which must be determined for each berth. The principal contribution of our paper is to develop a memetic algorithm as an alternative to solve the SBTP and improve the results presented so far for this problem because solution approaches presented so far for the problem are limited especially at level of large-scale instances. The effectiveness of memetic algorithms in solving others similarly optimization problem like vehicle routing problem (Zhang et al., 2019) is the reason for which we decide to develop our memetic for SBTP. Figure 1 shows a SBTP ’s solution example for five ships and two berths. In this example, the solution is presented in a two dimensional space where the y-axis presents the quay position (i.e. the berths of the terminal) and the x-axis presents the time horizon (T=20) Thus, the planning horizon starts at time 0 and ends at time 20 for berth 2. However, for berth 1 the planning starts at time 5 and ends at time 25 (i.e. the length of the time horizon is the same for each berth but their starting and ending time is different). Hence, the starting and ending time horizon for each berth is another variable that should be determined in a SBTP . For more details on the SBTP see (Imai et al., 2014). The rest of the paper is structured as follows: The next section presents a literature review on the BAP. Then, a mathematical model for SBTP is presented in Section 3. In Section 4, details description of our memetic algorithm is presented. Next, computational experiments and comparison results are exposed in Section 5. Finally, Section 6 concludes the paper.

Figure 1.

Solution example for SBTP with 5 ships and 2 berths