Research on Operation Optimization Problem of Material Handling System for Large Ship

Cuiping Wen, Kai Huang, Weifeng ZhuProceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013) 2013 · DOI

TL;DR

This paper tackles the logistical headache of resupplying large ships at sea by optimizing the sequence in which materials are handled. By framing the scheduling challenge as a variation of the classic Traveling Salesman Problem (TSP), the authors use an improved Genetic Algorithm to significantly reduce the total time required to move supplies from a dock to their final onboard warehouses.

What Problem Does This Paper Address?

Large ships are essentially floating cities that require constant "refueling" with food, water, and mission-specific materials. The efficiency of this resupply process is critical, especially when the ship is away from a secure base.

The authors identify a specific bottleneck: the material handling system. Supplies move from a supply boat (Point A) to a temporary storage section on the target ship (Point B), and finally to specific onboard warehouses (Point $C_i$). The challenge arises from three main constraints:

  1. Bottlenecks: The path from the supply boat to the ship can only handle one type of material at a time.
  2. Queueing: Materials arrive at the ship's storage area and must follow a First-In-First-Out (FIFO) rule.
  3. Mutual Interference: Certain materials cannot be transported from the storage area to their final warehouses simultaneously due to safety or structural constraints.

Finding the fastest sequence to move $n$ types of materials through this system is a combinatorial optimization problem that becomes exponentially harder as the number of materials increases.

Methods

The researchers modeled the logistics chain mathematically and identified it as a variant of the Traveling Salesman Problem (TSP), a classic NP-hard problem in computer science. To solve it, they implemented an Improved Genetic Algorithm (GA).

Key features of their approach include:

  • Coding: Solutions are represented as bit strings representing the handling sequence.
  • Adaptive Fitness Function: The "fitness" of a sequence is inversely proportional to the total time it takes. The shorter the time, the more likely that sequence's "genes" are to pass to the next generation.
  • Selection & Crossover: They used a "sorting choice" method for selection and an exchange heuristic crossover operator to combine successful sequences.
  • Mutation: To avoid getting stuck in local optima (sub-optimal solutions that look good only in the short term), they employed an inverted-insert hybrid mutation operator.

Datasets

The paper does not use a standard public benchmark dataset. Instead, the authors created a representative case study to validate their model:

  • Material Schedule: A list of 10 materials with specific transport times ($t_1$ for A to B, $t_2$ for B to C, and $t_3$ for single-unit handling).
  • Relationship Matrix: A $10 \times 10$ matrix ($r[10][10]$) defining which materials have "mutual influence" (conflicts) and cannot be moved at the same time.

Key Insights and Ideas

  • TSP Mapping: The most significant insight is abstracting a physical logistics problem (ship resupply) into a well-studied mathematical framework (TSP). This allowed the authors to leverage decades of research into intelligent algorithms.
  • Constraint Modeling: The authors successfully quantified "mutual influence" between materials, turning a vague safety concern into a hard mathematical constraint for the algorithm to solve.
  • Efficiency of GA: The study highlights that while traditional algorithms might struggle with the "climbing" ability needed for global optimization, a properly tuned Genetic Algorithm can find near-optimal solutions extremely quickly.

Key Results

The authors tested their algorithm on the 10-material scenario.

  • Speed: The optimal solution was found in just 0.031 seconds, converging by the 4th generation of the algorithm.
  • Optimization: Out of several tested sequences, the algorithm identified the handling order (3,2,1,4,7,5,10,8,9,6) as the optimum, resulting in a total time of 781 minutes.
  • Comparison: Other sequences resulted in times as high as 1249 minutes, representing a ~37% reduction in time compared to a poor handling sequence.

Limitations and Future Work

  • Scale: The example provided only uses 10 materials. While the authors claim the algorithm is ideal for large $n$, the paper doesn't provide performance data for hundreds or thousands of material types.
  • Static Variables: The model assumes transport times are known and fixed. In real-world maritime environments, factors like sea state, equipment failure, or human fatigue introduce stochastic (random) variables that this model doesn't currently account for.
  • Future Directions: The authors suggest that this modeling method can be applied to actual ship supply systems to guide real-time operations, but further integration with real-time sensor data would likely be necessary for a production-ready system.

Summary updated

Abstract

Material supply is the basic guarantee for the large ship sailing to ocean. In order to improve the efficiency of the supply of the large ship, the support of materials handling system is needed. According to the typical material handling system of the large ship, with the material handling's time shortest as the decision goal and the handling sequence as the decision variable, the analysis and construction of the model for optimizing the system's operation is given in this paper. The improved genetic algorithm is put forward. The specific model is also given and it's proved that the analysis and modeling method in this paper can effectively improve the efficiency of the material handling of the large ships.
BibTeX
@inproceedings{wen2013research,
  author = {Cuiping Wen and Kai Huang and Weifeng Zhu},
  title = {{Research on Operation Optimization Problem of Material Handling System for Large Ship}},
  booktitle = {Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013)},
  year = {2013},
  doi = {10.2991/iccsee.2013.477},
}
Figure