All projects
CESI · 3rd year
OptiMap
Computing a near-optimal delivery route on a given map.
CompletedMay 2024 – Jun 2024

Build an application that finds one of the best delivery routes on a given map. Since the problem is very close to the travelling salesman problem, we started from its solving methods.
Approach
- 1Mathematical modelling: a graph whose vertices are cities and whose edges are roads
- 2Study of the complexity of the problem and of the algorithms that solve it
- 3Implementation of six approaches: ant colony, genetic, simulated annealing, tabu search, particle swarm, TSP heuristic
- 4Performance measurement (running time and route length) and comparison

Conclusion: no algorithm wins everywhere, so the application picks the best fit for the map size and the user’s preferences. In front of the jury we suggested further work: several vehicles on one route, simple A-to-B routing, and route history.