- Latitude/longitude is the result of converting a textual address into geographic coordinates - a process called geocoding.
- Geocode ship-to addresses, not billing addresses.
- If far-away-customers are delivered via an exit harbour, then put their aggregated demand on that harbour (latitude/longitude), to ensure warehouses are pulled in the right direction.
- Batch Geocoder - free provides a free geocoding service based on OSM, and downloadable Excel interfaces with Google Maps, TomTom, and BING geocoding api.
- Batch Geocoder - paid provides a non-free geocoding service, based on Google Maps geocoding api.
- Within Europe, demand aggregation to two digit postal code level is often seen in supply chain modelling. You may
- Total demand per customer is ideally, expressed in your transport cost driver: volume or (volumetric) weight.
- Collect a full year of demand data if your business is highly seasonal.
- Demand can be based on sales order quantities × item master dimensions. But item masters are often not 100% clean. This may cause large errors in calculated volumes. So, if available, then use shipment data with actual volumes or (pay)weights.
- Exclude internal replenishment volumes to avoid double-counting.
- Split data per product group / sales channel / region if needed to calculate future demand volumes (see next section).
- Design for the future - include growth projections if those differ per product group / sales channel / region / customer. If not, then you may ignore growth, as it will have zero effect on optimal warehouse locations.
- Growth percentages provided separately "per product group" and "per sales channel" and "per region" cause future demand inconsistencies that may or may not need to be resolved.
- If a sales budget would be the only info about a new sales region, then demographics (such as population data) may help to create a geographical demand proxy.
- Check for outliers, empty, zero, and extremely large values. For example, are there shipment sizes that exceed truck capacity?
- Check the item master (for sold products only), if used to come up with demand volumes. For example, does it contain unrealistically heavy or large products, does kilogram/m3 make sense?
- Check for completeness. For example, does the total number of orderlines match with a warehouse productivity report?
- Check for consistency, if possible. Are gross volumes based on item master calculation in the same ballpark as shipment volumes? Beware: item master cleansing can become time-consuming.
- Check the list of top-X customers. Are there major customers missing? Or unknown customers appearing?
- Check the demand map. Are there gaps? Or large unknown locations? When creating a demand map then aggregate demand per latitude/longitude, otherwise customers with the same latitude/longitude are plotted on top of each other and a too small dot will be shown on the map.
- Latitude, Longitude, Demand are discussed in previous section "About customers (main input)".
- Warehouse_ID is used to assign a customer to a predefined warehouse. If left empty, then customers are assigned automatically.
- Group - free format - is used to force all customers within a group to be delivered by a single warehouse only (single sourcing). The group is assigned to the warehouse that comes with the lowest sum of weighted distances for this group of customers. What group stands for, is for you to decide. Note that warehouse capacity constraints or fixed customer assignments may disrupt single sourcing.
- Shipment_size translates into an individual customer transport rate. If specified, then it overrules the general customer shipment size. See section "Parameters & Constraints" - subsection "About transport rates & underlying cost curve" for more explanation.
- Lead_time_distance is the individual maximum allowed distance from the warehouse. If specified, then it overrules the general lead time distance as set under section 'Parameters & constraints'. Customers are colored in black if the leadtime distance is exceeded, indicating where service is compromised. Enter the distance in the correct distance unit, miles or kilometers, as you have selected under section 'Parameters & constraints').
- Border_group links the customer to a border group. A border group has specific border crossing points to enter or exit the bordered area. Those border crossing points are defined in table Border Crossing Points. A flow from a warehouse to a customer will go via one of the border crossing points, unless the warehouse and customer are both within the bordered area (auto-detected for a warehouse, as it may enter or exit the area during the optimization process).
- Warehouse_ID - free format, for example "Birmingham" - is used in the Customers and Suppliers table to assign customers or suppliers to this warehouse (instead of having the software assign customers and suppliers).
- Move_limit = 0 means a fixed location, > 0 means a location that may move away from its initial coordinates but no further than its move limit. Enter this move limit in the correct distance unit, miles or kilometers, as you have selected under section 'Parameters & constraints').
- Capacity is used to limit the demand that can be assigned to a warehouse. Capacity constraints may 'break' customer groups.
- Transport_rate_index is used to adjust customer transport rates of all customers supplied from this warehouse. An index below 100 means transport from this warehouse to customers is relatively cheaper, an index larger than 100 means more expensive. Customer transport rates are multiplied by the warehouse Transport rate index/100, for all customers assigned to the warehouse. The lower this index, the more customers a warehouse will get assigned (unless other constraints prevent this).
- Warehouse_ID (= link to table Predefined warehouses) is used to assign a supplier to a warehouse. If left empty, the software decides which Center(s)-of-Gravity is/are supplied by the supplier. If specified, then this supplier will not supply all warehouses directly, even if supply option "Each supplier delivers to each warehouse directly" has been selected.
- Shipment_size translates into an individual supplier transport rate.
- Supply_option (1, 3, or 4) can be set to overrule the general supply option (1, 3, or 4) as selected under section "Parameters & constraints". If you select overall option 2 "LP optimized supply flows", then individual supplier settings are ignored.
Border crossing points (very optional)
- If a customer area can only be entered at some specific points - for example, because the area is merely surrounded by water - you may setup border crossing points. But if - for the same example - many ferries operate from/to multiple harbours, then you may decide to ignore this functionality.
- A transport flow has to go via a border crossing point
- if a warehouse is outside the bordered area and supplies a customer within the bordered area ("entry")
- if the warehouse is inside the bordered area and supplies a customer outside the bordered area ("exit")
- A flow via a border crossing point means a detour, but also that the warehouse is pulled towards this point instead of the customer, until the border has been passed.
- Border_group - free format - is the name of the bordered area with all its crossing points (latitude, longitude) entered in this table. Field border_group is also found in the customers table and used to specify which customers belong to the border group. To function properly at least some customers of a bordered area should be located within a 50 km range of the border point.
- The border crossing point causing the smallest detour is auto-detected. Note that it is (currently) limited to one point per flow. A warehouse area exit point takes priority over a customer area entry point: "exit before entry".
Distance & service levelKilometersMilesFactor to convert as-the-crow-flies-distance into road distance estimationiColor customers black if warehouse distance exceeds lead time distancekmiImprove service leveliActivate border crossing pointsi
Closest cityDisplay CoG closest cityiOnly consider cities with a population larger thanOnly consider cities within countryiClosest city is based on the underlying database that contains cities with a population larger than 15,000.
-costs-increase-areas around Centers‑of‑Gravityi
Randomize each demand quantity ±
; using a
Supply optionsActivate supplyForbid total supply to be less than total demandiNon-unique products1. Each supplier delivers to closest warehouse onlyi
2. LP optimized supply flows - with autosized suppliersiUnique products3. Each supplier delivers to each warehousei
4. Each supplier delivers to each warehouse via closest warehousei
Transport ratesThis section is primarily meant to distinghuish between customer and supplier transport, relevant if you have entered suppliers.
Auto-size shipments per individual customeri
As % FTL
% FTL costs
iCosts/km iCosts/km/qty FTL Customer Supplier Interdepot Ratio supplier rate/customer rate =
- Transport rates enable differentiation between relatively less expensive FTL-like transport (from suppliers) and relatively more expensive LTL-like transport (to customers).. It becomes most relevant if your model includes suppliers. To minimize transport costs a Center‑of‑Gravity should move closer towards a customer than towards a supplier, if their volumes would be equal. The ratio between supplier and customer transport rate is more important than rates as such.
- Transport rates also enables differentiation between small and large customers, if shipment sizes are entered at individual customer level. However, the impact on Centers‑of‑Gravity locations is often small, if smaller and larger customers are scattered all around.
- Transport cost of a customer = demand × distance warehouse-customer × customer transport rate. The rate becomes customer specific if shipment size is specified in table Customers.
- LTL transport being relatively more expensive than FTL transport is expressed in the transport cost curve as seen below. An LTL shipment size of 50% FTL brings 72% FTL costs, approximately. Thus, per each unit transported LTL transport is in that case 1.44 times more expensive than FTL transport.
- Under map settings you can choose to display location sizes as transport-rated volumes (volume × rate ratio), instead of plain volumes. Suppliers will then appear relatively smaller than customers, which better reflects the 'pull force' of a supplier/customer.
Transport costs curvei LTL cost factor as % FTL cost Shipment size as %FTL
Point X (as %) Y (as %) Start point (P0) Start control point (P1) End control point (P2) End point (P3) Just a specific point on the curve You may also drag the control points in chart itself.
ConstraintsPredefined warehouse locationsFixed customer-warehouse assignmentsFixed supplier-warehouse assignmentsCapacity limitsLP optimizationiContinuous optimizationiPost-optimization onlyi
Customer groupsiThis section explains the links between constraints and input tables, and describes demo data.
- Check constraint "Fixed customer-warehouse assignments" to assign customers to a predefined warehouse.
Demo: field Warehouse_ID is set to "Birmingham" for all customers in UK/Ireland to assign them to the predefined Birmingham warehouse. It is set to "Madrid" for all customers in Spain/Portugal.
- Check constraint "Customer groups" to have all customers within a group delivered by the same single warehouse (the one that can deliver the group against lowest transport costs, still calculated at individual customer level).
Demo: field Group is filled with the applicable 2-letter ISO country code for all customers. So - in the demo - group stands for country. This prevents customers in Western France to get delivered by the UK warehouse.
- Check constraint "Activate border crossing points" to activate border crossing points.
Demo: field Border_group is filled for customers in UK, IE, Italy, and Iberia (= Spain + Portugal).
Predefined warehouses table (optional)
- Check constraint "Predefined warehouse locations" to include predefined warehouses in the solution.
Demo: contains one predefined warehouse in Birmingham (UK) and one in Madrid (Spain), with field Move limit set to 0 for the Birmingham warehouse (it cannot move), and set to 200 for the Madrid warehouse (it can move within a 200 km range).
- Check constraint "Capacity limits" to limit warehouse throughput capacities.
Demo: field Capacity is set for both predefined warehouses.
Suppliers table (optional)
- Check "Activate supply" to include suppliers.
Demo: contains one supplier in Rotterdam (The Netherlands - Entry harbour supplying 71% total demand), and one in Bologna (Italy).
- Flows from suppliers via warehouses to customers are constructed automatically, dependent on the selected Supply option.
- Check constraint "Fixed customer-warehouse assignments" to assign suppliers to a predefined warehouse. It links to field Warehouse_ID. If filled, then the supplier will only supply this warehouse. And via this warehouse to each other warehouse, if supply option "Each supplier delivers to each warehouse via closest warehouse" is selected. (If field Warehouse_ID is filled, then a supplier will never supply all warehouses directly, even if supply option "Each supplier delivers to each warehouse directly" has been selected.)
Border crossing points table (optional)
- Check constraint "Activate border crossing points" to activate border crossing points.
Demo: field Border_group relates to the same field found in the customer table and specifies which border crossing points (if any) are applicable for which customers. The demo contains only a limited amount of border crossing points, just to show you how this concept works.
|Distance||Demand cum||Demand||Customers cum||Customers||# Customers|
- Step 1 is creating a greenfield scenario. You only need to enter demand.
- Step 2 is replicating the current situation - often done to get a transport cost figure to compare against. You enter current warehouses.
- Step 3 is creating a realistic scenario that sits somewhere between the current situation and greenfield. Constraints of step 2 are partly relaxed, like "only some of the current warehouses remain as-is, but others may move to a Center‑of‑Gravity".
- Step 4 (optional) is adding suppliers to include supplier transport costs in the optimization.
1. Greenfield100% optimization freedom
• Free amount of new warehouses
at Centers‑of‑Gravity locations
• All customers reassignable
• No capacity constraints
3. Realistic scenarioSome optimization freedom
• Some warehouses as is
• Some warehouses closed
• Some warehouses extended
• Some warehouses newly added
• Some customers reassignable
• Some capacity constraints
2. Current situationZero optimization freedom
• All warehouses as is
• All customer assignments as is,
so warehouse capacity constraints
'automatically' adhered to as well
100% ←- Optimization freedom -→0%
- Fill out table Customers.
- Select the number of Centers‑of‑Gravity, and press Calculate.
- View the service level distance chart showing percentage of demand and customers reached per distance. This indicates if more warehouses should be opened, or if some could be closed.
- Check option "distance based customer coloring" under "Map settings". Customers beyond acceptable lead time distance (set under "Parameters & Constraints") become black. Based on this map you may decide to add/relocate warehouses. Or accept that some customers will have a longer lead time - which is probably already the case in reality. A few far-away customers should not be driving your supply chain network design!
- Check option "Improve service level" under section "Parameters & Constraints" and rerun. Service level will be improved at the expense of increased transport costs.
- Check option "Randomize each demand quantity" and rerun. Each customer demand temporarily changes between −X% and +X%. See how it affects Centers‑of‑Gravity.
- Check option "Display cost-increase-areas" and rerun. A grey area around each Center‑of‑Gravity appears. If the warehouse would be located at the dotted border, then its transport costs would increase X%.
- Fix warehouses at their current location by filling out table Predefined warehouse with field Move_range set to 0, and checking constraint "Predefined warehouse locations".
- Assign customers to their current warehouse by entering field Warehouse_ID in the Customers table, and checking constraint "Fixed customer warehouse assignments". You may skip this step if the automatic distance-based customer assignments closely match reality.
Gradually relax some constraints.
Relaxing some constraints, you may want to control the solution by other types of constraints:
- Investigate if current locations are optimal - given fixed customer assignments - by increasing Move_range of (some) predefined warehouses.
- Investigate if current customer assignments are optimal - given fixed warehouse locations - by removing Warehouse_ID of (some) customers, or by unchecking constraint "Fixed customer-warehouse assignments".
- Investigate where to open a next new warehouse by increasing the number of Centers‑of‑Gravity beyond the number of predefined warehouses. Make sure you allow (some) customers to get (re)assigned to this new warehouse.
- Limit warehouse capacities - by filling field Capacity in the Predefined warehouses table and activating constraint "Capacity limits". Keep in mind that current limits may not apply in future, if additional space can be rented or the owned facility expanded.
- Group customers for single sourcing to enforce all customers within a group to be assigned to the same, single warehouse, by filling field Group in the customers table and activating constraint "Customer groups".
A Center‑of‑Gravity analysis focuses on the demand side with its relatively high transport costs and lead time requirements. But you can add suppliers (locations and supply quantities) to include supply transport costs in the optimization. This is more relevant if there are a few dominant supply locations (such as a large plant or entry harbour), in which case a warehouse should move towards that location.
Supplier shipments are usually larger than customer shipments, on average. This makes supplier transport relatively cheaper. The lower transport rate makes suppliers pull Centers‑of‑Gravity relatively less than customers do. Enter supplier and customer transport rate under subsection "Parameters & constraints".
Select 1 of the 4 supply options: it determines how supply flows are constructed.
- Each supplier delivers to closest warehouse* onlyi
- LP optimized supply flows - with autosized suppliersi
- Each supplier delivers to each warehousei
- Each supplier delivers to each warehouse via closest warehouse*i* Closest warehouse can be manually overruled
Under options 2/3/4 each supplier - unlike a customer - pulls several/all warehouses.
Demand side onlyWarehouses are pulled by customers only
Supply option 3All warehouses are pulled towards a major supplier.
Supply option 4Especially the closest warehouse is pulled towards a major supplier.
This explanation is generic as it applies to any software that properly calculates supply chain Centers‑of‑Gravity. Some specific features of Centers‑of‑Gravity Calculator are described as well.
Centers‑of‑Gravity are indicative warehouse locations that minimize estimated transport costsIn fact, Centers‑of‑Gravity are those locations that minimize the sum of weighted distances, given the amount of warehouses. Weighted distance is the distance from warehouse to customer multiplied by customer demand. If a customer 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 of all customers acts as an indicator for transport costs.
Towards the algorithms - Introductory thoughtsUpfront: there exists no mathematical formula that can (simply) calculate the optimal warehouse position given customer locations and demand. So...
Imagine a case with two customers only. Customer A has a demand of 10 and customer B of 1. Where is the Center‑of‑Gravity? Somewhere on line A-B, closer to A?
Well, you could say that customer A pulls 10 times harder than customer B. If the 'Center‑of‑Gravity' * moves a distance d towards A the sum of weighted distances decreases (10 × d) – (1 × d) = 9 × d.
* If put between quotes then it refers to a location under investigation which is not yet the true Center‑of‑Gravity.
So, the Center‑of‑Gravity is right on top of customer A, not somewhere in between A and B!
The resultant pull force - sum of all customer pull forces - is leading. It always points in the direction that the 'Center‑of‑Gravity' should move into to decrease the sum of weighted distances. This resultant pull force is constructed by linking all customer pull forces together, head to tail.
However, the sum of weighted distances will only decrease if the 'Center‑of‑Gravity' moves the right distance! The resultant pull force does not tell how far to move. Move this far?
Or this far?
The smaller the move distance, the less chance of 'overshooting' the Center‑of‑Gravity, but the many more moves to be made. Therefore, it is better start with big moves. In case of 'extreme overshooting' the sum of weighted distances will have increased instead of decreased, and the resultant force arrow changed - or even completely reversed - its direction. By then, the move size needs to be reduced in order to get closer to the Center‑of‑Gravity. Else, the next move would end up at the previous position, followed by getting stuck in a loop of going back-and-forth without ever getting any closer. By reducing the move size each time the sum of weighted distances increased the 'Center‑of‑Gravity' ends up on top of the Center‑of‑Gravity.
Of course, the above was an extreme example. Usually, there is no single dominant customer, and the Center‑of‑Gravity will be somewhere in the center of all customers. Also then, the Center‑of‑Gravity is found by moving in the direction of the resultant pull force, but not too far. The resultant pull force becomes smaller the closer the location gets to the Center‑of‑Gravity (which implicates that the length of the resultant pull force somehow does relate to the distance to be moved). It becomes zero on top of the Center‑of‑Gravity, with all underlying pull forces (F) in a state of equilibrium in both x and y direction: ΣFx=0, ΣFy=0. All forces linked together start and finish at exactly the same location = zero resultant force.
Except if one dominant customer outweighs all other customers. Then the Center-of-Gravity is on top of this dominant customer, but the resultant force is not zero.
Another exceptional case, rather theoretical, is one in which there are only two customers, A and B, with equal demand. Then the resultant force is zero for all points between A and B on line A-B. Each of these points is Center‑of‑Gravity.
Single-Center‑of‑Gravity algorithmThere exists no mathematical formula that can calculate the Center‑of‑Gravity/optimal warehouse position, given customer locations and demand. It takes an iterative approach to determine the Center‑of‑Gravity.
The Single-Center‑of‑Gravity algorithm works like this on an x,y plane:
- Initialization: locate the 'Center‑of‑Gravity' at an initial (random) position, and give the move distance a large value.
- Calculate the resultant pull force. Move the 'Center‑of‑Gravity' in that direction, at move distance.
- Calculate the sum of weighted distances. If it increased, then divide the move distance by two.
- Repeat steps 2 and 3 until the move distance becomes very small.
- Initialization: locate the 'Center‑of‑Gravity' at an initial (random) position, and give the move distance a large value.
- A good initial position is the weighted average x and y coordinates of its customers. It is often near-optimal, but not the Center‑of‑Gravity, though you may have read elsewhere it is.
- A random location within the customer cloud can be used just as well, as the remainder of the algorithm will always find the Center‑of‑Gravity, in almost equal time.
- It is better to start with a bit too large move distance (100 kilometers) than with a bit too small, because if too small then it will take many iterations before the Center‑of‑Gravity is reached.
Calculate the resultant pull force. Move the 'Center‑of‑Gravity' in that direction, at move distance.
- Sum up all pull forces (vectors) to get the resultant pull force (vector) with a certain size (less relevant) and direction (most relevant) by summing up x and y components separately. For each customer pull force F: Fx = length demand vector × (customer_x − CoG_x)/(distance from customer to CoG), or shorter: Fx = demand × cosinus(angle F). Fy = demand × sinus(angle F).
- Normalize this resultant pull force (a vector with origin at 0,0 and end point at x,y) by dividing x by its length √(x2 + y2) and y by its length. The vector keeps pointing in the same direction, but its length becomes 1, which makes it a unit vector.
- Multiply x and y values of this unit vector with the step size to get the move vector representing move distance in x and y direction.
- If the move vector's tail starts at the current 'Center‑of‑Gravity' position, then its head ends at the next 'Center‑of‑Gravity' position. So, add the move distance in x direction to the current x position of the 'Center‑of‑Gravity', and add distance in y direction to its current y position. This brings the next 'Center‑of‑Gravity' position.
Calculate the sum of weighted distances. If it increased, then divide the move distance by two.
- This approach originates from the binary search algorithm - a.k.a. half interval search - to find the position of a target value within a sorted array. See half-interval search (wikipedia).
- Optional: move the 'Center‑of‑Gravity' back to its previous position if the sum increased, so with each 'accepted move' the solution always improves (or remains equal, but never worsens).
Repeat steps 2 and 3 until the move distance becomes very small.This algorithm will always find the global optimum with a single run. With this type of problem, there is no chance of getting stuck in local optimum. The algorithm relates to the gradient descent method (wikipedia), also used by Excel Solver's method GRG Nonlineair (GRG stands for Generalized Reduced Gradient).
- Then the Center‑of‑Gravity hardly changes anymore, and the sum of weighted distances converges.
- The Center‑of‑Gravity may be in the middle of a lake or on top of a mountain.
Determining the Center‑of‑Gravity is like finding the x and y coordinate of the lowest point (x,y,z) in a bowl-shaped 3D‑chart - visualizing the sum of weighted distances z = f(x,y) for each x and y - by going into the direction of steepest descent as pointed to by the resultant pull force. During this descent the direction gets adjusted after each move made/step taken.
Wikipedia presents complex methods to determine a proper move distance (a.k.a. step size) per iteration. Luckily, there is no urgent need for those, because the method of step 3 works quite good!
Visual simulationPress button Next process step to start the simulation.
Earth is a globe - Required adjustments
X,y on a flat plane (Chartesian coordinate system) becomes latitude,longitude on a globe (Spherical coordinate system). The algorithm involves summing up vectors with a length and an angle. The distance between two points on a globe is calculated with the Haversine formula, and the angle with a Bearing formula. Demand vectors are mapped to a flat tangent space before summing up, and the result is translated back to the globe - see also the picture of section 'Weiszfeld's algorithm as alternative'.
"No, it's not
a flat plane."
Latitudes and longitudes in both formulas need to be expressed in radians = degrees × 𝜋/180.
Haversine formula - in 2 steps
- a = sinus2((latitude_customer − latitude_cog)/2) + cos(latitude_cog) × cos(latitude_customer) × sinus2((longitude_customer − longitude_cog)/2)
- As-the-crow-flies-distance = 2 × atan2(√a , √(1-a)) × 6371. 6371 kilometers is Earth's mean radius.See Excel - As-the-crow-flies distance function for an Excel implementation. Excel's atan2 function takes its arguments in reversed order!
Bearing = atan2(sinus(longitude_customer − longitude_cog) × cosinus(latitude_customer) , cosinus(latitude_cog) × sinus(latitude_customer) − sinus(latitude_cog) × cosinus(latitude_customer) × cosinus(longitude_customer − longitude_cog)
Bearing is measured against the vertical longitude axis, not the horizontal latitiude axis, so you need to swap the use of cosinus/sinus when calculating forces in x and y direction.
Weiszfeld's algorithm as alternativeWeiszfeld's algorithm - see also Geometric median (wikipedia) - works like this on an x,y plane:
Applying Weiszfeld's algorithm to Earth is also done via a flat tangent space.
- Initialization: locate the 'Center‑of‑Gravity' at an initial (random) position.
- Calculate each customer weight as demand divided by distance to 'Center‑of‑Gravity'.
- Calculate the weighted average x,y of customers as the next 'Center‑of‑Gravity'.
- Repeat steps 2 and 3 until the sum of weighted distances converges.
Source: section 2.3 Weiszfeld Algorithm on a Riemannian Manifold of article Generalized Weiszfeld Algorithms for Lq Optimization by K. Aftab, R. Hartley, J. Trumpf.
Differences between both algorithms
Major difference between Single-Center‑of‑Gravity algorithm and Weiszfeld's algorithm is that the former uses an explicitly controlled move distance whereas - you could say - the latter has an implicit variable move distance of 1 ∕ Σ(demandi ∕ distancei), that is applied to a non-normalized resultant pull force vector.
This controlled move distance enables an advanced feature of Centers‑of‑Gravity Calculator: you can limit the move range of predefined warehouses. The optimal location may then be somewhere at the border of this limited range and Weiszfeld's algorithm cannot handle this. But this controlled move distance also means that, whereas under Weiszfeld's algorithm the sum of weighted distances decreases with each iteration, under the Single-Center‑of‑Gravity algorithm it decreases only if the move distance did not result in 'extreme overshooting'.
Weiszfeld's algorithm converges approx. 10% faster. After 15 iterations the sum of weighted distances will have become less than 0.01% above absolute minimum. Weiszfeld's algorithm does not use a move distance, but the Single‑Center‑of‑Gravity algorithm does, and if the initial move distance is set too high, then the first few iterations will become useless 'extreme overshoots' (as can be seen in the chart), but if it is set too low it will take many more iterations to move to the Center‑of‑Gravity, so it's better to initialize it a bit too high.
Centers‑of‑Gravity Calculator uses both algorithms: the faster Weiszfeld's algorithm as its default, and Single‑Center‑of‑Gravity algorithm in case of predefined warehouses with limited move range.
Multiple‑Centers‑of‑Gravity algorithmBelow, 'Center‑of‑Gravity' and warehouse are used interchangeably.
A single run of the Multiple‑Centers‑of‑Gravity algorithm does the following:
Multiple runs are done to find the global optimum, as a run may get stuck in a local optimum. The more runs, the more likely the global optimum is found. Usually, this global optimum will then have been found multiple times as best solution. The warehouse locations of the best solution found are considered to be the Centers‑of‑Gravity. But - especially with a higher number of warehouses - it may happen that two different warehouse structures bring an almost similar sum of weighted distances.
- Initialization: locate each warehouse at a random location within the customer cloud.
- (Re)assign each customer to its closest warehouse.
- Move each warehouse to the Center‑of‑Gravity of its assigned customers.
= apply Single‑Center‑of‑Gravity algorithm / Weiszfeld's algorithm per warehouse
- Repeat steps 2 and 3 until the sum of weighted distances converges.
The algorithm resembles the k-means clustering algorithm (wikipedia) used for cluster analysis in data mining and machine learning, as depicted on the left.
K-means Clustering creates clusters that are purely distance based, just like each customer gets linked to its closest warehouse. Expectation–Maximization (EM) algorithm creates clusters differently. With Centers‑of‑Gravity Calculator you can group customers beforehand - like all dots in the yellow oval - that need to be served by a single warehouse.
AnimationsThe animations show what happens during a single run of this algorithm. Customers are assigned to their closest warehouse, warehouses move to the center‑of‑gravity of their assigned customers, customer are reassigned, warehouses move, et cetera, until the final situation is reached where none of the customer assignments change anymore, and none of the warehouse positions.
Although each run starts with different random locations, the solution found (global optimum with a minimal sum of weighted distances) is the same in the first three run 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. Therefore, multiple runs need to be done to find the global optimum.
Run 4 - local minimum
A completely different approachA completely different approach is one in which a set of hundreds or thousands of possible warehouse locations are pre-generated, after which the k best ones are selected (see Combination - wikipedia). Advantage is that the warehouse-customer cost matrix can be based on various transport rate structures and can capture warehousing costs. Disadvantages are that it requires many more inputs (and still has the risk that the set of predefined locations may not contain the optimal locations), and that the number of possible warehouse combinations - thus runtime - may grow exponentially.
Web app Warehouse Selection Optimizer facilitates this approach.
Underlying assumptionsA major underlying assumption is that transport cost = rate/kilometer × distance. This assumption is only partly valid. Parcel rates are often distance independent within a region, macro-economic imbalances cause direction-dependent rates, different transport companies may have different rates for the same route because of differences in their customer base that may or may not enable certain efficiencies.
Besides, as-the-crow-flies distances × circuitry factor are used as approximation of road distances. The fastest route is usually more relevant than the shortest, as driver and truck cost are more time-related than distance-related. But the fastest route may depend on the time of the day, day of the week, and time of the year. As distance estimation errors will be more or less the same for each direction, approximations are usually acceptable, and commonly used in supply chain network design software.
Broader supply chain network design perspectiveOf 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, contractual obligations, distance to parcel/logistics hubs, workforce availability/public transport connections, et cetera.
Nevertheless, it is common practice to run a Center‑of‑Gravity analysis to get a view on which logical warehouse locations to consider in a supply chain network design.
Centers‑of‑Gravity Calculator - Advanced functionality and additional algorithmsCenters‑of‑Gravity Calculator - a professional web app for Center‑of‑Gravity analysis, developed by Stelling Consulting - 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 relatively less expensive.
Centers‑of‑Gravity Calculator offers more advanced functionality. For example, you can predefine existing warehouse locations including capacity limits. The additional subalgorithms that handle warehouse capacity constraints are explained in the next section.
Subalgorithms handling capacity constraintsWhen predefined warehouses have a limited capacity, a transportation problem arises. A transportation problem can be solved with the well-known Simplex method (LP). But it can be solved 50-100 times faster with a combination of Vogel + MODI + Stepping Stone method that generates an optimal solution - this combination has been implemented in the Centers‑of‑Gravity Calculator. Detailed descriptions of each separate method (standard as such) can be found on the internet. For a demo case, see our Transportation problem solver
Centers‑of‑Gravity Calculator also contains a superfast, sub-optimal, greedy algorithm as alternative that can be used if Vogel + MODI + Stepping Stone method runtime would become too long in case of an extremely large amount of customers and warehouses. It will also try to keep customer groups intact while adhering to capacity constraints. Roughly described, it works like this.
- Assign customers as if warehouses have unlimited capacity.
- Loop forwards and backwards through all warehouses, and while the capacity of a warehouse is exceeded reassign that customer (group) to that other warehouse that brings the lowest cost increase, until all capacity constraints of all warehouses are met.