FedEx ULD Packing Optimization

This repository contains Team 83's solution for the FedEx problem statement at Inter-IIT Tech Meet 13.0.

The task was a constrained 3D packing and assignment problem: place packages inside air cargo ULDs while respecting geometry and weight limits, ensure that every priority package is loaded, and minimize the combined cost of delayed economy packages and the spread penalty for priority shipments.

The codebase reflects the approach we submitted during the competition. Alongside a runnable implementation, it also captures the progression of our thinking from a simple greedy baseline to preference-driven heuristics and a fragment-tree-based packing strategy.

Problem Overview

For a given set of ULDs and packages, the solver must decide:

• which package should be assigned to which ULD
• where that package should be placed inside the ULD
• which of the six axis-aligned orientations should be used

A valid solution must satisfy three hard constraints:

1. The total packed weight in a ULD cannot exceed its weight limit.
2. Every priority package must be packed.
3. Packed packages must fit inside the ULD without overlap.

The optimization objective is to minimize total cost:

• delay cost of economy packages left unpacked
• spread cost incurred for each ULD that contains at least one priority package

In the competition setting, this made the problem a practical mix of 3D bin packing, constrained assignment, and heuristic search.

Our Approach

1. Baseline Greedy Packing

The initial approach tracks available empty cuboids inside each ULD and places packages greedily whenever a feasible space is found. This gave us a simple working baseline, but it was limited by how many free spaces needed to be updated and searched after every placement.

2. Preference-Driven Heuristics

We then separated packages into priority and economy sets.

Priority packages are packed first so that the hard feasibility requirement is respected. Economy packages are packed afterwards to reduce overall delay cost using the remaining capacity.

To improve packing quality, we experimented with ordering heuristics such as:

• package volume
• delay cost per unit volume
• delay cost per unit weight
• remaining free volume in each ULD
• remaining weight capacity in each ULD

The Preference solver in this repository implements that idea. In practice, it became the fastest strong baseline in our experiments.

3. Fragment Tree for Free Space Management

A major bottleneck in the baseline method was searching and updating free spaces stored in simple lists. To address that, we designed a fragment-tree representation where each node corresponds to an empty cuboid, and placing a package fragments that node into smaller child spaces.

This structure preserves spatial locality and makes it easier to prune infeasible regions during search. It also reduces unnecessary traversal when a subtree cannot possibly fit a package.

The Tree solver is the implementation of this idea.

4. Tree Plus Preference Hybrid

Our final direction combined tree-based free-space management with preference-driven package selection.

According to our report, this hybrid approach produced the best overall packing quality on the competition dataset, packing more packages at a lower total cost than the simpler heuristics, although it required more computation time.

The repository also contains an experimental MixedTree solver. It was part of our exploration, but the implementation is incomplete and currently unreliable for larger instances.

Packing Policies Explored

Beyond package and ULD ordering, we evaluated several policies for selecting candidate spaces and orientations.

Space selection policies included:

• first_find
• origin_bias
• min_length_sum
• min_surface_area
• max_surface_area
• min_volume
• max_volume

Orientation policies included:

• no_rot
• first_find
• min_volume

These policy combinations affected all three of the outcomes we cared about: number of packed packages, total cost, and runtime.

Results Summary

The final report compared multiple heuristics on the provided dataset.

Packing Mode	Packages Packed	Cost	Time (s)
Preference	212	32719	0.295
Normal Tree	189	45818	1.34
Preferential Tree	226	31169	4.95

A separate policy sweep on economy-package packing also showed that changing space and orientation policies noticeably shifts the tradeoff between packing quality and compute time.

We also used a smaller Gurobi-based verification setup to reason about the priority-package placement. As documented in the report, that analysis indicated that the provided priority packages could be packed within three ULDs, which aligned with the direction we used in our heuristics.

Repository Structure

.
├── input/                  # Sample inputs and data generation scripts
├── output/                 # Generated outputs
├── src/
│   ├── dataclass/          # Package and ULD data models
│   ├── helpers/            # Plotting and visualization utilities
│   ├── solvers/            # Packing heuristics and tree structures
│   └── main.py             # Entry point
├── run.sh                  # Recommended execution script
└── requirements.txt        # Python dependencies

Running the Project

Prerequisites

• Python 3.10 or newer
• the dependencies listed in requirements.txt

Install dependencies with:

pip install -r requirements.txt

Recommended Command

./run.sh <solver-type> <uld-file> <package-file> <output-dir>

Example:

./run.sh Preference input/ulds.csv input/packages.csv output/

If needed, you can run the entry point directly:

python3 src/main.py Preference input/ulds.csv input/packages.csv output/

Solver Options

• Preference: preference-based heuristic and the best quick option in this codebase
• Tree: fragment-tree-based packing approach
• BasicOverlap: baseline overlap-aware free-space tracking
• BasicNonOverlap: alternate baseline variant
• MixedTree: experimental and currently buggy

Input Format

The solver expects two CSV files.

ULD file columns:

ULD Identifier,Length (cm),Width (cm),Height (cm),Weight Limit (kg)

Package file columns:

Package Identifier,Length (cm),Width (cm),Height (cm),Weight (kg),Type (P/E),Cost of Delay

Sample files are available in the input/ directory.

Output Format

The main output file is written to output/output.txt.

The first line contains:

<total_cost>,<packed_package_count>,<number_of_priority_uld_used>

Each following line contains either a placement or an unpacked marker:

<package_id>,<uld_id>,x1,y1,z1,x2,y2,z2
<package_id>,NONE,-1,-1,-1,-1,-1,-1

The code also generates per-ULD PNG visualizations in the output directory. In addition, the current pipeline opens interactive PyVista windows for 3D inspection when run in an environment with display support.

Notes on the Codebase

This repository is a competition submission, not a production logistics system. The focus was on finding strong heuristics quickly under time constraints, which is why the code includes multiple solver variants, ablation paths, and some experimental branches.

That said, the core ideas are representative of the work we did: cost-aware prioritization, spatial reasoning for 3D packing, and custom data structures for improving search efficiency.

Competition Context

This project was built for the FedEx problem statement at Inter-IIT Tech Meet 13.0, IIT Bombay.

A team of six from IIT Dharwad represented the institute for this event, and the final standing for this problem was 11th out of 23 IITs.