Algorithm for finding the shortest path through all vertices?

Question

Algorithms

The garbage truck must collect waste from all collection points and return to the garage from which it left. You need to find the shortest path through all given points. Can you please tell me which algorithm can be used? Is it possible to solve the problem using neural networks? Set the NA on the data we have. We have a history of visiting points by drivers. Accordingly, we can predict the route

Answer 1

I found the solution (approximately) using two approaches
1) Ant colony algorithm, quite a working solution https://www.baeldungtest.com/java-ant-colony-optim...
2) Use Google OR-Tools https://developers. google.com/optimization/routing/tsp
At first we managed to solve the problem using method 1, but now we use 2 in the working code

Answer 2

This is an NP-complete problem. With a sufficient number of garbage cans, it simply cannot be solved efficiently and quickly.
It is important to understand what kind of solution you need: good enough or optimal. It is possible that you simply do not have enough resources to find the optimal solution.
The optimal route is searched for by enumeration, sometimes with different optimizations, which, however, will not help much in an arbitrary case.
Suboptimal ones are searched for, for example, by genetic algorithms.
This problem is called the traveling salesman problem :

The traveling salesman problem belongs to the category of transcomputational ones: even with a relatively small number of cities (66 or more), it cannot be solved by the method of enumeration of options by any theoretically conceivable computers in a time less than several billion years.

Answer 3

All mapping services have a distance matrix API, this is exactly what you need.