TODO: Route Optimization

Create a route optimization method that calculates the shortest path given a beginning, ending and indefinite amount of intermediate points. This method should reorganize all intermediate points so that the path trajectory path is the shortest possible.

Steps to implement:

[ ] Button in front-end for user to optimize trajectory.
[ ] When clicked, front-end sends all points of the trajectory, with the given distances between them, to the back-end.
[x] Back-end, using chosen algorithm, calculates shortest path and sends back the new order of points to front-end.
[ ] Front-end reorganizes points and calculates new trajectory.

Note: Points = Places

Algorithms/Heuristics to consider:

Traveling Salesman Problem (TSP)
- Advantages: Optimal and almost perfect use-case (there is no need to return to starting point)
- Disadvantages: Computationally intensive
Dijkstra’s Algorithm
- Advantages: Optimal and simple
- Disadvantages: It does not take into account visiting all points
Nearest Neighbor
Simulated Annealing (SA)
Genetic Algorithms (GA)
Christofides Algorithm

Summary of Use Cases:

Dijkstra’s Algorithm: Ideal for shortest path between two points, not suited for multiple intermediate points.
TSP (Exact Algorithm): Best for small datasets where you need the exact shortest path, but impractical for larger sets due to complexity.
Nearest Neighbor: Quick and simple for small datasets, but suboptimal for larger or more complex problems.
Simulated Annealing: Suitable for medium to large datasets where you need a good approximation and can’t afford getting stuck in local optima.
Genetic Algorithms: Flexible and capable for large datasets with complex constraints, but more complex to set up.
Christofides Algorithm: Best for medium-sized datasets, offering a good balance between accuracy and computational efficiency.

t0m4s79 / DREFleet

TODO: Route Optimization #71