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. |
|
| 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 |
|
|
| Pre-cluster followed by a TSP | Pre-cluster stops and use a TSP to route each vehicle. |
|
|
| 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. |
|
|
| Pre-cluster followed by a VRP using stop groups | Pre-cluster stops and use a VRP with stop groups matching stops to their 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.