We present a blueprint algorithm which is an extension to the Greenfield algorithm. The Greenfield algorithm identifies distribution center locations based on customer demand locations where all center locations are unknown at the beginning. However, supplier may want to answer which new distribution locations are required in addition to the existing centers due to increasing customer demand. The Blueprint algorithm identifies new distribution center locations with the existing locations.
Greenfield analysis is performed to be able to design a new network with all new locations (see the Greenfield analysis). For example, supplier is entering a new market and wants to identify where to locate distribution centers to meet the customer demand. We also talk about Brownfield analysis when network structure stays the same and relations in the network change. For example, supplier may want to keep the current locations but reallocate customers to depots. Bluefield analysis is described as a combination of both brownfield and greenfield, where some part of the network is being built new and some stays the same.
The analysis answers the following questions:
We consider the customer locations in the Greenfield analysis. Demand for each customer is satisfied by a distribution center. Supplier has three existing distribution centers and evaluates to add new centers to satisfy customer demand with minimum cost.
Figure 1 shows the customer locations, corresponding annual demand, and the existing distribution center locations.
|Figure 1: Customer demand map with three existing distribution centers|
We answer the following questions as a result of the analysis:
Similar to the Greenfield algorithm, algorithm the new distribution center locations while keeping the existing centers such that total weighted distance to customers is minimized. The following summarizes the algorithm steps.
For given existing and new distribution centers such that with the corresponding minimum and maximum number of customers and the maximum distance covered by a center,
Step 0: Randomly assign customers to clusters as each cluster center is a distribution center location. For each customer, calculate the distance to each cluster center using Haversine distance formula. We define the total weighted distance as a summation of customer demand multiplied by distance to each cluster center. Then, set the total weighted distance as previous objective.
Step 1: Run a binary allocation model to allocate customers to centers.
Step 2: Set total weighted distance as current distance.
Step 3: If current distance is greater than previous distance, then stop. Otherwise, recalculate new center locations as average latitude and longitude of assigned customers to each new center and repeat Steps 1-2 until there exists no better solution with the smallest total weighted distance.
Note that this algorithm is a generalized version of the Greenfield algorithm.
If and , then algorithm solves the greenfield problem. If and , then algorithm solves the brownfield problem.
The Haversine formula calculates the shortest distance between two points on a sphere using their latitudes and longitudes measured along the surface. You can find more detailed explan
Similar allocation model in the Greenfield algorithm is used to allocate customers to distribution centers with given cluster locations.
We define model parameters and variables as follows.
Let be the set of customers and be the set of distribution centers. Let be total demand for the customer . Let be the distance from the center to customer . Let be the maximum distance covered by the center . Let be the minimum number of customers can be allocated to center . Let be the maximum number of customers can be allocated to center .K
Let be the binary variable for assigning center to customer .
The following is the binary program for allocating customers to distribution centers.
The objective of the model minimizes the total weighted distance. Constraint ensures that each customer is allocated to a center. There exists a maximum distance can be covered by each center . Each center has minimum and maximum number of allocated customers as in and , respectively. Center to customer allocation is binaries as in .
The algorithm is implemented in Python. Google OR Tools is used to solve the allocation problem.
You can find the source code at the Bluefield With_Weighted_Kmeans repository on GitHub.
The algorithm is applied on the given problem. We iterate the algorithm for . Figure 2 shows run results.