Solving Capacitated VRP with multiple various sized vehicles

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.