Optimizing Container Loading and Unloading through Dual-Cycling and Dockyard Rehandle Reduction Using a Hybrid Genetic Algorithm

In plain words

A container ship is unloaded and loaded by a quay crane, one box at a time. The crane can save time by unloading a box and then loading a new one in the same trip, instead of returning empty. Which box comes off first decides how many such paired trips are possible.

Boxes that are to be loaded sit in a yard next to the dock. If a box needed next is buried under other boxes, those boxes must be moved out of the way. That extra shuffling takes time. The order in which the ship is unloaded also decides which boxes must be fetched from the yard, so the two problems are linked.

Earlier work usually optimised the crane order first and the yard layout second, with the first answer fixed. This paper proposes a genetic algorithm that searches over both at the same time. It keeps a population of candidate plans, mixes and mutates them, and keeps the cheapest ones. In simulated ships of different sizes it reports lower total time than four baseline methods.

TL;DR

• Jointly optimises the quay-crane unloading order (A1) and the dockyard layout (A2) for one ship row, with a hybrid GA that has a one-dimensional and a two-dimensional chromosome part §4.1 §4.2.3.
• Cost is operation time T = 105 s × single cycles + 170 s × dual cycles + 60 s × rehandles eq. 1 §5.3.
• Author-reported: lowest mean operation time in five of six simulated scenarios; 20 of 24 pairwise paired t-tests significant at α = 0.05 tab. 9 §5.5.
• A repository is linked from this card, not from the paper. Its code differs from the paper in several parameters and operators (crossover rate, mutation rate, fitness weight, roulette, dockyard initialisation and rehandle placement). See Paper vs code.

Problem

Quay cranes are the most capital-intensive asset in a terminal, and their utilisation often limits vessel turnaround §1. A single cycle (SC) unloads one container and returns empty. A dual cycle (DC) unloads a container and loads a prepared one in the same move; the paper states that DC can reduce crane time by 10–20 % in other studies §1 §2.1.

The unloading order determines how many DCs are possible §1 §3.1.1. A dockyard rehandle happens when the container to be loaded is not on top of its yard stack, so containers above it must be moved first §3.1.2.

The paper states that prior work optimised the crane sequence and the yard plan separately, so the dual-cycle order and the yard arrangement conflict §1 §2.3. It claims the joint problem is NP-hard with search space S! × N! (S stacks, N containers) §4.2.1. It gives no proof.

Assumptions §4.1.1: loading containers are ready at the dockside; unloaded containers move to the yard without delay; dual cycling is restricted to one row; rows are processed one at a time; no inbound-vehicle or crane delays; dockyard rehandles follow a nearest-lowest rule (assumption vi); turnaround time is proxied by cycle counts (assumption vii).

Method

Notation and cost

The ship row has N stacks. Each container is labelled [stack][tier], for example 2C for destination stack 2, tier 3 §3.1. The unloading plan and loading plan are per-stack lists §3.1 tab. 4.

Two decisions are encoded in each chromosome §4.2.3 alg. 1:

• A1: a permutation of the stack indices 1..N, the order in which the crane processes stacks §4.2.3.
• A2: the dockyard plan, a matrix of yard stacks; each cell holds a container label, and each column is a tier with Tier 1 at the bottom §4.2.3 fig. 3.

The objective is a weighted sum of single cycles w_s, dual cycles w_d and rehandles R eq. 1 §4.1.3:

T = \alpha\, w_s + \beta\, w_d + \gamma\, R eq. 1

\min T_{\max} eq. 2

The paper also states a scheduling model with constraints on completion times TU_c and TL_c (unloading and loading per stack), sequencing binaries X_ij and Y_ij, a big-M constant μ, and height limits H_mn §4.1.3. The constraints are numbered by LaTeX as eq. 3–eq. 12 (one row each):

TL_c - TU_c \ge \alpha L_c \quad \forall c \in S eq. 3

TU_i - TU_j + \mu X_{ij} \ge \alpha U_i \quad \forall i,j \in S eq. 4

TU_j - TU_i + \mu (1 - X_{ij}) \ge \alpha U_j \quad \forall i,j \in S eq. 5

TL_i - TL_j + \mu Y_{ij} \ge \alpha L_i \quad \forall i,j \in S eq. 6

TL_j - TL_i + \mu (1 - Y_{ij}) \ge \alpha L_j \quad \forall i,j \in S eq. 7

TU_c \ge \alpha U_c \quad \forall c \in S eq. 8

h_{mn} \le H_{mn} \quad \forall m,n eq. 9

X_{ij} \in \{0,1\} \quad \forall i,j \in S eq. 10

Y_{ij} \in \{0,1\} \quad \forall i,j \in S eq. 11

x_{rmno} \in \{0,1\} \quad \forall r,m,n,o eq. 12

The paper does not say how this model is solved. The GA evaluates each chromosome with a simulation of the cycle rules instead alg. 4 alg. 5.

Cycle rules and rehandles

Single and dual cycles are counted while the plans are executed. The first stack is unloaded with no pairing alg. 4. Afterwards, each container that leaves the ship is paired with the next pending load if there is one alg. 5. Remaining loads count as single cycles alg. 5.

When a container is requested from the yard, any containers above it are moved. Each move is one rehandle. Each moved container goes to the nearest stack with the lowest height, and yard state is updated §3.1.2 §4.1.1 vi. The paper's yard height limit is 6 §5.2.

Genetic algorithm

Population size P = 200 and elite share 20 % tab. 5 §4.2.10. Section §4.2.3 describes the initial population but does not say how it is drawn. The 1-D part (A1) uses two-point crossover with duplicate repair; the 2-D part (A2) uses a substring crossover §4.2.5 fig. 5 fig. 6. Mutation is a swap on A1 and a two-point swap on A2 §4.2.6 alg. 2 alg. 3. Parents are chosen by roulette wheel §4.2.8 alg. 6. The loop ends at termination §4.2.9 alg. 7.

# Main loop of QCDC-DR-GA  [alg. 1] [§4.2.2]
# Input:  loading plan and unloading plan of one row
# Output: best unloading sequence A1 and dockyard plan A2

def qcdc_dr_ga(loading_plan, unloading_plan, population):
    # Chromosome = (A1, A2); population size P = 200  [tab. 5]
    costs = [cost(loading_plan, a1, a2) for a1, a2 in population]
    population, costs = sort_ascending(population, costs)  # [§4.2.7]
    while not terminated(costs):             # [alg. 7] [§4.2.9]
        # Keep the best 20 % of members unchanged  [§4.2.8] [tab. 5]
        children = population[: elite_count(len(population))]
        while len(children) < len(population):
            # Two parents chosen by roulette wheel  [alg. 6]
            parent_1, parent_2 = roulette_pick(costs), roulette_pick(costs)
            # Crossover on A1 and A2 (see the operators below)  [§4.2.5]
            child_1, child_2 = crossover(parent_1, parent_2)
            # Mutate with probability P_m = 0.30  [alg. 2] [tab. 5]
            children += [maybe_mutate(child_1), maybe_mutate(child_2)]
        costs = [cost(loading_plan, a1, a2) for a1, a2 in children]
        population, costs = sort_ascending(children, costs)
    return population[0]

# Cost of one chromosome  [alg. 4] [alg. 5]
# Input:  loading plan, A1 (stack order), A2 (dockyard plan)
# Output: single cycles w_s, dual cycles w_d, rehandles R

def cost(loading_plan, a1, a2):
    w_s = 0
    w_d = 0
    rehandles = 0
    # The first stack is unloaded with no load paired  [alg. 4]
    for container in stack_top_first(a1[0]):
        if leaves_ship(container):
            unload(container)
            w_s += 1
    # Each later unload pairs with the next pending load  [alg. 5]
    for stack in a1[1:]:
        for container in stack_top_first(stack):
            if leaves_ship(container):
                unload(container)
                if load_pending():
                    moved = load_next(a2)  # counts rehandles [§3.1.2]
                    rehandles += moved
                    w_d += 1
    # Remaining loads have no unload to pair with  [alg. 5]
    while load_pending():
        moved = load_next(a2)
        rehandles += moved
        w_s += 1
    return w_s, w_d, rehandles

# Two-point order crossover on A1 with repair  [§4.2.5] [fig. 5]
# Input:  two permutations of stack indices, length N
# Output: two child permutations

def crossover_1d(parent_1, parent_2):
    # Two random cut points, left <= right  [§4.2.5]
    left, right = random_cut_points(len(parent_1))
    # Exchange the segment between the cut points  [§4.2.5]
    child_1 = parent_1[:left] + parent_2[left:right + 1] + parent_1[right + 1:]
    child_2 = parent_2[:left] + parent_1[left:right + 1] + parent_2[right + 1:]
    # Drop duplicated genes and append the missing ones  [§4.2.5]
    child_1 = repair(child_1, parent_1)
    child_2 = repair(child_2, parent_2)
    return child_1, child_2

# Roulette-wheel parent choice  [alg. 6] [§4.2.8]
# Input:  costs of the population (lower is fitter)
# Output: index of one selected member

def roulette_pick(costs):
    # Fitness is the inverse cost; scaling is not stated  [§4.2.8]
    fitness = [1.0 / cost for cost in costs]
    wheel = cumulative_sum(fitness)          # E_rw = wheel[-1]
    spin = random_uniform(0, wheel[-1])      # [alg. 6]
    return first_index_at_least(wheel, spin)

Two-dimensional operators, described in words:

• 2-D crossover §4.2.5 fig. 6: two random yard rows are chosen as boundaries, and the block of rows between them is exchanged between parents. Then two-point crossover is applied within the swapped rows. Duplicate containers are removed and missing ones re-inserted. The method is adapted from [tsai2015two].
• 2-D mutation alg. 3 fig. 8: pick two yard rows and one column in each, then exchange the two containers. The algorithm is in alg. 3.

Termination alg. 7 §4.2.9: the loop stops at generation G, or when the best cost has not changed for N_s successive generations, N_s = 100. G is not stated. The text instead says the run stops after 1000 consecutive iterations tab. 5 §4.2.10.

Hyperparameters

Scenario definitions tab. 6: scenario 1 is 30 stacks, height 10; scenario 2 is 25 and 10; scenario 3 is 20 and 10; scenario 4 is 15 and 8; scenario 5 is 10 and 5; scenario 6 is 5 and 4. Scenarios 1–2 are called large, 3–4 medium, 5–6 small §5.2 tab. 6.

Results

Author-reported. Setup: simulated row plans, 20 instances per scenario §5.2 §5.5; cycle weights 105, 170 and 60 s §5.3; baseline methods listed in §5.1; the paper reports running on 8 GB RAM, Ubuntu 22.04 and an Intel Core i5 (8th generation) with Python, Pandas and NumPy §5. No wall-clock time per instance is reported.

Paired t-test results, mean operation time in minutes tab. 9. Improvement is (baseline − proposed) / baseline. "ns" means not significant at α = 0.05.

Source: tab. 9. Significant in 20 of 24 comparisons §5.5 tab. 9. Scenario 6 against GA-ILSRS scenario 1 is the only comparison where the proposed mean is higher §5.3.2.

fig. 10 has four panels (a–d): single cycles, dual cycles, rehandles and total operation time, each comparing the proposed method with the four baselines fig. 10. The paper reports rehandle reductions of 11–84 % in §5.3.2, which are not in any table.

Controlled ablation with A2 frozen versus optimised, on one seeded instance set tab. 10 §5.4.1:

For scenarios 1–4, the ablation uses a proxy: the GA-ILSRS scenario 1 baseline, which optimises A1 with a fixed yard plan §5.4.2 §5.4.3. The paper reports 41.3 and 20.4 min (5.8 % and 3.5 %) for scenarios 1–2, and 8.4 and 19.6 min (2.0 % and 7.9 %) for scenarios 3–4 §5.4.3.

Paper vs code

Code: comparative_simulation/ in github.com/Abrar2652/QCDC-DR-GA at commit c7c68b8, MIT license. The paper does not link this repository. The owner is found by GitHub search, and the GitHub profile display name matches the second author, "Md Abrar Jahin". Confirm ownership before relying on it. I read the code and did not run it.

• Crossover rate. Paper: 0.8 tab. 5. Code: crossover is applied to every parent pair; there is no rate check qcdc_ga.py.
• Mutation rate. Paper: 0.30 tab. 5 alg. 2. Code: an integer threshold of 40 out of 0–100, so the mutation fires when randint(0, 100) <= 40, which is 41 of 101 values, about 0.41 qcdc_ga.py qcdc_driver.py _recovered_notebook.py. The harness default names "mut": 0.3, but the driver ignores that key ablation_harness.py.
• 2-D mutation. Paper: two rows, one cell in each, then exchange alg. 3. Code: one row is chosen and its two cells are swapped qcdc_ga.py.
• Duplicate repair in 1-D crossover. Paper: duplicates removed, missing genes appended to the end in order of appearance §4.2.5. Code: duplicates are replaced in place by missing genes taken from the largest-first end of a sorted list qcdc_ga.py.
• 1-D mutation. Code swaps two random positions, which can be the same position and then changes nothing qcdc_ga.py.
• Fitness weight. Paper: γ = 60 s throughout §5.3 §5.4.1. Code: the GA optimises with (105, 170, 90), and only the reported numbers use γ = 60 qcdc_ga.py qcdc_ga.py.
• Roulette second parent. Paper: the standard wheel alg. 6. Code: the second draw never breaks, so the second parent is always the worst-ranked member qcdc_ga.py. The code's own header says this "shaped Table 9". A corrected flag exists qcdc_ga.py.
• Dockyard initialisation. Paper: §4.2.3 does not say how the initial A2 is drawn. §5.4.1 says the fixed-A2 dockyard comes from a "random nearest-lowest" heuristic. Code: the ablation runs start both arms from the same instance dockyard (opt_init = "shared") qcdc_driver.py run_ablation_parallel.py. The dockyard generator places each container uniformly at random among non-full stacks, not nearest-lowest functions.py.
• Rehandle placement. Paper: nearest stack with the lowest height §3.1.2 §4.1.1 vi. Code: the nearest stack with room, left neighbour then right, with no height comparison. New stacks are appended when none has room Port.py.
• Dual-cycle counting. Paper: a dual cycle needs a pending load alg. 5. Code: a dual is an unload immediately followed by a load in the result list, and every other unload counts as a single cycle Port.py.
• Termination. Paper: N_s = 100 alg. 7 or 1000 consecutive iterations tab. 5. Code: the notebook loop runs iteration <= 2000 _recovered_notebook.py. The full run log records a patience of 250 full_run.log.
• Rehandle time. Paper: "uniform distribution of 60 seconds" §5.3. Code: constant 60 s ablation_harness.py.
• Baselines. The repository has no code for the greedy upper bound, the bi-level GA or GA-ILSRS. Their numbers cannot be checked from the code.

Pitfalls

• Termination is underspecified. Three values appear: N_s = 100 alg. 7, 1000 consecutive iterations tab. 5, and a fixed 2000-generation loop in the notebook. The maximum G is not stated. Pick one and say so.
• The MIP is not solved. Equations 2–12 describe a scheduling model with big-M μ and sequencing binaries eq. 3–eq. 12, but no solver, μ value or solution method is stated. Implement the GA with the simulation cost.
• Dual-cycle counting differs. Algorithm 5 counts a dual only when a load is pending, and does not count unpaired unloads alg. 5. The code counts every unpaired unload as a single cycle Port.py.
• Mutation is ~0.41, not 0.30. Use 0.30 if you follow the paper; the code's effective rate is 41 of 101 qcdc_ga.py.
• Yard capacity. The dockyard height limit is 6 §5.2. Scenario 1 has 30 stacks, so the yard holds 180 containers. The paper says a scenario 1 row can have up to 300 container positions §7. The repository's notes estimate a typical scenario 1 load at about 189 containers, which overflows the 180 capacity and makes the original generator loop forever ablation_harness.py. The paper does not say how the yard is sized.
• Headline claims disagree with the table. The abstract says 15–20 % for large ships against existing methods. §5.3.2 says 12.5–20.1 % against the best single-objective baseline. The best baseline for scenario 2 is GA-ILSRS scenario 1 at 3.51 % tab. 9, so the 15–20 % figures are against weaker baselines. §5.3.1 says the proposed method has the lowest mean in all six scenarios, but scenario 6 contradicts that tab. 9 §5.3.2.
• Ship-size ranges disagree. §5.2 gives 18,000–22,000 for large ships and 4,500–10,999 for small ships. Table 2 gives different ranges §5.2 tab. 2.
• Ablation numbers are not comparable to Table 9. Scenario 5 Opt-A2 gives 111.63 in tab. 10 and 119.40 in tab. 9, because the instance sets differ §5.4.1. The paper states this.
• Costs of the four baselines are not reproducible from the code. The greedy upper bound, bi-level GA and GA-ILSRS have no code in the repository.
• Instances. The paper's generator was not seeded and its instances were not archived §5.4.1. The repository includes instances.json and a seed of 20240101 ablation_harness.py.
• Dual cycles are row-local. Dual cycling is restricted to one row §4.1.1 viii, so the method does not model inter-row crane moves §7.

Lineage

• Builds on: double-cycling by Goodchild and Daganzo (2006), greedy unloading order §2.1; the two-dimensional substring crossover and swap mutation from Tsai et al. (2015) §4.2.5 §4.2.6. None has a card here.
• Compared against: greedy upper bound [Goodchild and Daganzo 2006]; QCDC bi-level GA [Zeng et al. 2015]; GA-ILSRS for rehandles [Ji et al. 2015], in scenario 1 and scenario 2 variants §5.1. None has a card here.
• Superseded by: not known.