2 Literature review

The BAP has been extensively studied in the literature. In this regard, due to the large variety of maritime terminal layouts, research has produced multitude of variants for this problem. Depending on how the quay is modeled, the BAP can be referred to as discrete (the quay is divided into segments called berths) or continuous (the quay is not divided, thus the vessels can berth at any position in the quay). Moreover, in some related works (Cordeau et al., Reference Cordeau, Laporte, Legato and Moccia2005; Umang et al., Reference Umang, Bierlaire and Vacca2013) there is also a hybrid consideration of the quay (the quay is divided into a set of berths and a vessel can occupy more than one berth at a time or share its assigned berth with other vessels). Depending on the arrival time, the BAP can be classified into static (the vessels are already in port when the berths become available) or dynamic (the vessels arrive during the planning horizon). For detailed descriptions, the reader is referred to Christiansen et al. (Reference Christiansen, Fagerholt, Nygreen and Ronen2007) and Bierwirth and Meisel (Reference Bierwirth and Meisel2010).

One of the most relevant approaches is the DBAP. It was first formulated by Imai et al. (Reference Imai, Nishimura and Papadimitriou2001) as an extension of the model proposed in Imai et al. (Reference Imai, Nagaiwa and Chan1997) for the Static BAP. Alternative formulations for the dynamic problem have been proposed and studied by Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005), Monaco and Sammarra (Reference Monaco and Sammarra2007) and Christensen and Holst (Reference Christensen and Holst2008). These models are described and compared in Buhrkal et al. (Reference Buhrkal, Zuglian, Ropke, Larsen and Lusby2011). The main conclusion extracted from the latter work is that the model presented by Christensen and Holst is superior to the other models in terms of the time performance. Namely, it is able to provide the optimal solutions within shorter computational times for the largest instances proposed in the work of Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005).

Recently, Lalla-Ruiz et al. (Reference Lalla-Ruiz, Melián-Batista and Moreno-Vega2012) presented an efficient Tabu Search metaheuristic with Path-Relinking for solving the DBAP. They also proposed a benchmark suite of instances for which the model by Christensen and Holst (Reference Christensen and Holst2008) does not provide feasible solutions within a time limit. de Oliveira et al. (Reference de Oliveira, Mauri and Lorena2012) presents a Clustering Search (CS-SA) with Simulated Annealing for solving the DBAP. This algorithm provides the optimal solutions for all the largest instances proposed by Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005). In this regard, Ting et al. (Reference Ting, Wu and Chou2014) propose a Particle Swarm Optimization (PSO) algorithm for addressing the DBAP, which reports optimal solutions within shorter computational times than CS-SA.

3 Dynamic Berth Allocation Problem

In this work, we address the Dynamic Berth Allocation Problem (DBAP) proposed by Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005) which is modeled as a Multi-Depot Vehicle Routing Problem with Time-Windows. Thus, based on that formulation, the vessels are seen as customers and the berths as depots at which one vehicle is located. The goal of the DBAP is to determine the berthing position and berthing time of |N| incoming vessels along the quay, which is divided into |M| berths. In order to make this paper self-contained, the description of the model proposed by Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005) is included. The following parameters are defined in the problem:

• ∙ N, set of vessels.

• ∙ M, set of berths.

• ∙ $t_{i}^{k} $ , handling time of vessel i∈N at berth k∈M.

• ∙ a _i , b _i , arrival, departure time of vessel i∈N.

• ∙ l ^k , e ^k , start, end of the availability of the berth k∈M.

• ∙ v _i , the service priority of each vessel i∈N.

Let us define a graph, G ^k =(V ^k , A ^k ) ∀ k∈M, where V ^k =N∪{o(k), d(k)} contains a vertex for each vessel as well as the vertices o(k) and d(k), which are the origin and destination nodes for any route in the graph. The set of arcs is defined as A ^k ⊆V ^k ×V ^k , where each one represents the handling time of the vessel. The decision variables are as follows:

• ∙ $x_{{ij}}^{k} $ ∈{0, 1}, ∀ k∈M, ∀ (i, j)∈A ^k , set to 1 if vessel j is scheduled after vessel i at berth k, and 0 otherwise.

• ∙ T _i ^k , ∀ k ∈ M, ∀ i∈ N, the berthing time of vessel i at berth k, that is, the time when the vessel berths.

• ∙ $T_{{o(k)}}^{k} $ , ∀ k∈M, starting operation time of berth k, that is, the time when the first vessel berths at the berth.

• ∙ $T_{{d(k)}}^{k} $ , ∀ k∈M, ending operation time of berth k, that is, the time when the last vessel departs from its assigned berth.

Furthermore, in the DBAP the following assumptions are considered:

1. a. Each berth k∈M can only handle one vessel at a time.

2. b. The service time of each vessel i∈N is determined by the assigned berth k∈M.

3. c. Each vessel i∈N can be served only after its arrival time a _i .

4. d. Each vessel i∈N has to be served until its departure time b _i .

5. e. Each vessel i∈N can only be berthed at berth k∈M after k becomes available at time step l ^k .

6. f. Each vessel i∈N can only be berthed at berth k∈M until k becomes unavailable at time step e ^k .

The time windows (TWs) of the vessels and berths are defined by (c)–(f). The objective function (1) aims to minimize the total (weighted) service time for all the vessels, defined as the time elapsed between their arrival to the port and the completion of their handling. When i is not assigned to berth k, the corresponding term in the objective function is zero because $\mathop{\sum}\nolimits_{j \, \in\, N{\cup}d(k)} {x_{{ij}}^{k} } \,{\equals}\,0$ and $T_{i}^{k} \,{\equals}\,a_{i} $ . A detailed mathematical formalization of the model can be consulted in Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005).

(1) $$minimize\,\mathop{\sum}\limits_{i\, \in\, N} {\mathop{\sum}\limits_{k\,\in\, M} {v_{i} } \left[ {T_{i}^{k} {\minus}a_{i} {\plus}t_{i}^{k} \mathop{\sum}\limits_{j\,\in\, N{\cup}d(k)} {x_{{ij}}^{k} } } \right]} $$

In order to facilitate the understanding of the DBAP, we provide in Figure 1 an example of solution. In the figure, a schedule and an assignment plan for six vessels within three berths are shown. The rectangles indicate the vessels and inside each rectangle we display its corresponding service priority (p _i ). The time windows of the vessels are represented by the lines at the bottom of the figure. In this case, for example, vessel 1 arrives at time step 4 and it should be served before time step 14. Moreover, the available time window of each berth is limited by the unshaded areas. Table 1 reports the different handling times for each vessel depending on the assigned berth. For example, if vessel 1 would be assigned to berth 1, its handling time would be equal to 8, which is larger than the handling time of 6 that it has at berth 2. Finally, the objective function value of the given solution example is 93.

Figure 1

Example of solution for the DBAP with six vessels and three berths

Table 1

Vessels handling time depending on the allocated berth

4 A cooperative search for the DBAP

In this work, we propose a cooperative search termed as DCM, which is a population-based approach inspired by Migrating Birds Optimization (MBO, Duman et al., Reference Duman, Uysal and Alkaya2012). In DCM, the population of individuals S is organized into groups and each individual performs a search procedure. Moreover, while the search is being performed, the individuals exchange information with other individuals belonging to their same group. The way the information is shared is almost constrained to the members of the same group in the sense that only at most two members of a group can share information with other groups. Nevertheless, some individuals may belong to more than one group and, therefore, they share information with more than one group, subsequently, DCM consists on the following basically of three main components that are summarized in the following points:

1. 1. In order to organize the individuals into groups a given criterion is used. That criterion can be established according to different measurements or strategies such as the objective function value, solution structure, similarity, etc. In the context of the DBAP, we have established the objective function value provided by Equation (1) as the criterion to be used. Moreover, the adjacency of each individual is determined by their generation order.

   Once the individuals are created and their objective function values are calculated, a comparison among the individuals and their adjacent ones based on the objective function value is performed. This way, when an individual presents a worse objective function value than its adjacent individual, then it will directly form part of its adjacent group. However, if both of them have the same objective function value, there will not exist any communication.

2. 2. The individuals share information with their adjacent partners. There is no direct exchange between individuals of different groups, but indirect exchanges may arise due to individuals belonging to more than one group. The information shared in DCM consists of the best discarded solutions and the way the individuals exchange information depends on their objective function value. That is, if an individual presents a better objective function value than its adjacent solution, it will directly share information with it by providing its best discarded solutions. However, if both of them have the same objective function value, there will not be any information exchanged. Finally, if the individual has a worse objective function value, it will receive information from its adjacent solution.

3. 3. The division of the population into groups and the way the information is exchanged among them is not always the same, it can be re-determined if a given reorganization condition is met. That is, every time that condition is met, the distribution of the population is re-designed.

The pseudocode of DCM is depicted in Algorithm 1. The initial population composed of n _s individuals is randomly generated (line 1). The best solution is initialized to the best individual (line 2). The distribution of the population in groups is determined by considering and comparing the objective function value of each individual and its adjacent ones (line 4). Once the individuals are organized into groups, the search process is performed (lines 5–15) until the reorganization condition is met. In this case, the reorganization condition used for the DBAP is set until the best solution known, s _best, is improved or any best solution of a group, s∈L, is able to improve. In the search process, n _on random neighbor solutions are generated (line 7) for each group solution belonging to the set containing the best solutions of each group, L, or belonging to the independent individuals set I (line 6). If the best neighbor random solution leads to an improvement, the current solution is replaced by that one (line 8). Then, each individual not being a leader or independent s∈F generates n _on−δ neighbors and adds the δ best discarded neighbors received from its adjacent individual (lines 11–12). In the special case that an individual belongs to two groups, it will receive 2·δ solutions. If the best solution (generated by the individual or received from a previous individual) leads to an improvement, the solution is replaced by that one (line 13). The DCM search process is carried out while a stopping criterion is not met (line 3). For the DBAP, the search is performed until a maximum number of neighbors equal to |N|³ has been generated by the individuals, where |N| is the number of vessels, or a number n _imp of consecutive iterations without improvement of any individual has been performed.

4.1 Solution structure for the DBAP

In the context of the DBAP, the DCM implementation for this problem considers a solution s as a sequence composed by features, where a feature, is defined as indicated below:

$$features\left( s \right)\,{\equals}\,\left\{ {\left( {i,\,j} \right)\,\colon\,\,{\rm vessel}\,j\,{\rm is}\,{\rm assigned}\,{\rm to}\,{\rm berth}\,i} \right\}.$$

Figure 2 shows an example of the solution structure depicted in Figure 1. Each berth is delimited by a 0. Thus, there will be M sub-sequences. The service order of each vessel is determined by its position in the subsequence. As can be seen in Figure 2, only vessel 4 is allocated at berth 1. At berth 2, the vessel 2 is the first vessel to be allocated. Once it departs from the berth, the next vessel to be allocated is vessel 1, and so on.

Figure 2

Solution structure for the Berth Allocation Problem

5 Computational results

This section is devoted to present the computational experiments carried out in order to assess the performance of our proposed approach. All the reported computational experiments were conducted on a computer equipped with an Intel 3.16 GHz and 4 GB of RAM. By taking into account the experiments carried out in this work, we identified the following parameter values for DCM: number of generated neighbour solutions per individual (n _on)=20, number of shared solutions (δ)=3, number of individuals n _s =30, and stopping criteria of max _N =|N|³ as the number of generated neighbor solutions by the individuals or n _imp=20 consecutive iterations without improvement from any individual of the population.

The problem instances used for evaluating our proposed algorithm are the largest ones provided in Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005) consisting of 60 vessels and 13 berths. As described in Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005), those instances were generated taking into account a statistical analysis of the traffic and berth allocation data at the maritime container terminal of Gioia Tauro (Italy). Furthermore, in order to compare our algorithmic proposal, the following approaches have been considered: (i) the mathematical model proposed by Christensen and Holst (Reference Christensen and Holst2008) implemented in CPLEX, (ii) PSO proposed by Ting et al. (Reference Ting, Wu and Chou2014), and (iii) an adaptation MBO algorithm for this problem.

Table 2 shows the computational results obtained by applying these solution approaches. The mathematical formulation implemented in CPLEXFootnote ² by Buhrkal et al. (Reference Buhrkal, Zuglian, Ropke, Larsen and Lusby2011) provides the optimal solution in 17.92 seconds in the worst case. However, as discussed in the work of Lalla-Ruiz et al. (Reference Lalla-Ruiz, Melián-Batista and Moreno-Vega2012), CPLEX may require large amounts of memory and computational time, depending on the complexity of the instances. Recently, Ting et al. (Reference Ting, Wu and Chou2014) have proposed a PSO, which finds the optimal solutions with less computational effort. The results shown in the table correspond to the best objective function values provided by PSO and the computational time is the average time required for 30 executions.

Table 2

Computational results with the best solution approach provided in the literature, Particle Swarm Optimization ((PSO, Ting et al. (Reference Ting, Wu and Chou2014)) for the largest instances (60 vessels and 13 berths) provided by Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005)

DCM=decentralized cooperative metaheuristic, MBO=migrating birds optimization, LS=local search.

Bold numbers indicate those cases where, after applying a local search, the optimal solution was provided.

The comparison of DCM with the population-based approach based on PSO reported in Table 2 shows that DCM presents a similar performance regarding the quality of the solutions within less computational time. In this regard, the comparison with PSO, which is a metaheuristic that follows a decentralized strategy inspired by the social behavior of individuals inside swarms, would highlight the benefits of applying a cooperative structure within a decentralized scheme.

Table 3 shows the comparison of the MBO approach for the DBAP with DCM. The rationale behind including this algorithm is to compare the behavior of DCM with MBO. Moreover, both algorithms are studied with and without a local search (LS) applied to each best solution once their search process is over. The aim of applying a local search after the algorithms have been executed seeks to analyze if they are able to point out high promising regions in the search space. As can be seen in the table, the bold numbers indicate those cases where the solution provided by DCM without local search is able to point out 21 regions that contained the optimal solution after a local search to each best individual in each group is applied. In this context, MBO is able to provide 17 regions where the optimal solution is included.

Table 3

Computational results with the Migrating Birds Optimization (MBO) algorithm for the largest instances (60 vessels and 13 berths) provided by Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005)

MBO=migrating birds optimization; DCM=decentralized cooperative metaheuristic; LS=local search.

Bold numbers indicate those cases where, after applying a local search, the optimal solution was provided.

Concerning the required computational effort, DCM is able to improve the computational time when it is compared with the best solution approaches presented in the literature. Nevertheless, from the comparison with MBO, it can be pointed out that the latter requires less computational time. Since both algorithms are executed under the same stopping criteria, it could likely indicate a premature convergence of MBO.

6 Conclusions and further research

The DBAP has been addressed in this work. In order to efficiently solve it, we propose the application of a cooperative search termed as DCM. It is based on a decentralized grouping strategy for dividing a population of individuals into groups. The individuals within the same group cooperate by exchanging information. This grouping strategy improves the diversification of the search as well as the intensification in some regions of the search space through the sum of efforts among the individuals of the same group. Furthermore, the constrained relation for sharing information among individuals through the division of groups allows to reduce resources in comparison to ‘all to all’ communication.

It can be concluded from the computational experimentation that the proposed algorithm is able to provide the optimal solutions within reasonable computational time for the instances proposed by Cordeau et al. (Reference Cordeau, Laporte, Legato and Moccia2005). In this regard, the time advantage exhibited by our proposed approach makes it suitable as a resolution method for being applied either individually or included into integrated schemes where solving the berth allocation is required. In addition, DCM is also appropriate for pointing out high promising regions in the search space. Moreover, the computational results show that DCM exhibits a better performance than other optimization algorithms presented in the literature for the DBAP. Finally, it is worth to mention that the comparison with the best population-based approach based on PSO highlights the benefits of applying a decentralized cooperative scheme for improving the solving times and detecting promising regions in the search space.

On the basis of the contributions presented in this paper, the subsequent stage of our research will be focused on the analysis of the influence of the different components composing our proposed approach as well as its application to other relevant optimization problems at the seaside of maritime container terminals.