CSE 643 Sec A
Homework Assignment 1:
Container Loading Problem using AI Search
Problem Description
You are tasked with modeling and solving a container loading problem for a ship departing from a
port. Containers are stored in a yard and need to be loaded onto the ship under the following
constraints:
1. Destination constraint: Containers must be arranged so that those to be unloaded at earlier
destinations are, as far as possible, not blocked by containers destined for later ports. (Include
your assumptions on how this is modelled, e.g, destination order as integers.)
2. Balance constraint: The ship must not become too imbalanced; heavy loads must not
accumulate excessively on one side. (Include your assumptions on how this will be handled.)
The goal is to nd a loading plan that respects these constraints and optimizes an objective
function that minimizes yard-to-ship loading time and unloading time at each destination while
maintaining acceptable levels of imbalance on the ship.
Tasks
1. Model the Problem
- De ne the formal problem representation (states, actions, constraints).
- Specify how an instance of the problem is described (input format: containers, weights,
destinations, yard con guration, ship layout).
- Clearly articulate the objective function you propose to optimize and (vs) constraints on feasible
solutions.
2. Design and Implement a Solution
- Choose a search algorithm (e.g., A*, heuristic search, simulated annealing, etc.).
- Be creative: use algorithms beyond those covered in class, but e.g. in the prescribed book(s).
- Code an environment for the container problem as well as the algorithms chosen.
- Demonstrate the algorithm on at least one non-trivial example instance.
- Analyse the problem and solution approach by testing on increasingly larger random instances.
3. Presentation & Video Explanation
- Prepare a presentation deck (5–8 slides) summarizing:
- Problem formulation
- Input representation
- Objective function
- Assumptions being made (IMPORTANT)
- Algorithm choice, data structures used, and justi cation.
-Results and analysis: e.g. how does the actual running time grow with size, impact of heuristics,
quality of solutions obtained etc.?
Submission
- Upload your CODE and PDF deck on ICAPP, and present it to the AI grader, answering
questions as you present.
Be sure to give breaks so that questions are asked and answered.
IMPORTANT:
(Be sure to RECORD a video (5–7 minutes) of the submission. The platform does NOT do this
yet, you need to record your screen and using a tool of your choice, upload it to a shared location
and save the link on the platform via the ‘save video link’ button that will show up once you have
ended your presentation by pressing the end button.)
fi
fi
fi
fi