Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. / Includes bibliographical references (p. 93-94). / One of the steps in stowage planning is crane split and sequencing, which determines the order of container discharging and loading jobs quay cranes (QCs) perform so that the completion time (or makespan) of ship operation is minimized. The vessel's load profile, number of bays and number of allocated QCs are known to port-planners hours before its arrival, and these are input parameters to the problem. The problem is modeled as a large-scale linear IP where the planning horizon is discretized into time intervals and at most one QC can be assigned to a bay at any period. We introduce clearance constraints, which prevent adjacent QCs from being positioned too close to one another, and yard congestion constraints, which prevent yard storage locations from being overly accessed at any time. This makes the model relevant in an industrial setting. We examine the case only a single ship arrives at port, and the case where multiple ships berth at different times in the planning horizon. The berth time of each ship and number of ships arriving is known. The problem is difficult to solve without any special technique applied. For the single-ship problem, a heuristic approach, which produces high-quality solutions, is developed. / (cont.) A branch-and-price method re-formulates the problem into a set-covering form with huge number of variables; standard variable branching provides optimal solutions very efficiently. For the multiple-ship problem, a solution strategy is developed combining Lagrangian relaxation, branch-and-price and heuristics. After relaxing the yard congestion constraints, the problem decomposes into smaller sub-problems, each involving one ship; the sub-problems are then re-formulated into a column generation form and solved using branch-and-price to obtain Lagrangian solutions and lower-bound values. Lagrangian multipliers are iteratively updated using the sub-gradient method. A primal heuristic detects and eliminates infeasibilities in the Lagrangian solutions which then become an upper bound to the optimal objective. Once the duality gap is sufficiently reduced, the sub-gradient routine is terminated. The availability of efficient commercial modeling software such as OPL Studio and CPLEX allows for larger instances of the problem to be tackled than previously possible. / by Shawn Choo. / S.M.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/39219 |
| Date | January 2006 |
| Creators | Choo, Shawn (Shawn Sheng Wen) |
| Contributors | David Simchi-Levi., Massachusetts Institute of Technology. Computation for Design and Optimization Program., Massachusetts Institute of Technology. Computation for Design and Optimization Program |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 94 p., application/pdf |
| Rights | M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission., http://dspace.mit.edu/handle/1721.1/7582 |
Page generated in 0.0028 seconds