A common problem across industries is how to best distribute supply points across an area. We define a supply point as any establishment which should be positioned close to demand points or ‘accounts’ to which they provide some goods or services. A supply point might refer to different things for different industries: a warehouse, a centralized kitchen, a clinic, a utility cabinet, an evacuation center to give a few examples.

**Setting Up the Problem**

The problem of distributing supply points can be attacked in a variety of ways. We take 3 steps to simplify the problem:

- 1.Demand Point Clustering

Demand points which are near each other can practically be considered to be one demand point. For example, demand points within the same mall would likely receive supply from the same supply point. Grouping together demand points reduces computations required in succeeding steps. We use the Mean Shift clustering algorithm to group together demand points within a specified distance from each other [7].

To provide an example, we apply our procedure to convenience stores, supermarkets and shopping centers in the Greater Manila Area (GMA). The resulting clusters are shown in Figure 1.

Figure 1. Clusters of demand points in GMA.

- Candidate Generation

Candidates are the possible locations for supply points being considered. We generate candidates by taking road points in fixed distance intervals along specified classes of roads.

In our sample run, we take 1000 meter intervals along primary, secondary, tertiary and trunk roads in GMA. The resulting candidates are shown in Figure 2.

Figure 2. Candidates generated in GMA

- Distance Computation

We use OpenTripPlanner to compute the duration of a trip from each candidate to each demand point travelling along roads by car.

After these 3 steps have been carried out, the task is simplified to selecting a combination of candidates to best supply the demand points, knowing the trip duration between each pair.

An Ideal Model

An Integer Linear Program (ILP) can be formulated to solve the supply point problem. The formulation shown in figure 3 minimizes the average distance from each cluster to the closest facility. Clusters are weighted by the number of accounts they contain to give more emphasis to minimizing the distances between the accounts and the closest facility assigned to them. The decision variable buildc denotes that we aim to decide which candidates we should select to build facilities on. The model only selects builds a specified number of facilities denoted as build limit.

Figure 3. Ideal ILP Model for Supply Points

While this is an ideal formulation, its weakness lies in the variable assignacand constraints denoted as ac. These variables and constraints scale along a * c. That is, if we were dealing with 1000 account clusters and 1000 candidates, we would have 1 million variables and 1 million constraints. This means that the model would take a very long time to solve using exact methods (those that guarantee optimal solutions). When used in large problems with numerous variables and constraints, the effectiveness of the exact methods (branch-and-bound, cutting plane) drops and the solution time and memory requirements increase [8].

Because of these weakness, we consider a partial search methods to solve the problem. These methods do not guarantee optimal solutions, but provide a near-optimal solution in a reasonable amount of time. In particular, we formulate a Genetic Algorithm (GA) to solve this problem.

A Nearly Ideal Solution

Genetic Algorithm an optimization technique inspired by Charles Darwin’s theory of natural evolution [1]. It can solve constrained and unconstrained optimization problems through the use of natural selection, or the process that if often referred to as biological evolution. Unfit “genes” or individual solutions are eventually removed in favor of more fit individuals. A specified metric is chosen to measure the fitness of an individual solution [2].

The algorithm utilizes a population of individual solutions, modifying them through successive iterations termed as generations. Within each generation, the genetic algorithm randomly selects parents from the population to mate and produce offspring for the next generation. Through these generations, some individuals may undergo changes known as mutations to ensure that the population can escape local optima. Lastly, the algorithm selects surviving individuals in each iteration, giving priority to more fit individuals. The population eventually “evolves” toward more optimal solutions. Figure 4 provides a simple flowchart for GA.

Figure 4. Flowchart for Genetic Algorithm Process

GAs have a wide number of applications and uses in optimizing decisions (e.g., [2], [3], [4]). Aside from advantages in performance, GA can be formulated to consider non-linear and highly complex constraints which are impractical to incorporate in ILPs.

GA for the Supply Point Problem

We formulate a variant of genetic algorithm to solve the supply point problem in a reasonable amount of time. Our formulation provides a near-optimal solution to the ideal ILP - that is, it aims to minimize the average distance from each cluster to the closest facility.

- Individual Definition

In our formulation, an individual is represented by a list of candidate ids, referring to the candidates selected as facilities. For example, if the desired number of facilities is 5 , the following could be a sample individual:

These numbers indicate the index number of the respective candidate locations chosen to be built. For our initial population, each individual is a random sample from the pool of candidates generated.

Because it is more intuitive to formulate GA as a maximization procedure, the fitness function we use is the negative sum of the duration from each account to its closest facility. This metric is used to identify which individuals are more fit relative to other individuals.

2. Parent Selection

From each generation, parents are selected to produce offspring solutions which comprise the next generation. The probability for an individual to be selected as a parent is directly proportional to their corresponding fitness. An example of this is shown below wherein the fitness is clearly correlated with the probability of being picked.

This process allows more optimal solutions to be chosen. The selected parents would then go through another stage called the mating function.

3. Mating Function

In our GA, the mating function pools of the selected candidates of the two parents. We then randomly select from the pool a number of candidates equal to the build limit. This would be their offspring solution set. A visual representation of the mating function would be as follows:

4. Mutation Function

The mutation function ensures that the algorithm doesn’t get stuck in a local optima. In our formulation, we mutate by randomly selecting one candidate from the individual and replacing it with a random unchosen candidate. Each new offspring has a small probability of mutating.

5. Survivor Selection

After a new generation is added, survivors are selected from the population. The probability of being selected as a survivor is proportional to that of the fitness of each individual. We select from the population corresponding to the set generation size without replacement.

The parent selection, mating, mutation, and survival functions are repeated based on the number of generations specified.

Testing the Procedure for the Greater Manila Area

To test our GA, we run our entire procedure with the goal of finding the best way to position supply points in GMA. We use convenience stores, supermarkets and shopping centers as our target accounts.

Figure 5 illustrates an evolution curve from on of our runs. This shows the improvement of the current solution throughout generations. If the curve continues shows signs of improvement towards the end of the run, then more generations may be required to have a near-optimal solution.

Figure 5. Genetic Algorithm Evolution Curve

Figure 6 shows a sample solution produced by our GA wherein the build limit was set to 1 facility.

Figure 6.Sample Solution for GMA

Colored account clusters represent those which are within a 30 minute trip duration of the closest facility. Since only one facility was build, it was not enough to capture all clusters within a 30 minute travel duration. Figure 7 shows more solutions for build limits of 1, 5 and 9 facilities.

Figure 7. GA solutions for build limits 1 (left), 5 (center), 9 (right) facilities

These solutions represent near-optimal ways to distribute specified numbers supply points around GMA if we are supplying to convenience stores, supermarkets and shopping centers. The following table provides some metrics on the above solutions.

Build Limit | Percentage of Accounts within 30 minutes of a Facility | Average Duration of Trip to Closest Facility (minutes) | Median Duration of Trip to Closest Facility (minutes) |

1 | 83.46% | 34.24 | 20.03 |

5 | 99.06% | 11.79 | 10.57 |

9 | 99.11% | 9.68 | 8.32 |

Our procedure and GA formulation provides a scalable method of distributing supply points to meet demand over an area. Furthermore, it is straightforward to modify the GA to consider additional parameters or constraints such as set-up costs, capacity limitations or current existing facilities.

References:

[1] Mccall, J. (2005). Genetic algorithms for modelling and optimisation. Journal of Computational and Applied Mathematics, 184(1), 205-222. doi:10.1016/j.cam.2004.07.034

[2] Yang, M., Yang, Y., Su, T., & Huang, K. (2014). An Efficient Fitness Function in Genetic Algorithm Classifier for Land Use Recognition on Satellite Images. The Scientific World Journal, 2014, 1-12. doi:10.1155/2014/264512

[3] Ghaheri, A., Shoar, S., Naderan, M., & Hoseini, S. S. (2015). The Applications of Genetic Algorithms in Medicine. Oman Medical Journal, 30(6), 406-416. doi:10.5001/omj.2015.82

[4] Sari, M., & Tuna, C. (2018). Prediction of Pathological Subjects Using Genetic Algorithms. Computational and Mathematical Methods in Medicine, 2018, 1-9. doi:10.1155/2018/6154025

[5] Aly, A.H. & Peralta, R.C. (1999). Comparison of a genetic algorithm and mathematical programming to the design of groundwater cleanup systems. Water Resources Research, 35(8):2415-2425.

[6] Jin, W., Hu, Z., & Chan, C. W. (2013). A Genetic-Algorithms-Based Approach for Programming Linear and Quadratic Optimization Problems with Uncertainty. Mathematical Problems in Engineering,2013, 1-12. doi:10.1155/2013/272491

[7] Liu, Y., Li, S. Z., Wu, W., & Huang, R. (2013). Dynamics of a mean-shift-like algorithm and its applications on clustering. Information Processing Letters,113(1-2), 8-16. doi:10.1016/j.ipl.2012.10.002

[8] Caccetta, L. and Hill, S.P. (2001), Branch and Cut Methods for Network Optimization, Mathematical and Computer Modelling 33, 517-532.