HyFlex UAV Animal Feeding Problem

Project Overview

This repository provides a HyFlex-compatible implementation of the UAV Zoo Feeding Problem (UZF), an NP-hard combinatorial optimisation problem.
The problem is inspired by a zoo feeding scenario where a single UAV must feed animals located in different enclosures in the shortest possible time.

The UAV:

• Starts and ends at the food preparation area $(F_x, F_y)$.
• Must visit each enclosure exactly once.
• The objective is to minimise the total flight distance, defined as:

$$L(a_i, a_j) = \lceil \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \rceil$$

Implementation

Problem Domain

• UZFDomain (HyFlex ProblemDomain implementation).
• UAVInstanceReader for reading .uzf problem instances.
• UZFSolution and UZFInstance for solution representation and evaluation.
• Initialisation methods:
  • RANDOM: Random feasible solution.
  • CONSTRUCTIVE: Greedy nearest-neighbour solution.

Low-level Heuristics

• Mutation:
  • AdjacentSwap
  • Reinsertion
• Local Search:
  • NextDescent (hill climbing)
  • DavissHillClimbing (DBHC with swap operator)
• Crossover:
  • Partially Mapped Crossover (PMX)

Selection Hyper-heuristic

• Heuristic Selection: Roulette Wheel Selection (proportionate to heuristic performance).
• Move Acceptance: All Moves acceptance.
• Adaptive behaviour: Updates heuristic scores dynamically based on improvements.

How to Run

1. Prerequisites

• Java 11+
• HyFlex Framework JAR files:
  • chesc.jar
  • chesc-ps.jar

2. Compile the JAR Files

3. Run the Hyper-heuristic

cd src/com/aim/project/uzf/runners

4. Visualize the Results

cd src/com/aim/project/uzf/visualiser

Evaluation

• Instances: square.uzf, libraries-15.uzf, carparks-40.uzf, tramstops-85.uzf, grid.uzf, clustered-enclosures.uzf, chatgpt-instance-100-enclosures.uzf
• Runtime control: 60 nominal seconds per run (HyFlex timing).
• Repetitions: 5 runs per instance.

Additional Information

• Project related information can be found in hyper heuristics lab sheet and project sheet.
• Framework API document
• HyFlex tutorial worksheet