Split-order consolidation optimization for online supermarkets: Process analysis and optimization models

Abstract

The large-scale online supermarket is a newly emerging online retailing mode which brings great convenience to people. Online supermarkets are characterized by having large amounts of daily orders with potentially multiple items, diverse delivery times, and a high order-split rate. Multiple shipments for one order caused by order splitting result in high cost and disturbance and a large number of discarded consumable packages at online retailers and customers, causing severe damage to the environment. Accordingly, research on split-order consolidation fulfilment is critical for the advancement of the practice and theory in the context of highly complex online retailing. This paper first analyzes the characteristics and the challenges associated with the split-order consolidation problem that online supermarket is confronting and summarizes the new operational process of split-order consolidation fulfilment. Then, a time–space network optimization model is built, and its corresponding solution algorithm is presented to solve the questions of where and when to consolidate the split orders. Finally, the computation results of the numerical experiments are provided to verify the effectiveness of the algorithm, and a sensitivity analysis of the relevant parameters is performed. This work highlights the effect of order consolidation processes and fulfilment methods on the order fulfilment decision-making for online supermarkets. The purpose of this article is to help pave the way for more effective online supermarket management and order implementation.

Graphical abstract

Keywords

online supermarkets / split-order consolidation / time–space network / genetic algorithm

1 Introduction

Smart logistics has gradually become a promising solution to deal with the increasing volume and complexity of logistics business (Feng and Ye, 2021) using tools, such as the Internet of Things, artificial intelligence, and intelligent algorithms. As an important part of logistics, order fulfilment usually includes: Order-warehouse assignment; item picking and packing in warehouses; and package shipping to the sorting centers, then to the delivery stations, and finally to individual customers. This step is an important aspect of online retailing and is directly related to the success of online transactions. The online supermarket is a newly emerging online retailing mode. This type of supermarket mainly sells the most frequently used daily commodities and Fast Moving Consumer Goods. Moreover, the online supermarket has rapidly become one of the most popular retailing modes. Meanwhile, the online supermarket is confronted with an awkward situation of dealing with low profits and high order fulfilment costs. Thus, an online supermarket must find a better way to fulfil its orders to save cost and reduce inconvenience to customers.

In this regard, we first analyze the features of the new online retailing mode and the complexity of its order fulfilment task and further identify several unique features of the online supermarket, in addition to the characteristics of online retailing summarized by Xu (2005) and Xu et al. (2009).

Various Stock Keeping Units (SKUs): Online supermarkets have very large-scale catalogs (e.g., food and beverages, toiletries, electronics, toys, beer and wine, meat and poultry, and fresh). However, online supermarkets need to store huge sales volume of SKUs in multiple warehouses in a big city or spread over a large area, including several cities, due to the limited capacity of a single warehouse. SKUs must be stocked in multiple category warehouses where storage overlap does not occur among individual warehouses because different storage conditions are required for the various categories of SKUs (Zhang et al., 2018).

Considerable number of average SKUs and items per order: In online supermarkets, the number of items in one order is 8–10 times the average of general online retailing orders. According to an interview with the delivery workers of yhd.com, a large-scale online supermarket in China, thousands of orders are delivered daily with an average of 7–8 SKUs and 16.7 items per order in a multi-warehouse inventory network in Shanghai (Huang et al., 2018). Xu et al. (2009) find that the number of shipments has increased by 3.75%–6% due to 10%–15% of order splitting in a large online retailer.

Multiple delivery options: Online retailing offers multiple delivery options, including two-day delivery, half-day delivery, timed delivery, and three deliveries per day.

The above-mentioned features pose new challenges to efficient order fulfilment in online supermarkets. Items in one order might no longer be shipped from the same warehouse or at the same time. A large proportion of orders with multiple items need to be split into multiple suborders first and then be fulfilled from different warehouses and/or at various times (Xu et al., 2009). Order splitting and multiple shipments for one order increase the difficulty of order fulfilment and cause higher shipping costs to the retailers, greater disturbance to the customers, and higher pollution (packing materials discarded) to the environment.

In this paper, we will examine the online supermarket order fulfilment problem that is shaped by these characteristics and address the following questions:

(1) If consolidation for split orders should be performed, then what is the new order fulfilment process?

(2) How to consolidate the split orders and timely deliver them to the customers? Where and when to consolidate?

To answer the above-mentioned two questions, we propose a new split-order consolidation fulfilment strategy. The optimal consolidating scheme is generated to minimize the total cost (including the transshipment cost, the storage cost, and the order overtime punishment cost). The number of delivery times can be reduced with this technique, resulting in an implicit reduction in environmental pollution and customer disturbance, neither of which were accurately measured in the paper.

The remainder of this paper is organized as follows. A literature review for the related work is provided in Section 2. A new operational process of order fulfilment is depicted, and the difficulty analysis of split-order consolidation of the large-scale online supermarket is conducted in Section 3. The time–space network optimization model and a solution for the split-order consolidation delivery decision problem of online supermarkets are demonstrated in Section 4. The experimental results and managerial insights are presented in Section 5. The paper concludes with a summary of the contributions and future directions for the large-scale online supermarket in Section 6.

2 Literature review

Online retailing order fulfilment has received considerable attention in academic literature, with the key issues being concerned with order splitting and consolidation. Existing research on order splitting mainly focused on assortment allocation and split-order assignment. Therefore, we divided the relevant literature into three categories: The assortment allocation of online retailing, order-warehouse assignment, and order consolidation.

(1) Assortment allocation

Assortment allocation is the problem of allocating SKUs to warehouses to minimize the number of shipments over the order history. Kök et al. (2015) review the academic literature on assortment planning. They then discuss each SKU in the shelf space allocation and point out that the dynamic classification problem is a topic worth studying. Co et al. (2007) develop a two-step heuristics algorithm by clustering frequently ordered SKUs to optimally allocate SKUs in each warehouse to minimize order splitting and maximize flexibility. Catalán and Fisher (2012) study how to assign SKUs to Distribution Centers (DCs) and propose four heuristic algorithms that are superior to the benchmark to minimize the number of split orders. Acimovic and Graves (2017) examine how to allocate inventory to Fulfilment Centers (FCs) based on a periodic-review joint-replenishment policy to minimize outbound shipping costs for a fixed amount of inventory. The measurement of assortment allocation could reduce order splitting to a certain degree from the perspective of good storage. However, this task is subject to the capacity of each warehouse and the limitation that the goods’ location cannot be frequently adjusted. A significant proportion of orders still needs to be split because one order in an online supermarket contains quite a large amount of goods on average. According to Catalán and Fisher (2012), the first large online supermarket in China, yhd.com (currently has been merged by jd.com), has found that approximately 22.68% of the orders remain to be split in a given week of 2012 utilizing the assortment allocation optimization. Therefore, a more practical and instructive measurement is needed to improve the operations related to the split-order consolidation fulfilment for daily dynamic changing orders of online supermarkets.

(2) Order warehouse assignment

Order allocation (order assignment) in online retailing is used to reduce the number of split orders in daily operations, assuming that one SKU can be stored in several warehouses. Xu et al. (2009) construct near-optimal heuristics for the reassignment of a large number of customer orders to minimize the total number of shipments. The authors find that re-evaluating order fulfilment decisions can reduce shipping costs. Jasin and Sinha (2015) prove that allocation of items to FCs for a single multi-item order is a non-deterministic polynomial (NP)-hard problem and propose a linear program (LP)-based correlated rounding scheme for multi-item order fulfilment. Acimovic and Graves (2015) dynamically allocate orders to FCs to minimize the total shipping cost and develop a heuristic algorithm that uses a linear programming program to estimate the cost of future order fulfilment. Torabi et al. (2015) propose a mixed integer programming model and a Benders’ decomposition-based approach considering the transfer of orders with transshipment. Lei et al. (2018) consider a Joint Pricing and Fulfilment problem where customer orders are fulfilled through multiple FCs to maximize the total expected profit. Ardjmand et al. (2018) propose an integrated multi-objective mathematical model for order cartonization and FC assignment in the retail industry. A decoupled mathematical model is established, and a genetic algorithm is used to solve the problem. Li and Jia (2019) suggest to combine the decision for assigning the order to FCs with the decision for routing the orders under the time window constraint. Then, they propose a Benders’ decomposition algorithm to solve the problem. Nasiri et al. (2018) integrate supplier selection and order allocation into Vehicle Routing Problems with cross-docking. The optimization of cost and responsiveness is realized. Order-warehouse allocation strategy is used to reduce order splitting for online retailers that have a network of multiple warehouses with overlapping storage of SKUs. However, the storage SKUs in different category warehouses typically do not overlap for the online supermarket. Order splitting has become inevitable even with a rational allocation strategy. Therefore, online retailers still have to fulfil a huge number of split orders from the perspective of daily operations.

(3) Order consolidation

Order consolidation reduces the delivery frequency by shipment consolidation, thus minimizing the transportation costs and environmental pollution. Hall (1987) and Stenius et al. (2016) combine two or more orders or shipments into a larger order or shipment to achieve economies of scale and improve transport operations. Satir et al. (2018) study the problem of allocating vehicle capacity between different shipment order types that are dynamically consolidated to save transportation costs. They prove that the quantity-based threshold strategy is superior to the time strategy. Wei et al. (2017) propose the optimal shipping and consolidation policy considering the delivery deadlines and the availability of expedited shipping options. Naccache and Montreuil (2015) present an optimization model for E-vendor’s consumer order consolidation. The model consolidates consumer orders into vehicles and assigns these vehicles to drop-off locations within the Third-Party Logistics (3PL) networks, consequently minimizing the total transportation cost. Zhang et al. (2019) study the problem of multiple parcels for the same customer being transported together in the distribution station, combine the orders, and send them to the customer at one time after meeting the time and cost conditions. The above-mentioned research provides valuable references for the research on the split-order consolidation delivery strategy of large online supermarkets and promotes inspiration in the time–element-based consolidation strategy. However, the demand for the consolidation of split orders of large online supermarkets cannot be satisfied due to the lack of consideration of key time factors, such as transport lead time, the diversity of split orders, the selectivity of routes, and the timeliness of orders. Thus, the optimization method of order set consolidation concerning the new characteristics and complexity of order consolidation for large online supermarkets must be studied to stabilize the process of split-order consolidation fulfilment.

3 Consolidation process for splitting orders and solution difficulty analysis

3.1 Operational process of split-order fulfilment

The order splitting problem (also known as split delivery) occurs when multi-item orders are split into several suborders that are separately fulfilled by multiple warehouses. The suborders are packed in different packages and delivered in multiple shipments (Zhang et al., 2021). Currently, large-scale online supermarkets split multi-item orders and assign the items to the corresponding warehouses; then, they fulfil the suborders and deliver the packages individually. Such an order fulfilment process would result in high distribution costs to the online retailers, great disturbance to the customers, and more discarded consumable packages to the environment.

3.2 New operational process of split-order consolidation fulfilment

A new operational mode and order fulfilment process must be constructed for a large online supermarket with a multi-warehouse inventory network if the split orders must be fulfilled by consolidation. Furthermore, considering the different inventory structures of warehouses (e.g., each warehouse carries the full assortment of SKUs or no overlap of SKU storage exists among category warehouses) and specific and dissimilar requirements from customers’ orders, various split-order consolidating strategies will be required. We summarize three split-order consolidating strategies: Split-order consolidating on the warehouse, sorting center, and delivery station, respectively. A new corresponding operational mode and order fulfilment process exist for each split-order consolidating strategy.

For example, the distribution network of order O₁ is composed of two warehouses (W₁, W₂), two sorting centers, and one delivery station. Order O₁ is split into O₁₁ and O₁₂. The three feasible split-order consolidating schemes are depicted in Fig.1. Each path shown by different shapes of arrows represents one type of split-order consolidating strategy.

3.3 Solution difficulty analysis

The rapid growth of selling SKUs increases complexities of the order fulfilment process. Order splitting and split-order warehouse assignment refer to the SKUs in one order that are to be split and assigned to one or more warehouses according to the inventory structures of warehouses and specific items in the orders. Catalán and Fisher (2012) prove that the problem of SKU assignment in warehouses is an NP-hard problem for one single order with SKUs-warehouse assignment. Specifically, the number of assignment schemes will exponentially increase with an increase in SKUs and suborders, not to mention the complexity of the huge amount of daily orders for one large online supermarket.

How can O₁ be split and split orders be assigned to each warehouse? In the case of a two-level distribution network with 6 warehouses, 10 DCs, and only 1 corresponding delivery station for O₁, the number of all possible order splitting schemes for one order among the warehouses is C_6^1+C_6^2+C_6^3+C_6^4+C_6^5+C_6^6=63; the number of all possible split-order consolidation schemes on one warehouse is 6\times \left(C_6^1+C_6^2+C_6^3+C_6^4+C_6^5+C_6^6\right)=378; the number of all possible split-order consolidation schemes on one sorting center is C_6^1\times {10}^2+C_6^2\times {10}^3+C_6^3\times {10}^4+C_6^4\times {10}^5+C_6^5\times {10}^6+C_6^6\times {10}^7\approx 1.77\times {10}^7; and the number of all possible split-order consolidation schemes on one delivery station is C_6^1\times {10}^1+C_6^2\times {10}^2+C_6^3\times {10}^3+C_6^4\times {10}^4+C_6^5\times {10}^5+C_6^6\times {10}^6\approx 1.77\times {10}^6. Accordingly, the total number of possible split-order consolidation schemes for each order is 378+1.77\times {10}^7+1.77\times {10}^6\approx 1.95\times {10}^7. The scenarios are more complicated when multiple orders and more warehouses, sorting centers, and delivery stations are involved in the splitting and assignment decision. The problem studied in this paper will be a combination of three decisions, i.e., order splitting, split-order warehouse assignment, and split-order consolidation.

The divide-and-conquer technique is always used to solve a complex problem. The practices of the online retailing show that large-scale online supermarkets can split orders containing multiple items and assign the items to the corresponding warehouses; then, they can fulfil the suborders and deliver the packages independently. However, a myopic order fulfilment method might have negative effects (e.g., high distribution cost and greater disturbance to the customers). Consequently, split-order consolidation decisions must be systematically made. The key decision-making for large online supermarkets is to determine the right location and time to consolidate under different split-order consolidation strategies for various scenarios.

4 Modeling and solution for the split-order consolidation decision of online supermarkets

4.1 Time–space network optimization model for the split-order consolidation decision

The consolidation fulfilment of the split orders is particularly complicated and difficult because of the large-scale orders of online supermarkets, the complicated urban traffic conditions, and the diversity of the required delivery time of the orders. A problem-solving method must be created to generate feasible and economical split-order consolidation fulfilment schemes in an efficient and effective way and obtain a satisfying fulfilment scheme. Considering the distinguished structure of the solution network formed by the possible schemes of order splitting and split-order consolidating, we apply the modeling method of the time–space network to depict the flow of each suborder package in the network over time while integrating the geographical changes of each package. Therefore, in this section, we first build a time–space decision network for the split-order consolidation problem for the online supermarket and then present a method to achieve the best consolidation scheme of the split orders for one order.

We use the example in Fig.2 to illustrate how the split-order consolidation fulfilment decision problem can be depicted by a time–space model, in which two warehouses labelled as W₁ and W₂, two sorting centers labelled as S₁ and S₂, and the corresponding delivery station labelled as D are present. Order O₁ is split into two suborders labelled as O₁₁ and O₁₂, and they are assigned to warehouses W₁ and W₂, respectively. Three consolidation strategies are shown in Fig.2. In the first strategy, O₁₁ and O₁₂ are consolidated in warehouse W₂, in which the triangle icons represent the parcels of O₁₁ and O₁₂. Prior to that, O₁₁ flows from W₁ to W₂ waiting to be consolidated. In the second strategy, which is indicated by circle icons, O₁₁ and O₁₂ flow from their warehouses to the sorting center S₂ and then are consolidated. In the third strategy, which is indicated by square icons, O₁₁ and O₁₂ flow from their warehouses to the corresponding sorting centers and then are consolidated at the delivery station D. The time–space network is established for all three split-order consolidation processes, as shown in Fig.2. The horizontal axis represents the time, and the vertical axis stands for locations (warehouses, sorting centers, and delivery stations). Each node in the time–space network, except the source node and the sink node (destination node), represents a location of a suborder package at a specific time. An arc denotes that the package flows from the warehouse to the sorting center, or flows from the sorting center to the delivery station. When all split-order packages of an order are delivered to the consolidation location, they can be delivered together to the next destination at an appropriate time.

Let A represent the set of all arcs in Fig.2, where an arc can be represented as a four-tuple (s, t, r, t') with (s, t) indicating the start time–space node and (r, t') denoting the end time–space node. Four types of arcs can be found in the network: Source arcs, task arcs (moving arcs), dwelling arcs, and sink arcs. Each source arc connects a source node to a time–space node in the first step. A sink arc connects any time–space node to the sink node in the last step. A task arc denotes a moving activity from the time–space node (s, t) to (r, t'). A dwelling arc (s, t, s, t+1) indicates that a package is positioned at one location at time t and continues to dwell at this location during [t, t+1], without any operations.

We make the following assumptions based on the analysis of the real-world situations:

(1) All transshipments are completed by dispatching vehicles according to a fixed schedule, and the transshipments will be carried out within a certain range of durations.

(2) Only the number of packages is considered in our model, regardless of their weight and volume, because packing is out of the scope of this paper.

(3) The smallest unit of transshipments is the package of the split order.

(4) The driving time of the vehicle is unlimited.

(5) Only one package is allocated to one warehouse after an order is split, and each split order that is assigned to a warehouse can only generate one package.

(6) The storage costs of one package per unit time at different logistics node are the same.

(7) This paper only considers the total number of orders placed by all customers within a certain time duration.

4.2 Mathematical model

We formulate its corresponding nonlinear optimization model with the following notations based on the time–space network flow model in Fig.2.

The objective function Eq. (9) is to minimize the total cost consisting of the transshipment cost (including the vehicle dispatching, shipping, and vehicle routing costs), the storage cost, and the order overtime punishment costs. Equations (10)–(12) represent the restrictions of vehicle loading capacity. Equations (13)–(15) ensure the balance of vehicles entering and exiting each logistics node. Equations (16)–(18) ensure that vehicles are not reused. Equations (19)–(21) ensure that when a vehicle is used by a logistics node, it must start from it. Equations (22)–(24) ensure that the vehicle does not repeatedly visit the same logistics node. Equations (25)–(27) mean that if a split-order package transshipment exists between two logistics nodes, then there must be vehicles driving. Equation (28) guarantees that all split orders from one order can only be consolidated in one logistics node. Equation (29) guarantees that all split packages of an order flow through the consolidation location. Equations (30)–(32) are the package flow balance constraints. Equations (33)–(37) represent variable value constraints. Variable N is a large number.

4.3 Solution methodology

The optimization model for split-order consolidation delivery is a nonlinear mixed-integer programming model. In large-scale online supermarkets, the tremendous amount of orders will result in a huge number of decision variables in the mathematical model. Additionally, the mathematical model contains segmental constraints. Solving the above-mentioned mathematical model directly via the exact algorithm (e.g., branch and bound and Benders’ decomposition) is not computationally tractable. Therefore, a heuristic algorithm is proposed, which is adapted to the characteristics of the split-order consolidation delivery problem.

The split-order consolidation delivery decision-making includes the decisions of the consolidation location, the transshipment route of the package, and the subsequent vehicle dispatching and vehicle routing plan. Accordingly, the problem can be decomposed into two sub-problems: The selection of the split-order consolidation location and the vehicle routing problem. The split-order consolidation delivery problem in the large-scale online supermarket has the characteristics of a wide variety of SKUs, a considerable number of average SKUs and items per order, and multiple delivery options. Meanwhile, fast and efficient decision-making must be achieved for e-commerce logistics with large-scale orders. In comparison with other heuristic algorithms, the Genetic Algorithm (GA) is more appropriate in addressing the split-order consolidation location problem. First, the main feature of GA is the group search strategy and the information exchange between individuals in the group. This mechanism does not require restrictive assumptions about the search space and has fast random search capability and global search ability, which is suitable for quickly solving the problem of large-scale orders. Second, GA can use a chromosome coding method with a piecewise integer that accurately represents the special attribute of the order, logistics facilities, and consolidation locations. Finally, GA uses the objective function as the search information. The GA calculation is simpler and more robust. However, considering the GA’s low efficiency and premature convergence, we proposed an improved GA (IGA), which enables us to search for the best consolidation location in a more efficient way.

The second sub-question, the vehicle routing problem, is an NP-hard problem, and its problem complexity for large online supermarkets is even higher. The C–W (Clarke–Wight) saving algorithm is one of the practical algorithms for vehicle path planning. This algorithm is simple, efficient, convenient, and suitable for vehicle routing problems with large-scale orders. Moreover, this algorithm can better handle various constraints in the vehicle routing problem of the large-scale online supermarket. Meanwhile, this algorithm can combine different vehicle characteristics to improve the algorithm and generate the optimal dispatching and vehicle routing plans in a hierarchical way to more quickly achieve cost savings.

The combination of IGA and the C–W saving algorithm can better adapt to the two sub-problems. In the first stage, we will apply IGA with the elite retention strategy and the adaptive strategy to decide the consolidation location of split orders and the initial delivering routes. In the second stage, we use the C–W saving algorithm to optimize the initial delivering routes and obtain the optimal split-order consolidation delivery plan.

4.3.1 IGA for split-order consolidation location selection and initial delivering routes

To obtain the best consolidation location for large-scale orders, the GA is improved from the following three aspects. First, the order is classified and grouped before chromosome encoding to reduce the length of chromosomes and speed up the algorithm solution. Second, the traditional GA simply performs crossover and mutation, which may destroy better genes. We will adopt the elite retention strategy to avoid destructing the optimal individual to speed up convergence and computation. Third, the crossover and mutation probabilities of the traditional GA seldom change, which is prone to premature convergence. To improve the accuracy and reliability of GA, the proposed IGA adopts the adaptive strategy, which can dynamically adjust the crossover and mutation probabilities according to the fitness of the population.

The data of the orders need to be preprocessed to better adapt to the IGA before obtaining the consolidation location. We classify the orders first and then group them to decrease the length of chromosomes to improve the solving efficiency. The number of order categories can be described as an M+1 dimensional array, \left(M_1,M_2,...,M_j,...,M_M,d_i\right), for M warehouses and n delivery stations. The values of the first M dimensions are all 0–1 variables, in which M_j indicates whether a sub-package for the order exists in warehouse j (1 means yes, and 0 means no). d_i indicates the destination delivery station of the order. A total of n\times \left(2^M-1\right) possible classifications are available for an order. For example, with 4 warehouses and 32 delivery stations, the array (1, 0, 1, 0, 16) for one order means that the order only has sub-packages in warehouses 1 and 3, and its destination is delivery station 16. Accordingly, the orders with the same split-order assignment and destination can be classified into one category according to the specific values in the M+1 dimensional array. In addition, the order categories in the first stage of IGA are equally allocated into multiple groups to increase the similarity between the chromosomes, thus enhancing the algorithm efficiency. Fig.3 shows the flow chart of IGA for solving the consolidating location problem. The chart starts with a random generation of the initial population p_0 and the number of iterations g_n.

(1) Chromosome encoding

IGA is more suitable for the selection of split-order consolidation locations and transshipment routes in online retailing. The objective of the split-order consolidation routing problem is to obtain the best consolidation location and delivery routes with minimal distance and minimal time. First, a chromosome is constructed through a permutation of integer numbers 0,1,2,...,n-1. Logistics facilities are numbered by integers to indicate the specific logistics network configuration, e.g., 1, 2, 3, 4, 5, in which the first three numbers, 1, 2, and 3, represent three warehouses, and 4 and 5 represent two sorting centers. A chromosome {3, 4, 0, 5, 1, ...} is randomly generated, indicating that the first category of orders is consolidated in warehouse 3, the second category of orders is consolidated in sorting center 4, and the third category of order is consolidated at the destination delivery station of the order. After the order consolidation location is determined, the initial transshipping route of the package can be obtained according to the value of x_{ijab}.

(2) Fitness function

In this section, we redefine the objective function of the first sub-problem as the sum of the transshipment cost, the storage cost, and the order overtime punishment cost. Given that the dispatching and vehicle routing plan will be solved in the second stage, the shipment cost per package per unit distance will be used as a substitute for the transshipment cost. Therefore, the transshipment cost per order can be calculated as follows, in which n is the average number of packages loaded by vehicles:

(38)c_i^{\text{trade}}=\sum _{j\in J}\sum _{a,b\in N}{x}_{ijab}{C}_{ab}/\phantom{x_{ijab}{C}_{ab}n}n.

The objective function of the first sub-problem is:

(39)Z\left(i\right)=\sum _{i\in I}{c}_i^{\text{storage}}+\sum _{i\in I}{c}_i^{\text{trade}}+\sum _{i\in I}{c}_i^{\text{punishment}}.

The selection of fitness function directly affects the convergence speed of GA and whether the optimal solution can be found. Given that the dynamic linear calibration method can better distinguish the pros and cons of individuals and expand the optimization ability of the fitness function, it is used to define the fitness function. The specific fitness function is:

(40)fit=\rho {\left[Z\right]}^{-\ln \left[Z\right]}.

(3) Selection, crossover, and mutation

The selection operator uses the roulette selection method. The individual with the higher fitness value has a greater probability of being selected. This method can prevent the evolution of the entire population toward a poor fitness value, increase the evolution efficiency of IGA, and gradually approach the optimal solution.

Considering the features of the split-order consolidation location decision problem, the crossover operator selects a two-point crossover. The locations of consolidation centers of split orders are relatively independent, and the change of one chromosome gene will not affect the others. Fig.4 illustrates how we exchange the crossover areas.

The mutation operator adopts a random gene position mutation. We should select multiple positions for the mutation to acquire a new chromosome to obtain a better consolidation location. The diversity of the population determines the speed and the efficiency of evolution. Given that new genes are difficult to generate by only using the crossover operator, the mutation operator must break the genome of the original population to produce new genes, which will increase the diversity of the population and the probability of high-quality individuals. The length of chromosomes will be longer due to the complex nature of the decision-making problem of split order and consolidation location. In an actual operation, multiple mutation positions will be generated according to a certain proportion of the chromosome length to randomly mutate to acquire new chromosomes. The operation of the mutation operator is shown in Fig.5.

(4) Elite retention strategy and adaptive strategy

In the iterative process of IGA, an optimal individual (the chromosome X-max with maximum fitness) exists in each generation of individuals. To prevent the entire evolutionary iteration process from degenerating, without affecting the evolutionary efficiency, the elite individuals of each generation are completely retained, placed in the elite pool, and no longer executed in the follow-up process of the algorithm. Moreover, the best individuals in the elite pool are copied into the new population with a certain proportion, and the worst individuals with the same proportion from the population are deleted to make the most high-quality genes for elite individuals and increase the probability of high-quality genes being selected in the next-generation evolution.

Meanwhile, an adaptive strategy is constructed to improve the solution efficiency, making the algorithm optimization process more purposeful and reducing the probability of random walks. The crossover and mutation probabilities of a simple GA tend to be fixed during the entire iterative process, which is highly prone to random search or premature convergence. Therefore, probabilistic intervention is needed in the evolution process to dynamically adjust the probability of crossover and mutation according to the state of evolution (group fitness). We propose the following strategies for the minimizing problem:

(41)p_{\text{c}}=\{\begin{array}{c}{k}_1,f⩽f_{\text{avg}}\\ k_2\left(f_{max}-f\right)/\phantom{\left(f_{max}-f\right)\left(f_{max}-f_{\text{avg}}\right)}\left(f_{max}-f_{\text{avg}}\right),f>f_{\text{avg}}\end{array},

(42)p_{\text{m}}=\{\begin{array}{c}{k}_3,f^{\prime }⩽f_{\text{avg}}\\ k_4\left(f_{max}-f^{\prime }\right)/\phantom{\left(f_{max}-f^{\prime }\right)\left(f_{max}-f_{\text{avg}}\right)}\left(f_{max}-f_{\text{avg}}\right),f^{\prime }>f_{\text{avg}}\end{array},

where p_{\text{c}} is the crossover probability, p_{\text{m}} is the mutation probability, f_{max} is the maximum fitness value of the population, f_{\text{avg}} is the average fitness value of the population, f is the greater fitness value of the two individuals that are about to cross, and f^{\prime } is the fitness value of the individual to be mutated. \left(f_{max}-f_{\text{avg}}\right) is smaller in the convergent population than in the dispersed population. In the crossover operation, given k_1=\text{1}\text{.0} and k_{\text{2}}=\text{1}\text{.0}, the crossover probability can be calculated by Eq. (41). In this way, the chromosomes with the greater-than-average fitness can be retained as many as possible to reduce crossovers to maintain the high-quality chromosomes. In the mutation operation, given k_3=\text{0}\text{.5} and k_4=\text{0}\text{.5}, the mutation probability is calculated by Eq. (42), which can make the chromosomes whose fitness is less than the average be completely mutated and speed up the algorithm searching process. To date, the best chromosome representing the best split-order consolidation location is finally obtained.

4.3.2 Using the C–W saving algorithm to solve the vehicle routing problem

Considering the two-level distribution network with multiple types of vehicles, the vehicle routing optimization problem obtains the route from warehouse to warehouse, from warehouse to sorting center, and from sorting center to delivery station. The C–W saving algorithm should be appropriately modified to solve the problem, in which a certain logistics node is used as the central node to deliver or transport goods for the other service nodes. When packages of split orders are transshipped among warehouses, one warehouse is selected as the central node and the others as service nodes. Then, the vehicle routes from the central node to the service nodes are optimized. Each warehouse is sequentially calculated in this way. When packages are transshipped from the warehouses to the sorting centers, a certain warehouse will be regarded as the central node, while the sorting centers accepting the split-order packages will be the service nodes. Then, the routes of vehicles dispatched from each warehouse are optimized. When packages are transshipped from a sorting center to the delivery stations, the sorting center serves as the central node, and the delivery stations serve as the service nodes. The specific steps are as follows.

Step 1: Allocate K vehicles to K service nodes, and connect the central node and the service nodes to obtain K routes to form set R;

Step 2: Calculate the saving value s\left(i,j\right) of combining every two routes to form a saving value set S, and arrange the elements in S in a descending order;

Step 3: If S is empty, then go to Step 8; otherwise, go to Step 4;

Step 4: Check the maximal saving value s\left(i,j\right) (the first item in S). If nodes i and j are in the existing same route, or if the two nodes belong to existing different routes, but each is neither a starting node nor an ending node, then go to Step 7; otherwise, go to Step 5;

Step 5: Check whether the load of the vehicle is exceeded after service nodes i and j are connected. If yes, then go to Step 7; otherwise, go to Step 6;

Step 6: Connect service nodes i and j to form R according to the rules. Let K=K-1, and remove nodes i and j;

Step 7: Remove s\left(i,j\right) from S, S=S-s\left(i,j\right); go to Step 3;

Step 8: Output R and draw the vehicle route(s).

5 Numerical study

5.1 Settings of the numerical example

We simulate order fulfilment cases according to the actual operating conditions of one online retailing company to verify the practicability and effectiveness of the solution framework of split-order consolidation. The numerical experiment was carried out on an Intel(R) Core(TM) i5-8300H 2.30 GHz processor with 16 G memory and Windows 10 (64 bit) operating system, and programming and running are completed on Matlab software.

We obtained some parameters of the online retailing company’s warehousing department by surveying its orders and logistics network. The order fulfilment logistics network is composed of 5 warehouses (numbered 1, 2, 3, 4, 5), 8 sorting centers (numbered 6, 7, 8, 9, ..., 12, 13), and 32 delivery stations (14, 15, ..., 44, 45). The coordinates of the warehouses (x, y) are randomly generated between [20, 80]. Meanwhile, the coordinates of the other logistics nodes are randomly generated between [0, 100]. The number of order splitting packages is randomly generated between [2, 5], and the split-order packages of one order are randomly distributed to the warehouses. The settings of other related parameters are shown in Tab.2.

There are totally 832 order categories of split orders (containing two or more packages) and they are equally allocated into 16 groups. Due to limited space, Tab.3 only randomly lists some samples of 832 order categories belonging to different groups, where the second row indicates that order 9 has two packages in warehouses 1 and 2, and its destination delivery station is delivery station 22. Each order generated is randomly chosen from the order categories.

5.2 Computational results

Considering the running time and convergence effects, we set the number of iterations to 700 and the population size to 100. Fig.6 indicates the IGA optimization process for grouped orders, in which the thick red line represents the optimal solution of the current generation, and the thin blue line represents the average solution of the current generation. This finding shows that the objective function value (total cost) gradually decreases with the iteration times and finally remains stable with good convergence. The running time of IGA is 273.57 s, which is within an acceptable range.

Tab.4 shows some samples of the consolidation location and transshipment path of the packages of the split orders. Taking the 822nd order as an example, five split packages are packaged in warehouses 1–5. The order is consolidated at warehouse 3; hence, the sub-packages packed in warehouse 1 need to be transshipped according to 1–3–9–35, that is, from warehouse 1 to warehouse 3 and then waiting to be consolidated with other sub-packages. These sub-packages are transshipped together to sorting center 9 and finally to delivery station 35.

In the second stage, the number of dispatching vehicles and the vehicle routes are obtained based on the initial parameter settings and the package transshipping requirements obtained in the first stage. The running time in the first cycle is 13.25 s. Tab.5 shows some routes of minivans dispatched by the sorting centers to the delivery stations.

We compared the split-order consolidation method (Strategy A) with the split-order separate fulfilment method (Strategy B) to prove its effectiveness and superiority. Another nine numerical examples with the same size were randomly generated according to the original parameter settings in Tab.2 to avoid the contingency of the sample. The total number of numerical examples is 10 (examples 1–10).

The comparison of the experimental results is shown in Tab.6. We take example 2 to explain the results. The total order fulfilment cost of Strategy A is 1211583.94 yuan, of which the end delivery cost accounts for 13.21% of the total cost; while the total order fulfilment cost of Strategy B is 1454439.46 yuan, of which the end distribution cost accounts for 29.53% of the total cost. Strategy A saves 16.70% of order fulfilment costs compared with Strategy B. The overall cost of Strategy A is lower than that of Strategy B. The main reason is the reduction in the end delivery cost due to the consolidation delivery. In Strategy A, the end delivery cost accounts for a smaller proportion. The storage, delivery, and transportation costs will increase due to the split-order consolidation. However, the increase in the cost is less than the decrease in the end delivery cost. In the 10 examples, the cost savings change between 11.40% and 16.70%, with an average value of 14.46%. The proposed method of split-order consolidation delivery can reduce the total cost of order fulfilment within a small range and reduce the end delivery times and the disturbance to customers.

We compared Strategy A with several other consolidation strategies based on example 1: Take the warehouse (Strategy C), sorting center (Strategy D), and delivery station (Strategy E) as the consolidation locations, respectively. The results are shown in Tab.7. Taking Strategy B as the benchmark, Strategies A, C, D, and E save cost. The largest cost savings is 14.41% by using Strategy A, which is higher than the average cost savings of other three strategies of 7.03%. The finding reveals the superiority of Strategy A. In terms of the proportion of end delivery cost to the total cost, Strategy A is slightly higher than Strategies C, D, and E. This notion means that the storage cost, transportation cost, and other costs of Strategy A are less than those of Strategies C, D, and E in the process of split-order consolidation. Therefore, Strategy A pays less in split orders and consolidation.

5.3 Managerial insights

To explore the influence of the parameters involved in the numerical examples, we conduct a sensitivity analysis to measure the effects of certain parameters on the total cost and cost savings. Then, we provide the corresponding management recommendations for the online retailer. We consider different values of order size, unit package shipment cost, and unit package storage cost according to the parameter settings of example 1 in Tab.2.

5.3.1 Effect of order size

The order size affects the calculation of the main costs and the setting of the logistics network. Seven numerical examples with different order sizes ranging from 50000 to 110000 are designed. The numerical results are shown in Fig.7. The total cost of all strategies gradually increases with the increase in the order size. The conclusions are as follows:

(1) The total cost of Strategy C gradually approaches that of Strategy A with the increase in the order size. The larger the order size, the greater unit cost savings by strategy C;

(2) When the order size is small, a little difference can be observed in the total costs of the five order fulfilment strategies;

(3) Given that Strategy A is a combination of the other four strategies, its cost is always the smallest one among all strategies.

We further calculate the cost savings only based on the comparison of Strategies A and B, which are shown in Fig.8. The cost savings remain relatively stable when the order size ranges from 50000 to 90000. Once the order size exceeds 90000, the cost savings rapidly decrease. Specifically, the economy (cost savings) of the split-order consolidation delivery (Strategy A) will gradually decrease with the increase in the order size. This situation can be explained by the increase in the split-order packages as the order size increases. In the process of consolidation, the optimal consolidation location changes due to the limited storage capacity of the logistics nodes, resulting in a longer package transshipment path and higher transportation costs. In addition, the storage capacity of the logistics node and the percentage change of cost savings will have the same changing trend as that of the order size.

5.3.2 Effect of unit package shipment cost

Given that the shipment cost occupies a relatively large proportion of the total cost, a sensitivity analysis of the unit package shipment cost factor will be conducted. We change the unit package shipment cost at an interval of 0.01 within the range of (0.02, 0.08) to observe its influence on the total cost. The numerical results are shown in Fig.9. The greater the growth of the unit package shipment cost, the greater the total cost of all strategies. Strategy C is more positively impacted by the unit package shipment cost compared with Strategies B, D, and E because it is beneficial to reducing the number of packages and delivery times from the source logistics nodes, which gradually makes its total cost closer to that of Strategy A.

We analyze the effect of unit package shipment cost on the cost savings. In Fig.10, the overall cost savings are on a downward trend with the increase in unit package shipment costs. This notion means that the economy of Strategy A is slowly decreasing. The reason is that additional shipment costs and the total cost of Strategy A increase as the scaling with the unit package shipment costs, which causes a decline in the percentage of cost savings.

5.3.3 Effect of unit package storage cost

To verify the influence of the unit package storage cost on the experimental results, we change it within the range of 0.14–0.30 at an interval of 0.02. The numerical results are shown in Fig.11. The greater the growth of the unit package storage cost, the greater the total cost of all strategies. Given that the unit package storage cost only considers the storage cost in the warehouse, the cost of using Strategy C is more impacted compared with Strategies B, D, and E.

In Fig.12, the cost savings gradually decrease with the increase in unit package storage cost. This result means that the increase in unit package storage cost has a negative impact on the economy of Strategy A.

6 Conclusions and future work

The split-order consolidation fulfilment is one of the key problems for the sustainable development of large-scale online supermarkets. This work analyzes the operational mode of split-order consolidation of the large online supermarket and designs the operational process of split-order consolidation with three different consolidation strategies, consolidating in the warehouse, sorting center, and delivery station, respectively, according to the unique features of the orders, the specific layout, and the functional configuration of the warehouses. Next, three split-order consolidating strategies are incorporated in the time–space optimization model, and the corresponding solution procedure is presented to decide where and when to consolidate the split orders. The contributions of this article are twofold. 1) A novel nonlinear time–space network model is built to fully integrate the decisions of split-order consolidation location and time. We decompose the problem into two sub-problems, namely, the split-order consolidation location problem and the vehicle routing problem. Then, we combine the improved genetic algorithm and C–W saving algorithm to obtain a better solution. 2) The mathematical model built on the time–space network is simplified by using decision variables to represent the time correlation constraints in the classic planning models. The amount of constraints is reduced by increasing the number of decision variables, making it possible to model and solve the complex dynamic network flow planning of large-scale split-order consolidation problems.

Several promising directions for future research remain. The volume and weight of the package must be taken into consideration as vehicle routing restrictions to improve the practicability and accuracy of vehicle loading. Another interesting and challenging extension would be to extend the parameters of end delivery cost and optimize the last-mile delivery. Moreover, the consolidation delivery with the equipment operating capacity limitation and staff workload balance can be further explored.

References

[1] Acimovic, J Graves, S C (2015). Making better fulfillment decisions on the fly in an online retail environment. Manufacturing & Service Operations Management, 17( 1): 34–51

[2] Acimovic, J Graves, S C (2017). Mitigating spillover in online retailing via replenishment. Manufacturing & Service Operations Management, 19( 3): 419–436

[3] Ardjmand, E Sanei Bajgiran, O Rahman, S Weckman, G R Young, II W A (2018). A multi-objective model for order cartonization and fulfillment center assignment in the e-tail/retail industry. Transportation Research Part E: Logistics and Transportation Review, 115: 16–34

[4] Catalán, A Fisher, M (2012). Assortment allocation to distribution centers to minimize split customer orders. SSRN Electronic Journal, 2166687

[5] Co, H C Miller, R H Xu, X (2007). Clustering of SKUs to reduce split delivery cost and improve on-time delivery in online merchandising. California Journal of Operations Management, 6( 1): 45–51

[6] Feng, B Ye, Q (2021). Operations management of smart logistics: A literature review and future research. Frontiers of Engineering Management, 8( 3): 344–355

[7] Hall, R W (1987). Consolidation strategy: Inventory, vehicles and terminals. Journal of Business Logistics, 8: 57–73

[8] Huang, M Guo, Q Liu, J Huang, X (2018). Mixed model assembly line scheduling approach to order picking problem in online supermarkets. Sustainability, 10( 11): 3931

[9] Jasin, S Sinha, A (2015). An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment. Operations Research, 63( 6): 1336–1351

[10] KökA GFisherM LVaidyanathanR (2015). Assortment planning: Review of literature and industry practice. In: Agrawal N, Smith S A, eds. Retail Supply Chain Management: Quantitative Models and Empirical Studies. Boston, MA: Springer, 175–236

[11] Lei, Y M Jasin, S Sinha, A (2018). Joint dynamic pricing and order fulfillment for ecommerce retailers. Manufacturing & Service Operations Management, 20( 2): 269–284

[12] Li, S Q Jia, S (2019). A Benders decomposition algorithm for the order fulfilment problem of an e-tailer with a self-owned logistics system. Transportation Research Part E: Logistics and Transportation Review, 122: 463–480

[13] Naccache, S Montreuil, B (2015). Optimizing consumer order delivery consolidation in drop-ship based B2C distribution. IFAC-Papers OnLine, 48( 3): 1996–2001

[14] Nasiri, M M Rahbari, A Werner, F Karimi, R (2018). Incorporating supplier selection and order allocation into the vehicle routing and multi-cross-dock scheduling problem. International Journal of Production Research, 56( 19): 6527–6552

[15] Satir, B Erenay, F S Bookbinder, J H (2018). Shipment consolidation with two demand classes: Rationing the dispatch capacity. European Journal of Operational Research, 270( 1): 171–184

[16] Stenius, O Karaarslan, A G Marklund, J de Kok, A G (2016). Exact analysis of divergent inventory systems with time-based shipment consolidation and compound Poisson demand. Operations Research, 64( 4): 906–921

[17] Torabi, S A Hassini, E Jeihoonian, M (2015). Fulfillment source allocation, inventory transshipment, and customer order transfer in e-tailing. Transportation Research Part E: Logistics and Transportation Review, 79: 128–144

[18] WeiLJasinSKapuscinskiR (2017). Shipping consolidation with delivery deadline and expedited shipment options. Ross School of Business Paper No. 1375

[19] XuP J (2005). Order Fulfillment in Online Retailing: What Goes Where. Dissertation for the Doctoral Degree. Cambridge, MA: Massachusetts Institute of Technology

[20] Xu, P J Allgor, R Graves, S C (2009). Benefits of reevaluating real-time order fulfillment decisions. Manufacturing & Service Operations Management, 11( 2): 340–355

[21] Zhang, Y K Huang, M F Hu, X P Sun, L J (2018). Package consolidation approach to the split-order fulfillment problem of online supermarkets. Journal of the Operational Research Society, 69( 1): 127–141

[22] Zhang, Y K Lin, W H Huang, M F Hu, X P (2021). Multi-warehouse package consolidation for split orders in online retailing. European Journal of Operational Research, 289( 3): 1040–1055

[23] Zhang, Y K Sun, L J Hu, X P Zhao, C (2019). Order consolidation for the last-mile split delivery in online retailing. Transportation Research Part E: Logistics and Transportation Review, 122: 309–327

RIGHTS & PERMISSIONS

Higher Education Press