Ant Colony Optimization for the Ship Berthing Problem

Chia Jim Tong, Hoong Chuin Lau, Andrew LimASIAN 1999 · DOI

TL;DR

This paper introduces FF-AS-SBP, an Ant Colony Optimization (ACO) algorithm designed to tackle the complex Ship Berthing Problem (SBP). By adapting ACO's natural inspiration of ant foraging behavior to the SBP, the authors demonstrate a more effective approach than traditional randomized methods, achieving better solutions with comparable computational effort.

What Problem Does This Paper Address?

The Ship Berthing Problem (SBP) is a challenging combinatorial optimization problem. It involves efficiently assigning ships to berths along a wharf, considering their arrival times, durations, lengths, and various clearance constraints. Essentially, it's about minimizing the required wharf length while ensuring all ships can be accommodated without conflicts. The SBP is a generalization of the Dynamic Storage Allocation Problem (DSA), which is known to be NP-complete, meaning that finding the absolute optimal solution becomes computationally infeasible as the problem size grows. Existing algorithms often struggle to find high-quality solutions for these complex scenarios.

Methods

The core of this paper is the application of Ant Colony Optimization (ACO) to the SBP. ACO is a metaheuristic inspired by the way ants find the shortest path to food sources by laying down pheromone trails. In this work, the authors adapt this paradigm by:

  • Representing Solutions: Instead of directly representing ship positions, the problem is framed in terms of permutations of ships. This permutation dictates the order in which ships are considered for berthing.
  • Indirect First-Fit (FF) Algorithm: A standard "first-fit" approach is used to berth ships based on the permutation. This means ships are placed as early as possible without violating constraints, given the order defined by the permutation.
  • FF-AS-SBP Algorithm: This is the novel ACO algorithm. It uses artificial "ants" to explore the space of ship permutations.
  • Pheromone Trails: Pheromone trails are used to guide the ants. Specifically, pheromone values $T_{ij}$ represent the desirability of placing ship $i$ before ship $j$ in the permutation.
  • Global Update: After ants build solutions, pheromone trails are reinforced based on the quality of the best solutions found (global update).
  • Local Update: As an ant constructs a permutation, it uses pheromone information to probabilistically choose the next ship in the sequence, balancing exploitation (choosing high-pheromone paths) and exploration (trying new paths).
  • Randomized FF Algorithm: A baseline algorithm is used for comparison, which simply generates random permutations and applies the FF berthing strategy.

Datasets

The paper describes experiments conducted on 6 test cases. These cases were generated using a block-cutting algorithm that creates "compact" problems with zero fragmentation, designed to be difficult to solve optimally. The constraints related to clearance distances and fixed/forbidden positions were absent in these test cases, meaning they were effectively treated as DSA problems.

Key Insights and Ideas

  • ACO's Applicability to SBP: The paper successfully demonstrates that ACO, a paradigm inspired by natural foraging, can be effectively applied to a complex logistical problem like ship berthing, even when the problem is NP-complete.
  • Indirect Solution Representation: Framing the SBP solution as a permutation of ships, rather than direct berth assignments, proved to be a more amenable representation for ACO. This indirect approach avoids the complexities of directly mapping pheromones to physical berthing locations.
  • Pheromone as a Guide for Permutations: The pheromone trails effectively guide the search towards better ship ordering permutations, leading to improved berthing solutions compared to random approaches. This highlights that pheromone information doesn't need to directly map to the physical structure of the problem to be useful.
  • Balancing Exploration and Exploitation: The FF-AS-SBP algorithm's success relies on its ability to balance exploring new permutation possibilities with exploiting promising ones, a hallmark of effective ACO implementations.

Key Results

FF-AS-SBP consistently outperformed the randomized FF algorithm, especially for larger and more complex cases.

  • For case 1, both algorithms found the optimum solution.
  • For larger cases (e.g., case 6 with 320 ships), FF-AS-SBP achieved significantly better mean costs (374.6) compared to randomized FF (421.2).
  • The paper suggests that ACO can find solutions with mean costs ranging from 0% to 17% of the optimum on difficult (compact) cases.

Limitations and Future Work

The authors acknowledge several areas for future investigation:

  • Heuristic Measures: Exploring heuristic measures for partial FF permutations during construction could further improve performance.
  • Pheromone Matrix Design: Investigating alternative designs for the pheromone matrix might yield better results.
  • Parameter Tuning: A deeper understanding of the parameter space and its impact on algorithm dynamics is needed for optimal settings, potentially through meta-heuristics.
  • Heterogeneous Ants: Employing ants with differing quantitative parameters or search strategies could enhance performance and offer insights into distributed computing.
  • Parallelization: Given that individual ants operate independently, distributing the workload across multiple processors could lead to significant speedups.
  • Local Search Integration: Combining ACO with local search techniques (like tabu search) is a promising avenue for improving solution quality.

Summary updated

BibTeX
@inproceedings{tong1999ant,
  author = {Chia Jim Tong and Hoong Chuin Lau and Andrew Lim},
  title = {{Ant Colony Optimization for the Ship Berthing Problem}},
  booktitle = {ASIAN},
  year = {1999},
  doi = {10.1007/3-540-46674-6\_30},
}
Figure