Why is my route size variance positive even when the routes are identical?

This is expected behavior. A positive route size variance does not necessarily mean the routes are unbalanced.

cuOpt’s route size variance can be positive even when routes are identical because the variance metric is computed using a route size definition that includes the starting depot node, while the mean route size excludes the depot nodes.

How the metric is computed

cuOpt computes route size variance using the standard sum of squares differences from the mean.

variance in route size \( = \sum_{r \in Routes} (|r| - \mu)^2 \)

Where

• \( |r| \) is the size of route \( r \), which includes the starting depot
• \( \mu \) is the mean route size, which is estimated upfront as the number of demand tasks divided by the number of vehicles

Because \( |𝑟∣ \) and \( \mu \) are not always based on the exact same counting method, the metric can be greater than zero, even when the routes identical.

Is this a bug?

No. This metric is not intended to be an exact statistical variance, since cuOpt estimates the mean upfront. For route-uniformity optimization, this approximation is generally sufficient and leads to the same or very similar solutions as an exact approach, while avoiding numerical scaling issues.

Can you give me an example?

Consider a problem with two tasks and two vehicles with a solution of two identical routes for each vehicle that each go from the starting depot to their pickup location to their ending depot.

In this example, the mean route size is two tasks divided by two vehicles, which equals a mean route size of one.

But when computing the length of each route, the starting depot is included in the route length calculation, so each route has a length of two. So the variance calculation is

$$ (2-1)^2 + (2-1)^2 = 2 $$

Even though the two routes are identical, the route size variance score is still positive due to the way the mean is estimated upfront.