How do I get more clustered routes?¶
A default routing solution might look like the image below. The routes span from the depot with stops along the way out and back. This solution minimizes route duration while avoiding unplanned stops. This plan may be acceptable for companies focused solely on efficiency, but often, companies must strike a balance between efficiency and driver satisfaction.
Drivers often prefer routes which may be less efficient, but more practical for them. The routes below are an alternative solution to those above, but may be preferable to drivers since they are driving out from the depot to a neighborhood before beginning to do their deliveries. They may prefer to drive a little further if it means they can consolidate their stops to a smaller region vs getting on/off at every exit to complete their route.
In order to encourage this behavior in your routing application, there are several options.
| Approach | Description | Pros | Cons |
|---|---|---|---|
| VRP with a cluster constraint | As the engine assigns stops to vehicles, the constraint limits assignment to vehicles whose centroid is closer to a stop cluster than other vehicles. | Hard constraint - no need to tune parameters. | Can result in unplanned stops in the solution. Can result in more vehicles being used in order to satisfy the hard constraint. |
| VRP with a cluster objective term | As the engine assigns stops to vehicles, the objective encourages assignment to vehicles whose centroid is closer to a stop cluster than other vehicles | Allows for a balance between cluster compactness and other KPIs. | Requires objective function tuning to select the right penalties to apply to each term. |
| Pre-cluster followed by a TSP | Pre-cluster stops and use a TSP to route each vehicle. | Hard constraint - no need to tune parameters. | Clusters may not be feasible with routing constraints and stops may be left unassigned. Clusters may not be full enough - resulting in too many vehicles being used. Prevents assignment to adjacent clusters. |
| Pre-cluster followed by a VRP using compatibility attributes | Pre-cluster stops and use a VRP with compatibility attributes matching stops and vehicles to their clusters. | Less restrictive and allows for more optionality than cluster → TSP. | Clusters may not be feasible with routing constraints and stops may be left unassigned. Prevents assignment to adjacent clusters. |
| Pre-cluster followed by a VRP using stop groups | Pre-cluster stops and use a VRP with stop groups matching stops to their clusters. | Less restrictive and allows for more optionality than cluster → TSP. Similar to compatibility attributes approach, but doesn't require pre-assignment to vehicles. |
Clusters may not be feasible with routing constraints and stops may be left unassigned. Prevents assignment to adjacent clusters. |
As input size scales, it may also be worthwhile to split your operations into strategic regions. We advise splitting into regions which are as “mutually exclusive” as can be. For example, if you never see vehicles going from the East side to the West side, you can safely split the region into “East” and “West” without sacrificing on solution quality. Splitting into regions can reduce the problem size to make it easier to solve and can also mitigate the risk of coming up against input file size limitations and matrix size limitations for map data.