Skip to content
All projects

CESI · 3rd year

OptiMap

Computing a near-optimal delivery route on a given map.

CompletedMay 2024 – Jun 2024
OptiMap

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

  1. 1Mathematical modelling: a graph whose vertices are cities and whose edges are roads
  2. 2Study of the complexity of the problem and of the algorithms that solve it
  3. 3Implementation of six approaches: ant colony, genetic, simulated annealing, tabu search, particle swarm, TSP heuristic
  4. 4Performance measurement (running time and route length) and comparison
Algorithm ranking for 15, 100 and 500 cities
Algorithm ranking for 15, 100 and 500 cities

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.