# Adapting a cluster-first-route-second approach for VRP with heterogenous fleet

I have the following data:

• A fixed depot/facility location
• Dropping points with demands
• List of available vehicles (heterogeneous fleets)

What I am trying to do is, given the list of vehicles and dropping points, particular serving time and travelling time how should the vehicles be assigned?

Progress so far:

With the help of capacitated clustering, I have already clustered the locations. I have considered both the geospatial proximity and the demand of each point, such that the total radius of the cluster doesn't exceed a given radius and maximum demand doesn't exceed the lowest serving demand of the available vehicle (which in this case is 700 kg).

Each of these clusters has a particular serving time which I have computed, and there is a travelling time to the center of the cluster which I can compute with osrm package in R. Each vehicle can be hired for a particular duration (E.g 12 hours)

Now, how to determine which clusters will be served by which vehicles given the time and capacity constraints? The cost associated is strictly a function of time, so if that can be optimized, then the total cost will be optimized too.

I am looking for some heuristics or a general approach to tackle the problem.

• If you have clustered the locations, then you implicitly already assigned one vehicle to it. Or am I missing something? Commented Sep 27, 2021 at 13:03
• @Pedrinho I can sense why you might be saying that but no. Suppose we have 3 clusters with 700 kgs of demand. Two vehicles with 1500, 700 capacities. Now which vehicles will serve which clusters? This was a small example. Now imagine, the same with 100+ clusters and 20+ vehicles. That's something I am looking at. Commented Sep 27, 2021 at 15:09
• @Shibaprasadb, based on what you mentioned, besides the clustering algorithm, you will need to use an assignment method to calculate the required capacity of the demand points and assigning them to the available capacity (in this case vehicles) based on some limitations like time window, pickup/delivery, etc. Maybe applying something like a bin-packing or GAP algorithm for each cluster be interested. Is it what you are looking for? Commented Sep 27, 2021 at 21:06
• Yes @A.Omidi! Something on the line of that. I will look for it. Thanks. Commented Sep 28, 2021 at 5:08