Greedy Algorithm for BAP Partitioning
(Due: 20 March 2007)
In this assignment, the goal is to implement a greedy algorithm for solving the BAP partitioning problem described in the lectures. 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).
In this assignment, you implement a simple greedy algorithm for solving BAP Partitioning, and test them out on various data sets. Each student will be assigned a greedy algorithm to implement. The description of the greedy algorithm and your assigned one can be found here.
Details of the BAP Partitioning Problem.
Details of the datasets to be used for testing your greedy algorithm. These data sets were randomly generated, although many of the parameters were based upon data that closely match real port situations.
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.
You will need to implement the greedy algorithm assigned to you. Then compile the BAP with your greedy algorithm and then test them on all the datasets given to you. (You need to print out the value of the objective function obtained by your algorithm.)
Then you should write a report that should have (at least) the following sections:
| No: | Section Name | Description |
| Problem Statement | Explain the BAP partitioning problem. | |
| Your Greedy Algorithm | Explain in one or two paragraph your greedy algorithm and how you implemented it. | |
| Complexity Analysis | Analyse the time complexity of your algorithm. | |
| Result and Observations |
Results obtained by your greedy algorithm,
observations, if any, and recommendations for better approaches. |
After you are done with programming your greedy heuristic, running it with the given test data, and doing the report, please put your report in a separate folder under the BAPS called "Report". Please also include a README-[name].txt (with "[name]" replaced by your name, example README-LeongHW.txt) that list the changes you made: namely, filename, and short description of changes you made to that file.
Then zip the whole BAPS folder and submit it to the workbin called "LEDA Assign 2 -- BAP Greedy Partitioning".