• Search
  • Advanced Search
Journal of Navigation and Port Research 2004;28(2):129-133.
Published online March 31, 2004.
A study on the column subtraction method applied to ship scheduling problem
Hee-Su Hwang, Hee-Yong Lee, Si-Hwa Kim
Abstract
Column subtraction, originally proposed by Harche and Thompson(1994), is an exact method for solving large set covering, packing and partitioning problems. Since the constraint set of ship scheduling problem(SSP) have a special structure, most instances of SSP am be solved by LP relaxation. This paper aim, at applying the column subtraction method to solve SSP which am not be solved by LP relaxation. For remained instances of unsolvable ones, we subtract columns from the finale simplex table to get another integer solution in an iterative manner. Computational results having up to 1,000 0-1 variables show better performance of the column subtraction method solving the remained instances of SSP than complex branch and-bound algorithm by LINDO.
Key Words: Column Subtraction;Ship Scheduling Problem;Set Packing;Set Partitioning;Set Covering;Branch-and-Bound
TOOLS
METRICS Graph View
  • 417 View
  • 0 Download
Related articles

A Study on the Insolvency Prediction Model for Korean Shipping Companies2024 April;48(2)

A Study on the Policy for Introduction of WIG Craft into Coastal Passenger Service2012 December;36(10)

A Study on the Database Integration Methodology using XML2005 December;29(10)

A Study on the Roll Motion of a Ship in Transient Irregular Wave2004 June;28(5)

A Study on the Motion of a Single Point Moored Ship in Irregular Waves2003 March;27(1)

ABOUT
BROWSE ARTICLES
FOR CONTRIBUTORS
Editorial Office
C1-327 Korea Maritime and Ocean University
727 Taejong-ro, Youngdo-gu, Busan 49112, Korea
Tel: +82-51-410-4127    Fax: +82-51-404-5993    E-mail: jkinpr@kmou.ac.kr                

Copyright © 2024 by Korean Institute of Navigation and Port Research.

Developed in M2PI

Close layer
prev next