I need to optimize routes to visit 7,000 points (~700 routes).
Should I calculate a Distance Matrix of size 7000 X 7000 = 49,000,000 options? That means I would receive a Google invoice of ~0.005*49M = $245,000.
-
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.– Community BotCommented Jan 31 at 6:24
Add a comment
|
1 Answer
No, you shouldn't do that. Not only because of the monetary cost, but because it's a well-known NP-hard optimisation problem, that of the traveling salesman. You should instead use an optimisation algorithm to find a "good enough" solution, rather than to brute force all the possible routes.
-
Thanks, but what does it mean practically? Distance Matrix is the basic object for any VRP, so how can I get "good enough" solution without it? Commented Jan 30 at 7:07
-
@ZetesILDev see the WIkipedia page I linked. There are a few algorithms in there. This is a (very) well known problem, thus a short internet search would yield results as well.– AdriaanCommented Jan 31 at 6:16
-
For such big a matrix you may want to try the (relatively new Route Optimization API at developers.google.com/maps/documentation/route-optimization– miguevCommented Mar 13 at 13:43