Leong Hon Wai, School of Computing, National University of Singapore
UROP (Computing) Projects for 1999/2000
(Leong Hon Wai, S16 05-05 & S15-04-16)

Important Notice: Please first read general information from my Student Projects Page.

Supervisor:     leonghw
Student:        
Project Title:  Study of Algorithms for Multi Knapsack Problem
Course:         CS2288 or CS3288 
Description:    

In this project, we study various algorithms for
solving the multi knapsack problem. The multi knapsack problem
is a generalization of the well known knapsack problem.
We will first study well known algorithms for solving the
problem and do a comparison of them. (Many of these implementations
are already available.) Then the project will pursue generalization
of these algorithms for solving practical problems such as
one dimensional cut-stock problems.



Supervisor:     leonghw
Student:
Project Title:  Customizing iRAS for Advertisement Layout System
Course:         CS2288 or CS3288
Description:    
In this project, we enhance an existing system iRAS
(Interactive Rectangle pAcking System) and customize it for the
purpose of newpaper advertisement layout design. 
The existing system, iRAS, is an incremental rectangle package
(by Ku Liang Ping) written in C on Unix that implements an efficient
incremental packing algorithm with animation features.
In particular, some of the enhancements/customisations are: 
  (i) to port the interface to Java or Tcl/Tk for platform independence,
 (ii) to fine tune the automatic packing feature of the system to
         customise it for newspaper advertisement packing, and 
(iii) (maybe) to upgrade (or rewrite) the animation engine.



Supervisor:     leonghw
Student:        nisharah
Project Title:  Re-Assignment Algorithms for iBAPS
Course:         CS3288
Description:    

iBAPS - Interactive Berth Allocation Planning System -- is the
interactive sub-system of the BAPS that handles dynamic re-assignment of
berths to vessels in a container port. We assume that the iBAPS system
maintains a current assignment of berths to vessels for the next
operation time period (say a day). These includes information on the
length of the vessel, the arrival time, the length of stay of the vessel
and so on.  The iBAPS system receives (on the fly) requests for changes
in the assignment and has to service these requests.

This UROP project aims to enhance the existing iBAPS system by
incorporating a module for the system that can handle the problem
of "bumping out" other assigned vessels to make room for
the current vessel. Extensive experimental studies will also be
carried out on the performance of the various reassignment algorithms. 

   Project WebPage



Supervisor:     leonghw
Student:        trantuan
Project Title:  Vehicle Routing with Scheduling 1
Course:         CS2288 or CS3288
Description:    

In the vehicle routing problem, we are given a set of given clients request 
for services at various locations around Singapore (and possibly the time
window for the service to be done).  The problem is to plan a series of service
routes for its service personnels to "cover" all the requested services around
the island.  The objective consists of multiple criteria including minimizing the
number of service routes, the sum of the travel distances, the travel time, etc.
The objective of this project is to study this problem, select a suitable
sub-problem to solve, and propose an algorithmic solution to the sub-problem.
A prototype will also have to be developed as proof of concept.


See links in Tim Duncan's Page on Vehicle Routing
from Michael Trick's OR Page



Supervisor:     leonghw
Student:        liujian1
Project Title:  Vehicle Routing with Scheduling 2
Course:         CS2288 or CS3288
Description:    

In the vehicle routing problem, we are given a set of given clients request 
for services at various locations around Singapore (and possibly the time
window for the service to be done).  The problem is to plan a series of service
routes for its service personnels to "cover" all the requested services around
the island.  The objective consists of multiple criteria including 
minimizing the number of service routes, the sum of the travel distances,
the travel time, etc.
In this research, we first study this problem, and propose a system for
solving vehicle routing with scheduling. There will be two UROP projects
that will study different sub-problems and propose algorithmic solutions
to these sub-problems. For each project, a prototype will also
have to be developed as proof of concept.



Supervisor:     leonghw
Student:        ouyongji
Project Title:  Efficient Network Clustering
Course:         CS2288 or CS3288 
Description:    

In this project, we want to find efficient network clusters that 
optimizes load distribution yet minimize interconnecion cost. 
We first study this issue in relation to centralized networks of
terminals and then extend the results to other networks.
In a previous project, some algorithms have been implemented for
this problem. In this project, the aim is to enhance the project
by (a) implementing a problem instance generator, (b) doing a more
careful study of performance evaluation of the current implemented
algorithms, and (c) study and implement more algorithms for solving
the problem.