Vehicle routing using google maps api

I am currently developing a piece of software that solves the vehicle routing problem using the Google Maps Javascript API v3 .

The task is as follows:

• I have several cars around the city.
• I have many destinations around the city.
• The number of destinations is greater than the number of available vehicles
• I need to calculate the optimal routes through several points for each vehicle in order to minimize the average transport time.

My naive approach is this:

• find nearest points for each vehicle using k-value clustering with raw Euclidean distance between map points (LngLat points)
• for each vehicle, for each destination from the set of nearest vehicle destinations, the optimal routes are calculated using the other destinations as intermediate points and using the option optimize:true
  
  and routes with the shortest average transport time are calculated

It appears that this approach may produce results that are not optimal.

Is there a better approach that provides better accuracy and / or fewer API requests.