PTV Group - Logistics Forum

One of my customers asked me about the handling of "imbalanceTolerance". He played with different combinations of imbalanceTolerance and ignoreImbalanceTolerance. While one of the combinations provided a good solution in terms of "all assigned territories total activities have almost equal values" the other results seem to provide an equal, poor level of balancing.

Getting same responses every time with below combination:
1. imbalanceTolerance=10,50&10 and ignoreImabalanceTolerance=false
2. ignoreImbalanceTolerance=true

But getting different response with combination imbalanceTolerance=0 and ignoreImabalanceTolerance=false.

Please let me know, why similar response is generated with above mentioned combinations? I am expecting different responses with different tolerance values.

Let me explain this... As you might know the clustrering tries to satisfy two conflicting goals:

• create geographic compact territories
• assign each territory an equal workload

I start with a definition:

Target activity: the average activity which satisfies the second goal in a perfect way. Simply the sum of all activities divided by the number of output clusters, e.g. the total activity is 10'000 and you want to create 5 clusters. TargetActivity is then 2'000.

So if you activate a specific tolerance T% (e.g.5%) we determine the target activity and derive thresholds for a potential solution:

• MinActivity := TargetActivity * (1 - T%), e.g. 2'000 * 0.95 = 1'900
• MaxActivity := TargetActivity * (1 + T%), e.g. 2'000 * 1.05 = 2'100

In this example all assignments which create clusters with clusterActivity between 1'900 and 2'100 are "valid" in terms of the second goal.

Now the next question is:

Why do the various tolerances in the customers example return same solutions?

For this you need to understand the iteration under the roof.

Trivial assignment: each customer is simply assigned to the closest cluster center.

This is how we create a kickof "condition" which we would try to improve if it violates the imbalanceTolerance.

• In the customers example the Trivial assignment satisfies all the imbalance tolerances [100%,50%, 10%] so there's no need to improve the trivial assignment.
• By setting the imbalanceTolerance to 0% the trivial assignment is no longer sufficient.

That's it.
Bernd

Appendix:
There's no such a call as "find me the best tolerance" in a single step. If you want to go for it you can apply a client logic based on one of the following approaches:

Stragegy 1: start with a low value of imbalance tolerance (e.g.0) - as long as this creates "no valid solution found" increase it step by step

Strategy 2 : start with a trivial tolerance and reduce it until you run into the "no valid solution found". The las successful solution is what you are looking for

Here's a follow-up question:

Does this mean that

• (ignoreImbalanceTolerance=true)
• (ignoreImbalanceTolerance=false) && (imbalanceTolerance=100)

return equal results?

Short answer: Nope. Let's look into the following example, again based on a total activity of 10'000.

Scenarios		Various tolerances
#clusters	target activity	min/max : 10	min/max : 50	min/max : 100	min/max : 200 (=illegal!)
2	5'000	4'500 to 5'500	2'500 to 7'500	0 to 10'000	-5'000 to 15'000
3	3'333	3'000 to 3'666	1'500 to 4'500	0 to 6'666	-3'333 to 10'000
4	2'500	2'250 to 2'750	1'250 to 3'750	0 to 5'000	-2'500 to 7'500
5	2'000	1'800 to 2'200	1'000 to 3'000	0 to 4'000	-2'000 to 6'000

So with a balanceTolerance of 100 only the #clusters==2 guarantees that any starting solution will terminate immediately.
In other words: "What imbalanceTolerance is equal to ignoreImpanceTolerance== true?" depends on the number of target clusters!
Now the value reange for the imbalanceTolerance is restricted to be <=100.
Here are some examples / edge cases based on "all orders are located in the area of cluster 1 and the total activity is 2'871":