Branch-and-cut-and-price Methods For Logistics Problems With Limited Risk

Date

2007-08-23T01:56:53Z

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Industrial & Manufacturing Engineering

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.

Description

Keywords

Citation