Algorithmic Symphony: Tailored Solutions for Varied Dimensions
In the fast-paced and ever-evolving landscape of e-commerce, where consumer demands ebb and flow in response to a multitude of factors, businesses find themselves in a perpetual quest for operational excellence. The Trendyol Tech Data Science-Optimization team leads this effort, integrating advanced mathematical optimization, machine learning, and cutting-edge technologies. Our unwavering commitment to innovation is manifested through a repertoire of sophisticated mathematical models and intelligent metaheuristic algorithms meticulously crafted to optimize every facet of our operations.
In addressing challenges, we adopt a comprehensive approach that actively involves stakeholders across business units, data science, and technology teams throughout the entire development process. Aligned with Trendyol’s We Live with Data philosophy, we initiate by leveraging a rich dataset to pinpoint operational challenges accurately, collaborating closely with diverse business units. Subsequently, we advance to the development and implementation of algorithms, followed by rigorous testing. Notably, our development is an ongoing process, sustained by continuous log monitoring in its final stages.
Thanks to our dedication to continuous monitoring and improvement within our development cycle, this November — the golden month of e-commerce, marked by a surge of discounts triggering a sharp rise in demand — provides us with a valuable lesson, prompting us to revisit our philosophy on algorithm design. Traditionally, our approach involved striving for the best algorithmic solution, considering its performance on instances drawn from our database of past operations. However, this approach might prove catastrophic, as new data shaped by changing customer behaviors may exhibit different characteristics. The algorithm we believe effectively addresses the problem may perform poorly, potentially resulting in operational disruptions. Consequently, relying on a single algorithm as the one ring to rule all possible problem instances diminishes the robustness of the system. In this article, we share our experience from the November discounts, specifically addressing an operational problem referred to as Worklist Creation Problem. After introducing the problem and highlighting recent challenges, we explain how we integrate multiple algorithms into a cohesive approach, creating a symphony of algorithms.
Worklist Creation Problem
In Trendyol, warehouses are organized into multiple zones. When an order with multiple items enters the system, an algorithm first identifies the combination of zones used to fulfill the demand within that order. By following this process, a pool is generated, which we refer to as Zone Combinations, each associated with a specific number of orders and, consequently, a specific number of items. The worklist creation problem is tasked with clustering zone combinations into what we call worklists. Each worklist is assigned a score known as Item per Zone (IPZ), calculated by dividing the total number of items fulfilled by that worklist by the distinct number of zones it utilizes. The objective of this problem is to maximize the average IPZ score of all generated worklists, with both lower and upper bounds on the number of orders a worklist can fulfill. It is noteworthy that this objective function aligns seamlessly with our operational target of picking orders as efficiently as possible.
The figure above depicts the process of creating worklists based on 20 hypothetical orders distributed across 4 distinct zones: 1A, 1B, 2A, and 2B. The figure highlights 4 different zone combinations, each distinguished by a unique color. Upon aggregation at the zone combination level, the resulting 4 combinations vary in terms of the number of orders and items associated with them. These specific combinations are then input into our algorithm, which generates the worklists. For the purposes of illustration, this hypothetical example yields 2 worklists. Worklist 1 incorporates the zone combinations 1A-1B-2A and 1B-2A-2B, fulfilling a total of 72 items across all 4 zones. As a result, the Item Per Zone (IPZ) score for worklist 1 is 18. Similarly, the IPZ score for worklist 2 is computed to be 34. Consequently, the overall IPZ score is determined as 26, obtained by averaging the scores of 18 and 34.
Mathematical Model and Equal Algorithm
To identify optimal worklists, i.e., clusters of zone combinations, we develop the following mixed-integer programming formulation.
Our approach begins with a mixed-integer nonlinear programming formulation, subsequently refined into the above-mentioned mixed-integer linear program through a series of systematic linearizations. Given the expansive nature of the mathematical model construction and the intricacies of specific linearization procedures, these details are omitted here, as they surpass the scope of this article. For those eager to delve into the specifics, we anticipate publishing a follow-up Medium story that delves deeper into the mathematical details outlined above.
It is a widely acknowledged fact that addressing mixed-integer programs becomes notably complex when confronted with large problem instances.
In accordance with the above fact and based on our initial computational experiments, it became evident that the scalability of the proposed MIP model for our operations was questionable. Consequently, we tailored the so-called Equal algorithm, introduced in [1], to address order batching algorithm.
The customized Equal algorithm has been operational for nearly six months, consistently delivering high-quality solutions within short timeframes. In the halcyon era of the Equal algorithm, we were safe in its efficiency and prowess, savoring the golden days of seamless operation. However, come November, the algorithm faced an unprecedented challenge as the input scales soared to magnitudes previously uncharted. The tranquility of its golden days was momentarily eclipsed by the sheer scale of complexity. We witnessed running times stretching to a worrisome 30 minutes, signalling a potential disaster for our daily workflow.
In our quest to understand the factors impacting the algorithm’s performance at such scales, we conducted a series of experiments. Ultimately, we figured out that our algorithm becomes vulnerable in the face of a vast number of distinct zones within the problem instances. The ensuing figure vividly illustrates this revelation.
Solving the Problem
Having identified the root cause, we engineered a scalable algorithm capable of accommodating an expanding array of distinct zones. Through our experiments, we observed a noteworthy reduction in running time, dwindling from a cumbersome 30 minutes to an impressive range of 10–30 seconds. However, this efficiency boost does come at the expense of compromised IPZ scores — up to a 12% sacrifice is necessary to attain this accelerated pace. Despite this trade-off, our analysis reveals that instances where the Equal algorithm falters are infrequent compared to those where it excels. Consequently, we advocate for a hybrid approach, strategically selecting the algorithm based on the dimensions of each specific problem instance.
In its essence, our system incorporates a threshold parameter, dictating that if the count of distinct zone combinations falls below the threshold, the Equal algorithm takes the reins. Conversely, if the count exceeds the threshold, the accelerated algorithm steps in, albeit with a trade-off in the objective function. This strategic approach aims to preserve the superiority of the Equal algorithm, positioning the new algorithm as an insurance for exceptionally large-scale problems. The ensuing figure illustrates the harmonious interplay of these algorithms as they collaborate seamlessly under different threshold configurations.
Conclusion
In conclusion, our journey through the challenges posed by the Worklist Creation Problem during the bustling November discounts has been transformative. The critical reassessment of our algorithmic philosophy led not only to a nuanced understanding of the limitations of singular approaches but also to the development of a hybrid solution, strategically blending the strengths of different algorithms. This adaptive strategy showcases our commitment to operational excellence in the face of dynamic e-commerce landscapes.
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.
References
