5
$\begingroup$

I am looking to form a Capacitated VRP problem like this:

  • I have 40,000 dropping locations with Demands of each point available
  • I have 5-6 types of vehicles available with different capacities and costs
  • I know the cost of travelling from one point to another for all the vehicles
  • A single Hub is considered here

My goal here is to select the combinations of vehicles, such that the total cost is minimized.

What are some heuristics I can apply here? As I am trying to model it in R, I am trying to avoid MIP model because it might take too much time.

I have searched different works of literature but couldn't find anything appropriate. So any help in this would mean a lot!

$\endgroup$
3
  • $\begingroup$ 40 000 locations is a lot. What's the order of magnitude of the computation time that you expect? $\endgroup$
    – fontanf
    Aug 5 at 16:02
  • $\begingroup$ Anything in the range of ~30 mins is fine at this moment. @fontanf $\endgroup$ Aug 5 at 16:33
  • 1
    $\begingroup$ Your main issue is problem size. We have a commercial optimiser (ODL Live) which solves this kind of problem, and solves larger problems than most optimisers, but even we don't currently recommend running problems larger than 10,000 jobs, and you need a solver for 40,000 jobs. At this scale even working out a travel matrix using road networks becomes problematic. As others have said, you need to cluster first. Before looking at clustering though, see if there's a natural problem split which makes sense - e.g. split either side of a major river, by state, by company management structure etc. $\endgroup$ Aug 6 at 1:58
5
$\begingroup$

You could cluster 40,000 dropping locations (by grouping them based on location/vehicle type need) to some reasonable number and can try to implement metaheuristics like Simulated annealing, Particle swarm etc. . Though they won't guarantee optimality but can tune accordingly to achieve desired solution quality.

$\endgroup$
5
  • $\begingroup$ +1 for suggesting clustering. This approach is generally called cluster-first route-second. It would be great if you could add more details to improve your answer. For example, mentioning $k$-means clustering (or any other clustering approach that you would consider) as well as the related R packages in your answer would be helpful to the OP (original poster). $\endgroup$
    – rasul
    Aug 5 at 22:07
  • $\begingroup$ Hi! Thanks for the help. Yes, I tried Clustering. Specially K-means. I got the idea from the cluster first route second approach as @r.beigi suggested. The problem I have is the clusters have demand which varies a lot and it is very right-skewed. Like this: imgur.com/7qyTPrb $\endgroup$ Aug 6 at 5:24
  • 1
    $\begingroup$ @stat_shib What is the number of clusters? the size of each cluster (how many demand points in each cluster)? the total demand in each cluster? the number of vehicles of each type? the capacity of each vehicle? the vector for each demand point that is used for clustering, i.e., is it just the $x$,$y$ coordinates, or it includes other features too (don't forget feature scaling if the latter is the case)? $\endgroup$
    – rasul
    Aug 6 at 7:24
  • $\begingroup$ @stat_shib You should try various heuristics based on the answers to the questions above and choose the one that works best in your special case. For example, you could set the number of clusters to the number of vehicles you have! IF you are lucky, i.e., a feasible allocation of vehicles to the clusters exist, then this simply leads to a solution (you just need to solve a TSP for each cluster)! $\endgroup$
    – rasul
    Aug 6 at 7:27
  • $\begingroup$ @r.beigi I did K-means with 200 clusters. The size and total demand of each cluster are different because the clustering is only done based on their longitude and latitude. Probably I will need to add more constraints like the total demand of each cluster with some constrained clustering. Probably you're right. I can do that and it can be a good starting solution I think. $\endgroup$ Aug 6 at 9:03
4
$\begingroup$

I'm not an expert in Vehicle Routing Problems, maybe someone else will have something more relevant to propose.

I think that a good starting point is this article:

"Efficiently solving very large-scale routing problems" (Arnold et al., 2019) DOI PDF

This paper is not exactly about your problem, but about the Capacitated Vehicle Routing Problem (CVRP), which is a simplified version of your problem.

However, they solve instances with up to 30000 locations, which is not far from your target, and, in Section 4.1, they describe how to adapt the classical Clark and Wright heuristic to large scale CVRPs and their experiments show that it can find pretty good solutions quickly (6% gap on average). In addition, it should be rather easy to implement.

Now the question is, how to adapt this heuristic to your variant? I don't see an obvious way and I am not aware of something similar in the literature about the Heterogeneous Fleet Vehicle Routing Problems. A simple approach would be to run the heuristic with only the vehicle type with the highest capacity, and after, try to change the vehicle type of each route for a cheaper one

Note that an implementation in R will likely be slower, you might expect a factor 10 compared to the computation times from the papers

EDIT

The answers about cluster-first route-second approaches reminded me of another relevant approach, route-first cluster-second, as described in this article:

"Route first—Cluster second methods for vehicle routing" (Beasley, 1983) DOI PDF

The idea is to first solve a Travelling Salesman Problem with all nodes to get a giant tour, and then to partition this giant tour into routes by dynamic programming. The author discusses how to adapt it to the case of an heterogenous fleet at the end of the article.

However, for a instance with 40000 locations, this requires to have a well optimized algorithm to solve the Travelling Salesman subproblem

$\endgroup$
1
3
$\begingroup$

I'm assuming in what follows that all demands must be met.

R has a very good genetic algorithm package ("GA") that includes support for permutation chromosomes. Assuming $n$ destinations and $m$ vehicles (not vehicle types, but actual vehicles), you can use a GA with each chromosome a permutation of $1, \dots, n + m$. To decode a chromosome, use the first $m$ values to permute the list of vehicles and the remaining $n$ values to permute the list of destinations. Then assign each destination, in the permuted order, to the first vehicle (in the permuted order) that has remaining capacity sufficient to hold it. The fitness function will be the total cost of the solution.

There's an implicit assumption here that your vehicle fleet has enough capacity (and individual demands are small enough relative to a vehicle's capacity) that any permutation decodes to a feasible solution. If that's not the case, one option is to allow the decoded solution to leave some demand unsatisfied and add to the fitness function a penalty for unmet demand. Another would be to just set the cost to Inf (or something really big if the GA package chokes on Inf) if the chromosome cannot be decoded to a feasible solution.

You might also want to explore the option in the GA package to do local search to try to improve a solution. The extra computation time per generation might or might not pay for itself.

One more variation that might or might not work better. Rather than filling up vehicles (which would make it hard if not impossible to find a solution with level loads), it might be better to rotate through the permuted vehicle list. So each destination other than the first, gets assigned to the first vehicle with adequate capacity after the one that took the previous destination, cycling back to the top of the list as needed.

$\endgroup$
1
  • 1
    $\begingroup$ +1 for suggesting a complete solution algorithm in R! $\endgroup$
    – rasul
    Aug 5 at 22:18
1
$\begingroup$

The question is in itself incomplete as the number of depots is not mentioned. Given that, the solutions become evident. Please correct the question.

Still, the solution is in breaking down the problem, yet, keeping it minimized is the challenging part. The only feasible approach is to create Primary and Secondary routing in which Primary is Pan-Country operations and Secondary is like Last-Mile Operations. And then apply the best of Graph Decomposition.

After that, completing it through Greedy approach in a graph based query mechanism .

However, heuristics/algorithm/AI based solvers would still keep the output sub-optimal. A complete zero-error Graph Decomposer is available with Neural Heights Private Limited. You can refer it here -

Linkedin profile of Neural Heights' founder

Mixing and matching the load volumes to get the exact number of vehicles needed is also part of the solution suite.

$\endgroup$
1
  • $\begingroup$ Thanks for the suggestion. I have edited it. Yes, it is based on one hub/depot. And in a part of one city. $\endgroup$ Aug 15 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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