VRP-Inspired Techniques for Discrete
Dynamic Berth Allocation and Scheduling

Nearest Neighbour (NN), is the simplest constructive heuristic for VRP instances. The core idea of NN is to iteratively extend existing subtours by appending unassigned vessels to the ends of the subtours of the nearest berths which are eligible for them. As a distance metric between a vessel and a berth’s subtour, we consider the marginal increase in cost resulting from the vessel’s insertion at the current endpoint of the berth’s subtour, that is, the difference in the subtour’s objective value before and after the assignment. Initially, all subtours are empty, and the heuristic proceeds by appending vessels to the subtours of eligible berths for them, until all vessels have been assigned or there are no eligible berths for any of the remaining unassigned vessels.

In the sequential variant of NN, the berth subtours are constructed one by one, expanding each time the current berth’s subtour with the nearest compatible vessel that is still unassigned, until it cannot accommodate any more vessels, before proceeding to the next berth. In the parallel variant of NN, which is the one implemented in this work, all berth subtours are constructed simultaneously. In each iteration, each berth’s subtour is extended with the closest compatible unassigned customer, which means that at most $|B|$ customers will be added. The parallel version often achieves better berth utilization, as it avoids the imbalance typically seen in the sequential version, where the last berth tends to service fewer vessels.

Finally, we consider this (parallel) variant of NN in two different scenarios with respect to the revelation of vessel arrivals. The first scenario, tagged as the complete knowledge Nearest Neighbour heuristic (ck-NN), exploits the a priori knowledge of all vessel arrivals. In each iteration it attempts to expand the subtour of every berth once. For each berth, the heuristic appends the nearest unassigned vessel. As previously mentioned, the nearest unassigned vessel to a berth is the one that results in the smallest marginal increase in total cost when appended to the end of its subtour. This process repeats in a round-robin fashion among the berths, until all vessels have been assigned or there are no other feasible assignments. The second scenario, tagged as the predetermined order Nearest Neighbour heuristic (po-NN), aims to adapt NN for online situations where there is no prior knowledge of all arrivals of vessels, but they are revealed to the heuristic one by one. Therefore, in each iteration of po-NN, only one vessel is processed, according to a predetermined order, and is assigned to the nearest eligible berth. Naturally, the order in which vessels are processed can influence significantly the quality of the resulting solution. In this work we focus on the most natural order, indicated by the arrival times of the vessels.

Insertion (INS) is a constructive heuristic that, unlike the NN method, evaluates all possible positions within each subtour to identify the optimal insertion point of some unassigned vessel, without changing the relative order of the already assigned vessels in the subtours. By considering all possible positions, the mooring times of already assigned vessels may be adjusted, provided they still satisfy all the relevant temporal constraints. As in the case of NN, two variants of INS are implemented, predetermined order Insertion (po-INS) which processes and allocates vessels in a predetermined order, and complete knowledge Insertion (ck-INS) which leverages full knowledge of all vessels. The po-INS variant begins by initializing an empty subtour for each berth and, in each iteration, inserts the next unassigned vessel according to the predetermined order, into an eligible subtour. After evaluating all the marginal cost increases for inserting the vessel to the cheapest position of each subtour, the subtour with the smallest marginal cost is eventually chosen for the insertion of the new vessel. The marginal cost of assigning vessel $i$ to berth $j$ is defined as the sum of $i$’s actual waiting time ${𝒕}_{𝒊}^{𝒋}-T_i^{ea}$, its handling time ${𝒉}_{𝒊}$, and its potential departure delay ${𝒕}_{𝒊}^{𝒍𝒅}$. In addition, it includes the cumulative increases in waiting times and departure delays for other vessels $k$ already scheduled at berth $j$ after $i$, due to shifts in their mooring times ${𝒕}_{𝒌}^{𝒋}$ caused by inserting $i$ into $j$’s subtour. As already mentioned, in this work we consider that the vessels are revealed according to their increasing estimated times of arrivals. In contrast, ck-INS operates in $|S|$ iterations, where each iteration evaluates all possible insertion positions for every unassigned vessel in each berth, always selecting the insertion that results in the lowest increase of the overall cost.

The quick and dirty Insertion heuristic (qd-INS) is a restriction of INS, designed to compute even more efficiently a feasible solution, while maintaining an acceptable level of solution quality. The key distinction from INS lies in the following restriction: when inserting a new vessel, not only the relative order, but also the actual mooring times of all the previously assigned vessels to subtours cannot be altered. In other words, this is a non-preemptive variant of the INS heuristic (exactly like the NN heuristic), since it does not affect at all the assignments of previously allocated vessels. As a result, only insertion positions that leave existing mooring times unchanged are considered eligible. This non-preemption limitation reduces the number of eligible insertion positions, thereby speeding up the process. The algorithm evaluates all eligible positions across all subtours and selects the one that minimizes the additional cost for the new vessel. This time, the additional cost is defined solely by the new vessel $i$’s waiting time ${𝒕}_{𝒊}^{𝒋}-T_i^{ea}$, its handling time ${𝒉}_{𝒊}$, and its potential departure delay ${𝒕}_{𝒊}^{𝒍𝒅}$. Once more, the order in which vessels are processed can significantly influence the final outcome. When the vessels are handled in a predetermined order, the corresponding variant of qd-INS is referred to as predetermined order quick and dirty Insertion (po-qd-INS). The complete knowledge quick and dirty Insertion (ck-qd-INS) is the variant of qd-INS that leverages full vessel information in advance.

The Reinsert improvement heuristic iteratively refines a given solution by selectively removing vessels from an existing schedule and then trying to reinsert them into alternative berths, in hope of improving the overall objective value. In each round, the algorithm performs a full pass over all vessels in the current schedule. For each vessel, it evaluates the effect of removing it from its assigned berth and attempting an insertion into an alternative eligible berth and berthing position, respecting all the vessel-to-berth eligibility constraints. If such a reinsertion leads to an improved solution, then the incumbent solution is immediately updated and the algorithm proceeds to the next vessel. The process continues until a full pass over all vessels fails to discover an improved solution.

The Swap improvement heuristic explores the neighbourhood of the current solution by evaluating all feasible pairwise exchanges of vessel assignments between two berths. Specifically, it generates all valid vessel pairs whose berth assignments could potentially be swapped without violating any vessel-to-berth eligibility constraint. For each candidate pair, the algorithm attempts to insert each vessel into the berth originally assigned to the other. If both these insertions are feasible and the resulting solution improves the overall objective value, the swap is immediately accepted and the current solution is updated; otherwise, the incumbent solution remains unchanged. The algorithm then proceeds to evaluate the next pair. By systematically exploring all such pairwise exchanges, the heuristic efficiently identifies and applies locally improving moves that may reduce the overall cost.

The Cuckoo Search Algorithm (CSA) [19] is a population-based metaheuristic optimization algorithm inspired by the breeding behavior of certain cuckoo species. Some cuckoos lay their eggs in the nests of other host birds. Hosts that discover these foreign eggs may either discard them or abandon the nest entirely. Inspired by this reproductive strategy, the following three rules are implemented to apply CSA to optimization problems: (i) Each cuckoo lays one egg at a time in a randomly selected nest; (ii) the best nests, containing eggs of high quality, are preserved and carried forward to the next iteration; (iii) the number of host nests is fixed and cuckoo eggs are discovered by host birds with a probability $p_{csa}\in (0,1)$.

While CSA is rarely applied to VRP variants, its simplicity and ease of implementation make it a useful choice for experimentation and as a benchmarking baseline. CSA is adjusted for DDBASPTW as follows (cf. Algorithm 1): A nest is a set of unique assignments of vessels for their servicing, where each vessel assignment is a pair of values (time, berth) that signifies the mooring time of the vessel at the particular berth. An egg represents either a berth or a mooring time for a particular vessel. The cuckoo egg represents a new assignment for a vessel (either a new berth, or a new mooring time). The total number of nests indicates the entire population of solutions. Each nest contains $2N$ eggs, i.e., two eggs (representing berth and mooring time) for each of the $N$ vessels. In general, the goal of CSA is to employ cuckoo eggs for the exploration and replacement of nests with lower quality.

At first, $m$ nests are created, forming the initial population, from a set of initial solutions which are generated using a slightly modified version of the po-INS heuristic; before processing the vessels, a shuffling step is applied, altering the order in which the vessels are processed. As a result, different vessel-allocation orders are produced for po-INS. In the initial population, the nest with the lowest cost (i.e., objective value) is identified. The reproduction step is carried out first: for each existing nest, a proportion $p_v$ of vessels is randomly selected, and a mutation operator is applied to the solution for each of them. The mutation operator consists of moving the selected vessel to a new, randomly chosen berth. The vessels that remain in the previous berth rearrange their mooring times (but not their relative order) to reduce their waiting times and departure delays as much as possible. A check is performed next to determine if the mutant nest is better than the original nest, comparing their objective values. In that case, the mutant nest replaces the original one. Following this, the probabilistic event of the host discovering the cuckoo’s egg is implemented. This probability, $p_{csa}$, ensures that in each iteration, approximately a fraction $p_{csa}$ of the population is replaced by newly generated random solutions. These new solutions are once again provided by po-INS after shuffling the vessels. The nest with the lowest objective value in the current iteration is identified and compared with the best nest discovered so far. If its cost is lower than the currently best solution, it replaces it. The algorithm terminates when a predefined number of iterations is reached. CSA leverages the rapid execution of po-INS, which is called numerous times, making its speed essential for ensuring the overall computational efficiency of CSA.

The Genetic Algorithm (GA) is a well-known population-based metaheuristic which is inspired by a biological evolution process. GA mimics the Darwinian theory of survival of the fittest in nature. The variants of GA are commonly used to generate high quality solutions to VRP instances and BASP instances via biologically inspired operators such as selection, crossover and mutation. In the context of the GA, a solution, i.e., a complete assignment of all vessels (if possible) to berthing positions, is often referred to as a chromosome.

The variant of GA that is implemented in this work for DDBASPTW (cf. Algorithm 2) begins by generating an initial population of size $m$, following the same procedure that was described for CSA. It then proceeds with a predefined number of iterations. In each iteration, $m$ pairs of “chromosomes” (i.e., solutions in the current population) are selected as parents for the offspring population using binary tournament selection. In a binary tournament, two chromosomes are randomly chosen, and the one with the better objective value is selected. After selecting $m$ parent pairs, a crossover operation is applied to generate offspring; for each vessel present in the parent solutions, the offspring inherits the assignment from one of the two parents with equal probability (50%). If an inherited assignment conflicts with previously inherited ones, the vessel is temporarily excluded from the offspring and stored for later reinsertion. These unassigned vessels are subsequently reinserted using a po-INS based repair mechanism. Next, the mutation operator, exactly as described in the previous section for CSA, is applied to each offspring. Consequently, the newly generated population, consisting of the $m$ offspring solutions, replaces entirely the parent population. At the end of each iteration, the best solution found so far is updated, whenever a better one exists in the current population. Upon completion of all iterations, the algorithm returns the best solution found.

Adaptive Large Neighborhood Search (ALNS) is a single-solution metaheuristic which was first introduced by Stefan Ropke and David Pisinger [16] as an extension of the Large Neighborhood Search (LNS) metaheuristic. LNS iteratively destroys and repairs a solution by applying one destroy operator and subsequently a repair operator. The destroy operator removes parts of a solution while the repair operator reinserts the removed parts making it a complete solution. Similar to its preceding method, ALNS deploys the same sub-classes of operators: destroy and repair. A current solution will be destroyed by the destroy operators and then repaired using the repair operators. The novelty of ALNS is that it now allows us to utilize multiple operators within the same searching process in an adaptive way, where this adaptiveness is attained by recording weights representing the effectiveness of each destroy-repair pair in producing better solutions and dynamically adjusting the random selection of destroy-repair methods proportionally to these weights [18]. ALNS is one of the most widely used metaheuristics for solving instances of VRP variants, and in this section, we adapt it to address DDBASPTW.

ALNS takes as input a feasible initial solution $x$, a set of destroy and a set of repair operators, and a parameter called $updatePeriod$. The algorithm returns the best solution found, denoted by $x_{best}$. The algorithm works as follows (cf. Algorithm 3): Initially, a temporary solution $x$ is constructed and the weights and selection probabilities associated with each operator are uniform. The algorithm then proceeds iteratively for a fixed number of iterations. In each iteration, one destroy and one repair operator are selected using the roulette wheel mechanism: each operator is selected with a probability proportional to its weight, which reflects its effectiveness so far. These operators are then applied to modify the current solution. The resulting solution $x^{\prime }$ is evaluated and potentially accepted based on a simulated annealing criterion, which accepts $x^{\prime }$ unconditionally if it improves the objective value (i.e., ). Otherwise, it accepts $x^{\prime }$ with a probability $e^{-(f(x^{\prime })-f(x))/T}$, where $T$ is a temperature parameter. This mechanism allows the algorithm to escape from local optima by occasionally accepting worse solutions. The temperature $T$ gradually decreases by performing the operation $T=aT$ in each updating period, using a cooling rate $\alpha$, where , thereby reducing the likelihood of accepting inferior solutions over time. If the new solution improves upon the best solution found so far, it replaces $x_{best}$. Every $updatePeriod$ iterations, the weights and selection probabilities of the operators are updated to reflect their effectiveness so far. An operator’s effectiveness weight is evaluated based on how frequently it has led to an accepted solution based on the simulated annealing criterion, relative to the number of times it was applied. Once the termination condition is satisfied, the algorithm returns the best solution obtained.

Five destroy operators were implemented to selectively dismantle parts of the current solution: (i) random removals of assigned vessels (nodes), (ii) clearance of randomly selected berths (subtours), (iii) removal of vessels that significantly contribute to the total objective cost (commonly referred to as Worst Removal), (iv) removal of vessels that are spatially similar to a selected seed vessel (a special case of the well-known Shaw Removal, based on physical attributes such as length or draft) and (v) removal of vessels that are temporally similar to a selected seed vessel (also a special case of the Shaw Removal, based on mooring time). The extent of destruction is governed by a parameter $deg$, known as the degree of destruction, which controls the proportion of the solution to be removed. A sufficiently high value of $deg$ allows the removal of structurally important parts of the solution, increasing the likelihood of escaping from local optima and improving the solution quality.

Six repair operators were implemented to reconstruct solutions after destruction. Three of these are based on po-qd-INS, differing only in the order in which the removed vessels are processed. Specifically, the orderings are determined by $T_i^{ea}$, $T_i^{rd}$ and $P_i$ (which can also be thought of as a measure of importance). The fourth repair operator leverages the po-INS heuristic, using the order in which the vessels were removed. The fifth operator repairs the solution using the ck-NN heuristic of constructing solutions. Finally, the sixth repair operator is based on a 2-regret-insertion, which iteratively selects and inserts a vessel that possesses the largest regret value in the list of removed (and still unassigned) vessels. The regret value of a vessel is obtained by taking the difference between the cost resulting from the best insertion position and the cost resulting from the second best insertion position.

Table 2 compares ten methods: Gurobi (GRB) (using a generic branch and cut algorithm), po-NN, ck-NN, po-INS, ck-INS, po-qd-INS, ck-qd-INS, CSA, GA, and ALNS. The comparison is based on computation times, optimality gaps, and number of vessels allocated across various data sets, all with a one-week planning horizon. The data set corresponding to each block of results is indicated in the first column, using the notation X-Y, where X denotes the number of vessels and Y the number of berths. For each such X-Y benchmark case size, we generated ten different random instances. Each random instance was solved twenty times to obtain stable runtime measurements. For heuristic methods, the execution time is the average over these twenty runs. For metaheuristic methods, both the execution time and the objective value are averaged over the twenty runs. The median across the ten random instances per X-Y size is then presented in the tables as follows. The “Time” row shows the execution time (in seconds). The “VA” row indicates the number of assigned vessels in each method’s solution. The “Gap” row reflects the relative error from the reference value used for comparison. When GRB reaches an optimal solution (i.e., $Gap=0$), the heuristic and metaheuristic methods are evaluated against this optimal value. If GRB fails to reach optimality within a three-hour limit for the execution time (i.e., $Gap>0$), the comparison is made using a derived lower bound, computed from the objective value reported by GRB and the optimality gap it had reached at the time limit. In both cases, the relative error is computed as the difference between the method’s objective value and the reference value, divided by the reference value. Instances where GRB hits the three-hour time limit are marked with an asterisk next to the execution time in the tables. Gap values in Table 2 are reported as decimals but represent percentages (e.g., a value of $0.2$ corresponds to a $20\%$ gap). Overall, the benchmark instances reflect realistic operational scales, with sizes larger or comparable to those of major terminals, such as the Piraeus Container Terminal [12] which can service up to $11$ vessels simultaneously.

In terms of performance, the ck-NN heuristic successfully serves all vessels in $9$ out of $13$ benchmark cases, but optimality gaps range from $17\%$ to $41\%$ which are considered rather unsatisfactory. When not all vessels are assigned to berths, objective values increase due to the penalties applied for unallocated vessels. As expected, po-NN performs poorly across all benchmark cases, as it is a very naive approach. The po-INS heuristic assigns all vessels to berths in $12$ out of $13$ benchmark cases, failing only on benchmark case 40-10, where it assigns one fewer vessel than Gurobi. However, it is worth noting that this is an exceptionally difficult benchmark case, because even Gurobi manages to berth only $39$ vessels within the three-hour limit.

For the benchmark cases where all vessels are successfully moored, po-INS achieves gaps ranging from $3.7\%$ to $26.5\%$. In contrast, the performance of ck-INS is significantly worse, primarily due to its tendency to postpone the consideration of large vessels, which have high handling costs and fewer compatible berths, until later in the construction. By the time these vessels are considered, their feasible berths are often already occupied and the algorithm cannot reassign previously placed vessels or even reorder them, leading to denial of service for these vessels and, thus, high penalties in the objective value of the resulting solution. The po-qd-INS heuristic assigns all vessels to berths in $11$ out of $13$ benchmark cases with gaps varying from $5.7\%$ to $27\%$. The ck-qd-INS variant also exhibits poor performance for the same reasons as ck-INS, as it similarly delays the consideration of larger vessels, leading to denial of service for many of them and thus incurring high penalties. Overall, we observe that po-NN, ck-INS, and ck-qd-INS yield unsatisfactory results and are excluded from further discussion. Among the remaining heuristics, it is evident that ck-NN performs the worst. Between po-INS and po-qd-INS, the former delivers higher solution quality, albeit with a slight increase in computational time. The po-qd-INS heuristic outperforms po-INS only in cases where both of them fail to allocate two vessels. Lastly, in four benchmark cases, namely, 30-10, 60-20, 65-20 and 75-20, po-INS and po-qd-INS produce identical objective values, which can be attributed to the predetermined vessel ordering used in both methods.

Regarding the metaheuristics, we observe that all three algorithms successfully allocate all vessels to berths in $12$ out of $13$ benchmark cases. In all cases, the metaheuristics consistently produce higher-quality solutions than the constructive heuristics, albeit with increased computational times. Among them, ALNS achieves the best performance, except for benchmark case 40-10, where only GA matches GRB in terms of the number of allocated vessels to berths. Overall, CSA and GA yield solutions of comparable quality, but GA is significantly faster. In summary, ALNS delivers the highest-quality solutions among all methods evaluated and, while slower than the constructive heuristics and the GA metaheuristic, it remains computationally efficient. Specifically, in the $12$ benchmark cases where all vessels are successfully allocated to berths, ALNS achieves optimality gaps ranging from $0\%$ to $13\%$ compared to GRB’s gap which ranges from $0\%$ to $8\%$, while being faster than GRB by factors ranging from $353$ to $83,076$.

Table 3 presents the results of the improvement heuristics Swap and Reinsert, applied to the base heuristics ck-NN, po-INS, and po-qd-INS. For each benchmark case, the improvements were applied to all $10$ instances and the median values across these instances are reported. The “Before” columns report the gap achieved by each base heuristic prior to applying the improvement heuristics (identical to the values in Table 2). The “Time” columns indicate the execution time in seconds per improvement heuristic, while the “Gap” columns show the updated gaps after applying Swap and Reinsert, respectively. We report results only for po-NN, po-INS, and po-qd-INS, as these were shown to be the best-performing constructive heuristics in Table 2.

Swap significantly enhances solution quality, particularly for the ck-NN heuristic which typically produces initial solutions with substantial room for improvement. In contrast, in benchmark cases such as 25-10 and 30-10, where po-INS and po-qd-INS already produce almost optimal solutions, the Swap heuristic offers little or no improvement. Similarly, in cases where some vessels remain unallocated, the Swap heuristic has limited impact, as the penalty for unassigned vessels tends to dominate the overall objective value. The Reinsert heuristic exhibits similar behaviour, proving especially effective when applied to ck-NN solutions for the same reasons. Again, when solutions are almost optimal, or when unassigned vessels drive the objective, Reinsert contributes minimally to the solution quality. When comparing Swap and Reinsert, there is no clear winner; both perform comparably and provide improvements when the solution space allows for meaningful adjustments. When benchmarked against metaheuristics, both improvement heuristics are faster but generally yield solutions of lower quality than CSA and GA and consistently worse than ALNS. Overall, when the initial solution is sufficiently suboptimal, both Swap and Reinsert effectively enhance solution quality, therefore standing between constructive heuristics and metaheuristics in the Pareto frontiers of the solution-quality to execution-time diagrams.