This page describes the core algorithms of Centers-of-Gravity Calculator
Centers‑of‑Gravity indicate where to locate warehouses to minimize transport costs
It is standard practice to do a Centers-of-Gravity analysis when designing a supply chain network. It will give you a first good view on what warehouse locations to consider.
Centers-of-Gravity are those locations that minimize the sum of weighted distances.
Weighted distance is the distance from warehouse to customer multiplied by demand.
If customer A has a demand of 10 and is located 25 kilometers (km) from its warehouse, then the weighted distance is 250 km.
The sum of weighted distances over all customers acts as an indicator for transport costs.
Underlying assumption: transport cost = rate/km × distance.
This assumption is only partly valid. Parcel rates are often distance independent within a smaller country or region, FTL pallet rate/km is lower than LTL pallet rate/km, macro-economic imbalances cause direction-dependent rates, et cetera.
Also, as-the-crow-flies distances are often used, instead of road distances. Nevertheless, a Centers-of-Gravity analysis provides a good starting point for a supply chain network design.
Weighted distance can also be defined as distance multiplied by demand (1st
weight) multiplied by transport rate (2nd
weight), which enables differentiation between a demand volume transported in small shipments versus the same demand volume transported large shipments: LTL transport is relatively more expensive than FTL transport.
Customer A has a demand of 10 and customer B a demand of 1.
Where is the Center-of-Gravity (CoG)? Somewhere on line A-B, closer to A?
Well, customer A pulls 10 times harder than customer B.
If the CoG moves a distance d towards A the sum of weighted distances
decreases (10 x d) – (1 x d).
So, the CoG is right on top of customer A, not
somewhere in between A and B!
Though the goal value is the sum of weighted distances
, distances itself are 'less relevant' when figuring out in what direction to move the CoG.
The overall demand force is leading. In the example it has a length of 9 and points towards customer A.
The overall demand force points the right direction, but does not tell how far to move the CoG.
Or this far?
Each single run of this algorithm does the following:
- Step 1: locate warehouses at a random location (optional: then assign customers, calculate weighted X,Y of assigned customers, and use this X,Y as initial position).
- Step 2: (re)assign each customer to the closest warehouse.
- Step 3: move each warehouse to the Center-of-Gravity of its customers = apply Single-Center-of-Gravity algorithm (described below).
- Repeat steps 2 and 3 until the goal value (sum of weighted distances) does not decrease anymore.
Multiple runs are done, each run starting with different random locations. The best solution out of those runs is presented as final outcome. The higher the number of runs, the more likely the optimum solution will be found.
Animation of the Multiple-Centers-of-Gravity algorithm
The animation shows what happens during a single run of this algorithm: customers (circles) are assigned to the closest warehouse (triangles), warehouses move to their center-of-gravity, customer are reassigned, warehouses move, et cetera, until the final situation is reached where none of the asssignments and warehouse positions change any more.
On a side note, the problem and algorithm are comparable to k-means clustering
: cluster analysis performed in data mining, and used in machine learning.
(step 3 of the Multiple-Centers-of-Gravity algorithm)
Initial Center-of-Gravity position
The Center-of-Gravity is initially positioned at the weighted average X and Y coordinates of its assigned customers. This inital Center-of-Gravity position is not optimal (though others often state it is).
Imagine there are only two customers, customer A with demand 10 at position (0 , 0) and B with demand 1 at position (100 , 0). The weighted X,Y position is at (9.09 , 0), with 9.09 calculated as (10 × 0 + 1 × 100)/(10+1). If the Center-of-Gravity moves a distance d towards customer A the goal value improves 10 × d (closer to A) − 1 × d (further from B) = 9 × d. So the optimal position is on top of customer A, not at the weighted X,Y position! The optimal Center-of-Gravity has a goal value of (10 × 0 + 1 × 100) = 100, whereas the initial Center-of-Gravity at (9.09 , 0) has a much higher value of (10 × 9.09 + 1 × 90.91) = 182, so 82% higher costs. In realistic situations with multiple customers, the relative difference will be much smaller - less than 5% - as also can be seen in the visual simulation further below.
Moving the Center-of-Gravity in the direction of the overall pull force will decrease the sum of weighted distances, if moved the right distance
All forces pulling the Center-of-Gravity need to be summed up to get the overall pull force, which is a vector with a size (irrelevant) and a direction.
Single Center-of-Gravity algorithm
- Step 1: locate Center-of-Gravity at an initial position (same as step 1 of the Multiple-Centers-of-Gravity algorithm), and initiate 'move distance' at a large value, for example 100 kilometers.
- Step 2: calculate the overall pull force and move the Center-of-Gravity in that direction, at move distance.
- Step 3: calculate the sum of weighted distances. If it has increased, then move back to the previous position, and divide move distance by two.
- Repeat steps 2 and 3 until the move distance has become sufficiently small.
This algorithm resembles the gradient descent method
with force replacing the gradient.
Visual simulation of the Single-Center-of-Gravity algorithm
Note that X,Y on a flat plane needs to be translated into latitude, longitude on a sphere (globe). All principles remain the same, but formulas become more complicated.