The BAP Partitioning Problem

Informal Problem Statement

Very briefly, the BAP partitioning problem is to assign incoming vessels to a transshipment port to different sections of the port (for berthing) so as to minimize the cost of transshipment (which is the cost of container movement between vessels and between vessels and the port). The constraints on the assignment are that vessels must not "cross" two different sections and "there must be enough room to berth all the vessels assigned to any given section at any given time".

Problem Instances

An instance of the BAP Partitioning Problem is specified by

Input File Description
section file
 info on the sections: number of sections, section lengths, and intersection distances. (Note: section 0 is a virtual section.)
vessel file
 info on the vessels: number of vessels, vessel ids, lengths, arrival times, departure times. (Note: vessel 0 is a virtual vessel.)
transshipment file
 a list of container transshipments in the form
"source vessel" "destination vessel" "#containers".

In our simplified formulation, the arrival and departure times are given as integers in the range [0..W] where W is the length of the "planning window" for the problem.

BAP Partitioning Solutions

In BAP partitioning, we want to assign each vessel to a section (of the port). However, the assignment must satisfy some constraints. Therefore, we define:

A feasible BAP partitioning solution (or simply, a solution) consists of the assignment of each vessel to a section (of the port) that satisfies the following constraints:

  1. each vessels must be assigned to only one section,
  2. at any given time (during the planning window), the sum of the lengths of vessels occupying a given section must be less than the corresponding section length.

Note that in some problem instances, there may be no feasible solution.

The objective in BAP partitioning is to find a solution that

  1. minimizes first the number of unassigned vessels and then
  2. minimizes the total transshipment cost to move all the containers.
The transshipment cost measures the total cost of container movement for the problem.

For a more detailed explanation of these, please see the lecture notes and the MSc thesis by David Ong given in the References.

How to Deal with Unassigned Vessels

In cases when there are no feasible partitioning solution or when your partitioning algorithm fail to find a feasible section, some vessels will *have* to be left unassigned.

These unassigned vessels are assigned a section of -1. Note that, for the purpose of computing the transshipment cost, we assume that the unassigned vessels are put in a section that is "very far away" -- with distance of "infinity" from all other sections (including any other unassigned vessels). In this way, there is a high penalty (on the cost function) imposed by any unassigned vessel. (The real-life situation is "similar" -- the ship are left out at sea, meaning they are also very, very far away. ;-) Imposing the penalty also models the "price" we pay since the vessel has to be delayed from berthing immediately.)

For your implementations, please set "infinity=1000000".

Remarks on the BAP Partitioning Problem

The BAP Partitioning problem is a generalization of (a) the graph partitioning problem, and (b) the quadratic assignment problem. Both these problems are NP-complete, and so the BAP partitioning problem is also NP-complete. Thus, it is unlikely that you can find an algorithm that efficiently solves large instances. So it is natural to look for heuristic algorithms, which find good (but maybe not optimal vessel partitions). Another option is to implement an exponential algorithm, and use it to solve small instances of the problems.

References

BAP Partitioning Problem (Sept 2008)