Customer clustering to solve very large-scale VRPs

Question

I am looking for references that used customer aggregation to solve large-scale Vehicle Routing Problems. By aggregation, I mean clustering the customers together and representing them with one node in the network. I found some related studies but they are not exactly what I am looking for.

1- I am aware of cluster-first route-second methods to solve the VRP however, these approaches normally cluster the customers to be visited by one vehicle and then solve a TSP for each cluster. What I want is the cases that the vehicle's capacity is enough to visit multiple clusters and a VRP should be solved after the clustering.

2- Clustered vehicle routing problem (CLuVRP), in which customers are grouped into predefined clusters, and all customers in a cluster must be served consecutively by the same vehicle. This is the closest problem to what I am looking for except that I aim to use clustering to scale down the problem search space and most proposed approaches for CLuVRP won't do that.

3- Districting for VRP, these types of studies focus on building the districts (clusters) not the routing decisions or questions such as how to calculate the parameters (e.g. distances and time windows for an aggregated network), how to find the actual sequence of the customers after finding the sequence of clusters.

4- I only was able to found two studies by A. Campbell that use customer clustering to reduce the size of VRP.
- "Aggregation for the probabilistic traveling salesman problem"
- "Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines"

Surprisingly, I couldn't find more references on this. If you know any relevant sources I would be grateful if you could share them.

Answer 1

You can check the following papers:

1. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. From the abstract:

   Phase I aims to identifying a set of cost-effective feasible clusters while Phase II assigns clusters to vehicles and sequences them on each tour by using the cluster-based MILP formulation. Ordering nodes within clusters and scheduling vehicle arrival times at customer locations for each tour through solving a small MILP model is finally performed at Phase III.

You can see in their figures that they touch on your question, i.e. a vehicle visits multiple clusters.

Note that I got the image below from the version available on academia.edu

2. Modelling and solution of a large-scale vehicle routing problem at GE appliances & lighting. (Disclaimer: I'm one of the authors). The figure below, which is the network illustration, shows that the nodes (small circles) are divided into macro-nodes (the outermost circles) and inside of them, are clusters (the dotted circles). A vehicle can go from one cluster to another and from one macro-node to another.

Answer 2

You might find some interesting points in the following two papers

1. C. Walshaw, 2002, A Multilevel Approach to the Travelling Salesman Problem, Operations Research, Vol. 50, nr. 5, pages 862-877. In this paper they present a method which first simplifies the problem by aggregating customers until you have a very simple graph. After the simplification phase, the method alternates between a refinement step and an "unpacking" step. The refinement phase improves the route found on the simplified graph while the unpacking step expands the simple to a slightly more complex one. This procedure continues until one has created a solution to the original problem.
2. J. Oppen and A. Løkketangen, 2006, "Arc routing in a node routing environment", Computers & operations research, Vol. 33, nr. 4, pages 1033--1055. In this paper aggregation on 4 different "levels" is discussed for the stringed VRP.

Maybe these papers or references therein can point in a helpful direction.

Answer 3

We (Thibaut Vidal, Daniele Vigo, Michael Schneider, and I) just released a preprint on decomposition methods for Vehicle Routing heuristics.

Clustering is one such family of methods and we try different types of clustering in our computational experiments. Indeed, it works very well, as long as:

• The clusters are based on some existing high-quality solution. In other words, clustering based on routes works much better than clustering based on geographical distance.
• The cluster size is not too large (or the sub-problem optimising the routes visiting the cluster's customers is almost as hard as the original problem) nor too small (or the sub-problem is too trivial).