Formulating and solving the integrated online order batching and delivery planning with specific due dates for orders

Formulating and solving the integrated online order batching and delivery planning with specific due dates for orders

Abstract

Keywords

1 Introduction

2 Literature review

Table 1
Comparison of our study with the available literature

Author Orders arrival (Online/Offline) Orders delivery time Vehicle routing Order pickers warehouse zoning Order Batching method

Zhang, et al. [35] Online For each zone Not Considered Multiple No Improved seed and saving algorithms based on orders urgency degree

Moons, et al. [33] Offline For each order For each order Multiple No Without batching

Zhang, et al. [36] Online Not considered Not Considered Single No Recalculation saving algorithm

Moons, et al. [13] Offline For each order For each order Multiple No Without batching

Zhang, et al. [37] Online Not considered Not Considered Single Yes Heuristic method based on recalculation saving algorithm

Schubert, et al. [10] Online For each order For each order Multiple No Without batching

Kuhn, et al. [34] Offline For each order For each order Multiple No Adaptive large neighborhood search algorithm

Our study Online For each order For each cross-dock Single Yes Seed algorithm based on the similarity degree

Table 2
Delivery intervals specification

Delivery interval Start time Finish time Order finalizing time Nextft (minute)

1 9 AM 12 PM last day, 7 PM 0

2 12 PM 3 PM same day, 8 AM 60

3 3 PM 6 PM same day, 11 AM 240

4 6 PM 9 PM same day, 2 PM 420

5.2 Algorithm A1

5.2.1 Order batching sub-problem of A1

5.2.2 Delivery sub-problem of A1

5.3.3 Achievement computation

5.3.4 Modified delivery planning model (M2)

6 Numerical experiment

6.1 Experiment parameters

Table 4
Picking-related parameters

Z= 5 CO_z= 6, ∀z = 1, …, Z

I_z= 8, ∀z = 1, …, Z SL= 48 Meter/Minute

WI_z= 2 Meter, ∀z = 1, …, Z t^p= 0.17 Minute

LI_z= 10 Meter, ∀z = 1, …, Z $t_{z}^{st}$ = 4 Minute, ∀z = 1, …, Z

Table 8
Cost analysis in cases with 3 cross-docks

Cross-docks Total orders Lower bound Algorithm Transportation cost Delay cost Total cost Total cost/Lower bound

800 98,265 A1 155,604 15,600 171,204 1.74

A2 131,003 1,000 132,003 1.34

900 113,273 A1 177,087 23,000 200,087 1.77

A2 157,268 600 157,868 1.39

3 1000 125,326 A1 190,767 57,800 248,567 1.98

A2 166,887 4,800 171,687 1.37

1100 131,116 A1 199,494 113,800 313,294 2.39

A2 202,491 24,600 227,091 1.73

Total 467,978 A1 722,951 210,200 933,151 1.99

A2 657,648 31,000 688,648 1.47

6.3.1 Effect of number of inbound trucks

Table 16
Impact of number of inbound trucks on costs

Lower Bound Number of trucks Algorithm Transportation cost Delay cost Total cost Total cost/Lower bound

2 A1 467,498 26,400 493,898 4.15

A2 426,482 12,800 439,282 3.69

3 A1 350,140 26,400 376,540 3.17

A2 318,206 9,600 327,806 2.76

118,896 4 A1 268,676 24,800 293,476 2.47

A2 224,746 22,400 247,146 2.08

5 A1 196,070 20,800 216,870 1.82

A2 191,872 1,600 193,472 1.63

6 A1 196,070 20,800 216,870 1.82

A2 192,506 2,400 194,906 1.64

Table 18
Cost of trucks based on their capacity

Trucks capacity Inbound trucks cost Rental trucks cost

100 65 260

125 85 340

150 100 400

175 115 460

200 135 540

Table 21
Impact of picking device capacity on costs

Lower Bound Batches capacity Algorithm Transportation cost Delay cost Total cost Total cost/Lower bound

4 A1 275,220 324,000 599,220 5.04

A2 275,820 269,600 545,420 4.59

5 A1 277,056 89,600 366,656 3.08

A2 261,452 31,200 292,652 2.46

118,896 6 A1 268,676 24,800 293,476 2.47

A2 224,746 22,400 247,146 2.08

7 A1 262,810 16,000 278,810 2.34

A2 212,274 8,000 220,274 1.85

8 A1 235,606 15,200 250,806 2.11

A2 213,470 9,600 223,070 1.88

7 Conclusion

References

Abstract

Keywords

1 Introduction

2 Literature review

Table 2 Delivery intervals specification Delivery interval Start time Finish time Order finalizing time Nextft (minute) 1 9 AM 12 PM last day, 7 PM 0 2 12 PM 3 PM same day, 8 AM 60 3 3 PM 6 PM same day, 11 AM 240 4 6 PM 9 PM same day, 2 PM 420

5.2 Algorithm A1

5.2.1 Order batching sub-problem of A1

5.2.2 Delivery sub-problem of A1

5.3.3 Achievement computation

5.3.4 Modified delivery planning model (M2)

6 Numerical experiment

6.1 Experiment parameters

Table 4 Picking-related parameters Z= 5 CO z = 6, ∀z = 1, …, Z I z = 8, ∀z = 1, …, Z SL= 48 Meter/Minute WI z = 2 Meter, ∀z = 1, …, Z t p = 0.17 Minute LI z = 10 Meter, ∀z = 1, …, Z t z st = 4 Minute, ∀z = 1, …, Z

6.3.1 Effect of number of inbound trucks

Table 18 Cost of trucks based on their capacity Trucks capacity Inbound trucks cost Rental trucks cost 100 65 260 125 85 340 150 100 400 175 115 460 200 135 540

7 Conclusion

References

Table 2
Delivery intervals specification

Delivery interval Start time Finish time Order finalizing time Nextft (minute)

1 9 AM 12 PM last day, 7 PM 0

2 12 PM 3 PM same day, 8 AM 60

3 3 PM 6 PM same day, 11 AM 240

4 6 PM 9 PM same day, 2 PM 420

Table 4
Picking-related parameters

Z= 5 CO_z= 6, ∀z = 1, …, Z

I_z= 8, ∀z = 1, …, Z SL= 48 Meter/Minute

WI_z= 2 Meter, ∀z = 1, …, Z t^p= 0.17 Minute

LI_z= 10 Meter, ∀z = 1, …, Z $t_{z}^{st}$ = 4 Minute, ∀z = 1, …, Z

Table 18
Cost of trucks based on their capacity

Trucks capacity Inbound trucks cost Rental trucks cost

100 65 260

125 85 340

150 100 400

175 115 460

200 135 540

Today with the outbreak of the COVID-19 many people prefer to stay home and buy their required products from online sellers and receive them in their home or office at their desired times. This change has increased the workload of online retailers. In an online retailing system, lots of orders containing different products arrive dynamically and must be delivered in the due dates requested by customers, so there is a limited time to retrieve products from their storage locations, pack them, load them on trucks, and deliver to their destinations. In this study, we deal with the integrated order batching and delivery planning of an online retailer that stores a variety of products in a warehouse and sells them online. A mixed-integer nonlinear programming model is proposed that decides on order batching, scheduling of batches, assigning orders to trucks, and scheduling and routing of trucks simultaneously in an offline setting. This model clarifies the domain of the problem and its complexity. Two rule-based heuristic algorithms are developed to solve the problem in the online setting. The first algorithm deals with two sub-problems of order batching and delivery planning separately and sequentially, while the second algorithm considers the relationship between two sub-problems. An extensive numerical experiment is carried out to evaluate the performance of algorithms in different problem sizes, demonstrating that the second algorithm by integrating two sub-problems leads to a minimum of 14% reduction in cost per delivered order, as the main finding of this study. Finally, the effect of several parameters on the performance of algorithms is analyzed through a sensitivity analysis, and some managerial insights are provided to help the retail managers with their decision-making that are the other findings of this paper.

Delivery planning online retailing order batching rule-based heuristic specific due dates

Nowadays rapid increase in the use of information technology and the improvement of e-commerce have noticeably changed the way of shopping, managing activities, and distributing products for individuals and companies [1]. Retailing is one of the industries significantly influenced by these changes. In an e-commerce context of retailing, a large number of small orders must be prepared and delivered to numerous end consumers in a limited time [2]. In an online system, orders become available dynamically when there is no information about future orders [3]. On the other hand, the spread of the Covid-19 pandemic has faced online retailers with a significant upsurge [4]. Thus, they need effective decision support systems for managing intensive daily operations to control their costs and maintain their customers’ satisfaction.

Order picking is the most costly and critical operation of any material handling system [5]. Order picking is defined as the process of retrieving items of an order from their storage locations. When there are lots of small orders, usually order batching methods are used to decrease the order picking process time. These methods, group a set of orders into a number of batches so that each batch of orders can be picked in one picking tour [6].

Recently, the fast development of e-commerce results in new challenges and opportunities for the logistics system [7]. An important issue of selling products through the internet is that orders have to be delivered to the customers, so the delivery policy needs to be considered carefully. The delivery policy determines customer areas, delivery costs, delivery time windows, and lead times [8]. Consequently, having a distribution system with reliable, effective, and efficient performance is crucial for the success of companies in the competitive marketplace [9].

In this study, we address the integrated order batching and delivery planning problem of online retailers. As mentioned before, in the online retailing systems, orders become available during the planning horizon. We also assume that orders have specific due dates. Order batching and delivery planning are two strongly interconnected problems due to the short period between the arrival of orders and delivery times [10]. The delivery planning determines whether an order should be picked immediately or can wait. On the other hand, the order batching scheduling specifies when an order is ready to be delivered. Thus, a schedule for the order batching may be favorable for the batching process but inefficient for the delivery process [10]. Therefore, balancing between these two operations is remarkably important for online retailers. A highly-efficient distribution plan, not only reduces the total transportation cost of supply chain systems but also improves customer satisfaction by delivering orders at a suitable time [11, 12].

Several newly published papers demonstrated that the integration of order picking and delivery planning problems can significantly reduce system cost compared to the use of a sequential approach [10, 13]. Because these operations need to be carried out every day, such a cost-saving in big warehouses with a huge amount of operational costs will lead to a remarkable benefit in the long term [14, 15]. However, as demonstrated in the literature review, this integration has scarcely been addressed in the online setting.

The main novelty of this study is considering three essential aspects of online retailing systems together, including the integrated planning of order batching and delivery processes, the dynamic arrival of orders during the planning horizon, and having a specific due date for each order. Simultaneous consideration of these aspects makes our work more realistic and practical. Moreover, changing the case model and its assumptions will change the research space that may make the current solution methods inefficient [16]. Meanwhile, the best study proposes a simple but effective algorithm to solve a complex problem [17]. These facts motivate us to contribute to both problem formulation and solution algorithm in the new setting. Through this study, we are going to propose a decision-making tool for the online retailers enabling them to solve their daily operational problems, demonstrating the impact of the integration of two sub-problems on the system performance and cost, and investigating the effect of changing different parameters on the results.

The contributions of this paper are as follows. First, we propose a mixed-integer nonlinear programming model for the integrated problem in an offline setting. This model clarifies the domain of the problem and its complexity. The offline model generates order batches, schedules picking of batches, assigns orders to trucks, and defines and schedules delivery routes of trucks. Second, for solving the problem in the online setting, two rule-based heuristics of A1 and A2 are proposed. A1 deals with two sub-problems separately and sequentially, so that use the output of order batching in the delivery planning. However, A2 considering the relationship between two sub-problems tries to reduce the number of delayed orders and maximize trucks’ utilization. To the best of our knowledge, our algorithms plan and schedule the operations of order picking and delivery processes jointly for a full working shift considering the dynamic arrival of orders and due dates for the first time. Third, the performance of algorithms is evaluated through an extensive numerical experiment. It is demonstrated that A2 by considering the relationship between two sub-problems can improve the performance of the system compared to A1. Moreover, a sensitivity analysis is conducted to show the effect of several parameters on the solutions. Finally, some managerial insights are provided for retail managers based on the sensitivity analysis.

The final aim of our study is to provide a practical decision-making system for online retailers to help them by effectively managing their daily operations. Our algorithms can also contribute to the design of a new retailing system, analyzing its costs and benefits as well as defining needed facilities such as the number of inbound trucks and the capacity and type of trucks. Below the highlights of this research are listed:

noticeably reducing the number of delayed orders, integrated planning of order picking and delivery processes increases customer satisfaction.

Integration of order picking and delivery planning leads to a minimum of 14% reduction in the cost per delivered order.

A correct combination of system settings such as the picking device capacity and the number and the type of trucks dramatically improves the performance of the system.

The remainder of the paper is organized as follows. Section 2 contains a review of related literature. Section 3 is the problem description. The offline integrated model is presented in section 4, and solution methods are described in section 5. Section 6 presents the numerical experiment, performance evaluation of algorithms, the sensitivity analysis, and managerial insights. Finally, section 7 includes conclusions and further research opportunities.

Order picking is one of the essential operations in retailing warehouses that many researchers have dealt with this problem in both offline and online settings. De Koster, et al. [6] presented a comprehensive review of decision problems of an order picking system. Cano, et al. [18] reviewed order batching, batches sequencing, and order pickers routing problems to identify existing methods and approaches and as well as research gaps.

In some studies, having different due dates for orders is also considered in the order picking process. In this regard, Elsayed, et al. [19] and Elsayed and Lee [20] modeled order batching and batch sequencing problems in an automated warehouse with one order picker. They used heuristic methods to solve the problems. Tsai, et al. [21] presented a multiple genetic algorithm for order batching, sequencing, and order picker routing problems with one order picker. Henn and Schmid [22] introduced two metaheuristics for the aforementioned problems. Their first algorithm was based on iterated local search, and the second one was derived from the attribute-based hill climber method. Chen, et al. [23] used a genetic algorithm for order batching and sequencing, and an ant colony algorithm for the order picker routing problem. Henn [24], Scholz, et al. [25], Menéndez, et al. [26], and van Gils, et al. [14] addressed the same problem with multiple order pickers.

In recent years, online order picking systems are more popular and many researchers have dealt with the online order batching problem. Lu, et al. [27] presented an interventionist routing algorithm for an online order picking system. They only addressed the routing problem and did not deal with order batching, then Giannikas, et al. [28] developed that algorithm by adding the possibility of order batching. Pérez-Rodríguez, et al. [29] proposed a continuous estimation of the distribution algorithm-based approach for online order batching. They assumed that orders have different arrival time but their information is available in advance, however, this assumption is not realistic in an online system because orders become available gradually. Giannikas, et al. [28] modeled joint planning of order batching and pickers routing. The order batching method was based on the similarity coefficient. For the routing problem, an ant colony algorithm was presented. They also considered the assumption of Pérez-Rodríguez, et al. [29] for orders’ arrival information.

Henn [3] modified offline order batching heuristics for the online problem to minimize the maximum order completion time. Three decision points were considered so that whenever one of them occurs the algorithm should do an action. Moreover, he used a competitive analysis to prove that used heuristics are 2-competitive. It means that the objective function of the online solution is at most twice of the offline solution. Gil-Borrás, et al. [30] developed an algorithm based on the combination of a greedy randomized adaptive search procedure and a variable neighborhood descent for the online order batching problem. Alipour, et al. [31] expanded the algorithm of Henn [3] considering multiple order pickers. Zhang, et al. [32] proposed a hybrid rule-based algorithm for order batching and sequencing problems. Their approach is somewhat similar to Henn [3], but they considered multiple order pickers and batching methods are different in some details.

Order picking and delivery planning are two main interconnected problems that integration of them will improve the efficiency and flexibility of the system [13]. In recent years some researchers have integrated these two problems. Moons, et al. [33] addressed joint order picking and vehicle routing problem and solved it optimally in small sizes when orders have different due dates and arrival times. Meanwhile, they assumed that the arrival time of all orders is available in advance. Moons, et al. [13] proposed a record-to-record travel algorithm to solve the same problem in both small-size and large-size instances. Schubert, et al. [10] developed a decision support model and a general variable neighborhood search-based algorithm to solve the joint order picking and delivery planning in omnichannel retail. They assumed same-day delivery in which customers should register their orders before a definite cut-off time. However, in all of these papers, the authors did not address the order batching problem. Kuhn, et al. [34] also proposed an Adaptive large neighborhood search metaheuristic for the joint order batching and vehicle routing problem in an offline setting.

Zhang, et al. [35] integrated online order batching and delivery planning. In their study, a third-party logistics company is responsible for the delivery operation. They assumed that each order belongs to a delivery zone, and each delivery zone has a dedicated truck with a definite departure time. If an order is not ready until the departure time of the related truck, it cannot be delivered on time and has to wait until the next day’s departure time. Their model minimizes picking time as the first objective function and maximizes the number of on-time delivered orders as the second objective function. They also proposed a rule-based heuristic algorithm to solve the problem in which, either after passing a specific time or ordering a defined number of products, the algorithm solves the offline problem using order batching and batch assignment heuristics.

Zhang, et al. [36] considered assumptions of Zhang, et al. [35] with a difference that vehicles could deliver products several times a day. The authors proposed a rule-based algorithm that solves delivery planning and order batching separately. When a new Order arrives, the order batching algorithm needs to be updated based on defined rules. In the delivery part, for each delivery zone at predefined periods, as many picked orders as possible will be allocated to the vehicle. Zhang, et al. [37] also considered the integration of order picking and delivery planning with multiple pickers incorporating learning effects in an O2O community supermarket. They proposed a rule-based heuristic to solve the problem and proved that their algorithm is 2-competitive. They also considered sequential warehouse zoning. In the delivery part, once the number of picked orders satisfies the capacity of a truck, the truck will deliver those orders.

According to the reviewed literature, while the integrated planning of order batching and delivery operations is highly beneficial [10, 13], limited studies have dealt with this issue. On the other hand, in an online system, orders arrive dynamically during the planning horizon and have different due dates. To the best of our knowledge, none of the previous studies considered these three aspects of our research together. Moons, et al. [33], Moons, et al. [13], and Kuhn, et al. [34] assumed that all orders are known at the beginning of the planning horizon. Schubert, et al. [10] considered dynamic arrival of orders until a fixed cut-off time. However, we assume that customers can register their orders every time during the day. Moreover, these studies ignored order batching problem. Meanwhile, although Zhang, et al. [35], Zhang, et al. [36], and Zhang, et al. [37] addressed integrated order batching and delivery planning with dynamic arrival of orders, they did not consider different due dates for orders. Therefore, the need for a comprehensive formulation and efficient algorithms considering real-world conditions and leading to practical solutions is obvious. Table 1 compares our research with similar studies and shows the differences and similarities between our work and other studies.

Author	Orders arrival (Online/Offline)	Orders delivery time	Vehicle routing	Order pickers	warehouse zoning	Order Batching method
Zhang, et al. [35]	Online	For each zone	Not Considered	Multiple	No	Improved seed and saving algorithms based on orders urgency degree
Moons, et al. [33]	Offline	For each order	For each order	Multiple	No	Without batching
Zhang, et al. [36]	Online	Not considered	Not Considered	Single	No	Recalculation saving algorithm
Moons, et al. [13]	Offline	For each order	For each order	Multiple	No	Without batching
Zhang, et al. [37]	Online	Not considered	Not Considered	Single	Yes	Heuristic method based on recalculation saving algorithm
Schubert, et al. [10]	Online	For each order	For each order	Multiple	No	Without batching
Kuhn, et al. [34]	Offline	For each order	For each order	Multiple	No	Adaptive large neighborhood search algorithm
Our study	Online	For each order	For each cross-dock	Single	Yes	Seed algorithm based on the similarity degree

3 Problem description

In this study, we deal with an online retailing system that sells different products through its website. Customers register their orders, select their desired delivery times among available delivery intervals, and receive the orders in predefined locations. This system conducts two essential operations of picking and delivery of orders every day. All products are stored in one warehouse. The warehouse storage area is divided into several zones so that similar products are located in the same zone. Based on the synchronized zoning method, in each storage zone, an order picker is responsible for manually retrieving items from that zone. An order may contain products from several storage zones. After picking the items from all zones, the order is ready to be delivered. The order batching method is used to reduce the picking operation time.

When the picking process of orders is completed, they should be delivered to their destinations. Because locations of customers are scattered in a large area and are usually far from the warehouse, there are several cross-docks that service customers in their neighborhood. In Cross-docking systems, orders receive to a distribution center by inbound trucks and then deliver to end-customers by outbound trucks with a minimum handling and storage cost [38, 39]. Each customer is assigned to one cross-dock. Prepared orders are transferred to relevant cross-docks by inbound and rental trucks. In this study, we do not address the distribution planning in the cross-docks. Therefore, here the delivery process refers to transferring orders from the warehouse to their relevant cross-docks so that they can be delivered to customers on time. The online order batching and delivery planning problem is defined base on the following assumptions derived from a real-world online retailing system.

The exact storage location of each product is defined, and every product is stored in only one place.

The warehouse layout in each storage zone is single-block with two cross aisles as shown in Fig. 1.

An order picker is assigned to only one zone.

If the picking process of an order does not complete on time, it will be delivered with a delay.

Special containers are used for collecting items of each order in each zone. These containers are also used in the delivery process. We assume that the requested products of a zone in each order do not exceed one container.

In each zone, the order picker uses a picking device with a specific capacity of containers.

Once an order picker starts the picking process of a batch, the list of orders in the batch can’t change.

The picking completion time of an order equals the maximum completion time of all batches of all zones to which that order is assigned.

All orders after picking from zones are transferred to a specific place in the warehouse and then, they are ready to be loaded in trucks.

Order pickers routing in each storage zone is based on the well-known s-shape method that is demonstrated in figure 1.

Order pickers work in one shift a day with a definite start and finish time.

Cross-docks have an unlimited capacity.

Each order is assigned to the nearest cross-dock.

There are limited numbers of inbound trucks with a limited capacity.

If the inbound trucks are not enough to deliver all orders, rental trucks can be used by paying additional costs.

Orders can’t be divided into two or more shipments.

We assume four three-hour delivery intervals starting at 9 AM and finishing at 9 PM.

Customers can choose one delivery interval among four available intervals after registering their orders.

The start time of the first delivery interval that a customer can choose is at least four hours after registering time.

We can assign each truck to only one delivery route in each delivery interval.

All trucks must deliver their shipments before the start time of the next delivery interval at all cross-docks in their delivery routes.

Fig.1

Warehouse structure in each storage zone and an s-shape route.

Integrated order batching and delivery planning model.

To formulate the model, the used indices, parameters, and decision variables are presented as follows:

Indices:

i : Order number index, i∈ { 1, …, O }

j : Batch number index, j∈ { 1, …, G_z }

v : Truck number index, v∈ { 1, …, V + V′ }

z : Storage zone index, z∈ { 1, …, Z }

s : Storage aisle index, s∈ { 1, …, I_z }

h : Cross-dock index, h∈ { 1, …, H }, h= 0 represents the warehouse

r : Delivery interval index, r∈ { 1, …, D }

Parameters:

O : Total number of available orders

Z : Number of storage zones

H : Number of cross-docks

D : Number of delivery intervals

V : Number of inbound trucks

V′ : Maximum number of rental trucks

G_z : Number of needed batches in zone z

I_z : Number of storage aisles in zone z

LI_z : Length of each storage aisle in zone z

WI_z : width of each storage aisle in zone z

CO_z : Capacity of a batch in zone z

a_r : Start time of delivery interval r

b_i : Delivery interval of order i, b_i∈ { 1, …, D }

$Q_{i}^{z} :$ Number of product items of order i in zone z

$N_{i}^{z} :$ 1 if order i contains at least one item stored in zone z, 0 otherwise

$I_{i}^{sz} :$ 1 if order i contains at least one item stored in aisle s of zone z, 0 otherwise

M_ih : 1 if order i is assigned to cross-dock h, 0 otherwise

cap_v : Capacity of truck v (number of product containers)

CV_v : Cost of truck v per time unit

SV : Travel speed of trucks

CD : Delay cost per order per delivery interval

SL : Order picker travel speed

t^p : The needed time for picking a product item from its shelf and putting it in the container

$t_{{hh}^{'}}^{tr} :$ Travel time between cross-docks h and h′

$t_{z}^{st} :$ Batch setup time in zone z, consisting of the needed time for traveling from the loading area to the storage area, coming back to the loading area, and unloading picking device

$t_{i}^{ar} :$ Arrival time of order i

t^l : Truck loading time

t^ul : Truck unloading time

$f_{i}^{z} :$ Distance between the right-side cross aisle and the last storage location of order i in zone z

tsd : Start time of a working day

tfd : Finish time of a working day

Independent decision variables:

$x_{ij}^{z} :$ = 1 if order i is assigned to batch j in zone z, 0 otherwise

${ts}_{j}^{z} :$ Picking start time of batch j in zone z

u_rv : 1 if truck v is used in delivery interval r, 0 otherwise

td_rv : Departure time of truck v in delivery interval r

y_hh′rv : 1 if truck v visits cross-dock h′ after cross-dock h in delivery interval r, 0 otherwise

w_irv : 1 if order i is delivered by truck v in delivery interval r, 0 otherwise

Dependent decision variables:

$t_{j}^{z} :$ Picking time of batch j in zone z

${dis}_{j}^{z} :$ Order picker travel distance for picking batch j in zone z

$t_{i}^{opc} :$ Picking completion time of order i

$I_{j}^{zs} :$ 1 if batch j contains at least one item stored in aisle s of zone z, 0 otherwise

${lf}_{j}^{z} :$ Distance between the right-side cross aisle and the last storage location of batch j in zone z

d_i : Number of delayed delivery intervals of order i

As mentioned before, order pickers routing is based on the s-shape method. In this routing method, the order picker only visits aisles from which at least one product should be picked and then comes back to the start point. All visited aisles are traversed entirely unless the last aisle. If the number of visited aisles is even, the order picker visits the last aisle entirely, and if the number of aisles is odd, the order picker will traverse the last aisle from the right side to the last storage location and then come back [40]. Consequently, the traversed distance of batch j in zone z can be computed through Equation (1). ${dis}_{j}^{z} = {\begin{matrix} ({LI}^{z} . \sum_{s = 1}^{I_{z}} I_{j}^{zs}) + (2 . {WI}^{z} . \max {s | s \in I^{z}, I_{j}^{zs} = 1}) & if the number of aisles is even \\ ({LI}^{z} . \sum_{s = 1}^{I_{z}} I_{j}^{zs}) + (2 . {If}_{j}^{z}) + (2 . {WI}^{z} . \max {s | s \in I^{z}, I_{j}^{zs} = 1}) & if the number of aisles is odd \end{matrix}$ (1) The picking time of a batch consists of three parts: 1. Order picker travel time. 2. The time for picking items from shelves and putting them into the containers. 3. Batch setup time. Equation (2) expresses the picking time of batch j in zone z. $t_{j}^{z} = \frac{{dis}_{j}^{z}}{SL} + t^{p} . \sum_{i = 1}^{O} x_{ij}^{z} . Q_{i}^{z} + t_{z}^{st}$ (2) The integrated model aims to deliver the maximum number of orders on time, by minimum cost. The cost includes transportation cost and delay cost. In this model, we assume that all orders are available at the beginning of the planning horizon (the offline setting). Based on the aforementioned assumptions, the integrated order batching and delivery planning model is formulated as follows. $Minz = \sum_{v = 1}^{V + V^{'}} \sum_{r = 1}^{D} \sum_{h = 0}^{H} \sum_{\begin{matrix} h^{'} = 1, \\ h^{'} \neq h \end{matrix}}^{H} y_{{hh}^{'} rv} . {CV}_{v} . (t_{{hh}^{'}}^{tr} + t^{ul}) + \sum_{v = 1}^{V + V^{'}} \sum_{r = 1}^{D} \sum_{h = 1}^{H} y_{h 0 rv} . {CV}_{v} . t_{h 0}^{tr} + \sum_{i = 1}^{O} d_{i} . CD$ (3) $\begin{matrix} s . t . : \\ \sum_{j = 1}^{G_{z}} x_{ij}^{z} ⩽ N_{i}^{z} \forall i \in {1, \dots, O}, \forall z \in {1, \dots, Z} \end{matrix}$ (4) $\sum_{i \in O} x_{ij}^{z} ⩽ {CO}_{z} \forall z \in {1, \dots, Z}, \forall j \in {1, \dots, G_{z}}$ (5) $I_{j}^{zs} ⩽ \sum_{i \in O} I_{i}^{zs} . x_{ij}^{z} \forall z \in {1, \dots, Z}, \forall j \in {1, \dots, G_{z}}, \forall s \in {1, \dots, I_{z}}$ (6) $I_{j}^{zs} ⩾ \frac{\sum_{i \in O_{1}} I_{i}^{zs} . x_{ij}^{z}}{| O |} \forall z \in {1, \dots, Z}, \forall j \in {1, \dots, G_{z}}, \forall s \in {1, \dots, I_{z}}$ (7) ${ts}_{j}^{z} ⩾ {ts}_{j - 1}^{z} + t_{j - 1}^{z} \forall z \in {1, \dots, Z}, \forall j \in {2, \dots, G_{z}}$ (8) $t_{i}^{opc} ⩾ {ts}_{j}^{z} + t_{j}^{z} - M . (1 - x_{ij}^{z}) \forall i \in {1, \dots, O}, \forall z \in {1, \dots, Z}, \forall j \in {1, \dots, G_{z}}$ (9) $t_{i}^{opc} ⩽ {td}_{rv} - t^{l} + M . (1 - w_{irv}) \forall i \in {1, \dots, O}, \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}}$ (10) ${td}_{rv} ⩾ {td}_{r - 1, v} + \sum_{h = 0}^{H} \sum_{\begin{matrix} h^{'} = 0, \\ h^{'} \neq h \end{matrix}}^{H} y_{{hh}^{'} r - 1, v} . (t_{{hh}^{'}}^{tr} + t^{ul}) - (t^{ul} . u_{r - 1, v}) + t^{l} - M . (1 - u_{rv})$ (11) $\begin{matrix} \forall r \in {2, \dots, D}, \forall v \in {1, \dots, V} \\ {td}_{rv} + \sum_{h = 0}^{H} \sum_{\begin{matrix} h^{'} = 1, \\ h^{'} \neq h \end{matrix}}^{H} y_{{hh}^{'} rv} . (t_{{hh}^{'}}^{tr} + t^{ul}) ⩽ a_{r} \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}} \end{matrix}$ (12) $\sum_{v = 1}^{V + V^{'}} \sum_{r = 1}^{D} w_{irv} ⩽ 1 - \frac{\sum_{z = 1}^{Z} N_{i}^{z} - \sum_{z = 1}^{Z} \sum_{j = 1}^{G_{z}} x_{ij}^{z}}{\sum_{z = 1}^{Z} N_{i}^{z}} \forall i \in {1, \dots, O}$ (13) $w_{irv} ⩽ u_{rv} \forall i \in {1, \dots, O}, \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}}$ (14) $d_{i} ⩾ \sum_{v = 1}^{V + V^{'}} \sum_{r = 1}^{D} r . w_{irv} - b_{i} \forall i \in {1, \dots, O}$ (15) $d_{i} ⩾ R - M . \sum_{v = 1}^{V + V^{'}} \sum_{r = 1}^{D} w_{irv} \forall i \in {1, \dots, O}$ (16) $\sum_{h^{'} = 0}^{H} y_{{hh}^{'} rv} = \sum_{h^{'} = 0}^{H} y_{h^{'} hrv} \forall h \in {1, \dots, H}, \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}}$ (17) $\sum_{h = 1}^{H} y_{0 hrv} = u_{rv} \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}}$ (18) $\sum_{h = 1}^{H} y_{h 0 rv} = u_{rv} \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}}$ (19) $\sum_{h \in S} \sum_{h^{'} \in S} y_{{hh}^{'} rv} ⩽ | S | - 1 \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}}, \forall S \subseteq {1, \dots, H}, 2 ⩽ | S | ⩽ H$ (20) $\sum_{h^{'} = 0}^{H} y_{{hh}^{'} rv} ⩾ w_{irv} . M_{ih} \forall i \in {1, \dots, O}, \forall h \in {1, \dots, H}, \forall r \in {1, \dots, D},$ (21) $\forall v \in {1, \dots, V + V^{'}}$ $\sum_{i = 1}^{O} w_{irv} . \sum_{z = 1}^{Z} N_{i}^{z} ⩽ {cap}_{v} \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}}$ (22) ${ts}_{1}^{z} ⩾ tsd \forall z \in {1, \dots, Z}$ (23) ${ts}_{j}^{z} + t_{j}^{z} ⩽ tfd \forall z \in {1, \dots, Z}, \forall j \in {1, \dots, G_{z}}$ (24)

$\begin{matrix} x_{ij}^{z}, y_{{hh}^{'} rv}, w_{irv}, I_{j}^{zs}, u_{rv} \in {0, 1}, {ts}_{j}^{z}, {td}_{rv}, d_{i} ⩾ 0 \\ \forall i \in {1, \dots, O}, \forall z \in {1, \dots, Z}, \forall j \in {1, \dots, G_{z}}, \forall h, h^{'} \in {1, \dots, H}, \\ \forall r \in {1, \dots, D}, \forall v \in {1, \dots, V + V^{'}} \end{matrix}$ (25)

The objective function (3) consists of three parts. The first part computes the transportation cost from the warehouse to the last cross-docks. The second part considers travel cost from the last cross-docks to the warehouse, and the third part expresses the delay cost. Equation (4) guarantees that if an order includes at least one product of a zone, this order can be assigned to at most one batch in that zone. Constraint (5) indicates picking device capacity limitation. Inequalities (6) and (7) compute $I_{j}^{zs}$ considering orders assigned to batch j. Constraint (8) indicates that the picking process of a batch can start after the picking completion of the previous batch. Inequality (9) expresses that picking of an order is completed when the picking process of all batches including that order are completed. M is an enough large number. Constraint (10) ensures that the departure time of each truck is greater than the picking completion time of its assigned orders. Constraint (11) guarantees that the departure time of each truck at each delivery interval is greater than the return time of previous intervals. Equation (12) necessitates that trucks arrive at the last cross-docks in their routes before the start time of each delivery interval. Equation (13) ensures that each order can be assigned to at most one delivery route if in all relevant zones is assigned to one batch.

Constraint (14) impedes an order to be assigned to a truck at a delivery interval if the truck is not used at that delivery interval. Inequality (15) creates a lower bound for variable d_i. Because the objective function minimizes the total cost in the optimal solution, d_i equals its lower bound. Equation (16) causes d_i to become equal to D if order i is not assigned to a truck.

Equation (17) ensures that if cross-dock h is visited in a route by a truck, that truck in that route travels to h exactly from one cross-dock, and from h moves to only one cross-dock. Equations (18) and (19) guarantee that if a truck is used in a delivery interval, that truck leaves the warehouse and comes back to the warehouse only one time at that delivery interval. Inequality (20) is the sub-tour elimination constraint in delivery routes. Constraint (21) expresses that if order i should be delivered to cross-dock h and is assigned to truck v in delivery interval r, truck v has to visit cross-dock h in delivery interval r . Inequality (22) is the capacity constraint of trucks. Inequality (23) ensures that the picking start time of the first batch of each zone is greater than the start time of the working day. Constraint (24) expresses that the picking finish time of all batches of all zones should be less than the finish time of the working day. Finally, constraint (25) defines the domain and type of decision variables.

The integrated model defines order batching and delivery planning for available orders however, in an online system, orders become available gradually during the day. Gademann and Velde [41] have proved that the order batching problem is NP-hard and cannot be solved optimally in a reasonable time. Heuristic and metaheuristic algorithms are an alternative approach to deal with the NP-hard problems [42]. Our problem is a combination of order bathing and vehicle routing problem, thus, has more complexity than the general order batching problem. On the other hand, the list of available orders changes continuously so, we need an algorithm to deal with the dynamic nature of the problem effectively.

5 Solution methods

Solving the integrated online order batching and delivery planning problem has two phases. The first phase is determining the updating times of the current plan, and the second one is solving the offline problems. We propose two hybrid rule-based heuristic methods (algorithm A1 and A2) to solve the online problem. Algorithm A1 deals with two sub-problems of order batching and delivery planning sequentially, while algorithm A2 considers the relationship between two sub-problems. The batching method used in both A1 and A2 is explained in section 5.1. Then, algorithms A1 and A2 are introduced in sections 5.2 and 5.3, respectively.

Before introducing the algorithms, we need to clarify our approach. We assume that all orders of each delivery interval become available until a definite time. We call this time as nextft_r for delivery interval r. Order pickers start their daily work at 7 AM and finish at 6 PM, so one shift consists of 660 minutes. Delivery intervals are shown in Table 2. Table 3 shows available delivery intervals that a customer can choose among them based on order arrival time.

Delivery interval	Start time	Finish time	Order finalizing time	Nextft (minute)
1	9 AM	12 PM	last day, 7 PM	0
2	12 PM	3 PM	same day, 8 AM	60
3	3 PM	6 PM	same day, 11 AM	240
4	6 PM	9 PM	same day, 2 PM	420

Table 3

Delivery intervals that can be chosen at each time

Order arrival time	Available delivery intervals				Colors
12 AM to 8 AM	2	3	4	1	Same day
8 AM to 11 AM	3	4	1	2	Next day
11 AM to 2 PM	4	1	2	3	2 days later
2 PM to 7 PM	1	2	3	4
7 PM to 12 AM	2	3	4	1

Each order has a priority according to its delivery interval. The priority of an order that its delivery interval passed and has not been delivered yet is P₀. Orders of the next delivery interval are of priority P₁ and the priorities of other orders are defined similarly. taop_z is defined as the point of time in which order picker of zone z completes picking of all planned batches and becomes available. Bellow sets also are defined and used in the algorithms.

DO: Set of orders that their picking operations have been finished or scheduled in all storage zones.

PO: Set of orders that their picking operations have not been scheduled in at least one of the storage zones.

VRPO: Orders of PO and DO with priorities P₀ and P₁.

BO: Orders of PO with priorities P₀ and P₁.

5.1 Batching algorithm

We use the similarity degree of orders to generate batches. The similarity degree of orders i and j is defined as ${simi}_{ij} = \frac{| {aisle}_{i} \cap {aisle}_{j} |}{| {aisle}_{i} \cup {aisle}_{j} |},$ in accordance with the seed batching algorithm [43]. |aisle_i ∩ aisle_j| expresses the number of mutual storage aisles of orders i and j, and |aisle_i ∪ aisle_j| is the total number of aisles that must be visited for picking orders i and j together.

For making the first batch, two orders with the highest similarity degree are selected and form a batch. Then the similarity degrees between the generated batch and the other orders are computed. In the next step, the order with the highest similarity degree with the generated batch is joined to the batch. This procedure continues until the batch capacity is satisfied. All needed batches are generated likewise.

In algorithm A1, the order batching and delivery planning are conducted separately and consecutively at each delivery interval. In the order batching process, orders with higher priority are batched and scheduled at time nextft_r, after completion of the picking process of scheduled orders in each zone, if some time is remained until nextft_r+1, the algorithm generates new batches of orders with lower priority and schedules picking of them. Hence, the probability of occurring delay decreases, and order pickers do not waste their time. The delivery sub-problem uses the output of the order batching process as the input. Details of the order batching and the delivery sub-problems of algorithm A1 are explained in sections 5.2.1 and 5.2.2, respectively.

The steps of the order batching sub-problem of algorithm A1 are described as follows.

Step 1: Initialize at t = 0, r = 1, and taop_z = 0 . Update PO and DO sets and determine the priority of orders.

Step 2: Apply batching algorithm (section 5.1) on orders of BO and sequence batches ascendingly based on their picking times in each zone. Compute $t_{i}^{topc}$ and start the picking of generated batches.

Step 3: Update taop_z, set ${taop}_{z^{'}} = min_{z} {taop}_{z}$ .

Step 4: Update PO and orders’ priority at taop_z′.

Step 5: If taop_z′ < nextft_r, create one batch of PO orders of zone z′ by the use of the batching algorithm and come back to step 3 otherwise, set t = taop_z′ and go to step 6.

Step 6: If t < 660setr = r + 1, update PO set and orders’ priority, and then go to step 2 otherwise, stop.

In the delivery sub-problem of A1, the below model is solved at each delivery interval r at time nextft_r for all orders of DO. In this model, we maximize the number of delivered orders so that orders with higher priority have greater weight in the objective function. We also assume that a truck can be scheduled if at least a certain amount of its capacity is utilized. $maxz = \sum_{i = 1}^{O} \sum_{v = 1}^{V + V^{'}} w_{iv} / (2 * P_{i}^{'}) - cost / C$ (26) $\begin{matrix} s . t . : \\ \sum_{v = 1}^{V + V^{'}} w_{iv} ⩽ 1 \forall i \in {1, \dots, O} \end{matrix}$ (27) $\sum_{i = 1}^{O} w_{iv} . \sum_{z = 1}^{Z} N_{i}^{z} ⩽ u_{v} . {cap}_{v} \forall v \in {1, \dots, V + V^{'}}$ (28) $\sum_{i = 1}^{O} w_{iv} . \sum_{z = 1}^{Z} N_{i}^{z} ⩾ u_{v} . {cap}_{v} . n_{v} \forall v \in {1, \dots, V + V^{'}}$ (29) ${td}_{v} ⩾ t_{i}^{topc} - M . (1 - w_{iv}) + t^{l} \forall v \in {1, \dots, V + V^{'}}, \forall i \in {1, \dots, O}$ (30) ${td}_{v} + \sum_{h = 0}^{H} \sum_{h^{'} = 1}^{H} y_{{hh}^{'} v} . (t_{{hh}^{'}}^{tr} + t^{ul}) = a_{r} \forall v \in {1, \dots, V + V^{'}}$ (31) $\sum_{h^{'} = 0}^{H} y_{{hh}^{'} v} = \sum_{h^{'} = 0}^{H} y_{h^{'} hv} \forall v \in {1, \dots, V + V^{'}}, \forall h \in {1, \dots, H}$ (32) $\sum_{h = 1}^{H} y_{0, h, v} = u_{v} \forall v \in {1, \dots, V + V^{'}}$ (33) $\sum_{h \in S}^{H} \sum_{h^{'} \in S}^{H} y_{{hh}^{'} v} ⩽ | S | - 1 \forall v \in {1, \dots, V + V^{'}}, \forall S \subseteq {1, \dots, H}, 2 ⩽ | S | ⩽ H$ (34) $\sum_{h^{'} = 0}^{H} y_{{hh}^{'} v} ⩾ w_{iv} . M_{ih} \forall v \in {1, \dots, V + V^{'}}, \forall h \in {1, \dots, H}, \forall i \in {1, \dots, O}$ (35) ${td}_{v} ⩾ t_{v}^{vav} + t^{l} \forall v \in {1, \dots, V + V^{'}}$ (36)

$cost = \sum_{h^{'} = 0}^{H} \sum_{h = 0}^{H} \sum_{v = 1}^{V + V^{'}} y_{{hh}^{'} v} . {CV}_{v} . (t_{h, h^{'}}^{tr} + t^{ul}) + \sum_{h = 0}^{H} \sum_{v = 1}^{V + V^{'}} y_{h, 0, v} . {CV}_{v} . t_{h, 0}^{tr}$ (37)

$\begin{matrix} y_{{hh}^{'} v}, w_{iv}, u_{v} \in {0, 1}, {td}_{v}, {tc}_{v}, cost ⩾ 0 \\ \forall i \in {1, \dots, O}, \forall h, h^{'} \in {1, \dots, H}, \forall v \in {1, \dots, V + V^{'}} \end{matrix}$ (38)

In the above model, $P_{i}^{'}$ equals 1 for orders with priorities P₀ and P₁, and 2 for orders with priority P₂ and so on. cost is the transportation cost. C is a parameter to control the transportation cost and is set experimentally as 30,000 in the numerical experiment. n_v is the minimum used capacity of truck v set as 0.15 for inbound trucks and 0.3 for rental trucks. $t_{v}^{vav}$ is the point of time in which truck v becomes available. w_ivequals 1 if order i is assigned to truck v . y_hh′v is 1 if truck v travels from cross-dock h to cross-dock h′. u_v equals 1 when truck v is used. Other notations are the same as the integrated model.

The objective function (26) has two parts, $\sum_{i = 1}^{O} \sum_{v = 1}^{V + V^{'}} w_{iv} / (2 * P_{i}^{'})$ maximizes the number of delivered orders so that orders with higher priority are more likely to be delivered, and cost/C is a factor to control the transportation cost. Constraint (27) guarantees that each order is assigned to at most one truck. Constraints (28) and (29) limit the maximum and minimum utilization of each truck. Constraints (30) to (35) are equivalent to constraints (10), (12), (18), (19), (21), and (22) of the integrated model, respectively. Constraint (36) expresses that the departure time of trucks must be greater than the time in which they become available. Equation (37) computes the transportation cost based on the travel time of trucks. This model is a mixed-integer linear programming model and can be solved optimally in small and medium sizes of the problem.

Finally, Fig. 2 shows the flowchart of algorithm A1.

Fig.2

The flowchart of algorithm A1.

5.3 Algorithm A2

Algorithm A2 tries to deal with both sub-problems of order batching and delivery planning simultaneously to deliver orders with the minimum delay and transportation cost alongside with the maximum utilization of order pickers and inbound trucks. To be more specific, for each delivery interval r, at the time nextft_r we solve the delivery planning model for orders of VRPO set to find the minimum transportation cost and investigate either we can pick orderss based on the delivery planning solution or need to modify the delivery planning considering the order batching solution. Then, we try to maximize the used capacity of assigned trucks with orders of the next delivery intervals as much as possible. Finally, until nextft_r+1, whenever an order picker becomes idle we create a new batch of available orders and assign it to him. Detailed steps of algorithm A2 are described as follows.

Step 1: Initialize at t = 0, r = 1, andtaop_z = 0 .

Step 2: If t < 660, update PO and DO sets, determine priority of orders, and go to step 3 otherwise, stop.

Step 3: Solve model M1 (section 5.3.1) for orders of VRPO.

Step 4: Compute avtd_i for orders of VRPO as the average departure time of the trucks assigned to the cross-dock of order i in the M1 solution. This parameter is an estimation of the departure time of order i and will be used in the batch sequencing process (section 5.3.2).

Step 5: Use batching method (section 5.1) for orders of BO, and then sequence batches by the use of avtd_i as described in section 5.3.2. Then, compute $t_{i}^{opc}$ for orders of BO and, start picking of batches, and Update PO, DO, and taop_z.

Step 6: Assign orders of VRPO to trucks and compute achievement as described in section 5.3.3.

Step 7: If achievement = 1, go to step 8 otherwise, go to step 9.

Step 8: Deliver orders based on the M1 solution, remove orders of VRPO from DO, and go to step 11.

Step 9: Solve model M2 (section 5.3.4) to revise delivery planning based on the batching schedule. Then deliver orders based on M2 solution, remove assigned orders from DO, and go to step 10.

Step 10: If trucks have free space, assign as many orders of DO as possible to trucks considering their destination and remained capacity as well as $t_{i}^{opc}$ and td_rv, then remove assigned orders from DO and go to step 12. Step 11: Run step 10. Then, if trucks have still free space, use algorithm A2-GA (section 5.3.5) to assign more orders to them. Update PO, DO, and taop_z. Go to step 12.

Step 12: Set ${taop}_{z^{'}} = min_{z} {taop}_{z}$ . If taop_z′ ⩾ nextft_r, set t = taop_z′ and r = r + 1, and go to step 2 otherwise, go to step 13.

Step 13: Update PO and DO sets at taop_z′, create a batch of PO orders of zone z′, update taop_z, and go to step 12.

Figure 3 displays the flowchart of algorithm A2.

Fig.3

The flowchart of algorithm A2.

5.3.1 Primary delivery planning model (M1)

Model M1 allocates the capacity of trucks to cross-docks’ demands in each delivery interval and determines the departure time as well as the routes of trucks, aiming the minimum transportation cost. This model is formulated as follows.

$Mincost = \sum_{v = 1}^{V + V^{'}} \sum_{h = 0}^{H} \sum_{\begin{matrix} h^{'} = 1, \\ h^{'} \neq h \end{matrix}}^{H} y_{{hh}^{'} v} . {CV}_{v} . (t_{{hh}^{'}}^{tr} + t^{ul}) + \sum_{v = 1}^{V + V^{'}} \sum_{h = 1}^{H} y_{h 0 v} . {CV}_{v} . t_{h 0}^{tr}$ (39) $\begin{matrix} s . t . : \\ \sum_{v = 1}^{V + V^{'}} x_{hv} = d_{h}^{r} \forall h \in {1, . ., H} \end{matrix}$ (40) ${td}_{v} + \sum_{h = 0}^{H} \sum_{h^{'} = 1}^{H} y_{{hh}^{'} v} . (t_{{hh}^{'}}^{tr} + t^{ul}) = a_{r} \forall v \in {1, \dots, V + V^{'}}$ (41) $\sum_{h^{'} = 0}^{H} y_{{hh}^{'} v} = \sum_{h^{'} = 0}^{H} y_{h^{'} hv} \forall v \in {1, \dots, V + V^{'}}, \forall h \in {0, \dots, H}$ (42) $\sum_{h = 1}^{H} y_{0, h, v} ⩽ 1 \forall v \in {1, \dots, V + V^{'}}$ (43) $\sum_{h \in S} \sum_{h^{'} \in S} y_{{hh}^{'} v} ⩽ | S | - 1 \forall v \in {1, \dots, V + V^{'}} \forall S \subseteq {1, \dots, H}, 2 ⩽ | S | ⩽ H$ (44) $\sum_{h = 1}^{H} x_{hv} ⩽ {cap}_{v} \forall v \in {1, \dots, V + V^{'}}$ (45) ${td}_{v} ⩾ t_{v}^{vav} + t^{l} \forall v \in {1, \dots, V + V^{'}}$ (46) $x_{hv} ⩽ M . \sum_{h^{'} = 0}^{H} y_{{hh}^{'} v} \forall v \in {1, \dots, V + V^{'}}, \forall h \in {0, \dots, H}$ (47) $\begin{matrix} y_{{hh}^{'} v} \in {0, 1}, x_{hv}, {td}_{v} ⩾ 0 \\ \forall h, h^{'} \in {1, \dots, H}, \forall v \in {1, \dots, V + V^{'}} \end{matrix}$ (48) In this model, x_hv is the capacity of truck v assigned to orders of cross-dock h. The objective function (39) is the total transportation cost. Constraint (40) ensures that orders of each cross-dock are delivered completely. Constraint (41) to (46) are equivalent to constraints (12), (18), (19), (21), (23), and (36) respectively. Inequality (47) ensures that orders of cross-dock h can be assigned to a truck only if that truck visits h in its route.

5.3.2 Batch sequencing

After generating batches at each storage zone as described in section 5.1, they need to be sequenced. In this step, we compute the priority of each batch in each storage zone as p_j = ∑_i∈javtd_i + t_j, where avtd_i is the average departure time of the trucks visiting cross-dock of order i in their routes, and t_j is the picking time of batch j. Then we rank batches ascendingly based on p_j and pick them based on their rank. Consequently, we can compute the start time and finish time of each batch as well as the picking completion time of each order.

The solution of M1 determines the departure time and route of each truck as well as the amount of its assigned capacity to each cross-dock. In this step, we should allocate the orders to the trucks and compute the Achievement index. For order i and truck v, if ${td}_{v} > t_{i}^{opc} + t^{l}$ and the remained capacity of v is greater than the needed space for i, truck v can deliver order i. We determine the list of available trucks for each order and set w_i as 1 if there is at least one available truck for order i, and 0 otherwise. Then we assign i to the available truck with the earliest departure time or minimum td_v and update the remained capacity of that truck. Achievement index expresses what percent of VRPO orders can be picked and delivered based on the M1 solution, and is computed as Achievement $= \frac{\sum_{i \in VRPO} w_{i}}{| VRPO |}$ . When Achievement is less than one, it shows that some of the orders cannot be picked until the departure time of scheduled trucks based on the M1 solution, so we need to modify our delivery plan using model M2.

Model M2 tries to deliver the maximum number of orders with minimum additional cost compared to the cost of the M1 solution considering picking completion time of orders. M2 is formulated as follows. $maxz = \sum_{k = 1}^{K_{h}} \sum_{h = 1}^{H} \sum_{v = 1}^{V + V^{'}} w_{hkv} - g * (\frac{cost - mincost}{DC})$ (49) $\begin{matrix} s . t . : \\ \sum_{v = 1}^{V + V^{'}} x_{hv} ⩽ d_{h}^{r} \forall h \in {1, . ., H} \end{matrix}$ (50) ${td}_{v} + \sum_{h = 0}^{H} \sum_{h^{'} = 1}^{H} y_{{hh}^{'} v} . (t_{{hh}^{'}}^{tr} + t^{ul}) = a_{r} \forall v \in {1, \dots, V + V^{'}}$ (51) $\sum_{h^{'} = 0}^{H} y_{{hh}^{'} v} = \sum_{h^{'} = 0}^{H} y_{h^{'} hv} \forall v \in {1, \dots, V + V^{'}}, \forall h \in {0, \dots, H}$ (52) $\sum_{h = 1}^{H} y_{0, h, v} ⩽ 1 \forall v \in {1, \dots, V + V^{'}}$ (53) $\sum_{h \in S} \sum_{h^{'} \in S} y_{{hh}^{'} v} ⩽ | S | - 1 \forall v \in {1, \dots, V + V^{'}} \forall S \subseteq {1, \dots, H}, 2 ⩽ | S | ⩽ H$ (54) $\sum_{h = 1}^{H} x_{hv} ⩽ {cap}_{v} \forall v \in {1, \dots, V + V^{'}}$ (55) ${td}_{v} ⩾ t_{v}^{vav} + t^{l} \forall v \in {1, \dots, V + V^{'}}$ (56) $x_{hv} ⩽ M . \sum_{h^{'} = 0}^{H} y_{{hh}^{'} v} \forall v \in {1, \dots, V + V^{'}}, \forall h \in {0, \dots, H}$ (57)

$cost = \sum_{v = 1}^{V + V^{'}} \sum_{h = 0}^{H} \sum_{\begin{matrix} h^{'} = 1, \\ h^{'} \neq h \end{matrix}}^{H} y_{{hh}^{'} v} . {CV}_{v} . (t_{{hh}^{'}}^{tr} + t^{ul}) + \sum_{v = 1}^{V + V^{'}} \sum_{h = 1}^{H} y_{h 0 v} . {CV}_{v} . t_{h 0}^{tr}$ (58)

$\sum_{v = 1}^{V + V^{'}} w_{hkv} ⩽ 1 \forall h \in {1, \dots, H}, \forall k \in {1, \dots, K_{h}}$ (59)

$\sum_{k = 1}^{K_{h}} w_{hkv} . u_{h, k} ⩽ x_{hv} \forall h \in {1, \dots, H}, \forall v \in {1, \dots, V + V^{'}}$ (60)

${td}_{v} ⩾ t_{h, k}^{opc} + t^{l} - M . (1 - w_{hkv}) \forall v \in {1, \dots, V + V^{'}}, \forall h \in {1, \dots, H}, \forall k \in {1, \dots, K_{h}}$ (61)

$\begin{matrix} y_{{hh}^{'} v}, w_{hkv} \in {0, 1}, x_{hv}, {td}_{v} ⩾ 0 \\ \forall h, h^{'} \in {1, \dots, H}, \forall v \in {1, \dots, V + V^{'}}, \forall k \in {1, \dots, K_{h}} \end{matrix}$ (62)

In this model, K_h is the number of orders of cross-dock h . w_hkv is a binary variable which equals 1 if kth order of cross-dock h is assigned to truck v. u_h,k is the number of product containers for kth order of cross-dock h. The objective function (49) consists of two parts; the first part counts for the number of delivered orders, and the second part controls additional cost. g is a parameter that is tuned experimentally as 0.95 due to the importance of the on-time delivery of orders.

Constraints (50) to (57) are the same as constraints (40) to (47) of model M1. Equation (58) is the cost function of the new model. Inequality (59) ensures that each order is assigned to only one truck. Constraint (60) guarantees that if truck v does not visit cross-dock h, then w_hkv is 0, and the needed space for orders of cross-dock h assigned to truck v does not exceed the total allocated space of truck v to cross-dock h. Inequality (61) ensures that the departure time of a truck is greater than the completion time of the orders assigned to that truck.

5.3.5 Algorithm A2-GA

Algorithm A2-GA is applied when scheduled trucks have remained capacity, and there is no picked order to be assigned to these trucks. Therefore, A2-GA tries to generate new batches and pick more orders to increase the utilization of trucks. For this purpose, a genetic algorithm is designed. To find an initial solution, first of all, we define sets ${PO}_{z}^{'}$ , including orders of PO with priorities P₂ or P₃ that contain at least one product of zone z. Then the number of required batches at each zone is computed as ${bn}_{z} = \frac{| {PO}_{z}^{'} |}{{CO}_{z}}$ . A chromosome is a m × n matrix named BM where m = |PO′| and n = Z. BM shows the batch number of each order in each zone and is generated randomly through the Equation (63). ${BM}_{i, z} = {\begin{matrix} 0 ifi \notin {PO}_{z}^{'} \\ random number in range [1, {bn}_{z}] ifi \in {PO}_{z}^{'} \end{matrix}$ (63)

After generating BM, we can compute the start time, the picking time, and the picking completion time of batches, as well as the picking completion time of orders. Then, the orders need to be assigned to the trucks as explained in section 5.3.3. Consequently, we remove unassigned orders from batches and calculate the start time, picking time, and completion time for new batches and the picking completion time for remained orders. Now, we have an initial feasible solution. Expression (64) indicates the cost function of the GA algorithm. $cost function = mean ({taop}_{z}) . b - \sum_{i \in {PO}^{'}} N_{i} . x_{i}$ (64)

Where x_i equals 1 if order i is assigned to a truck, and zero otherwise. b is a parameter for normalization which is set as 0.1. This cost function leads to answers with the maximum number of assigned orders along with the minimum picking time. For creating new solutions, the uniform crossover operation is used. Crossover operation is applied on BM. Then other parts of the solution are computed as described above. Mutation operation is done by the rate μ = 0.15 so that μ * |PO′| times, in each row of BM, two non-zero elements are selected randomly and exchanged. Other parameters of the designed GA are as follows. Number of iterations = 80, population size = 60, crossover rate = 0.5, mutation rate = 0.25. These parameters are tuned experimentally.

5.4 Cost lower bound

To evaluate the performance of the algorithms, we consider the estimated cost of solving the offline problem as the lower bound of the system cost. In this case, the information of all orders is available in advance, so all orders of each day can be picked and delivered, with the minimum transportation cost and no delay. The minimum transportation cost of the offline problem is calculated by solving model M1 for all orders of four delivery intervals of the current day. Because in the offline setting, all orders are available at the beginning of the planning horizon, we assume that it is possible to pick all orders and deliver them on time by inbound trucks. Therefore, there is no need for rental trucks. On the other hand, having full information in advance, there is enough time to conduct all operations. So, we eliminate time-related limitations (constraints (41) and (46)) of model M1 and solve it. Last but not least, this lower bound is the minimum transportation cost, when we can deliver all orders of each day with inbound trucks and without any delay.

In this section, an extensive problem series is designed to evaluate the quality of solutions produced by algorithms. We compare the results of algorithms from different aspects, including system costs, numbers of delayed orders, number of picked and delivered orders, and cost per delivered order. Moreover, the total cost of algorithms is compared to the lower bound to evaluate the efficiency of proposed algorithms in response to the dynamic nature of the problem. Last but not least, we investigate the impact of several parameters on the solutions of algorithms through a sensitivity analysis and provide some helpful managerial insights for decision-makers of the online retailing industry.

The order picker routing in each storage zone is the s-shape that is frequently used in other papers [3, 36]. The warehouse has five identical storage zones. At each zone, there are eight storage aisles in which products are stored on both sides of aisles. The center to center distance between two adjacent aisles is 2 meters, and the length of each aisle is 10 meters. Order picker travel speed is considered 48 meters per minute. The picking time of an item is 0.17 minutes based on the experiments of Henn [3]. Batch setup time is 4 minutes for each batch. Picking device capacity at each zone is six product containers or six orders. Table 4 summarizes the picking-related parameters.

We consider two cases with three and five cross-docks. Zhang, et al. [36] also solved their problem with five delivery zones. They assumed that each delivery zone has one dedicated truck. However, we deal with the case that all trucks can visit several cross-docks in their delivery routes. There are four inbound trucks. We also assume that an unlimited number of rental trucks can be used whenever inbound trucks are not sufficient. Moreover, we need 15 minutes to find and rent a truck.

The capacity of each truck is 150 product containers. The transportation cost is 100 units per minute for inbound trucks and 400 units per minute for rental trucks. The travel speed of trucks is 1.3 kilometers per minute. Truck loading time at the warehouse and unloading time at each cross-dock is 10 minutes. Table 5 displays the locations of the warehouse and cross-docks. For the case of three cross-docks, we consider the first three points. The distance between two points is computed through the Euclidean distance formula. The delay cost of an order is 4000 units per delivery interval. Table 6 summarizes the delivery-related parameters.

Table 5

Location of warehouse and cross-docks

Table 6

Delivery-related parameters

V= 4	SV= 1.3 Kilometer/Minute
CV_v= 100, for each inbound truck	t^l= 10 Minute
CV_v= 400, for each rental truck	t^ul= 10 Minute
cap_v= 150 Container	CD= 4000

The planning horizon is a 660-minute working day. At the beginning of the working day, there are two order sets named DO and PO1 in the system. DO set consists of orders that have been picked last day and are ready to be delivered. PO1 includes orders that have not been picked in some or all of the storage zones. Another order set that we need to be introduce is the PO2 set. PO2 comprises orders that will arrive during the day. Based on the literature such as Henn [3], the arrival time of orders of PO2 is distributed exponentially with parameter λ. This parameter expresses the average inter-arrival time of order i and orderi + 1. The delivery interval of each order is determined randomly among possible intervals based on Table 3 regarding the order arrival time. Table 7 displays four considered problem sizes. We solve each problem size with both three and five cross-docks.

Table 7

Number of orders in each problem size

Size number	Total orders	DO	PO1	PO2	λ
1	800	50	130	620	1.065
2	900	60	150	690	0.957
3	1,000	70	170	760	0.868
4	1,100	80	190	830	0.795

Each order is assigned to one of the cross-docks randomly. $N_{i}^{z}$ is a Bernoulli distributed variable with the probability of $\frac{1}{2} .$ If $N_{i}^{z} = 1$ , to determine the number of products of order i in each storage aisle of zone z, $I_{i}^{sz}$ is set as a Bernoulli distributed variable with the probability of $\frac{1}{4}$ . When $I_{i}^{sz}$ = 1 the number of product items of order i in aisle s of zone z can be either 1, 2, or 3 randomly. Then $Q_{i}^{z}$ is calculated as the sum of the items of order i in all aisles of zone z . $f_{i}^{z}$ that expresses the last storage location of order i in zone z is a uniform variable between 0 and 10.

As described above, we consider four different sizes of the problem and for each size, generate 20 different order sets for both cases of having three or five cross-docks. Therefore, 160 instances are generated and solved with two algorithms, and the average results are reported. The experiment is carried out on an Intel Core i7 and 16GB RAM. The algorithms are implemented with MATLAB R2018b, and GAMS 25.1.2 is used to solve mathematical models with the CPLEX solver.

6.2 Performance evaluation of algorithms

Tables 8 and 9 show cost analysis of cases with 3 and 5 cross-docks, respectively. These tables include the cost of the offline problem as the lower bound, transportation cost, delay cost, total cost, and the ratio of the total cost to the lower bound. According to these tables, in almost all cases, algorithm A1 outperforms algorithm A2 considering system cost. Zhang, et al. [36] used competitive analysis and proved that their proposed algorithm has a competitive ratio of 4. Zhang, et al. [37] also proved that their method has a competitive ratio of 2, but both of the studies ignored due dates of orders. We use the ratio of the total cost to the lower bound to compare the results of algorithms with the minimum cost of the offline problem. Based on experimental results, the average ratio of the total cost to the lower bound for algorithm A1 is 1.99 and 2.48 for cases with 3 and 5 cross-docks, respectively, and for algorithm A2, is 1.47 and 2.12. Considering due dates has increased the complexity of the problem. Furthermore, in this case, the cost of delayed orders has raised the total cost. By the way, algorithm A2 has an acceptable performance in comparison to the previous studies. On the other hand, considering the relationship between two sub-problems of order batching and delivery planning in algorithm A2 leads to noticeably better results compared to A1. Moreover, through the sensitivity analysis, in section 6.3, it is demonstrated that changes in some parameters can lead to even better solutions and a lower ratio of the total cost to the lower bound in both algorithms.

Cross-docks	Total orders	Lower bound	Algorithm	Transportation cost	Delay cost	Total cost	Total cost/Lower bound
	800	98,265	A1	155,604	15,600	171,204	1.74
			A2	131,003	1,000	132,003	1.34
	900	113,273	A1	177,087	23,000	200,087	1.77
			A2	157,268	600	157,868	1.39
3	1000	125,326	A1	190,767	57,800	248,567	1.98
			A2	166,887	4,800	171,687	1.37
	1100	131,116	A1	199,494	113,800	313,294	2.39
			A2	202,491	24,600	227,091	1.73
	Total	467,978	A1	722,951	210,200	933,151	1.99
			A2	657,648	31,000	688,648	1.47

Table 9

Cost analysis in cases with 5 cross-docks

Cross-docks	Total orders	Lower bound	Algorithm	Transportation cost	Delay cost	Total cost	Total cost/Lower bound
	800	99,415	A1	209,565	10,600	220,165	2.21
			A2	201,178	1,600	202,778	2.04
	900	104,204	A1	247,050	9,600	256,650	2.46
			A2	209,563	7,600	217,163	2.08
5	1000	121,309	A1	265,458	32,400	297,858	2.46
			A2	236,274	16,200	252,474	2.08
	1100	135,894	A1	285,123	83,800	368,923	2.71
			A2	265,226	39,800	305,026	2.24
	Total	460,821	A1	1,007,196	136,400	1,143,596	2.48
			A2	912,241	65,200	977,441	2.12

From Tables 8 and 9 it can also be seen that when the number of orders rises from 1000 to 1100, the ratio of the total cost to the lower bound significantly increases in both algorithms. So, we can conclude that for this system with this defined setting accepting more than 1000 orders may not be cost-effective. On the other hand, when the number of orders increases, by assigning more order pickers as well as more inbound trucks, the daily cost can be decreased. However, the additional cost of purchasing new trucks and adding order pickers should be specified to determine the most beneficial scenario.

Tables 10 and 11 analyze the performance of algorithms in terms of the number of picked, delivered, and delayed orders. These tables also include the number of same-day orders (the orders that have to be delivered on the current day), the lower bound per order, the total cost per delivered order, and the delay percentage. According to the results reported in these tables, the number of picked orders in algorithm A1 is on average 3.6% and 4.5% more than the algorithm A2 for the cases with 3 and 5 cross-docks, respectively. However, the cost per delivered order in A2 is significantly less than A1. We can conclude that A1 has better performance in the batching sub-problem, but A2 can improve the total performance of the system by the integration of two sub-problems.

Table 10

Analysis of processed orders in cases with 3 cross-docks

Cross-docks	Total orders	Same day orders	Lower bound per order	Algorithm	Picked orders	Delivered orders	Delayed orders	Cost per delivered order	% Delay
	800	466	210.7	A1	707	540	3.9	316.8	0.7%
				A2	671	533	0.25	247.7	0.0%
	900	527	215.0	A1	677	581	5.75	344.3	1.0%
				A2	657	576	0.15	274.2	0.0%
3	1000	589	212.7	A1	660	625	14.45	398.0	2.3%
				A2	636	628	1.2	273.3	0.2%
	1100	642	204.4	A1	663	659	28.45	475.3	4.3%
				A2	648	667	6.15	340.6	0.9%
	Total	2224	210.4	A1	2706	2405	52.55	388.0	2.2%
				A2	2612	2404	7.75	286.5	0.3%

Table 11

Analysis of processed orders in cases with 5 cross-docks

Cross-docks	Total orders	Same day orders	Lower bound per order	Algorithm	Picked orders	Delivered orders	Delayed orders	Cost per delivered order	% Delay
	800	464	214.5	A1	706	535	2.65	411.7	0.5%
				A2	655	527	0.4	384.5	0.1%
	900	527	197.9	A1	676	583	2.4	440.2	0.4%
				A2	642	589	1.9	368.7	0.3%
5	1000	581	208.8	A1	657	622	8.1	479.0	1.3%
				A2	639	616	4.05	410.1	0.7%
	1100	646	210.3	A1	662	664	20.95	555.6	3.2%
				A2	651	659	9.95	463.2	1.5%
	Total	2217	207.9	A1	2701	2404	34.1	475.8	1.4%
				A2	2586	2391	16.3	408.9	0.7%

Moreover, when the number of cross-docks increases, the average cost per order in the lower bound decreases by 1.2%, while in the online setting, this amount increases by 23% and 43% in algorithms A1 and A2, respectively. That is because in the lower bound, there is no time-related limitation for delivering orders, and we can ship all orders of each cross-dock together. Conversely, in the online problem, orders become available gradually and have to be picked and delivered before a definite time. So, we have to use more trucks with less utilized capacity for delivering more orders on time, and this raises the transportation cost as well as the total cost.

Tables 12 and 13 compare the results of algorithms in terms of two key factors including the number of delayed orders and total cost per delivered order. The number of delayed orders has a direct effect on customer satisfaction and their loyalty to the system. On the other hand, the total cost per delivered order reflects efficiency of the algorithms. According to Tables 12 and 13, algorithm A2 can remarkably reduce the number of delayed orders as well as cost per delivered orders.

Table 12

Comparison between A1 and A2 in problems with 3 cross-docks

H = 3	Number of delayed orders	Cost per delivered orders
Total orders	A1/A2	A1/A2
800	15.6	1.279
900	38.3	1.256
1000	12.0	1.456
1100	4.6	1.396
Total	6.8	1.354
% Improvement	578%	26.2%

Table 13

Comparison between A1 and A2 in problems with 5 cross-docks

H = 5	Number of delayed orders	Cost per delivered orders
Total orders	A1/A2	A1/A2
800	6.63	1.071
900	1.26	1.194
1000	2.00	1.168
1100	2.11	1.199
Total	2.09	1.164
% Improvement	109.2%	14.1%

To statistically verify the results, we have performed an analysis of variance (ANOVA) that is used in many related papers [44 –46]. The analysis of variance has been performed on the cost per delivered order for cases with three and five cross-docks separately. Tables 14 and 15 demonstrate the results for cases with three and five cross-docks, respectively. From these tables, there is an obvious statistically significant difference between the performances of the two algorithms.

Table 14

The results of ANOVA for cases with 3 cross-docks

Groups	Count	Sum	Average	Variance
Algorithm A1	80	30,692	384	7,313
Algorithm A2	80	22,756	284	3,564
Source of Variation	SS	df	MS	F	P-value	F crit
Between Groups	393,628	1	393,628	72	1.3E-14	3.9
Within Groups	859,333	158	5,439
Total	1,252,961	159

Table 15

The results of ANOVA for cases with 5 cross-docks

Groups	Count	Sum	Average	Variance
Algorithm A1	80	37,736	472	5,992
Algorithm A2	80	32,606	408	3,190
Source of Variation	SS	df	MS	F	P-value	F crit
Between Groups	164,443	1	164,443	36	1.4E-08	3.9
Within Groups	725,400	158	4,591
Total	889,843	159

6.3 Sensitivity analysis

In this section, we investigate the effect of three parameters of the number of inbound trucks, the capacity of trucks, and the capacity of the picking device on the solutions of algorithms. For this purpose, we solve five instances of the case with five cross-docks and 1000 orders with new settings.

To investigate the impact of the number of inbound trucks, we solve problems with two to six inbound trucks. Tables 16 and 17 demonstrate the results. According to the results, the number of inbound trucks is highly influential on the performance of the system from different viewpoints. It is evident that when the number of trucks increases from four to five, the cost per delivered order decreases by about 26% in both algorithms. However, increasing the number of trucks from five to six cannot lead to more decrease in cost.

Lower Bound	Number of trucks	Algorithm	Transportation cost	Delay cost	Total cost	Total cost/Lower bound
	2	A1	467,498	26,400	493,898	4.15
		A2	426,482	12,800	439,282	3.69
	3	A1	350,140	26,400	376,540	3.17
		A2	318,206	9,600	327,806	2.76
118,896	4	A1	268,676	24,800	293,476	2.47
		A2	224,746	22,400	247,146	2.08
	5	A1	196,070	20,800	216,870	1.82
		A2	191,872	1,600	193,472	1.63
	6	A1	196,070	20,800	216,870	1.82
		A2	192,506	2,400	194,906	1.64

Table 17

Impact of number of inbound trucks on processed orders

Today orders	Lower Bound per order	Number of trucks	Algorithm	Picked orders	Delivered orders	Delayed orders	Cost per delivered order
		2	A1	665	622	6.6	794
			A2	638	606	3.2	725
		3	A1	665	622	6.6	605
			A2	645	615	2.4	533
584	204	4	A1	665	622	6.2	472
			A2	639	600	5.6	412
		5	A1	665	622	5.2	349
			A2	652	638	0.4	303
		6	A1	665	622	5.2	349
			A2	653	645	0.6	302

6.3.2 Effect of trucks capacity

In this part, we consider five different cases for the capacity of trucks and their cost displayed in Table 18. The results of solving problems with new settings are reported in Tables 19 and 20. According to these tables, in the lower bound, increasing the capacity of trucks, the cost per delivered order decreases remarkably. It is because, in the lower bound, orders can be aggregated to larger shipments with a lower cost per order without any time limitation. In contrast, in the online case that orders become available gradually, decreasing the capacity and cost of trucks leads to better results. It is evident that, when the capacity of trucks decreases from 150 to 125, the cost per delivered order reduces about 11% and 8% in algorithms A1 and A2, respectively, and when it equals 100, the reductions reach 10% and 21%. Managers can execute such analysis when designing their systems to determine the appropriate type of transportation fleet consistent with their systems’ characteristics.

Trucks capacity	Inbound trucks cost	Rental trucks cost
100	65	260
125	85	340
150	100	400
175	115	460
200	135	540

Table 19

Impact of trucks capacity on costs

Trucks capacity	Lower bound	Algorithm	Transportation cost	Delay cost	Total cost	Total cost/Lower bound
100	169,406	A1	222,266	39,200	261,466	1.54
		A2	188,448	10,400	198,848	1.17
125	145,888	A1	234,028	28,000	262,028	1.80
		A2	222,614	4,800	227,414	1.56
150	118,896	A1	268,676	24,800	293,476	2.47
		A2	224,746	22,400	247,146	2.08
175	101,020	A1	309,098	24,800	333,898	3.29
		A2	242,602	24,800	267,402	2.63
200	94,273	A1	356,066	24,800	380,866	4.04
		A2	275,508	41,600	317,108	3.36

Table 20

Impact of trucks capacity on processed orders

Trucks capacity	Today orders	Lower bound per order	Algorithm	Picked orders	Delivered orders	Delayed orders	Cost per delivered order
100	584	290	A1	665	619	9.8	423
			A2	641	614	2.6	324
125	584	250	A1	661	625	7.0	420
			A2	653	603	1.2	377
150	584	204	A1	665	622	6.2	472
			A2	639	600	5.6	412
175	584	170	A1	665	622	6.2	537
			A2	650	606	6.2	441
200	584	161	A1	667	616	6.2	618
			A2	650	619	10.4	513

6.3.3 Effect of picking device capacity

In this section, the impact of picking device capacity on solutions of algorithms is investigated. Picking device capacity determines the maximum number of orders in each batch and can considerably affect total picking time. Problems have been solved with picking device capacities from four to eight orders. The results are reported in Tables 21 and 22. According to these tables, increasing picking device capacity from six orders to seven orders, the cost per delivered order decreases 8% and 16% in algorithms A1 and A2 respectively and by increasing it from six to eight orders, in both algorithms 19% reduction in the cost per delivered order occurs. In addition to the cost reduction, greater picking device capacity increases the number of picked orders that can be considered as the productivity of order pickers.

Lower Bound	Batches capacity	Algorithm	Transportation cost	Delay cost	Total cost	Total cost/Lower bound
	4	A1	275,220	324,000	599,220	5.04
		A2	275,820	269,600	545,420	4.59
	5	A1	277,056	89,600	366,656	3.08
		A2	261,452	31,200	292,652	2.46
118,896	6	A1	268,676	24,800	293,476	2.47
		A2	224,746	22,400	247,146	2.08
	7	A1	262,810	16,000	278,810	2.34
		A2	212,274	8,000	220,274	1.85
	8	A1	235,606	15,200	250,806	2.11
		A2	213,470	9,600	223,070	1.88

Table 22

Impact of picking device capacity on processed orders

Today orders	Lower bound per order	Batches capacity	Algorithm	Picked orders	Delivered orders	Delayed orders	Cost per delivered order
		4	A1	542	541	81.0	1,107
			A2	548	548	67.4	995
		5	A1	599	600	22.4	611
			A2	599	597	7.8	490
584	204	6	A1	665	622	6.2	472
			A2	639	600	5.6	412
		7	A1	730	639	4.0	436
			A2	689	634	2.0	347
		8	A1	797	654	3.8	384
			A2	749	670	2.4	333

6.4 Managerial insights

The online retailing systems deal with costly operations of order picking and delivery process on a daily basis. Moreover, the dynamic nature of the system, makes it more difficult to plan and schedule such operations. This study aims to provide a decision-making tool for online retailers to design their systems at the strategic level and efficiently make their daily decisions at the operational level. It is displayed that an integrated approach of dealing with the order picking and the delivery planning problems can lead to an average of 26.2% and 14.1% reduction in the cost per delivered order for cases with three and five cross-docks, respectively as shown in Tables 12 and 13. Such saving is very crucial for the retailers because they are already operating on very thin margins [47]. It also remarkably decreases the number of delayed orders that directly affect customer satisfaction and improves the reputation of the retailer in today’s competitive marketplace.

At the strategic level, when it comes to deciding on the requirements of a system, online retailing managers need to explore the effects of different parameters on the performance of their systems. In section 6.3 the effects of three important parameters including picking device capacity, number of inbound trucks, and the capacity of trucks on the cost and performance of the system have been investigated. From the results of Tables 16 and 17, retail managers can estimate the operational cost-saving of purchasing new trucks, compare it to the required initial investment, calculate the return of capital, and make the best decision when assigning budgets to different projects. According to Tables 19 and 20, we conclude that in retailing systems with a great number of orders to be delivered in each delivery interval, big trucks are more cost-effective, while is medium-sized and small-sized systems, trucks with less capacity and less fixed and variable costs are more beneficial. Therefore, the managers must balance a trade-off between the number of their daily orders and the type, capacity, and consequently the cost of their inbound trucks.

Another finding of our sensitivity analysis is that increasing the capacity of picking device, leads to both cost reduction and order pickers’ productivity improvement (Tables 21 and 22). As a result of productivity improvement, at the end of each day, fewer unpicked orders remain for the next day, and the working load of order pickers reduces in the long term. As another result, more orders can be delivered on time, and customer satisfaction rises. Last but not least, retail managers can obtain significant benefits by readily changing the picking devices.

In recent years many people prefer to buy their required products from online sellers and receive them in their home or office at their desired times. Especially, with the spread of the Covid-19 pandemic, online retailers are experiencing increased demand for their products and new challenges in their operations. These changes have encouraged us to develop a decision-making system to help online retailers either to manage their daily operations much more efficiently or to redesign their systems in response to the increased demand. Online retailers should plan and act in a limited time to satisfy their customers. Two main interconnected operational problems of online retailing systems are order picking and delivery planning. Although integrated dealing with these problems is highly beneficial, scarce studies addressed them jointly in the online setting, and there is a clear gap in the available literature in this field. In this paper, we proposed a mixed-integer nonlinear programming model that decides on order batching, batch picking scheduling, assignment of orders to trucks, as well as the scheduling and routing of trucks simultaneously in the offline setting. However, in an online system, orders become known during the planning horizon. Therefore, in addition to the complexity of the integrated problem, retailers need an approach to respond to the dynamic nature of online systems. We proposed two rule-based heuristic algorithms to solve the online problem. The first algorithm (A1) considers two sub-problems of order batching and delivery planning separately and sequentially, while the second algorithm considers the relationship between two sub-problems.

Through an extensive numerical experiment, the performances of algorithms have been compared to each other and to the minimum cost of the offline problem as a lower bound. It is demonstrated that algorithm A2 noticeably outperforms algorithm A1 regarding two critical factors of cost per delivered order and the number of delayed orders. In algorithm A2, by integrating two sub-problems, the average cost per delivered order reduces by 26% and 14% compared to algorithm A1 in the cases with three and five cross-docks, respectively. We have also investigated the impact of main parameters, including the number of inbound trucks, the capacity of trucks, and the picking device capacity on the solution of algorithms. It is concluded that the correct combination of these parameters dramatically improves the solutions of both algorithms. For example, adding one dedicated truck to the system leads to a 26% reduction in the cost per delivered order in both algorithms and, using small trucks can cause a minimum of 10% decrease in the cost per delivered order. Our algorithms can also be applicable for retail managers to estimate the costs and benefits of different scenarios when designing a new system or developing their current systems.

We have formulated the problem based on the settings of a real-world online retailing system. However, although we have carried out an extensive numerical experiment because our problem instances have been generated randomly, we might have ignored some unexpected conditions that could affect the results. Therefore, it will be helpful to solve real-world cases with our proposed algorithms and analyze the results.

For further study, a system with multiple pickers in each storage zone can be addressed. Such a system can handle more orders every day. Although we used the s-shape routing method for the order pickers, it will be useful to apply other order pickers routing methods and compare the results to each other. In the batching operation, we used the similarity degree index to create batches, the effect of using other batching methods can be investigated in future studies. Last but not least, some online retailers sell perishable products that need special considerations, it could be beneficial to develop our algorithm for such products.

Torabbeigi

, Lim

G.J.

, Kim

S.J.

, Drone Delivery Scheduling Optimization Considering Payload-induced Battery Consumption Rates, Journal of Intelligent & Robotic Systems 1–17, 2019.

Gong

, De

, Koster, A polling-based dynamic order picking system for online retailers, IIE Transactions 40(11) (2008), 1070–1082.

Henn

, Algorithms for on-line order batching in an order picking warehouse, Computers & Operations Research 39(11) (2012), 2549–2563.

Roggeveen

A.L.

, Sethuraman

, How the COVID Pandemic May Change the World of Retailing, Journal of Retailing, (2020).

Chew

E.P.

, Tang

L.C.

, Travel time analysis for general item location assignment in a rectangular warehouse, European Journal of Operational Research 112(3) (1999), 582–597.

De Koster

, Le-Duc

and Roodbergen

K.J.

, Design and control of warehouse order picking: A literature review, European Journal of Operational Research 182(2) (2007), 481–501.

Richards

, Warehouse management: a complete guide to improving efficiency and minimizing costs in the modern warehouse. Kogan Page Publishers, (2017).

De Koster

, Distribution strategies for online retailers, IEEE Transactions on Engineering Management 50(4) (2003), 448–457.

Torabbeigi

, Lim

G.J.

, Kim

S.J.

, Drone delivery schedule optimization considering the reliability of drones, in 2018 International Conference on Unmanned Aircraft Systems (ICUAS) 2018 IEEE, 1048–1053.

10.

Schubert

, Kuhn

, Holzapfel

, Same-day deliveries in omnichannel retail: Integrated order picking and vehicle routing with vehicle-site dependencies, Naval Research Logistics (NRL), (2020).

11.

Fathollahi-Fard

A.M.

, Ahmadi

, Sajadieh

M.S.

, An Efficient Modified Red Deer Algorithm to Solve a Truck Scheduling Problem Considering Time Windows and Deadline for Trucks’ Departure, Evolutionary Computation in Scheduling (2020), 137–167.

12.

Golshahi-Roudbaneh

, Hajiaghaei-Keshteli

, Paydar

M.M.

, A hybrid Approach in Metaheuristics for a Cross-dock Scheduling Considering Time Windows and Deadline for Trucks Departure, Scientia Iranica (2019).

13.

Moons

, Braekers

, Ramaekers

, Caris

, Arda

, The value of integrating order picking and vehicle routing decisions in a B2C e-commerce environment, International Journal of Production Research 57(20) (2019), 6405–6423.

14.

van Gils

, Caris

, Ramaekers

and Braekers

, Formulating and solving the integrated batching, routing, and picker scheduling problem in a real-life spare parts warehouse, European Journal of Operational Research 277(3) (2019), 814–830.

15.

Shavaki

F.H.N.

, Jolai

, A rule-based heuristic algorithm for joint order batching and delivery planning of online retailers with multiple order pickers, Applied Intelligence (2020), 1–19.

16.

Fathollahi-Fard

A.M.

, Hajiaghaei-Keshteli

, Mirjalili

, A set of efficient heuristics for a home healthcare problem, Neural Computing and Applications 32(10) (2020), 6185–6205.

17.

Fathollahi-Fard

A.M.

, Hajiaghaei-Keshteli

, Tian

, Li

, An adaptive Lagrangian relaxation-based algorithm for a coordinated water supply and wastewater collection network design problem, Information Sciences 512 (2020), 1335–1359.

18.

Cano

J.A.

, Correa-Espinal

A.A.

, Gomez-Montoya

R.A.

, A review of research trends in order batching, sequencing and picker routing problems, Revista ESPACIOS 39(04) (2018).

19.

Elsayed

, Lee

M.-K.

, Kim

, Scherer

, Sequencing and batching procedures for minimizing earliness and tardiness penalty of order retrievals, The International Journal of Production Research 31(3) (1993), 727–738.

20.

Elsayed

, Lee

M.-K.

, Order processing in automated storage/retrieval systems with due dates, IIE Transactions 28(7) (1996), 567–577.

21.

Tsai

C.-Y.

, Liou

J.J.

, Huang

T.-M.

, Using a multiple-GA method to solve the batch picking problem: considering travel distance and order due time, International Journal of Production Research 46(22) (2008), 6533–6555.

22.

Henn

, Schmid

, Metaheuristics for order batching and sequencing in manual order picking systems, Computers & Industrial Engineering 66(2) (2013), 338–351.

23.

Chen

T.-L.

, Cheng

C.-Y.

, Chen

Y.-Y.

, Chan

L.-K.

, An efficient hybrid algorithm for integrated order batching, sequencing and routing problem, International Journal of Production Economics 159 (2015), 158–167.

24.

Henn

, Order batching and sequencing for the minimization of the total tardiness in picker-to-part warehouses, Flexible Services and Manufacturing Journal 27(1) (2015), 86–114.

25.

Scholz

, Schubert

, Wäscher

, Order picking with multiple pickers and due dates–Simultaneous solution of Order Batching, Batch Assignment and Sequencing, and Picker Routing Problems, European Journal of Operational Research 263(2) (2017), 461–478.

26.

Menéndez

, Bustillo

, Pardo

E.G.

, Duarte

, General Variable Neighborhood Search for the Order Batching and Sequencing Problem, European Journal of Operational Research 263(1) (2017), 82–93.

27.

, McFarlane

, Giannikas

, Zhang

, An algorithm for dynamic order-picking in warehouse operations, European Journal of Operational Research 248(1) (2016), 107–122.

28.

Giannikas

, Lu

, Robertson

, McFarlane

, An interventionist strategy for warehouse order picking: evidence from two case studies, International Journal of Production Economics 189 (2017), 63–76.

29.

Pérez-Rodríguez

, Hernández-Aguirre

, Jöns

, A continuous estimation of distribution algorithm for the online order-batching problem, International Journal of Advanced Manufacturing Technology 79 (2015).

30.

Gil-Borrás

, Pardo

E.G.

, Alonso-Ayuso

, Duarte

, GRASP with Variable Neighborhood Descent for the online order batching problem, Journal of Global Optimization (2020), 1–31.

31.

Alipour

, Mehrjedrdi

Y.Z.

, Mostafaeipour

, A rule-based heuristic algorithm for on-line order batching and scheduling in an order picking warehouse with multiple pickers, RAIRO-Operations Research 54(1) (2020), 101–107.

32.

Zhang

, Wang

, Chan

F.T.

, Ruan

, On-line order bathing and sequencing problem with multiple pickers: A hybrid rule-based algorithm, Applied Mathematical Modelling 45 (2017a), 271–284.

33.

Moons

, Ramaekers

, Caris

, Arda

, Integration of order picking and vehicle routing in a B2C e-commerce context, Flexible Services and Manufacturing Journal (2017), 1–31.

34.

Kuhn

, Schubert

, Holzapfel

, Integrated Order Batching and Vehicle Routing Operations in Grocery Retail–A General Adaptive Large Neighborhood Search Algorithm, European Journal of Operational Research (2020).

35.

Zhang

, Wang

, Huang

, Integrated on-line scheduling of order batching and delivery under B2C e-commerce, Computers & Industrial Engineering 94 (2016), 280–289.

36.

Zhang

, Wang

, Huang

, On-line scheduling of order picking and delivery with multiple zones and limited vehicle capacity, Omega 79 (2018), 104–115.

37.

Zhang

, Liu

, Tang

, Li

, The online integrated order picking and delivery considering Pickers’ learning effects for an O2O community supermarket, Transportation Research Part E: Logistics and Transportation Review 123 (2019), 180–199.

38.

Mohammadzadeh

, Sahebjamnia

, Fathollahi-Fard

, Hajiaghaei-Keshteli

, New approaches in metaheuristics to solve the truck scheduling problem in a cross-docking center, International Journal of Engineering 31(8) (2018), 1258–1266.

39.

Golshahi-Roudbaneh

, Hajiaghaei-Keshteli

, Paydar

M.M.

, Developing a lower bound and strong heuristics for a truck scheduling problem in a cross-docking center, Knowledge-Based Systems 129 (2017), 17–38.

40.

Le-Duc

, Design and control of efficient order picking processes. (2005).

41.

Gademann

, Velde

, Order batching to minimize total travel time in a parallel-aisle warehouse, IIE Transactions 37(1) (2005), 63–75.

42.

Fathollahi-Fard

A.M.

, Ahmadi

, Al-e-Hashem

S.M.

, Sustainable closed-loop supply chain network for an integrated water supply and wastewater collection system under uncertainty, Journal of Environmental Management 275 (2020), 111277.

43.

Y.-C.

, Tseng

Y.-Y.

, A study on order-batching methods of order-picking in a distribution centre with two cross-aisles, International Journal of Production Research 44(17) (2006), 3391–3417.

44.

Hajiaghaei-Keshteli

, Fard

A.M.F.

, Sustainable closed-loop supply chain network design with discount supposition, Neural Computing and Applications 31(9) (2019), 5343–5377.

45.

Hajiaghaei-Keshteli

, Afshari

A.J

and Nasiri

, Addressing the freight consolidation and containerization problem by recent and hybridized meta-heuristic algorithms, International Journal of Engineering 30(3) (2017), 403–410.

46.

Sahebjamnia

, Fathollahi-Fard

A.M.

, Hajiaghaei-Keshteli

, Sustainable tire closed-loop supply chain network design: Hybrid metaheuristic algorithms for large-scale networks, Journal of Cleaner Production 196 (2018), 273–296.

47.

Smriti

, Predicting Online Returns, in: Supply Chain Management Strategies and Risk Assessment in Retail Environments: IGI Global (2018), 181–194.

Z= 5	CO_z= 6, ∀z = 1, …, Z
I_z= 8, ∀z = 1, …, Z	SL= 48 Meter/Minute
WI_z= 2 Meter, ∀z = 1, …, Z	t^p= 0.17 Minute
LI_z= 10 Meter, ∀z = 1, …, Z	$t_{z}^{st}$ = 4 Minute, ∀z = 1, …, Z

Warehouse location

Cross-dock location