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

Question

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.

Answer 1

As per the comment of @Pedrinho, your clustering approach has a problem. A vehicle route is an ordered sequence of customers. A cluster-first-route-second approach splits the problem of determining routes into 2 parts: (1) partitioning the customers into disjoint groups, s.t. every group can be assigned to a vehicle, (2) for customers that are grouped together, a route is determined. A major advantage of this approach is that step (2) can be accomplished for each vehicle independently, so the routing problem becomes relatively simple. A cluster-first-route-second approach works generally well for homogeneous vehicles, since every route can be executed by every vehicle, i.e. we don't need to assign routes to specific vehicles.

In case of heterogeneous vehicles, there's a problem. You could create clusters in such a way that every cluster can be assigned to every vehicle. This implies that the total demand of customers in a single cluster cannot exceed the capacity of the smallest vehicle. Essentially you create a lot of small routes, which you can then assign to all vehicles. The obvious downside is that a lot of the capacity of your larger vehicles will remain unused. If you go for this approach, you should implement an improvement heuristic as well.

I would recommend to read this book chapter, which gives an overview of several heuristics for the VRP with heterogeneous vehicles: Baldacci R., Battarra M., Vigo D. (2008) Routing a Heterogeneous Fleet of Vehicles. In: Golden B., Raghavan S., Wasil E. (eds) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, vol 43. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-77778-8_1

Instead of using a cluster-first-route-second approach, I would probably opt for a simple insertion heuristic: assign customers, one-by-one to your vehicles, always inserting in a way that your objective function increases the least. This will give you a feasible initial solution, which you can then improve with an improvement heuristic (e.g. LNS/VNS).