Transportation problem with nonlinear side constraints: A branch and bound approach

Transportation problem with nonlinear side constraints: A branch and bound approach

0.00 Avg rating0 Votes
Article ID: iaor19921814
Country: Germany
Volume: 36
Start Page Number: 185
End Page Number: 197
Publication Date: Feb 1992
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors:
Keywords: programming: critical path, programming: branch and bound
Abstract:

In a container terminal management, the following problem frequently arises: how to assign a reasonable depositing position for an arriving container, so that the efficiency of searching for and loading of a container later can be increased. In this paper, the problem is modeled as a transportation problem with nonlinear side constraints (TPNSC). The reason of nonlinear side constraints arising is that some kinds of containers cannot be stacked in the same row (the space of storage yard is properly divided into several rows). A branch and bound algorithm is designed to solve this problem. The algorithm is based on the idea of using disjunctive arcs (branches) for resolving conflicts that are created whenever some conflicting kinds of containers are deposited in the same row. During the branch and bound, the candidate problems are transformed into classical transportation problems, so that the efficient transportation algorithm can be applied, at the same time the reoptimization technique is employed during the branch and bound. Further, a heuristic is designed to obtain a feasible initial solution for TPNSC in order to prune some candidates as early and/or as much as possible. Computational results on randomly generated problems are reported.

Reviews

Required fields are marked *. Your email address will not be published.