Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Large optimization problems usually require significant computational effort. A natural way to solve these problems is by decomposing them into independent sub-problems that are treated with an appropriate procedure. In doing so, [9] propose the POPMUSIC framework. Its basic idea is to locally optimize sub-parts of a solution, ‘a posteriori,’ once a solution to the problem is available. These local optimizations are repeated until a local optimum is found. POPMUSIC may be viewed as a local search working with a special, large neighbourhood.

In this paper, we study the application of POPMUSIC for solving the discrete Dynamic Berth Allocation Problem (DBAP) proposed by [4]; for a general survey on berth allocation problems see [1]. In the DBAP, we are given a set of incoming ships \(N\) and a set of berths \(M\). Each ship \(i \in N\) has to be assigned to an empty berth \(j \in M\) within their (berth and ship) time windows. The main goal of this problem is to minimize the sum of the ships service times, i.e. the time required to serve a ship from its arrival. This problem has been modeled as a Generalized Set-Partitioning Problem (GSPP) [3], its implementation in CPLEX allows to solve small-sized problem instances within reasonable computational times [6]. However, as the size of the instances becomes larger, it runs out of memory.

The GSPP formulation is as follows. A column represents a feasible assignment of a ship to a berth. The set of columns is denoted by \(\varOmega \). Two matrices \(A\) and \(B\) are defined, both containing \(|\varOmega |\) columns. Matrix \(A = (A_{i\omega })\) contains a row for each ship, and \(A_{i\omega } = 1\), if and only if column \(\omega \) represents an assignment of ship \(i \in N\) to a berth. Each column of \(A\) contains exactly one non-zero element. Matrix \(B = (B_{p\omega })\) contains a row per (berth, time) position. The rows of \(B\) are indexed by the set \(P\), with \(|P| = \sum _{k \in M}(e^k-s^k)\), where \(s^k\) and \(e^k\) are the start and end of the availability of berth \(k\), respectively. The entry \(B_{p\omega }\) is equal to \(1\), if and only if, position \(p \in P\) is contained in the assignment that column \(\omega \) represents. The cost \(c_{\omega }\) of any column \(\omega \in \varOmega \) is the service time of the respective position assignment. With these definitions the GSPP formulation of the DBAP presented in [2] is as follows.

$$\begin{aligned} \min \sum _{w \in \varOmega } c_wx_w \end{aligned}$$
(1)
$$\begin{aligned} \sum _{w \in \varOmega } A_{iw}x_w = 1,&\forall i \in N \end{aligned}$$
(2)
$$\begin{aligned} \sum _{w \in \varOmega } B_{pw}x_w \le 1,&\forall p \in P \end{aligned}$$
(3)
$$\begin{aligned} x_{w} \in \{0, 1\},&\forall w \in \varOmega \end{aligned}$$
(4)

The objective function (1) minimizes the service time of the vessels. The set of constraints (2) ensures that all vessels are served. Finally, the constraints (3) guarantee that at a time interval, in a berth, only one vessel can be served.

2 POPMUSIC Approach for the DBAP

The POPMUSIC approach for the DBAP considers a solution \(S\) by means of its scheduling order, where the solution is represented as an integer string and each berth is delimited by a \(0\). An example of a solution structure for 3 berths and 6 ships is as follows, \(S=\{1, 0, 2, 4, 6, 0, 3, 5 \}\). In this case, ship 3 is the first ship to be served at berth 3; once it departs, the next ship to be served is ship 5.

figure a

Algorithm 1 shows the POPMUSIC approach for the DBAP. The initial solution \(S\) is randomly generated by applying a random-greedy method (R-G) proposed by [4]. The solution is divided into \(h\) parts depending on the number of berths. The seed part, \(s_{seed}\), is selected at random from the set of parts, \(H\). Once a solution part is selected, the sub-problem \(R\) is established by joining the \(s_{seed}\) and its \(r\) neighbour parts according to the \(id\) of the part. Two parts are at distance 1, if they are consecutive, e.g. \(part_1\) and \(part_2\). The GSPP mathematical formulation of \(R\) is solved using CPLEX. The POPMUSIC-G differs from the original in the way the set of parts \(O\) is fulfilled when there is an improvement. That is, if a sub-problem is improved, all its composing parts (\(s_{seed}\) and its neighbour parts) are included in \(O\).

Once the POPMUSIC process is over, all the solution parts are joined. The information obtained from them is used for determining a reduced problem instance that will be provided to CPLEX. Similarly to the corridor method [7] this narrow problem allows CPLEX to solve the complete problem to optimality.

The computational experiments carried out in this work are conducted on a computer equipped with an Intel 3.16 GHz and 4 GB of RAM. The problem instances used for evaluating the proposed algorithm are a representative set of the largest instances provided by [4] and a representative set of instances proposed by [6]. For the latter set of instances the GSPP implemented in CPLEX using a standard computer runs out of memory. Moreover, we make a comparison among the best approximate approaches for each set of instances, namely, (i) Clustering-Search with Simulated-Annealing (CS-SA) [5], (ii) Particle Swarm Optimization (PSO) [8], (iii) \(T^2S^*\)+PR Tabu Search with Path-Relinking [6].

Table 1 illustrates the results for the instances of [4]. Regardless of the selection of the parameter \(r\), POPMUSIC and POPMUSIC-G provide optimal solutions in all cases. This characteristic points out that recognizing ‘useless’ or ‘time-consuming’ parameters of the problem parameter space can be narrowed through using the information provided by exactly solving the sub-problems. POPMUSIC-G running times are meaningful compared to those of the approximate solution approaches. Note that, although CS-SA and PSO are able to provide optimal solutions for these cases, they cannot guarantee optimality.

Table 1. Results for the instances provided by [4]
Full size table

Table 2 shows the results obtained for some large instances proposed by [6]. As can be seen, CPLEX runs out of memory as the size of the instances is larger. In this sense, thanks to the POPMUSIC template, the problem can be narrowed and solved to optimality. This feature is relevant when assessing the behaviour of the best solution approach employed for these instances, \(T^2S^*\)+PR, where the evaluation of its performance could not be done because CPLEX runs out of memory without providing an upper bound. Evidently, for some of the instances we are able to improve the best solution results to date.

Table 2. Results for the instances provided by [6]
Full size table

3 Conclusions

In this paper we have provided a POPMUSIC adaptation to the Discrete Dynamic Berth Allocation Problem. By using a given mathematical programming formulation together with the decomposition approach inherent to POPMUSIC we were able to solve large scale instances from the literature to optimality or close to optimality that had been out of reach for optimal solution before.

While additional experimentation is still needed, the results provided in this work highlight the application of POPMUSIC for solving large-sized problems. In this regard, the POPMUSIC approaches proposed in this work have a great potential for ‘recognizing’ relaxed constraints in the parameter space of the problem through leveraging the information obtained by solving the sub-problems. This also incorporates an explicit learning mechanism towards having an autoadaptive control of the size of the sub-problems to be solved.