FEUP · Artificial Intelligence · 2024
Delivery Route Optimisation
Comparing metaheuristics on a delivery problem with fragile and urgent packages.
Source code (opens in a new tab)No public deployment
The problem
One vehicle must deliver a set of packages. Fragile packages can break with distance travelled, urgent packages are penalised per minute late, and every kilometre has a cost. The goal is the delivery order with the lowest total cost.
What was built
- Solutions encoded as a permutation of delivery locations, with a cost function combining travel cost, expected breakage and lateness penalties.
- Implemented hill climbing, simulated annealing, tabu search and a genetic algorithm, plus a greedy baseline, behind a configurable menu.
- Compared the algorithms on solution cost and execution time.
My role
Group project for the Artificial Intelligence course.
Technologies
- Java
- Simulated annealing
- Genetic algorithms
- Tabu search
- Hill climbing