The aim of the course project is to apply advanced algorithms and data structures to solve real problems. The problem chosen for this purpose is the BAP partitioning, a sub-problem of the Berth Allocation Planning (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 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 efficient and effective algorithms for BAP Partitioning, and verify the performance of your algorithm on various benchmark datasets. 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, shortest path, etc).
In this BAP Partitioning Challenge, the "challenge" is to do design the best possible algorithm for solving 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 hopefully solve smaller instances almost optimally.
As far as I know, BAP partitioning is isn't a very well-studied problem, so there should be a chance to get some good research results in this class project. I also hope that some of the good projects can be suitably extended after this class into research papers. I will give some relevant references that you may want to consider in the design of your own algorithms.
More details of the BAP partitioning problem can be found here.
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.
My research group (the RAS-Group, SoC, NUS) has developed a software prototype software system called BAPS that solves the BAP. The BAPS is developed in C++ and uses the LEDA software for some of its data structures. We have also extracted some key components and classes of the BAPS to be used for the case study in this project. It is provided here:
You will need to download the BAP source code, understand the code (with the help of the lecture notes). Read the BAP Package class since most of the functions/methods that you need should be found in there. You don't need to understand all the code in order to do your assignment. Pay more attention on the BAPTVPartitioner code since your own greedy algorithm will be based on it.
The concept of "time zones" is discussed in many BAP papers and can be found in Chapter 3.1.1 of David Ong's thesis. The link to the thesis can be found in the BAP description.
To help you achieve your project goal of implementing your best algorithm for BAP Partitioning, I have set three milestones for the project:
Give a brief report (call it BAP-M1-Rep-[your-name].doc/pdf/ps) on your greedy partitioner that includes a table of the results obtained. The table of results should contain at least, columns for the number of vessels unassigned, the transshipment cost, and the penalty cost. (An additional thing that you may want to do is to try to draw some conclusions (good, bad, or ugly) on your assigned greedy heuristic algorithm.) Put your report under a new directory called "Reports".
To submit your BAP M1 deliverables, please do the following:
No: | Section Name | Description |
Problem Statement | Explain the BAP partitioning problem. | |
Overview of Your Algorithm for M3 | Explain the general idea(s) behind your BAP partitioning algorithm for M3. Give possible reasons why you think it should give good results for BAP partitioning. | |
Details of Your Algorithm for M3 | Give the technical details of your algorithm here. Together with information on how you implemented it. Clearly state any parameters you have in your algorithm and describe briefly how you choose their values. | |
Complexity Analysis | Analyse the time complexity of your algorithm. | |
Result and Observations |
Results obtained by your M3 algorithm,
observations, if any, and recommendations for better approaches. |