An Optimization Approach for Store Clustering in Q-Commerce
Introduction
The online food and grocery delivery industry has experienced rapid growth in recent years, particularly fueled by the global impact of the COVID-19 pandemic. With the prevailing uncertainties and lifestyle adjustments brought about by the pandemic, people have increasingly turned to mobile applications as a convenient means to satisfy their culinary and grocery needs. This surge in digital reliance has significantly enhanced the efficiency of daily life, saving both time and effort for consumers.
However, this exponential growth in the online delivery sector has not been without its challenges. The operational landscape has become increasingly intricate, necessitating the development of robust systems to address the emerging complexities. As we delve into the narrative, a particular operational problem within the realm of food delivery comes to light, and we explore how the power of optimization is harnessed to confront and overcome this challenge.
This story not only unveils the complexity of an operational dilemma but also delves into alternative approaches that could be explored in the quest to resolve the issues at hand. The dynamic nature of the online food and grocery delivery business requires continuous innovation and adaptability, and this story seeks to shed light on the multifaceted strategies employed to navigate the evolving landscape of this burgeoning industry.
Problem Environment
In the food delivery environment, each courier is assigned either a single delivery or multiple deliveries to meet the current customer demand in real-time. Numerous challenges lie ahead to ensure the satisfaction of our customers. Fluctuations in demand can lead to unforeseen complexities, causing our initially planned courier workload to exceed predictions. During such periods, our couriers might need to carry more than a single delivery to meet the heightened customer demand. These specific deliveries are referred to as bundled deliveries.
However, bundled deliveries must have some limitations; otherwise, they could create much more complex issues to deal with. The most basic and fundamental condition for bundling deliveries is that they must be from the same restaurant. With this condition, couriers can easily determine the restaurant’s location even if there are multiple deliveries to be made to customers. Consequently, it becomes more manageable to handle deliveries when there is a single store assigned to a single courier.
However, challenges arise in crowded areas, such as shopping malls and city centers, where numerous meal restaurants are clustered together. The close proximity of stores in these bustling areas prompted us to reevaluate our delivery bundling scheme. This raised the question: “Can we send a single courier to multiple stores to handle multiple deliveries?” This question became the primary motivation behind initiating and exploring the possibilities of this project.
In figure 2 you can see a clustering of multiple stores as an example. By doing so, we could bundle more deliveries and save courier’s start to pickup distance cost.
Start to pickup=(courier’s current location to store location)
Optimization Model
There are several clustering algorithms that could potentially be useful in tackling this problem, including DBSCAN, K-means, and their variations. However, we made the decision to address this problem using the power of optimization. Other clustering algorithms proved less effective in meeting our operational objectives. Additionally, incorporating distance and delivery load limitations for each cluster, as required for other clustering algorithms, was time-consuming. This consideration was especially significant given that we needed to tailor the algorithms to align with the specifics of our operational problem.
To address these challenges, we developed and implemented an Integer Programming (IP) mathematical model. This model provides the number of clusters and the stores assigned to each cluster as output. Below, you will find an example of our IP model along with corresponding explanations:
The model’s objective is to minimize the number of cluster centers chosen to serve as the central point for each cluster. This objective ensures the efficient consolidation of as many stores as possible within a cluster. A set of constraints is then applied to enforce that the maximum distance within each cluster does not exceed a pre-determined value, and similarly, the total delivery load of that cluster does not surpass the specified load limitation. By employing this mathematical model, we can systematically determine which stores can be appropriately clustered and which ones cannot. However, it’s important to note that this model exhibits a weakness, or in terms of operations research, it has “multiple optimal solutions.” The following figure provides an example illustrating this weakness.
Considering we select a clustering decision, such as version 1, it can still satisfy the constraints and remains the best solution available. However, the overlap of stores between clusters could cause a lack of tracking orders and assigned couriers’ delivery history for operation teams. Then, we need a smoothing model which has the same number of clusters and constraints (1b)-(1f) as in the explained model but the objective is revised as to minimize the total distance between the stores within clusters. After our smoothing model we could have the desired result such as in version 2 of the (Fig.3).
The second mathematical model, as mentioned above, performs the task as expected. The distinction lies in the fact that our objective now is to minimize the total distance of assigned store locations to each cluster center while constraining the number of deployed cluster centers (denoted as ‘p’), using the results obtained from the previous mathematical model. This approach aims to achieve a superior outcome in terms of inter-cluster distances.
Results and Acknowledgements
Utilizing optimization algorithms to address operational problems proves to be crucial and impactful when dealing with a well-defined problem and a set of constraints. The success of this approach is contingent on fostering strong relationships between business partners who possess insights into operational challenges and needs, and technology partners who are both agile and open to approaching problems with innovative perspectives. Through this collaborative effort, we achieved a significant accomplishment — realizing more than a 10% uplift in the number of bundled orders within just a few weeks of going live. This success highlights the effectiveness of a synergistic partnership in implementing optimization solutions for operational enhancement.
Join Us
We’re building a team of the brightest minds in our industry. Interested in joining us? Visit the pages below to learn more about our open positions.
