Hee-Su Hwang

Graduation Semester and Year

2006

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Industrial Engineering

Department

Industrial and Manufacturing Systems Engineering

First Advisor

Jay M Rosenberger

Abstract

There exist many uncertainties in a logistics system, such as unknown demand, unsteady fuel cost, machine breakdowns, and accidents to name a few. Logistics management is difficult because logistics managers must solve a global optimization problem, which includes eliminating as much uncertainty as possible, finding effective methods of managing uncertainty, and operating the entire logistics system effectively. To cope with uncertainty, many efforts have been made for vehicle routing problems. On the contrary, traditional ship-scheduling models ignore uncertainty, even in highly volatile markets. We present a set-packing model that limits risk using a quadratic variance constraint. After generating first-order linear constraints to represent the variance constraint, we develop a branch-and-cut-and-price (delayed column and cut generation, DCCG) algorithm for medium-sized ship-scheduling problems. Computational results show that we can significantly limit standard deviation of the profit with a small expected profit reduction. We also present a lagrangian decomposition method in which the set-packing model with a quadratic constraint can be reformulated as the sum of two integer problems by introducing linking variables and constraints. We explore a lagrangian-based heuristic method and a simple rounding heuristic. The heuristic methods are applicable throughout the branch-and-bound tree and can substantially improve the DCCG algorithm. By incorporating heuristic methods with the DCCG algorithm, we can find very good solutions effectively and reduce the CPU time significantly. Computational results are provided, and extensions are discussed.

Disciplines

Engineering | Operations Research, Systems Engineering and Industrial Engineering

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS