The BAP Partitioning Challenge
(Due: 4th November 2002)
The aim of this project is to use LEDA to solve a practical algorithmic problem. In this project, you will be solving a sub-problem of the Berth Allocation Problem (BAP). The BAP is an optimization problem that arises from operations in large transshipment ports such as PSA, Singapore.
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).
This project is to implement algorithms for BAP Partitioning, and test them out on various data sets. This project is modelled after various DIMACS Challenges, where researchers are invited to implement algorithms to solve specific problems. (Past DIMACS challenge problems include matching, network flows, graph colouring, maximum clique, satisfiability, TSP, etc).
In this BAP Partitioning Challenge, the "challenge" is to do as well as possible on the BAP Partitioning Problem, which is known to be NP-complete. So, the twin sub-goals of the challenge are to come up with good heuristic algorithms on large instances, and to solve smaller instances exactly with a branch and bound algorithm. As far as I know, BAP partitioning is isn't a well studied problem, so there should be a chance to publish if you get really good results and to prove some interesting theorems as well.
Here are details of the BAP Partitioning Problem.
An important aspect of the DIMACS Challenges is a publically available set of problem instances which made it possible to directly compare results. Likewise, the probem instances for the BAP Partitioning Challenge are made available in the course web-site. The data sets were randomly generated, although many of the parameters were based upon data that closely match real port situations.
The results of the BAP Challenge are given in the BAP Challenge Website.
What you are expected to to do for your project and what you have to hand in (submit).
Details on deadlines, milestones, submission, and so on.