Container ship stowage problem complexity and connection to the coloring of circle graphs

DOI10.1016/S0166-218X(99)00245-0zbMath0962.90049OpenAlexW2074617595MaRDI QIDQ1570840

Naomi Shpirer, Mordecai Avriel, Michal Penn

Publication date: 11 July 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00245-0

zbMATH Keywords

complexityNP-completecontainer shipstowage plan for containerscoloring of circle graphsshift problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Related Items (32)

The terminal-oriented ship stowage planning problem ⋮ Loading, unloading and premarshalling of stacks in storage areas: survey and classification ⋮ The pickup and delivery problem with time windows, multiple stacks, and handling operations ⋮ Stowage planning for container ships: a heuristic algorithm to reduce the number of shifts ⋮ Multi-objective optimization of the 3D container stowage planning problem in a barge convoy system ⋮ Complexity results for storage loading problems with stacking constraints ⋮ Heuristic search for the stacking problem ⋮ A 3D-BPP approach for optimising stowage plans and terminal productivity ⋮ An exact algorithm for the unrestricted block relocation problem ⋮ Tree search for the stacking problem ⋮ A mathematical model for the container stowage and ship routing problem ⋮ Solving the generalized multi-port container stowage planning problem by a matheuristic algorithm ⋮ A constraint programming model for fast optimal stowage of container vessel bays ⋮ Planning in multi-agent environment using strips representation and non-cooperative equilibrium strategy ⋮ An asymptotically optimal algorithm for online stacking ⋮ A mathematical formulation and complexity considerations for the blocks relocation problem ⋮ Integer linear programming models for the containership stowage problem ⋮ On the complexity of container stowage planning problems ⋮ Genetic algorithm and its performance analysis for scheduling a single crane ⋮ Applying the corridor method to a blocks relocation problem ⋮ The capacitated max \(k\)-cut problem ⋮ Using a Bin Packing Approach for Stowing Hazardous Containers into Containerships ⋮ Circle graphs and monadic second-order logic ⋮ A hybrid approach for multi-objective combinatorial optimisation problems in ship design and shipping ⋮ A decomposition heuristics for the container ship stowage problem ⋮ Joint optimization of container slot planning and truck scheduling for tandem quay cranes ⋮ Generalised online colouring problems in overlap graphs ⋮ Matheuristics for slot planning of container vessel bays ⋮ The stack loading and unloading problem ⋮ Simulation-Based Optimization for Steel Stacking ⋮ The assignment of storage locations to containers for a container stack ⋮ Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reducing prime graphs and recognizing circle graphs
• Scheduling trams in the morning
• Circle graph obstructions
• Stowage planning for container ships to reduce the number of shifts
• Finding maximum cliques in circle graphs
• The Complexity of Coloring Circular Arcs and Chords
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• The complexity of colouring circle graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: Container ship stowage problem complexity and connection to the coloring of circle graphs