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

1 Introduction

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.

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.

2 Literature review

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.

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.

OPEN IN VIEWER

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 = { ( LI z . ∑ s = 1 I z I j zs ) + ( 2 . WI z . max { s | s ∈ I z , I j zs = 1 } ) if the number of aisles is even ( LI z . ∑ s = 1 I z I j zs ) + ( 2 . If j z ) + ( 2 . WI z . max { s | s ∈ I z , I j zs = 1 } ) if the number of aisles is odd(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 = dis j z SL + t p . ∑ 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 = ∑ v = 1 V + V ′ ∑ r = 1 D ∑ h = 0 H ∑ h ′ = 1 , h ′ ≠ h H y hh ′ rv . CV v . ( t hh ′ tr + t ul ) + ∑ v = 1 V + V ′ ∑ r = 1 D ∑ h = 1 H y h 0 rv . CV v . t h 0 tr + ∑ i = 1 O d i . CD(3) s . t . : ∑ j = 1 G z x ij z ⩽ N i z ∀ i ∈ { 1 , … , O } , ∀ z ∈ { 1 , … , Z }(4) ∑ i ∈ O x ij z ⩽ CO z ∀ z ∈ { 1 , … , Z } , ∀ j ∈ { 1 , … , G z }(5) I j zs ⩽ ∑ i ∈ O I i zs . x ij z ∀ z ∈ { 1 , … , Z } , ∀ j ∈ { 1 , … , G z } , ∀ s ∈ { 1 , … , I z }(6) I j zs ⩾ ∑ i ∈ O 1 I i zs . x ij z | O | ∀ z ∈ { 1 , … , Z } , ∀ j ∈ { 1 , … , G z } , ∀ s ∈ { 1 , … , I z }(7) ts j z ⩾ ts j - 1 z + t j - 1 z ∀ z ∈ { 1 , … , Z } , ∀ j ∈ { 2 , … , G z }(8) t i opc ⩾ ts j z + t j z - M . ( 1 - x ij z ) ∀ i ∈ { 1 , … , O } , ∀ z ∈ { 1 , … , Z } , ∀ j ∈ { 1 , … , G z }(9) t i opc ⩽ td rv - t l + M . ( 1 - w irv ) ∀ i ∈ { 1 , … , O } , ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(10) td rv ⩾ td r - 1 , v + ∑ h = 0 H ∑ h ′ = 0 , h ′ ≠ h H y hh ′ r - 1 , v . ( t hh ′ tr + t ul ) - ( t ul . u r - 1 , v ) + t l - M . ( 1 - u rv )(11) ∀ r ∈ { 2 , … , D } , ∀ v ∈ { 1 , … , V } td rv + ∑ h = 0 H ∑ h ′ = 1 , h ′ ≠ h H y hh ′ rv . ( t hh ′ tr + t ul ) ⩽ a r ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(12) ∑ v = 1 V + V ′ ∑ r = 1 D w irv ⩽ 1 - ∑ z = 1 Z N i z - ∑ z = 1 Z ∑ j = 1 G z x ij z ∑ z = 1 Z N i z ∀ i ∈ { 1 , … , O }(13) w irv ⩽ u rv ∀ i ∈ { 1 , … , O } , ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(14) d i ⩾ ∑ v = 1 V + V ′ ∑ r = 1 D r . w irv - b i ∀ i ∈ { 1 , … , O }(15) d i ⩾ R - M . ∑ v = 1 V + V ′ ∑ r = 1 D w irv ∀ i ∈ { 1 , … , O }(16) ∑ h ′ = 0 H y hh ′ rv = ∑ h ′ = 0 H y h ′ hrv ∀ h ∈ { 1 , … , H } , ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(17) ∑ h = 1 H y 0 hrv = u rv ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(18) ∑ h = 1 H y h 0 rv = u rv ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(19) ∑ h ∈ S ∑ h ′ ∈ S y hh ′ rv ⩽ | S | - 1 ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ } , ∀ S ⊆ { 1 , … , H } , 2 ⩽ | S | ⩽ H(20) ∑ h ′ = 0 H y hh ′ rv ⩾ w irv . M ih ∀ i ∈ { 1 , … , O } , ∀ h ∈ { 1 , … , H } , ∀ r ∈ { 1 , … , D } ,(21) ∀ v ∈ { 1 , … , V + V ′ } ∑ i = 1 O w irv . ∑ z = 1 Z N i z ⩽ cap v ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(22) ts 1 z ⩾ tsd ∀ z ∈ { 1 , … , Z }(23) ts j z + t j z ⩽ tfd ∀ z ∈ { 1 , … , Z } , ∀ j ∈ { 1 , … , G z }(24)

x ij z , y hh ′ rv , w irv , I j zs , u rv ∈ { 0 , 1 } , ts j z , td rv , d i ⩾ 0 ∀ i ∈ { 1 , … , O } , ∀ z ∈ { 1 , … , Z } , ∀ j ∈ { 1 , … , G z } , ∀ h , h ′ ∈ { 1 , … , H } , ∀ r ∈ { 1 , … , D } , ∀ v ∈ { 1 , … , V + V ′ }(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.

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.

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.2 Algorithm A1

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.

5.2.1 Order batching sub-problem of A1

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.

5.2.2 Delivery sub-problem of A1

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 = ∑ i = 1 O ∑ v = 1 V + V ′ w iv / ( 2 * P i ′ ) - cost / C(26) s . t . : ∑ v = 1 V + V ′ w iv ⩽ 1 ∀ i ∈ { 1 , … , O }(27) ∑ i = 1 O w iv . ∑ z = 1 Z N i z ⩽ u v . cap v ∀ v ∈ { 1 , … , V + V ′ }(28) ∑ i = 1 O w iv . ∑ z = 1 Z N i z ⩾ u v . cap v . n v ∀ v ∈ { 1 , … , V + V ′ }(29) td v ⩾ t i topc - M . ( 1 - w iv ) + t l ∀ v ∈ { 1 , … , V + V ′ } , ∀ i ∈ { 1 , … , O }(30) td v + ∑ h = 0 H ∑ h ′ = 1 H y hh ′ v . ( t hh ′ tr + t ul ) = a r ∀ v ∈ { 1 , … , V + V ′ }(31) ∑ h ′ = 0 H y hh ′ v = ∑ h ′ = 0 H y h ′ hv ∀ v ∈ { 1 , … , V + V ′ } , ∀ h ∈ { 1 , … , H }(32) ∑ h = 1 H y 0 , h , v = u v ∀ v ∈ { 1 , … , V + V ′ }(33) ∑ h ∈ S H ∑ h ′ ∈ S H y hh ′ v ⩽ | S | - 1 ∀ v ∈ { 1 , … , V + V ′ } , ∀ S ⊆ { 1 , … , H } , 2 ⩽ | S | ⩽ H(34) ∑ h ′ = 0 H y hh ′ v ⩾ w iv . M ih ∀ v ∈ { 1 , … , V + V ′ } , ∀ h ∈ { 1 , … , H } , ∀ i ∈ { 1 , … , O }(35) td v ⩾ t v vav + t l ∀ v ∈ { 1 , … , V + V ′ }(36)

cost = ∑ h ′ = 0 H ∑ h = 0 H ∑ v = 1 V + V ′ y hh ′ v . CV v . ( t h , h ′ tr + t ul ) + ∑ h = 0 H ∑ v = 1 V + V ′ y h , 0 , v . CV v . t h , 0 tr(37)

y hh ′ v , w iv , u v ∈ { 0 , 1 } , td v , tc v , cost ⩾ 0 ∀ i ∈ { 1 , … , O } , ∀ h , h ′ ∈ { 1 , … , H } , ∀ v ∈ { 1 , … , V + V ′ }(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 _iv equals 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, ∑ i = 1 O ∑ 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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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 = ∑ v = 1 V + V ′ ∑ h = 0 H ∑ h ′ = 1 , h ′ ≠ h H y hh ′ v . CV v . ( t hh ′ tr + t ul ) + ∑ v = 1 V + V ′ ∑ h = 1 H y h 0 v . CV v . t h 0 tr(39) s . t . : ∑ v = 1 V + V ′ x hv = d h r ∀ h ∈ { 1 , . . , H }(40) td v + ∑ h = 0 H ∑ h ′ = 1 H y hh ′ v . ( t hh ′ tr + t ul ) = a r ∀ v ∈ { 1 , … , V + V ′ }(41) ∑ h ′ = 0 H y hh ′ v = ∑ h ′ = 0 H y h ′ hv ∀ v ∈ { 1 , … , V + V ′ } , ∀ h ∈ { 0 , … , H }(42) ∑ h = 1 H y 0 , h , v ⩽ 1 ∀ v ∈ { 1 , … , V + V ′ }(43) ∑ h ∈ S ∑ h ′ ∈ S y hh ′ v ⩽ | S | - 1 ∀ v ∈ { 1 , … , V + V ′ } ∀ S ⊆ { 1 , … , H } , 2 ⩽ | S | ⩽ H(44) ∑ h = 1 H x hv ⩽ cap v ∀ v ∈ { 1 , … , V + V ′ }(45) td v ⩾ t v vav + t l ∀ v ∈ { 1 , … , V + V ′ }(46) x hv ⩽ M . ∑ h ′ = 0 H y hh ′ v ∀ v ∈ { 1 , … , V + V ′ } , ∀ h ∈ { 0 , … , H }(47) y hh ′ v ∈ { 0 , 1 } , x hv , td v ⩾ 0 ∀ h , h ′ ∈ { 1 , … , H } , ∀ v ∈ { 1 , … , V + V ′ }(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.

5.3.3 Achievement computation

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 = ∑ i ∈ 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.

5.3.4 Modified delivery planning 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 = ∑ k = 1 K h ∑ h = 1 H ∑ v = 1 V + V ′ w hkv - g * ( cost - mincost DC )(49) s . t . : ∑ v = 1 V + V ′ x hv ⩽ d h r ∀ h ∈ { 1 , . . , H }(50) td v + ∑ h = 0 H ∑ h ′ = 1 H y hh ′ v . ( t hh ′ tr + t ul ) = a r ∀ v ∈ { 1 , … , V + V ′ }(51) ∑ h ′ = 0 H y hh ′ v = ∑ h ′ = 0 H y h ′ hv ∀ v ∈ { 1 , … , V + V ′ } , ∀ h ∈ { 0 , … , H }(52) ∑ h = 1 H y 0 , h , v ⩽ 1 ∀ v ∈ { 1 , … , V + V ′ }(53) ∑ h ∈ S ∑ h ′ ∈ S y hh ′ v ⩽ | S | - 1 ∀ v ∈ { 1 , … , V + V ′ } ∀ S ⊆ { 1 , … , H } , 2 ⩽ | S | ⩽ H(54) ∑ h = 1 H x hv ⩽ cap v ∀ v ∈ { 1 , … , V + V ′ }(55) td v ⩾ t v vav + t l ∀ v ∈ { 1 , … , V + V ′ }(56) x hv ⩽ M . ∑ h ′ = 0 H y hh ′ v ∀ v ∈ { 1 , … , V + V ′ } , ∀ h ∈ { 0 , … , H }(57)

cost = ∑ v = 1 V + V ′ ∑ h = 0 H ∑ h ′ = 1 , h ′ ≠ h H y hh ′ v . CV v . ( t hh ′ tr + t ul ) + ∑ v = 1 V + V ′ ∑ h = 1 H y h 0 v . CV v . t h 0 tr(58)

∑ v = 1 V + V ′ w hkv ⩽ 1 ∀ h ∈ { 1 , … , H } , ∀ k ∈ { 1 , … , K h }(59)

∑ k = 1 K h w hkv . u h , k ⩽ x hv ∀ h ∈ { 1 , … , H } , ∀ v ∈ { 1 , … , V + V ′ }(60)

td v ⩾ t h , k opc + t l - M . ( 1 - w hkv ) ∀ v ∈ { 1 , … , V + V ′ } , ∀ h ∈ { 1 , … , H } , ∀ k ∈ { 1 , … , K h }(61)

y hh ′ v , w hkv ∈ { 0 , 1 } , x hv , td v ⩾ 0 ∀ h , h ′ ∈ { 1 , … , H } , ∀ v ∈ { 1 , … , V + V ′ } , ∀ k ∈ { 1 , … , K h }(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 = | 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 = { 0 ifi ∉ PO z ′ random number in range [ 1 , bn z ] ifi ∈ PO z ′(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 - ∑ i ∈ 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.

6 Numerical experiment

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.

7 Conclusion

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.