In fact, Centers‑of‑Gravity are those locations that minimize the sum of weighted distances. Weighted distance is the distance from warehouse to customer multiplied by its demand. If customer A has a demand of 10 and is located 25 kilometers from its warehouse, then its weighted distance is 250 kilometers. The sum of weighted distances - summed over all customers - acts as an indicator for transport costs.
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!
Note that though the goal is to minimize the sum of weighted distances, distances are irrelevant for figuring out in what direction to move the CoG: the overall demand force points towards the optimal Center‑of‑Gravity position.In the example it has a length of 9 and points towards customer A.
In a case with many customers it is the angle of a demand force pulling the Center‑of‑Gravity that is relevant. If the angle is a given, then distance as such is irrelevant: a customer that is 1000 kilometers away pulls as hard as a customer 1 kilometer away. But - of course - angle is determined by distance when decomposed into X and Y distance. Note that the further away a customer, the lesser the angle is affected when moving the Center-of-Gravity.
Moving the Center‑of‑Gravity in the direction of the overall pull force decreases the sum of weighted distances, if moved the right distance. The overall demand force always points the right direction, but in itself it does not tell how far to move the CoG. This far?
Or this far?
The smaller the move distance, the less chance of bypassing the CoG, but the more moves to be made. So, start with big moves. If the CoG is bypassed ('overshooting') then the sum of weighted distances will have increased instead of decreased, and the move size should be reduced to half of its size. By then, the force arrow will have reversed its direction (it always points in the right direction). By taking smaller steps each time having bypassed the CoG you will finally end up on top of it! You may stop moving back-and-forth if the move size has become very small. Or alternatively: do not move to a next position if it would increase the sum of weighted distances, but lower step size first (then the force arrow will never completely reverse its direction).
Below you will find a real-time generated animation that visualizes the above process, step-by-step, for a multiple-customers-case.
- Locate Center‑of‑Gravity at an initial position, and initiate move distance at a large value, for example 100 kilometers.
- A good initial position (X,Y) is the weighted average X and Y coordinates of its customers.
This position is good, but not optimal, though others often present it as optimal.
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 average X,Y position is (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 position has a value of (10 × 9.09 + 1 × 90.91) = 182, so 82% higher! In a real case, the difference is often less than 5%, which can also be seen in the simulation further below.
- A random initial position, such as a randomly selected customer location, can be used for initialisation as well.
Calculate the overall pull force and move the Center‑of‑Gravity in that direction, at move distance.
- All demand forces pulling the Center‑of‑Gravity need to be summed up to get the overall pull force, which is a vector with a certain size (less relevant) and direction (most relevant). Moving the Center‑of‑Gravity in the direction pointed to by the overall pull force decreases the sum of weighted distances, if moving the right distance.
Calculate the sum of weighted distances. If it increased, then move back to previous position, and divide move distance by two. Repeat steps 2 and 3 until the move distance has become sufficiently small.
On a side note, this algorithm resembles the gradient descent method.
Note that X,Y on a flat plane (Chartesian coordinate system) needs to be translated into latitude, longitude on a globe (Spherical coordinate system). As explained above, the algorithm involves summing up vectors, each having a length and angle. Angle on a flat plane compares to bearing on a globe.
All principles remain the same, but formulas become more complicated.
"No, it's not
a flat plane."
Each single run of the Multiple-Centers‑of‑Gravity algorithm does the following:
To find the optimum multiple runs are done, as sometimes a run will finish with a local optimum instead of the global optimum. The best solution out of those runs is the final solution. The higher the number of runs, the more likely the true optimal solution will be found. Usually, this optimal solution will then have been found multiple times as well.
- Locate warehouses at a random location, such as a randomly selected customer location
- (Re)assign each customer to the closest warehouse.
- Move each warehouse to the Center‑of‑Gravity of its customers = apply Single-Center‑of‑Gravity algorithm.
- Repeat steps 2 and 3 until the sum of weighted distances does not decrease anymore.
Centers‑of‑Gravity may end up in the middle of a lake or on top of a mountain. On a side note, this algorithm resembles the k-means clustering algorithm used for cluster analysis in data mining and machine learning.
The animation shows what happens during a single run of this algorithm. Customers are assigned to the closest warehouse, warehouses move to their center‑of‑gravity, customer are reassigned, warehouses move, et cetera, until the final situation is reached where none of the customer assignments and warehouse positions change anymore.
Although each run starts with different locations, the solution (global minimum) is the same in the first three examples.
Run 1 - global minimum Run 2 - global minimum Run 3 - global minimum
The example below shows a run that got stuck in a local optimum. Multiple runs are done to find the global minimum.
Run 4 - local minimum
Underlying assumption of the Centers‑of‑Gravity analysis is: transport cost = rate/kilometer (or mile) × distance.
This assumption is only partly valid. Parcel rates are often distance independent within a smaller country or region, FTL pallet rate/kilometer is lower than LTL pallet rate/kilometer, macro-economic imbalances cause direction-dependent rates. And (upscaled) as-the-crow-flies distances are used as an approximation of road distances.
Of course, transport costs are only a part of supply chain costs. The optimal number of warehouses and their locations are driven by many quantitative and qualitative factors such as (future) transport and warehousing rates, future demand (and supply), lead time requirements, inventory effects, supply chain risk/redundancy, and contractual obligations. Nevertheless, it is common practice to run a Centers‑of‑Gravity-analysis to get a view on what warehouse locations to consider, when designing a supply chain network.
Centers‑of‑Gravity Calculator uses a more advanced version of weighted distances, defined as distance × demand (1st weight) × transport rate (2nd weight). The transport rate enables differentiation between a demand volume transported in small shipments versus the same volume transported in large shipments, which is less expensive.