After adjustment, a single Calculation is run to effectuate changesCustomer/supplier size factor⇐ Set it such that 1st legend value becomesiCenters‑of‑Gravity size factorFlow size factori
Customer/supplier opacityCenter‑of‑Gravity opacityCenter‑of‑Gravity colorLabel font sizeDisplay transport-rated volumesiDisplay Centers‑of‑Gravity as fixed-sized circlesiDifferentiate demand mapiDisplay customer flowsDisplay supplier flowsSupplier flows colorSupplier flows arrow sizeiScale arrows
Save all map settings asunder button
Reload: click a button
⇒ Your custom settings used at startupii
Customer_ID | Latitude | Longitude | Demand | Warehouse_ID (opt) | Group (opt) | Shipment_size (opt) | Lead_time_distance (opt) | Border_group (opt)
Supplier_ID | Latitude | Longitude | Supply | Warehouse_ID (opt) | Shipment_size (opt) | Supply_option
Warehouse_ID | Latitude | Longitude | Move_limit (km) | Capacity (opt) | Transport_rate_index (opt)
|BORDER CROSSING POINTS|
Border_group | Latitude | Longitude
- Warehouse_ID (= link to table Predefined warehouses) is used to assign a customer to a predefined warehouse. If left empty, the software decides to which Center‑of‑Gravity the customer will be assigned. If you specify Warehouse_ID, then the customer will be assigned to that warehouse, regardless Group.
- Group - free format, for example "UK" - is used to force all customers within a group to be delivered by a single warehouse only , the one that comes with the lowest sum of weighted distances for this group of customers. What group means, is up to you - often used is country. Warehouse capacity constraints may cause some customers of a group to get reassigned to another warehouse. You can fill group for some customers (treated as group), and leave group blank for others (treated individually).
- Shipment_size is used to calculate an individual customer transport rate.
- Given two customers with equal demand, the customer with smaller shipments will pull the Center‑of‑Gravity harder than the customer with larger shipments, as transporting many small shipments is more expensive than tranporting a few large shipments. So, customers with smaller shipments will pull a Center‑of‑Gravity relatively less and vice versa.
- The impact of individualized shipment sizes on Centers‑of‑Gravity locations will be marginal, if small and large (shipment) customers are scattered all around, which is usually the case. You can start without individualized shipment sizes.
- Transport rates - including logic behind transforming shipment size into transport rate - are explained under section "Optional constraints and parameters".
- Lead_time_distance (km) represents lead time requirement expressed as the maximum allowed distance from the warehouse. Customers are colored in black if warehouse distance exceeds leadtime distance. This provides a visual clue of where lead times are compromised. You can then decide to increase the number of warehouses, or to setup a predefined warehouse at a location closer to these customers (with a zero or limited move range), or accept that some customers will have a longer lead time (like in reality; a few small far-away customers should not be driving your supply chain network design!).
- 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 (= 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 set, 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 is used to calculate a supplier specific transport rate. Transport rates are explained under section "Optional constraints and parameters".
- Supply_option is used to overrule the generic supply option as selected under section "Optional constraints and parameters".
- Supply closest warehouse onlyi
- Supply each warehousei
- Supply each warehouse via closest warehousei
- 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, whereas Move_limit > 0 (in km, not miles!) means a moveable location that may move within its Move limit around its coordinates.
- 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).
Border crossing pointsBorder crossing points can enhance routing accuracy. For example:
- UK: the English Channel is crossed at a specific points.
- Italy: merely surrounded by sea and trucks enter/exit via its north side. Border crossing points prevent that flows go directly from Italy into Albania/Croatia (or vice versa) crossing the Adriatic sea.
Border crossing points get activated:
- if a warehouse is outside the area and supplies a customer within the area (entry)
- if the warehouse is inside the area and supplies a cusomer outside the area (exit)
- Border_group - free format - is the name of the bordered region (often a country) with its specific border crossing points as defined in this table. Field border_group is also found in the customers table, to link customers to the group. The customers define its shape.
The optimal border crossing point is auto-detected. To function properly at least some customers of a bordered area should be located within a 50 km range of the border point.
One border crossing per flow is supported, currently. A DC area exit point will take priority over a customer area entry point ("exit before entry").
The demo case contains just a few sample border crossing points to show you how it works. Feel free to adjust!
|Sum of weighted distances||
Distance / lead time / service levelFactor to convert as-the-crow-flies-distance into fastest route road distanceiColor customers black if warehouse distance exceeds lead time distancekmiImprove service leveli
Closest city nameDisplay CoG closest cityiOnly consider cities with a population larger than
- City name appears as Center-of-Gravity name on the map and in reports, if you have checked 'Display closest city name'.
- But warehouse_ID is shown as name in case of a predefined immovable warehouse.
- When determining closest city, only cities with a population larger than the population threshold are included.
- The database contains cities that have a population larger than 15,000, as depicted below.
-costs-increase-areas around Centers‑of‑Gravityi
Randomize each demand quantity ±
; using a
Apply constraintsPredefined warehouse locationsFixed customer-warehouse assignmentsFixed supplier-warehouse assignmentsCapacity limitsRun LP post-optimizationiCustomer groupsi
Supply optionsActivate supplyEach supplier delivers to closest warehouse onlyi
Each supplier delivers to each warehousei
Each supplier delivers to each warehouse via closest warehousei
Auto-size shipments per individual customeri
% FTL costs
iCosts/km iTransport rate FTL Customer Supplier Interdepot Ratio supplier rate/customer rate = Transport cost of a customer = demand × distance warehouse-customer × customer transport rate (that becomes
customer specific if shipment size is specified in customer table - same rate logic as shown above applicable).
- Transport rates enable differentiation between relatively less expensive FTL-like (supplier) transport and relatively more expensive LTL-like (customer) transport.
- In order 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 the rates as such.
- 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, thus properly reflecting the force with which a location pulls a Center‑of‑Gravity (though in case of a supplier, this force may be split across all warehouses, dependent on selected supply option).
- You may even enter shipment size per individual customer, to differentiate transport rates between customers. However, impact on Centers-of-Gravity locations will be marginal, if small and large (shipment) customers are scattered all around.
- LTL transport is relatively more expensive than FTL transport. An LTL shipment size of 50% FTL brings 72% FTL costs, approximately. Thus, per each unit transported LTL transport is 1.44 times more expensive than FTL transport.
Shipment costs curvei LTL cost factor as % FTL cost Shipment size as %FTL
Point X Y Start point (P0) % % Start control point (P1) % % End control point (P2) % % End point (P3) % % Just a specific point on the curve % %
- Check constraint "Fixed customer-warehouse assignments" to assign customers to a warehouse. Demo data: customers in UK/Ireland are assigned to the predefined Birmingham warehouse (field Warehouse_ID set to "Birmingham"), and customers in Spain/Portugal to the Madrid warehouse.
- Check constraint "Customer groups" to have all customers within a group delivered by the same single warehouse. Demo data: all customers have field Group filled with a 2-letter ISO country code. In this case group means country: each country is delivered by one warehouse only.
Predefined warehouses table (optional)
- Check constraint "Predefined warehouse locations" to activate predefined warehouses and include those in the solution. Demo data: there is one warehouse in Birmingham/UK (cannot move, field Move limit set to 0) and one in Madrid/Spain (can move within a 200 km range around Madrid, field Move limit set to 200).
- Check constraint "Capacity limits" to limit warehouse throughput capacities. Demo date: field Capacity is set for both Birmingham and Madrid.
Suppliers table (optional)
- Check parameter "Activate supply" to activate supply. Demo data: there is one supply location in harbour Rotterdam/The Netherlands (supplies 71% total demand volume), and one in Bologna/Italy (supplies 29% total demand volume).
- Suppliers - like customers - pull Centers‑of‑Gravity which will tend to move towards suppliers, as supply volumes are usually high compared to individual customer demand volumes. However, supplier transport is - due to larger shipment sizes - relatively less expensive than customer transport. Transport rates express how much less. Supplier quantity × supplier transport rate = supplier pull force. Suppliers will appear relatively smaller on the map - reflecting pull force as used in the calculations - if you check Map Settings option "Display transport rated volumes".
- Flows from suppliers to customers via warehouse(s) are constructed automatically. Under Supply options you can chose from three options. Option “each supplier delivers to each warehouse” is the default option, and means that the supplier volume to each warehouse is pro rata the customer demand assigned to each warehouse.
|Distance||Demand cum||Demand||Customers cum||Customers||# Customers|
CoG_ID | Latitude | Longitude | Capacity | Rate index | Demand | Total_demand_% | Utilization | Closest_city | Distance_to_Closest_city
Customer_ID | Latitude | Longitude | Demand | Warehouse_ID | Group | Ship_size | Leadtime_dist | CoG_ID | Distance | Transport_rate | Transport_costs | Latitude_border; | Longitude_border
SERVICE LEVEL DISTANCES
Distance | Demand_cum_% | Demand_% | Customers_cum_% | Customers_% | Number_of_customers
Current situation0 optimization freedom
• All warehouses as is
• All customer assignments as is,
so warehouse capacity constraints
adhered to as well
Realistic scenarioSome optimization freedom
• Some warehouses as is
• Some warehouses closed
• Some warehouses extended
• Some warehouses newly added
• Some customers reassignable
• Some capacity constraints
Greenfield100% optimization freedom
• Free amount of new warehouses
at Centers-of-Gravity locations
• All customers reassignable
• No capacity constraints
|100% ←- Optimization freedom -→0%|
- Fill out input table Customers.
- Select the number of Centers‑of‑Gravity, and press Calculate.
- View map and other outputs. Then change the number of Centers‑of‑Gravity and see how it affects sum of weighted distances (transport costs indicator) and service level distances.
To understand how the software calculates you can read page How to determine Centers‑of‑Gravity.
- 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 can quickly (un)check those constraints to see how those affect outcomes.
Once you have replicated the current situation you can gradually allow more optimization freedom while keeping constraints activated.
- 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.
Relaxing some constraints, you may want to implement other types of constraints:
- Limit warehouse capacities - to constrain demand volume that can be assigned to a warehouse - by filling field Capacity in the Predefined warehouses table and activating constraint "Capacity limits". Keep in mind that in the future capacity limits may not be applicable anymore, if additional space can be rented or the owned facility expanded.
- Group customers for single sourcing to enforce all customers within a group (free format, what group stands for is up to you) to be assigned to a single warehouse, by filling field Group in the customers table (for some or all customers) and activating constraint "Customer groups". (In the demo group stands for country. Customers are grouped per country. Group is used to avoid that customers in the western part of France are delivered by a warehouse in the UK.)
Besides, you can run a sensitivity analysis that indicates how much transport costs increase if a warehouse is located outside the Center-of-Gravity. An area around the Center-of-Gravity is drawn. At the area border the transport costs of the warehouse would increase x%. The higher x is set, the larger the (irregularly shaped) area becomes.
A Center‑of‑Gravity analysis usually focuses on the demand side with its relatively high transport costs and lead time requirements. But you can add the supply side to optimize supply transport costs as well. Adding the supply side becomes more relevant if there are a few major supply locations, such as a harbour, in which case a warehouse should move towards the harbour.
Because supplier shipments are larger than customer shipments - which makes supplier transport relatively cheaper - suppliers pull Centers‑of‑Gravity relatively less than customers. Differentation between customer and supplier transport rate is handled in subsection "Optional constraints and Parameters".
Flows from suppliers to customers are constructed automatically. You chan choose from 3 supply options:
- Each supplier delivers to closest warehouse* only
- Each supplier delivers to each warehouse
- Each supplier delivers to each warehouse via closest warehouse** Closest warehouse (auto-detected) can be overruled by specifying a predefined warehouse in the supplier table
Under option 1 each supplier - like a customer - pulls one warehouse (though relatively less).
Under options 2 and 3 each supplier - unlike a customer - pulls all warehouses.
Demand side onlyCenters‑of‑Gravity are pulled by customers only
Supply option 2All Centers‑of‑Gravity are pulled towards a major supplier.
Supply option 3Especially the closest warehouse is pulled towards a major supplier.
You can quickly (de)activate the supply side and see how this affects the Centers‑of‑Gravity locations. Note that you can no longer directly compare the solution value to the value of a model without supply.
Run sensitivity analysisThe software supports:
- the creation of an area around each Center-of-Gravity on the map that shows where it can be located before its transport costs would increase more than X%.
- the randomization of the demand quantity of each customer with ±X%, after which you can investigate how it affects the solution.
Remark: broader supply chain network design perspectiveTransport costs are only a part of supply chain costs, and 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, 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 do a Center‑of‑Gravity-analysis in a supply chain network design, as it provides useful insights.
Collect customer adresses and demand quantitiesRetrieve customer addresses and demand quantities and/or shipment data from your system. Ideally, express demand quantities in the main transport cost driver applicable for your business: weight, volume or volumetric weight.
- Consider seasonality: take a full year of data if your business is seasonal.
- Demand can be based on sales order quantities × item master dimensions. But most likely, your item master will not be 100% clean. It may contain items that accidentally got 'kilogram' instead of 'gram' as UoM. This may cause large errors when calculating volumes. So, if available, then collect shipment data with actual (pay)weight or volumes.
- Validate your input data
- Check for zero and empty values.
- Check item master (sold products only). For example, does kilogram/m3 make sense?
- Check for outliers. For example, calculated shipment sizes that exceed truck capacity.
- Check completeness. For example, compare number of orderlines to a warehouse productivity report.
- Check top-X customers list. Major customers missing? Unknown/small customers appearing?
- Check demand map. Gaps? Unknown large locations?
- Though not used as input by the Centers‑of‑Gravity Calculator, product groups and sales channels may become relevant when designing your supply chain network in more detail. Define relevant product groups/levels - related to your network design questions - before data collection.
Include growth projectionsDesign for the future: include growth projections if those are substantial and different (per product group) per region.
Geocode adresses (and aggregate demand)Geocoding is the process of converting addresses (like a street address) into geographic coordinates (latitude and longitude). Those are used for creating locations and flows on the map, and in (distance) calculations. See Free Batch Geocoder or Batch Geocoder if you still need to retrieve latitudes and longitudes of locations.
Consider aggregating demand per latitude/longitude (using an Excel pivot table), especially when creating a demand map. Without aggregation customers with the same latitude/longitude are plotted on top of each other and a relatively small dot will appear on the map. After aggregation a bigger dot will appear, which better reflects underlying volumes.
Consider harboursIf far-away-customers are delivered via an exit harbour, then put the aggregated far-away-customers' demand on top of that harbour, instead of their original location in the demand country. The harbour may be located in opposite direction of the demand country, seen from a warehouse perspective, and a warehouse should be pulled in the right direction in the optimization process!
Consider regional setupsYou may want to split your data set. For instance, if you already know that you will operate a warehouse/warehouses in the UK to deliver UK/IE customers only, then split your data set into 'UK data' and 'mainland Europe data' and run the model for both sets separately. If it is about a single UK warehouse only, then - alternatively - you can link UK/IE customers to a predefined UK warehouse (that is allowed to move), without having to split the data set.
Optional: Collect supplier adresses and supply quantitiesYou may want to add suppliers so supplier (and interdepot) transport costs are also taken into account when optimizing Centers‑of‑Gravity.
Feedback and suggestions for improvement are welcomedStellingConsulting
Centers‑of‑Gravity Calculator explained • How to calculate Centers‑of‑Gravity
Centers‑of‑Gravity Calculator determines indicative warehouse locations that minimize transport costs. How does it work? The section below explains the core algorithms of Center‑of‑Gravity‑Calculator. This explanation applies to any software that properly calculates Centers‑of‑Gravity.
Centers‑of‑Gravity are indicative warehouse locations that minimize 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 resultant force never becomes 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. The controlled move distance enables a feature of Centers‑of‑Gravity Calculator: allowing predefined warehouses to move within a limited range. They may need to end up somewhere at the border of this range and Weiszfeld's algorithm as such 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 an explicit move distance, so no need to worry about its initialization value. Under the Single‑Center‑of‑Gravity algorithm: 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 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, FTL pallet rate/kilometer is lower than LTL pallet rate/kilometer, macro-economic imbalances cause direction-dependent rates.
Besides, as-the-crow-flies distances × circuitry factor are used as approximation of road distances. What is meant with road distance? The distance of the fastest or the shortest route? The fastest route is usually more relevant, as driver and truck cost are more time-related than distance-related. But the fastest route may depend on the time of the day, and on the day of the week. Reality is complex. As the estimation errors will be more or less the same for each direction, approximations are 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.
Web app Centers‑of‑Gravity CalculatorWeb app Centers‑of‑Gravity Calculator (or simply scroll to the top of the page) 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.
Besides, Centers‑of‑Gravity Calculator offers more advanced functionality to run a supply chain Center‑of‑Gravity analysis. For instance, you can predefine existing warehouse locations including capacity limits.