As a result of the study, locations for Pan-Asian food delivery service in Kharkiv have been found so that their network evenly covered the entire city; and different units were at an acceptable distance from each other. The company's order database allowed us to apply ML algorithms, in particular, clustering methods to find optimal locations. Three clustering models were developed and a series of experiments were conducted with each of them. The analysis of the model results allowed us to confirm both hypotheses put forward in the paper, namely: 1) reducing dimension does not skew clustering results obtained on the full database; 2) urban traffic has a significant impact on clustering results. This made us recommend pre-group the data and consider urban traffic in location tasks for the referred company.
The company’s success significantly depends on the location. It affects not only the cost of rent, access to materials, workers, transportation, but also the perception of the brand and expansion of the customer number.
Location databases have enabled companies to do initial screening themselves,
hence reducing their need to rely on external experts to providing only very specific
information on locations [
Various theoretical aspects of ML application in the location tasks are explored in
the scientific literature. Montejano et al. overviewed different location models used
within the geomarketing field, exemplifying it through the use of Geographic
Information Systems (GIS) [
A lot of papers are devoted to the location task analysis in food retail. To propose
new locations for the supermarkets, Grassi [
Geomarketing algorithms are also widely used in international and domestic
business practices. For example, WIGeoGIS [
The object of the study is the Pan-Asian food delivery service, which is tasked with finding optimal locations for a network of its units. The company is represented in several cities of Ukraine, including Kharkiv where it already has three divisions.
The company is rising rapidly, the number of its customers is growing, so the current production capacity is no longer sufficient to meet the orders flow in strict delivery time limits. Therefore, the company has a need to open two new divisions so that the load at all units was uniform, and the delivery time took no more than 15 minutes. It was decided to renovate the company structure completely closing the old units and opening new ones in the optimal locations.
Delivery time is a key location factor for this company. Thus, it was important to test the impact of urban traffic on model results.
To find the optimal locations, data on the orders made in Kharkiv last year at peak hours (from 15-00 to 21-00) were collected. During this period 36095 orders were received from 9002 customers (table 1).
To find dense areas of the customers, we decided to design clustering models.
Since it was decided to use Google Maps API [
However, according to preliminary estimates, the use of pairwise distances methods requires more than 81 million requests for a base of 9,000 clients; while for the five clusters detecting, centroid methods require about 45,000 requests for each iteration (and given that 30-40 iterations are needed for the algorithm convergence, we get about 1.5 million requests only). Thus, the centroid method has been chosen.
Nevertheless, the question of query optimization remained open. To solve this problem, it was decided to test the hypothesis that dimension reduction does not skew the results of clustering.
Thus, the following two hypotheses were put forward for consideration in the paper: 1) reducing dimension does not skew clustering results obtained on the full database; 2) urban traffic has a significant impact on clustering results.
Three clustering experiments were performed to test these hypotheses: full sample clustering, pre-grouped sample clustering, clustering based on the urban traffic data.
Mean Shift algorithm based on the centroid method was selected for clustering. Mean
shift clustering is a sliding-window-based algorithm that attempts to find dense areas
of data points. It is a centroid-based algorithm meaning that the goal is to locate the
center points of each class, which works by updating candidates for center points to
be the mean of the points within the sliding-window. These candidate windows are
then filtered in a post-processing stage to eliminate near-duplicates, forming the final
set of center points and their corresponding groups [
To use this algorithm with geographical coordinates, one has to select a distance
metric. Since the size of the sliding window was given in kilometers, it was decided to
use the Haversine metric [
The results of the baseline clustering model obtained on the full dataset are presented in Table 2 and Figure 1.
To check the first hypothesis, a weighted clustering method was used to reduce the
dimension. A centroid calculated by a weighted value considers each customer to
have individual value. The centroid is not created in the center of all customers but in
the center of the customers who most satisfy the value, one has weighted [
Using a k-means algorithm with the Haversine metric to detect 500 clusters, the coordinates of the weighted centers were obtained.
Figure 2 presents the initial points (marked red), and the weighted centers (marked purple).
Next, the set of 500 points was clustered using the Mean Shift algorithm and the following estimates were obtained (Figure 3, Table 3).
Comparative analysis of the first and second clustering results showed that the reduction of dimension does not lead to its significant skew, the obtained clusters coincide by 97%. This allowed us to use the pre-grouped dataset for the calculations, which require urban traffic data.
To consider urban traffic data, the clustering algorithm has been modified – to
measure the distance between the two points instead of the Haversine metric we used
data provided by Google Maps [
Working with the Google Maps API, the following settings were specified: type of transport was ‘car’; forecast time was ‘02.12.2019 18:00’; forecast type was ‘most likely’ (‘pessimistic’ and ‘optimistic’ estimates were also tested).
As a result of the clustering model with regard to urban traffic, the following estimates were obtained (Figure 4, Table 4).
Cluster
Comparative analysis of three clustering experiments showed that traffic data significantly affects the clustering results. This leads to the conclusion that it is necessary to consider this factor in location tasks for the referred company.
As a result of the study, locations for Pan-Asian food delivery service in Kharkiv have been found so that their network evenly covered the entire city; and different units were at the acceptable distance from each other (less than 15 minutes by car).
To find the locations, data about 36095 orders from 9002 customers were collected. The location database has enabled us to do screening using ML algorithms, in particular, clustering methods, which within a geomarketing approach, use spatial data along with general information.
Two hypotheses have been put forward for consideration, namely: 1) reducing dimension does not skew clustering results obtained on the full database; 2) urban traffic has a significant impact on clustering results.
Three clustering models were developed and a series of experiments were conducted with each of them.
Comparative analysis of the first and second clustering results showed that the reduction of dimension does not lead to its significant skew. This allows us to use the pre-grouped dataset for the calculations based on urban traffic data.
To calculate the distance between two points with regard to urban traffic, the Haversine metric has been replaced with Google Maps data. The analysis of the experiments showed that traffic data significantly affects the clustering results.
Thus, as a result of the study, both hypotheses were confirmed. This made us recommend pre-group the data and consider urban traffic in location tasks for the referred company.