2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ If you have clustered the locations, then you implicitly already assigned one vehicle to it. Or am I missing something? $\endgroup$
    – PeterD
    Sep 27, 2021 at 13:03
  • $\begingroup$ @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. $\endgroup$ Sep 27, 2021 at 15:09
  • 1
    $\begingroup$ @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? $\endgroup$
    – A.Omidi
    Sep 27, 2021 at 21:06
  • $\begingroup$ Yes @A.Omidi! Something on the line of that. I will look for it. Thanks. $\endgroup$ Sep 28, 2021 at 5:08

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ Thank you! Your answer makes few things very clear. I will try to assign the points with the nearest neighbor search and then improve them. Let's see how it goes. $\endgroup$ Sep 28, 2021 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.