Prioritize nearby visits with transition attributes

This example shows how to use transition attributes to prioritize routes where nearby pickups and deliveries are performed by the same vehicle in one time block. To learn more about transition attributes, see Model Business Logic with Transition Attributes.

In this example:

  • Deliveries of shipments A, B, and C are close to each other on the same road.
  • Additional deliveries are further down the road.
  • Deliveries have no specified delivery times.
  • Regardless of the visit schedule, the vehicle needs to drive this road twice: once in the morning on the way from the depot, and once in the evening on the way back.
  • The overall travel distance and duration of the route is always the same, regardless of when A, B, and C are performed.

Example with deliveries of shipments on the same road. There are three shipments A, B, and C on the road from the depot towards other shipments. A is 1000m from the depot, B is 50 meters further away from the depot, and C is 30 meters further in the same direction. There are other shipments 1000m far from C.

In this situation, and for a request that uses only cost per hour and cost per kilometer, the optimized route could have A and B handled in the morning and C handled in the evening and the cost of the solution would be the same as if all three are handled at the same time.

Cost per kilometers with a threshold

To group nearby visits, you first need to select a threshold distance. This is the maximal distance between two visits that you consider to be nearby. This example uses a threshold of 100 meters that roughly corresponds to one block in an urban area. You can increase or decrease the threshold to match your business needs and the preferences of your drivers.

To group nearby visits within 100 meters of each other, you set a high cost on the first 100 meters of each transition and a lower cost for any additional meters of the transition. Since the first 100 meters are the most expensive, the optimizer makes the biggest savings by using transitions that are shorter than the 100-meter threshold, even if it means extending the overall length of the route.

To set up the costs, you add a new entry to ShipmentModel.transition_attributes with the following properties:

{
  "model": {
    "transitionAttributes": [
      {
        "excluded_dst_tag": "UNUSED_TAG",
        "excluded_src_tag": "UNUSED_TAG",
        "distanceLimit": {
          "softMaxMeters": 100,
          "costPerKilometerBelowSoftMax": 50,
          "costPerKilometerAboveSoftMax": 1,
        }
      }
    ]
  }
}

The tag #unused_tag# must not be used by any shipments or vehicles to match all possible transitions. For more information, see How to match all visit requests.

How a high cost below threshold works

This section shows how the cost below and above threshold affect the overall cost of different solutions of the example scenario.

Solution 1: Perform A, B on the way there, C on the way back

In this solution, the shipments are split into the two traversals of this road. Two of them are delivered on the first traversal, and the remaining one is delivered on the second. There are 5 transitions:

Transition Distance Below threshold Above threshold
Distance Cost Distance Cost
depot →A 1000 m 100 m 5 900 m 0.9
A→B 50 m 50 m 2.5 0 m 0
B→other 1030 m 100 m 5 930 m 0.93
other→C 1000 m 100 m 5 900 m 0.9
C→depot 1080 m 100 m 5 980 m 0.98
Total 450 m 22.5 3710 m 3.71

The overall cost is computed the sum of the two costs per kilometer:

  • the cost per kilometer below threshold (50) times the total traveled distance below threshold (450 m = 0.45 km),
  • the cost per kilometer above threshold (1) times the total traveled distance above threshold (3710 m = 3.71 km).

The overall cost is thus 0.45 * 50 + 3.71 * 1 = 22.5 + 3.71 = 26.21.

Solution 2: Perform A, B, C on the way there, nothing on the way back

In this solution, unlike solution 1, all three shipments are delivered "as a group" during one traversal of the road. On the other traversal, the vehicle does not stop at all. Again, there are 5 transitions, but their lengths and compositions are different:

Transition Distance Below threshold Above threshold
Distance Cost Distance Cost
depot →A 1000 m 100 m 5 900 m 0.9
A→B 50 m 50 m 2.5 0 m 0
B→C 30 m 30 m 1.5 0 m 0
C→other 1000 m 100 m 5 900 m 0.9
other→depot 2080 m 100 m 5 1980 m 1.98
Total 380 m 19 3780 m 3.78

Using the same computation as in solution 1, the overall cost is 0.38 * 50 + 3.78 * 1 = 19 + 3.78 = 22.78, and performing all visits in one time block has a lower cost than performing them in two groups. You can reinforce this effect by increasing DistanceLimit.cost_per_kilometer_below_soft_max.

Why a low cost per kilometer below threshold doesn't work

Since you want to prefer short transitions over long transitions, you may be tempted to give a high cost per kilometer to long transitions, and keep the low cost per kilometer for short transitions. But this has in fact an inverse effect: since the first 100 meters of the transition are the cheapest, the optimizer uses these "cheap" meters to the greatest effect by preferring transitions that have close to or over 100 meters.

You can see this effect on the two example solutions. If you swap the cost per kilometer below and above the threshold, the route costs change:

High cost above threshold High cost below threshold
Solution 1 Solution 2 Solution 1 Solution 2
KMs below threshold 0.45 0.38 0.45 0.38
Cost per KM below threshold 1.00 1.00 50.00 50.00
KMs above threshold 3.71 3.78 3.71 3.78
Cost per KM above threshold 50.00 50.00 1.00 1.00
Total cost 185.95 189.38 26.21 22.78

For each version, the lower of the total costs of the two solutions is highlighted in bold. You can see that when you use a high cost above threshold, the total cost of the route is now higher for the route where the visits are grouped, which is the opposite of what you wanted to achieve.