
In this paper, we present a linearized finite difference scheme and a compact finite difference scheme for the time fractional nonlinear diffusion-wave equations with space fourth order derivative based on their equivalent partial integro-differential equations. The finite difference scheme is constructed by using the Crank-Nicolson method combined with the midpoint formula, the weighted and shifted Gr¨unwald difference formula and the second order convolution quadrature formula to deal with the temporal discretizations. Meanwhile, the classical central difference formula and fourth order Stephenson scheme are used in the spatial direction. Then, the compact finite difference scheme is developed by using the fourth order compact difference formula for the spatial direction. The proposed schemes can deal with the nonlinear terms in a flexible way while meeting weak smoothness requirements in time. Under the relatively weak smoothness conditions, the stability and convergence of the proposed schemes are strictly proved by using the discrete energy method. Finally, some numerical experiments are presented to support our theoretical results.
Citation: Emadidin Gahalla Mohmed Elmahdi, Jianfei Huang. Two linearized finite difference schemes for time fractional nonlinear diffusion-wave equations with fourth order derivative[J]. AIMS Mathematics, 2021, 6(6): 6356-6376. doi: 10.3934/math.2021373
[1] | Yuhua Long, Sha Li . Results on homoclinic solutions of a partial difference equation involving the mean curvature operator. AIMS Mathematics, 2025, 10(3): 6429-6447. doi: 10.3934/math.2025293 |
[2] | Mohamed A. Barakat, Abd-Allah Hyder, Doaa Rizk . New fractional results for Langevin equations through extensive fractional operators. AIMS Mathematics, 2023, 8(3): 6119-6135. doi: 10.3934/math.2023309 |
[3] | Yuhua Long . Existence and nonexistence of positive solutions to a class of nonlocal discrete Kirchhoff type equations. AIMS Mathematics, 2023, 8(10): 24568-24589. doi: 10.3934/math.20231253 |
[4] | Xiaojie Guo, Zhiqing Han . Existence of solutions to a generalized quasilinear Schrödinger equation with concave-convex nonlinearities and potentials vanishing at infinity. AIMS Mathematics, 2023, 8(11): 27684-27711. doi: 10.3934/math.20231417 |
[5] | Lamya Almaghamsi, Aeshah Alghamdi, Abdeljabbar Ghanmi . Existence of solution for a Langevin equation involving the ψ-Hilfer fractional derivative: A variational approach. AIMS Mathematics, 2025, 10(1): 534-550. doi: 10.3934/math.2025024 |
[6] | Song Wang, Xiao-Bao Shu, Linxin Shu . Existence of solutions to a class of damped random impulsive differential equations under Dirichlet boundary value conditions. AIMS Mathematics, 2022, 7(5): 7685-7705. doi: 10.3934/math.2022431 |
[7] | Wei Guo, Jinfu Yang, Jiafeng Zhang . Existence results of nontrivial solutions for a new p(x)-biharmonic problem with weight function. AIMS Mathematics, 2022, 7(5): 8491-8509. doi: 10.3934/math.2022473 |
[8] | Zhilin Li, Guoping Chen, Weiwei Long, Xinyuan Pan . Variational approach to p-Laplacian fractional differential equations with instantaneous and non-instantaneous impulses. AIMS Mathematics, 2022, 7(9): 16986-17000. doi: 10.3934/math.2022933 |
[9] | Najla Alghamdi, Abdeljabbar Ghanmi . Multiple solutions for a singular fractional Kirchhoff problem with variable exponents. AIMS Mathematics, 2025, 10(1): 826-838. doi: 10.3934/math.2025039 |
[10] | H. Salah, M. Anis, C. Cesarano, S. S. Askar, A. M. Alshamrani, E. M. Elabbasy . Fourth-order differential equations with neutral delay: Investigation of monotonic and oscillatory features. AIMS Mathematics, 2024, 9(12): 34224-34247. doi: 10.3934/math.20241630 |
In this paper, we present a linearized finite difference scheme and a compact finite difference scheme for the time fractional nonlinear diffusion-wave equations with space fourth order derivative based on their equivalent partial integro-differential equations. The finite difference scheme is constructed by using the Crank-Nicolson method combined with the midpoint formula, the weighted and shifted Gr¨unwald difference formula and the second order convolution quadrature formula to deal with the temporal discretizations. Meanwhile, the classical central difference formula and fourth order Stephenson scheme are used in the spatial direction. Then, the compact finite difference scheme is developed by using the fourth order compact difference formula for the spatial direction. The proposed schemes can deal with the nonlinear terms in a flexible way while meeting weak smoothness requirements in time. Under the relatively weak smoothness conditions, the stability and convergence of the proposed schemes are strictly proved by using the discrete energy method. Finally, some numerical experiments are presented to support our theoretical results.
Interest on the operation of warehouses and distribution centers has grown considerably in recent years, particularly due to the growing importance of e-commerce and the increasing number of deliveries of small size packages [1]. Improving the efficiency of the operational process in storing facilities is critical for the overall performance of a firm [2,3,4,5]. These processes include all the activities carried out in distribution centers, like receiving, transferring, putting away, sorting, picking-up, classifying, grouping, accumulating and dispatching orders [6,7,8]. This requires coordinating different technical teams and designing the lay-out of the storage center [9,10].
The receiving activities consist in unloading orders from vehicles, carrying them inside the depot, updating the inventory databases and inspecting the items to detect eventual inconsistencies with the quality, quantity and packaging declared. The putting away tasks amount to moving the items from the unloading dock to their assigned place in the storage area, registering their corresponding placement. This involves handling the goods, verifying the suitability of the placement sites and proceeding to store them until they are requested in an order [11]. The order picking process covers the most expensive activities in most warehouses, consisting in picking up the right amount of requested goods from the corresponding storage sites and taking them to the preparation/dispatch area [3,12,13]. Classifying and grouping the requested and picked up articles consists in consolidating the orders of the clients in the modular packages (boxes, pallets, containers, etc.) to be dispatched [14,15]. In most cases this involves marking, labeling and grouping several goods into a single unit load. Dispatch is the process of verifying the load units to be transported, checking that the orders received are fulfilled, elaborating the documents to accompany them, to finally load them on transports.
Given the high costs in resources and time of the logistics in the storage facilities, leads us to focus on the order picking activities. We are particularly interested in the solution of the integral batching and pick-up problems, by taking the displacement costs and the earliness and tardiness penalties into consideration. We treat this combined problem in a multi-level storage system (with a 3D positioning of items) solved by applying a hybrid evolutionary algorithms.
The rest of this paper is organized as follows: Section 2 describes the problem and reviews the relevant literature. Section 3 presents the formal model, while Section 4 describes the algorithm devoted to solve this question. Section 5 presents datasets with different order characteristics and 3D warehouse environments and section 6 discusses the results of computer experiments Finally, section 7 discusses the results and the prospects for further work.
To pick up orders fastly and at a minimal cost, three planning problems, involving operations in warehouses or distribution centers, have to be addressed. One is the allocation of storage positions for the received articles. Another one is batching-up the orders in lots to be collected. Finally, we have the problem of scheduling the sequence of pick-ups and delivery displacements to the dispatch area [16]. In this paper we focus on the integrated treatment of the two last problems, which are critical for the efficiency of the activities in the storage floor. Furthermore, they generate most of the costs associated to the operation of the distribution center since they involve activities that are intensive in labor and equipment [17,18,19].
A more precise description of the order picking process is the following. The process starts with incoming multiple customer orders. Each order involves requests of different articles made by a customer, detailing the amount of each article and the due time at which the order has to be available at the dispatch area. The articles must be picked-up from the storage positions at the right time by a pick-up team that has to visit them in a sequence [20,21]. Masae et al. [22] review systematically the literature on order picker routing policies.
Small orders may reduce the displacement time, by finishing them in single picking tours. This can be taken advantage by order batching procedures that split up larger orders into smaller ones. Alternatively, small orders can be combined in a single large order that can then be picked in a single picking tour [23]. Figure 1 depicts this process, indicating that it starts and ends at the dispatch area.
So, the integrated process consists in designing a plan to reduce the cost of selecting, picking-up batches of different orders simultaneously, given precise deadlines for the finishing of each one. This cost is proportional to the displacement times across the storage floor and the punctuality in finishing the requested tasks. Since the final goal is to dispatch the batches, the schedule of pick-ups depends on the schedule of deliveries to customers. If the order were finished with delays it would lead to violations of the contracts with customers. Penalties and related costs ensue. On the other hand, if the orders are finished before the stipulated time the goods may clog the regular flow in the dispatch area, increasing the processing time of urgent requests, increasing the total cost of operations.
In more formal terms, this problem integrates two already known NP-Hard problems, the order batching problem (OBP) and the order picking problem (OPP). OBP consists in determining how to conform the batches that will be collected by the pick-up teams, taking into account the capacities of the teams and the time at which each article should be at the dispatch area. OPP in turn consists in identifying optimal visit sequences to the storage positions in which the goods of a given batch can be found, minimizing the distance covered and the processing time of the batch, visiting each storage position only ones. We denote the integrated problem as OBP/OPP.
De Koster et al. [7] present a thorough literature revision on OBP and OPP. Ho and Tseng [24] reviewed the heuristics used to solve OBP. Chen and Wu [14] use a clustering-based approach to solve OBP taking into account demand patterns instead of the distance covered in each sequence of visits. Henn et al. [15] proposed using heuristics like taboo search and attribute-based hill climbing for OBP. Henn and Schmid [25] added the iterated local search heuristic to address OBP. Later on, Lam et al. [26] proposed and integer programming model for OBP in which the distance covered by each sequence is estimated and the problem is solved using a fuzzy logic-based heuristic.
Van Gils et al. [27] reviewed and classified the literature on OPP. Petersen [28], De Koster et al. [6] as well as Theys et al. [29] presents revisions of the heuristics for OPP. Henn et al. [30] used ant colony optimization and iterated local search to solve OPP, while Chen and Lin [31] used a very efficient two-stage method. Lu et al. [32] present a routing algorithm for dynamical OPP.
Tsai et al. [2] used a multiple-GA to solve the integrated OBP/OPP on 2D and 3D item positions. The novelty of this work resided in the use of flexible time windows for the delivery of orders, allowing a certain degree of earliness and tardiness. Miguel et al. [3], presented an evolutionary algorithm hybridized with a local search method to solve the 2D instances in reference [2]. Later on, Miguel et al. [4] changed the representation of individuals, improving the results of reference [3].
In this paper we seek to further test and improve the performance, using experimentation, of the algorithm presented in reference [3] applying it on the 3D instances of reference [2].
The main contributions of this paper are the following:
ⅰ) We addressed the order batching and order picking with a more realistic model, by considering a multi-level storage system (with a 3D positioning of items), explicitly incorporating the due times of the requests.
ⅱ) We take into account that the actual procedures in warehouses involve several pick-up teams. This has been barely approached in the literature on the processing and routing of pick-ups in distribution centers.
ⅲ) The improvements are obtained by implementing an algorithm that solves the problem in a single stage, unlike the more complex algorithm presented in [2], which requires 2 stages.
ⅳ) The algorithm is tested on sets of orders generated probabilistically using the methodology presented in reference [2], showing its robustness.
The literature has not covered sufficiently the resolution of the integrated problem by dividing larger problems into smaller ones to be fulfilled by multiple pick-up teams. While reference [33] comes close to this, it does not allow the splitting of orders. This aspect of our work indicates its scientific relevance.
We present here a specification of OBP/OPP based on a mathematical programming formulation [2]. In this setting we define the decision variables, the objective function as well as the constraints that involve delivery deadlines, number of pick-up teams and the operational restrictions on the use of the storage facility.
P denotes the set of different items in storage1. We assume that there are nArt items. Each unit of an item has a weight, being the set of those weights W={w1,…,wp,…,wnArt}. Pi is the subset of items requested by customer i. We assume that each customer places a single order or request of different articles, with different amounts of them. Thus, the number of customers nC, equals the number of requests nReq, being the set of customers/orders I={1,…,i,…,nC}. Each request has a specified deadline, with the class of those deadlines being T={t1,…,ti,…,tnPed}. Pr is the set of items in a batch r. The items in Pr can be requested by a single or several customers. L={l0,l1,…,lp,…,lnArt} represents the set of storage positions of the types of articles plus l0 which indicates the dispatch area. For an item p∈P, its storage position lp is given by its coordinates in the store, lp=(xp,yp,zp). R={1,..,r,…,|R|} indicates that set of batches to be picked-up. Sr=⟨s1,…,su,…,s|Sr|⟩ is the sequence of positions to be visited to conform batch r, where su is the u−th position to be visited. qi,p∈Q denotes the number of units of item p requested by customer i, with Qi=∑p∈Piqi,p being the total number of goods demanded by i while Qp=∑i∈Iqi,p denotes the total number of requested units of p. Finally, K={1,…,|K|} is the set of pick-up teams, each one with total weight capacity Cap.
1 Each item has a different reference code (SKU). So for instance, 200 units of the smartphone EjS22 share the same SKU, which is not the same of the smartphone EjS7, another item.
We define an undirected graph G=(V,A), where V are the nodes, each one corresponding to a storage position of an item p∈P, plus two copies (0 and n+1) of the node corresponding to the dispatch area. A, represents the class of edges connecting pairs of nodes of V. Each edge(h,l)∈A has an associated travel time thl given by the distance between positions h and l over the speed of a picking-up team, v (i.e., thl=Dh,l/v) and an operational cost for each unit of time, ς. tpick is the average time to pick a unit of any item, once the team has reached the corresponding storage site.
xhlkr=1 if h is picked-up right before item in storage position l by the pick-up team k in the sequence corresponding to batch r, where h,l∈V, k∈K and r∈R. This means that xhlkr=1 if team k has to travel through edge(h,l) to form batch r.
yhkr=1 if k picks up item in storage position h for batch r, where h∈V, k∈K and r∈R.
minTOC:[∑h∈V∑l∈VDh,l⋅∑k∈K∑r∈Rxhlkrv+∑p∈Pq∈Qqp⋅tpick]⋅ς+∑i∈I(α⋅Ei+β⋅Ti) | (1) |
s.t.
∑h∈Vr(qp⋅wp)⋅yhkr≤Cap,∀k∈K,r∈R | (2) |
∑r∈Ryhkr=1,∀h∈P,∀k∈K | (3) |
∑k∈Kyhkr=|K|,∀h∈{0,n+1},r∈R | (4) |
∑h∈Vxhlkr=ylkr,∀l∈V∖{0},k∈K,r∈R | (5) |
∑l∈Vxhlkr=yhkr,∀h∈V∖{n+1},k∈K,r∈R | (6) |
∑i∈I∑k∈K∑r∈Rqi,p⋅ypkr=Qp,∀p∈P | (7) |
∑p∈P∑k∈K∑r∈Rqi,p⋅ypkr=Qi,∀i∈I | (8) |
xhlkr∈{0,1},∀h,l∈V,k∈K,r∈R | (9) |
yhkr∈{0,1},∀h∈V,k∈K,r∈R | (10) |
The objective function Eq (1) represents the total operational cost of the pick-up process, expressed in monetary units, corresponding to the collection of batches, plus penalties for earliness and tardiness. The travel times in the first term obtain from the analysis of the lay-out of the storage facility.
With respect to the second term, α is the penalty per unit of time for earliness, while β is the current penalty per unit of time for tardiness. Er is the earliness in making up order i, while Ti is tardiness in making up order i. Formally, Ei=max{0,ti−ci} and Ti=max{0,ci−ti}, where ci is the finishing time of order i, defined as the time at which all the units of all items corresponding to order i are picked up and collected to form the order.
Constraints Eq (2) forbid that the total weight of a batch exceed the capacity of the teams and their equipment, Vr is the set of storage positions of the items that belong to lot r (p∈Pr). Constraints Eq (3) indicate that each storage position cannot be visited more than once for each batch r. Constraints Eq (4) ensure that all pick-up teams start and end at the dispatch area. In turn Eqs (5) and (6) preserve the flow of pick-up operations. If pick-up team k gets item l for batch r, it has to have picked up item h or vice versa. Constraints Eq (7) indicate that all the requests of item p are satisfied, while constraints Eq (8) state that all the requests of customer i have to be satisfied. Constraints Eqs (9) and (10) restrict the range of values of variables.
Figure 2 shows the lay-out of the distribution center used in our previous analysis of the OBP/OPP problem. The bottom left corner corresponds to the access to the dispatch area, where all the sequences of pick-up operations start and end. That is, a team leaves the dispatch area following a pre-specified sequence, going from a storage position to another, picking-up the items before moving on to the next storage position, until all the articles in a batch have been collected. After that, the team returns with the articles to the dispatch area. Graphically, we have surrounded with a dashed red curve the storage and dispatch areas, where all the actual OBP/OPP operations are carried out.
This configuration agrees with the one presented originally by Tsai et al. [2]. We keep the parameters used by them to test and validate our proposed solution method for the OBP/OPP problem. More precisely, we assume that there are two lateral racks and two double racks in the middle of the storage area. Pick-ups can be carried out along two transversal and three longitudinal aisles. The distance traveled from the storage position of item l to that of h, i.e., from ll to lh, where ll=(xl,yl,zl) and lh=(xh,yh,zh), can be expressed as follows:
Dl,h={|xl−xh|+|yl−yh|+|zl−zh|,ifAl=Ah|xl−xh|+min{|2Y−(yl−H)−(yh−H)|;|(yl−H)−(yh−H)|}+|zl−zh|,ifAl≠Ah |
In this expression Al and Ah denote the aisles along which ll and lh can be reached, respectively. H is the second coordinate of l0, the start and end of a pick-up sequence. Y is the length of the picking aisles.
The algorithm applied was introduced in reference [3] to solve the 2D instances presented by Tsai et al. [2]. It consists of an evolutionary algorithm [34] that evolves the solutions to the OBP/OPP problem hybridized with a constructive method based on the k closest neighbors heuristic, to improve the sequences using a local search with λ-exchanges. It uses the representation of as permutation of integers, usual in the treatment of combinatorial problems. Each chromosome consists of two genomes. A simple example shows how this representation works. Consider three requests and four items. Table 1 indicates that, for instance, request 1 consists of 2 items (one unit of A and two units of C), totaling 3 articles.
Request | Item | Total | |||
A | B | C | D | ||
1 | 1 | 0 | 2 | 0 | 3 |
2 | 1 | 1 | 2 | 1 | 5 |
3 | 0 | 2 | 0 | 2 | 4 |
Total | 2 | 3 | 4 | 3 | 12 |
Table 2 shows a representation consisting of two rows, one for items and the other for requests. The columns indicate the total number of requested articles (in this case, 12).
Item | A | A | B | B | B | C | C | C | C | D | D | D |
Request to which it belongs | 1 | 2 | 2 | 3 | 3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
Table 3 indicates how the information in Table 2 is used to define two genomes. The first genome contains the information of the items assigned to batches (we consider three batches in this case). So, for instance, one unit of item A in request 1, is assigned to batch 2. On the other hand, genome 2 corresponds to the sequence of visits to the storage positions of the items. For instance, in batch 2, item A is collected from position 2. Table 4 presents the final chromosome to be evolved.
Item | A | A | B | B | B | C | C | C | C | D | D | D |
Request to which it belongs | 1 | 2 | 2 | 3 | 3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
Genome 1 / Assigned batch | 2 | 3 | 2 | 3 | 3 | 1 | 1 | 3 | 1 | 1 | 1 | 3 |
Genome 2 / Position in sequence | 2 | 1 | 1 | 3 | 5 | 1 | 3 | 4 | 5 | 4 | 2 | 2 |
Genome 1 | Genome 2 | ||||||||||||||||||||||
2 | 3 | 2 | 3 | 3 | 1 | 1 | 3 | 1 | 1 | 1 | 3 | 2 | 1 | 1 | 3 | 5 | 1 | 3 | 4 | 5 | 4 | 2 | 2 |
Table 5 shows how the chromosome of Table 4 is decoded, indicating the batches and their corresponding pick up sequences.
Batch | Item (Request) | ||||
1 | C (1) | D (3) | C (1) | D (2) | C (2) |
2 | B (2) | A (1) | |||
3 | A (2) | D (3) | B (3) | C (2) | B (3) |
We can see that this chromosome is not yet a solution for the problem since, for instance for batch 1, this sequence prescribes going from the dispatch area to the position where item C is, pick up one unit, then go the position of item D, pick up one unit and return to the position of C to pick up another unit. After that the sequence prescribes going back to the position of D and then again back to C. This is clearly inefficient, since it could pick up three units of C and then two of D (or the other way around) with a lower cost. The evolutionary process ends up discarding chromosomes like that of Table 4.
The main advantage of this type of representation that incorporates specific knowledge about the problem is that it allows reaching higher levels of efficiency than Holland's original binary representation [35]. The downside is that it requires using operators adapted to this representation instead of general ones [36].
The penalty term in the objective function facilitates discarding non-feasible chromosomes. On the other hand, the satisfaction of the family of constraints Eqs (2)–(6) is ensured by the hybridization of the genetic operators with the closest neighbor heuristic. The constraints given by Eqs (7) and (8) are trivially satisfied by the representation.
The initial population is generated randomly, to ensure a larger variety of alternatives. The process terminates according a cost-oriented criterion, which limits the maximal number of iterations.
We use here the tournament selection approach [37], according to which the individuals that get selected are those with the higher scores among k individuals chosen at random from the current population. This is repeated until a new population is generated.
Table 6 presents the pseudo-code of the algorithm, as presented in reference [3].
1: Load Input % information of requests, the lay-out of the storage center and parameters of the algorithm. |
2: nBatch ← nBatchMin 3: while nBatch < nBatchMax 4: t ← 0; 5: P(t) ← InitPop(input); 6: FitP(t) ← EvalPop(P(t)); 7: For t ← 1 a MaxNumGen 8: Q(t) ← SelecBreeders (P(t), FitP(t)); 9: Q(t) ← HybridCrossover(Q(t)); 10: Q(t) ← HybridMutation(Q(t)); 11: FitQ(t) ← EvalPop(Q(t)); 12: P(t) ← SelSurviv(P(t), Q(t), FitP(t), FitQ(t)); 13: FitP(t) ← EvalPop(P(t)); 14: if TermCond(P(t), FitP(t)) 15: break; 16: end 17: end 18: nBatch ← nBatch + 1; 18: end |
Tsai et al. [2] generated instances for OBP/OPP positioning items in two and three dimensions, as shown in Table 7. We have previously applied the HEA to find very good solutions to some 2D instances (DS0, DS1, DS2 and DS3) [3,4]. Here we address 3D instances (DS4, DS5 and DS6). In this, more complex setting, we can test and improve the performance of the algorithm.
DS0 | DS1 | DS2 | DS3 | DS4 | DS5 | DS6 | |
Problem size | Small | Small | Medium | Large | Small | Medium | Large |
Number of requests | 25 | 40 | 80 | 200 | 40 | 100 | 250 |
Number of different items | 30 | 80 | 160 | 300 | 80 | 200 | 400 |
Lay-out type | 2D | 2D | 2D | 2D | 3D | 3D | 3D |
Average total weight (kg.) | 18584 | 13704 | 37152 | 158784 | 12424 | 54048 | 295784 |
Capacity of pick-up teams (kg.) | 7000 | 10000 | 10000 | 20000 | 10000 | 10000 | 50000 |
We assume that the number of units of item p requested by a customer i is uniformly distributed between 1 and 10, i.e., qi,p∼U(1,…,10). In turn, the number of different ítems requested by a customer follows a normal distribution, with mean 10 and standard deviation 5, i.e., |Pi|∼N(10,5). The deadline for finishing the request of i follows a uniform distribution over the range of seconds between 10:00 am and 18:00 pm, ti∼U(36000,…,64800). The unit weight of each item p is uniformly distributed between 8 and 24 kilograms, i.e., wp∼U(8,…,24). With respect to the parameters of the pick-up teams, we assume an average travel speed of v=2m/s, an average pick-up time for each unit of tpick=15 seconds, a travel cost per unit of time ς=$0.05 and a capacity (Cap) that depends on the instance under consideration.
For the objective function we consider an earliness penalty per unit of time of α=0.5 while the corresponding penalty for tardiness is β=1.
With respect to the strategy to limit the search space and facilitating the comparison with the results of Tsai, Liou and Huang [2], we postulate lower and upper bounds on the number of possible batches, |R|min and |R|max, respectively. These bounds are defined as follows: |R|min=(φ1⋅∑p∈Pwp)/Cap and |R|max=(φ2⋅∑p∈Pwp)/Cap, where φ1 and φ2 are constants such that φ2≥φ1. If φ1 is too large or φ2 is too small, unfeasible sequences may be generated. The latter case generates longer pick-up routes and the batches may exceed the capacity of the pick-up teams. Similarly, a large φ1 would induce a very large number of batches that may generate large travel costs.
Tables 8–10 summarize the information about instances DS4, DS5 and DS6, respectively. Each row indicates the items and amounts of them requested by customer i. The last column shows the deadline for finishing the requests.
Request | Items:quantities | Deadline |
P1 | (4:2) (5:9) (18:5) (40:4) (55:5) (62:6) (67:5) | 17:38:41 |
P2 | (1:6) (11:7) (13:1) (16:3) (18:4) (20:2) (58:6) (59:9) (60:5) (64:8) (68:6) (76:3) (77:2) | 17:11:44 |
P3 | (7:1) (21:10) (27:5) (31:4) (38:7) (41:8) (42:5) (44:4) (46:8) (51:7) (60:7) (78:5) | 15:56:12 |
P4 | (23:4) (35:4) (53:9) (54:8) (62:4) (64:8) (70:7) (80:8) | 17:57:13 |
P5 | (10:2) (33:7) (38:8) (39:1) (41:7) (46:7) (52:7) (53:5) (63:3) (71:10) | 15:15:02 |
P6 | (11:5) (19:3) (44:9) (59:2) (72:7) (80:8) | 15:52:38 |
P7 | (11:10) (18:4) (26:5) (34:4) (37:4) (53:4) (54:4) | 14:22:30 |
... | ... | ... |
P38 | (17:10) (34:3) (47:4) (49:3) | 14:35:54 |
P39 | (15:2) (23:10) (31:9) (45:8) (59:9) (66:2) (69:6) (76:6) | 15:24:01 |
P40 | (9:2) (29:1) (37:6) (49:6) (58:3) (74:2) (76:1) | 16:36:54 |
Request | Items:quantities | Deadline |
P1 | (15:9) (34:6) (107:10) (120:4) (134:7) (178:2) (184:1) (192:6) | 15:05:09 |
P2 | (1:6) (7:8) (40:7) (62:2) (85:1) (98:10) (121:8) (123:6) | 16:10:57 |
P3 | (6:1) (19:10) (44:4) (113:9) (115:2) (124:10) (132:5) (160:6) (167:10) (195:5) (198:2) | 16:24:33 |
P4 | (57:6) (78:1) (85:9) (89:1) (94:2) (107:7) (133:3) (143:4) (166:8) (180:9) (199:2) | 15:27:07 |
P5 | (7:10) (21:8) (33:5) (37:1) (50:6) (74:2) (119:4) (171:3) (176:5) | 16:42:02 |
P6 | (11:3) (15:4) (34:5) (37:2) (48:2) (69:8) (155:6) (174:9) (176:9) (177:8) (182:9) (188:9) | 15:38:01 |
P7 | (73:1) (145:9) (191:7) (193:6) | 15:25:51 |
... | ... | ... |
P98 | (44:1) (57:8) (65:7) (79:5) (121:3) (157:3) (189:7) | 14:47:52 |
P99 | (34:10) (52:5) (120:8) (133:1) (160:2) | 15:29:12 |
P100 | (7:8) (13:6) (28:10) (38:2) (51:8) (86:2) (121:5) (127:3) (183:10) | 14:58:35 |
Request | Items:quantities | Deadline |
P1 | (10:2) (87:5) (126:7) (172:1) (207:4) (276:4) (314:1) (351:8) (396:7) | 14:46:43 |
P2 | (54:1) (107:4) (157:3) (255:7) (328:2) | 15:31:42 |
P3 | (141:5) (152:10) (171:7) (243:7) (306:5) | 15:16:38 |
P4 | (35:1) (68:7) (194:3) (228:6) (313:8) (321:2) (335:4) (359:8) (375:7) (391:6) | 14:13:20 |
P5 | (54:9) (70:9) (85:7) (115:3) (154:6) (280:8) (370:2) (399:4) | 15:30:15 |
P6 | (45:5) (64:4) (111:7) (150:1) (161:6) (166:5) (346:10) | 15:26:27 |
P7 | (84:8) (151:10) (313:9) (353:2) (400:4) | 14:06:20 |
... | ... | ... |
P248 | (43:4) (157:4) (313:10) (362:2) | 15:01:47 |
P249 | (66:8) (99:10) (114:4) (140:4) (174:9) (178:10) (195:5) (196:3) (292:7) | 16:17:18 |
P250 | (26:6) (56:8) (97:4) (106:6) (107:1) (126:4) (186:6) (228:4) (254:3) | 17:27:49 |
A first stage of calibration allows assigning values to other parameters. So, the maximal number of iterations is MaxGen=500, the size of populations is PopSize=150, the size of tournaments in the selection process is SizeTournament=2, the parameters in the bounds on the number of batches are φ1=2 and φ2=4, the probability of crossover is Prcross=0.9, the probability of mutations is Prmut=0.15 while the number of individuals in the elite is (5% of the population) nElite=0.05⋅PopSize, using direct sampling as elite selection rule.
In this section we present the results of running our HEA on 3D instances (DS4, DS5 and DS6) generated by Tsai et al. [2]. We used a PC with an Intel Core i7 3.00 GHz processor with a 8 GB RAM. 100 runs for each instance yielded the results presented in this section. Figures 3–5 depict the TOC when the number of batches R, varies between |R|min and |R|max for each instance.
We can see that the number of batches is optimal when TOC reaches its lowest value. In order to find more precise optimal values, we penalized the solutions with excess weight, adding an additional cost to them.
Table 11 presents the best solutions obtained by the HEA for instances DS4, DS5 and DS6. We compare them to results in reference [2]. The rows indicate some natural measures of performance, like the total travel distance in the pick-up plan (Dtotal), the optimal number of batches, the mean of the distribution of distances travelled on batches (Dmed), the standard deviation of that distribution (Dstd), the sum of earliness and tardiness (ETtime) and the total operational cost (TOC). Here distances are measured in meters, times in seconds and monetary costs in US dollars.
Multiple-GA [2] | HEA [3] | |||||
DS4 | DS5 | DS6 | DS4 | DS5 | DS6 | |
Dtotal | 948.00 | 4905.00 | 17799.00 | 1036.74 | 4470.20 | 19448.89 |
nLot | 8.00 | 15.00 | 23.00 | 8.00 | 14.00 | 22.00 |
Dmed | 118.50 | 327.00 | 773.87 | 129.59 | 319.30 | 884.04 |
Dstd | 8.26 | 18.96 | 24.35 | 11.26 | 24.55 | 59.94 |
ETtime | 1790.00 | 6826.00 | 25500.00 | 1700.50 | 6552.96 | 22440.00 |
TOC | 1322.20 | 4431.03 | 14546.63 | 1281.58 | 3672.14 | 14317.82 |
Table 12 indicates that HEA yields a better TOC on the different instances. This is, in general not the case for the total distance traveled (except for instance DS5).
DS4 | DS5 | DS6 | Average | |
Dtotal(Multiple-GA)/Dtotal(HEA) | 0.914 | 1.097 | 0.915 | 0.976 |
TOC(Multiple-GA)/TOC(HEA) | 1.032 | 1.207 | 1.016 | 1.085 |
Figure 6 presents boxplots indicating the variability, degree of asymmetry and the extreme values of the distributions of Dtotal, ETtime and TOC obtained with our HEA on instances DS4, DS5 and DS6, using the optimal number of batches in each case.
We can see that in the boxplot of instance DS4 for Dtotal, we have an atypical value close to the minimal one for 8 batches, but 50% of the values of the distribution of Dtotal is way above that value. In the case of ETtime the central values are below their corresponding benchmark values. This is also the case for TOC. In summary, even if HEA does not yield better results in terms of Dtotal, the quality of solutions measured by TOC and ETtime improves over the known results.
In this paper we addressed an integrated problem that combines the Order Batching Problem (OBP) and the Order Picking Problem (OPP) using a hybrid evolutionary algorithm (HEA). This algorithm uses a novel representation of the problem using specific knowledge that allows restricting the search space. The crossover and mutation operators are hybridized with a heuristic that allows finding better routes for the pick-up teams. Tsai et al. [2] generated 2D instances of this problem (in which items are stored at the same level) and 3D ones (with items placed at different levels). We have previously applied the HEA to 2D instances, with very good results [3,4]. In this paper we have addressed the more complex 3D instances. The results, in terms of the objective function, improve over those in reference [2], which were obtained using a Multiple-GA. This completes the testing of the HEA.
Future work involves considering this problem but in a multi-objective and cross-dock setting. The reach of the problem can be extended, studying the relation between the placement of items in the different layouts and the distribution of the last mile. Other aspects should also be considered, in particular those impacting on the operational planning of the activities in storage sites, like the volume and size of the packages, the relative demands of the different items, their rotation and similar considerations.
The authors are grateful for partial support from the following sources: National Scientific and Technical Research Council CONICET Grant PIP No. 11220150100777, Universidad Nacional del Sur Grant PGI 24/J086 and Universidad Nacional de Río Negro PI-JI 40-A-917.
The authors declare they have no financial interests. In addition, the authors have no conflicts of interest to declare that are relevant to the content of this article.
[1] | R. Herrmann, Fractional Calculus, An Introduction for Physicists (2nd Edition), Singapore, World Scientific, 2014. |
[2] |
D. Baleanu, O. Defterli, O. P. Agrawal, A central difference numerical scheme for fractional optimal control problems, J. Vib. Control., 15 (2009), 583–597. doi: 10.1177/1077546308088565
![]() |
[3] |
T. S. Aleroev, H. T. Aleroeva, J. F. Huang, N. M. Nie, Y. F. Tang, et al., Features of seepage of a liquid to a chink in the cracked deformable layer, Int. J. Model. Simul. Sci. Comput., 1 (2010), 333–347. doi: 10.1142/S1793962310000195
![]() |
[4] | L. Song, W. Wang, Solution of the fractional Black-Scholes option pricing model by finite difference method, Abstr. Appl. Anal., 45 (2013), 1–16. |
[5] |
R. Metzler, J. Klafter, Boundary value problems for fractional diffusion equations, Physica A., 278 (2000), 107–125. doi: 10.1016/S0378-4371(99)00503-8
![]() |
[6] |
W. R. Schneider, W. Wyss, Fractional diffusion and wave equations, J. Math. Phys., 30 (1989), 134–144. doi: 10.1063/1.528578
![]() |
[7] | Y. Luchko, F. Mainardi, Some properties of the fundamental solution to the signalling problem for the fractional diffusion-wave equation, Cent. Eur. J. Phys., 11 (2013), 666–675. |
[8] |
X. Hu, L. Zhang, On finite difference methods for fourth-order fractional diffusion-wave and sub-diffusion systems, Appl. Math. Comput., 218 (2012), 5019–5034. doi: 10.1016/j.amc.2011.10.069
![]() |
[9] |
J. F. Huang, D. D. Yang, A unified difference-spectral method for time-space fractional diffusion equations, Int. J. Comput. Math., 94 (2017), 1172–1184. doi: 10.1080/00207160.2016.1184262
![]() |
[10] | O. Nikan, A. Golbabai, J. T. Machado, T. Nikazad, Numerical approximation of the time fractional cable equation arising in neuronal dynamics, Eng. Comput., (2020), 1–19. |
[11] |
F. Zeng, Second order stable finite difference schemes for the time fractional diffusion-wave equation, J. Sci. Comput., 65 (2015), 411–430. doi: 10.1007/s10915-014-9966-2
![]() |
[12] |
O. Nikan, H. Jafari, A. Golbabai, Numerical analysis of the fractional evolution model for heat flow in materials with memory, Alexandria Eng. J., 59 (2020), 2627–2637. doi: 10.1016/j.aej.2020.04.026
![]() |
[13] | R. R. Nigmatullin, To the theoretical explanation of the universal response, Phys. Status Solidi, B Basic Res., 123 (1984), 739–745. |
[14] |
R. R. Nigmatullin, Realization of the generalized transfer equation in a medium with fractal geometry, Phys. Status Solidi, B Basic Res., 133 (1986), 425–430. doi: 10.1002/pssb.2221330150
![]() |
[15] | K. B. Oldham, J. Spanier, The Fractional Calculus, Academic Press, NewYork, 1974. |
[16] |
A. H. Bhrawy, E. H. Doha, D. Baleanud, S. S. Ezz-Eldien, A spectral tau algorithm based on Jacobi operational matrix for numerical solution of time fractional diffusion-wave equations, J. Comput. Phys., 293 (2015), 142–156. doi: 10.1016/j.jcp.2014.03.039
![]() |
[17] |
J. Chen, F. Liu, V. Anh, S. Shen, Q. Liu, et al., The analytical solution and numerical solution of the fractional diffusion-wave equation with damping, Appl. Math. Comput., 219 (2012), 1737–1748. doi: 10.1016/j.amc.2012.08.014
![]() |
[18] |
A. Ebadian, H. R. Fazli, A. A. Khajehnasiri, Solution of nonlinear fractional diffusion-wave equation by traingular functions, SeMA. J., 72 (2015), 37–46. doi: 10.1007/s40324-015-0045-x
![]() |
[19] |
M. H. Heydari, M. R. Hooshmandasl, F. M. Maalek Ghaini, C. Cattani, Wavelets method for the time fractional diffusion-wave equation, Phys. Lett. A., 379 (2015), 71–76. doi: 10.1016/j.physleta.2014.11.012
![]() |
[20] |
N. Khalid, M. Abbas, M. K. Iqbal, D. Baleanu, A numerical algorithm based on modified extended b-spline functions for solving time-fractional diffusion wave equation involving reaction and damping terms, Adv. Differ. Equ., 2019 (2019), 378. doi: 10.1186/s13662-019-2318-7
![]() |
[21] | O. H. Mohammed, S. F. Fadhel, M. G. S. AL-Safi, Numerical solution for the time fractional diffusion-wave equations by using Sinc-Legendre collocation method, Math. Theory. Model., 5 (2015), 49–57. |
[22] | F. Y. Zhou, X. Y. Xu, Numerical solution of time-fractional diffusion-wave equations via Chebyshev wavelets collocation method, Adv. Math. Phys., 2017 (2017), 2610804. |
[23] |
H. Y. He, K. J. Liang, B. L. Yin, A numerical method for two-dimensional nonlinear modified time-fractional fourth-order diffusion equation, Int. J. Model. Simul. Sci. Comput., 10 (2019), 1941005. doi: 10.1142/S1793962319410058
![]() |
[24] |
Y. Liu, Y. W. Du, H. Li, S. He, W. Gao, Finite difference/finite element method for a nonlinear time-fractional fourth-order reaction-diffusion problem, Comput. Math. Appl., 70 (2015), 573–591. doi: 10.1016/j.camwa.2015.05.015
![]() |
[25] | O. Nikan, J. T. Machado, A. Golbabai, Numerical solution of time fractional fourth order reaction-diffusion model arising in composite environments, Appl. Math. Model., 81 (2020), 819–836. |
[26] |
O. Nikan, Z. Avazzadeh, J. A. Tenreiro Machado, An efficient local meshless approach for solving nonlinear time fractional fourth-order diffusion model, J. King Saud Univ. Sci., 33 (2021), 101243. doi: 10.1016/j.jksus.2020.101243
![]() |
[27] | K. Diethelm, The Analysis of Fractional Differential Equations. Springer, Berlin, (2010). |
[28] | J. F. Huang, S. Arshad, Y. D. Jiao, Y. F. Tang, Convolution quadrature methods for time-space fractional nonlinear diffusion-wave equations, E. Asian J. Appl. Math., 9 (2019), 538–557. |
[29] |
C. Lubich, Convolution quadrature and discretized operational calculus I, Numer. Math., 52 (1988), 129–145. doi: 10.1007/BF01398686
![]() |
[30] |
W. Y. Tian, H. Zhou, W. H. Deng, A class of second order difference approximations for solving space fractional diffusion equations, Math. Comput., 84 (2015), 1703–1727. doi: 10.1090/S0025-5718-2015-02917-2
![]() |
[31] | Z. Z. Sun, The Method of Order Reduction and Its Application to the Numerical Solutions of Partial Differential Equations, Science Press, Beijing, 2009. |
[32] |
M. R. Cui, Compact difference scheme for time-fractional fourth-order equation with first Dirichlet boundary condition, E. Asian J. Appl. Math., 9 (2019), 45–66. doi: 10.4208/eajam.260318.220618
![]() |
[33] |
J. C. Lopze-Marcos, A difference scheme for a nonlinear partial integrodifferential equation, SIAM J. Numer. Anal., 27 (1990), 20–31. doi: 10.1137/0727002
![]() |
[34] |
Z. B. Wang, S. W. Vong, Compact difference schemes for the modified anomalous fractional sub-diffusion equation and the fractional diffusion-wave equation, J. Comput. Phys., 277 (2014), 1–15. doi: 10.1016/j.jcp.2014.08.012
![]() |
[35] | C. Li, F. Zeng, Numerical Methods for Fractional Calculus, Chapman and Hall/CRC, New York, 2015. |
[36] |
J. Cao, Y. Qiu, G. Song, A compact finite difference scheme for variable order subdiffusion equation, Commun. Nonlinear Sci. Numer. Simul., 48 (2017), 140–149. doi: 10.1016/j.cnsns.2016.12.022
![]() |
[37] |
C. C. Ji, Z. Z. Sun, A high-order compact finite difference scheme for the fractional sub-diffusion equation, J. Sci. Comput., 64 (2015), 959–985. doi: 10.1007/s10915-014-9956-4
![]() |
1. | Huan Zhang, Yin Zhou, Yuhua Long, Results on multiple nontrivial solutions to partial difference equations, 2022, 8, 2473-6988, 5413, 10.3934/math.2023272 | |
2. | Yuhua Long, Multiple results on nontrivial solutions of discrete Kirchhoff type problems, 2023, 69, 1598-5865, 1, 10.1007/s12190-022-01731-0 | |
3. | Yuhua Long, Dan Li, Multiple nontrivial periodic solutions to a second-order partial difference equation, 2023, 31, 2688-1594, 1596, 10.3934/era.2023082 | |
4. | Yuhua Long, Huan Zhang, Existence and multiplicity of nontrivial solutions to discrete elliptic Dirichlet problems, 2022, 30, 2688-1594, 2681, 10.3934/era.2022137 | |
5. | Yuhua Long, Qinqin Zhang, SIGN-CHANGING SOLUTIONS OF A DISCRETE FOURTH-ORDER LIDSTONE PROBLEM WITH THREE PARAMETERS, 2022, 12, 2156-907X, 1118, 10.11948/20220148 | |
6. | Yuhua Long, Nontrivial solutions of discrete Kirchhoff-type problems via Morse theory, 2022, 11, 2191-950X, 1352, 10.1515/anona-2022-0251 |
Request | Item | Total | |||
A | B | C | D | ||
1 | 1 | 0 | 2 | 0 | 3 |
2 | 1 | 1 | 2 | 1 | 5 |
3 | 0 | 2 | 0 | 2 | 4 |
Total | 2 | 3 | 4 | 3 | 12 |
Item | A | A | B | B | B | C | C | C | C | D | D | D |
Request to which it belongs | 1 | 2 | 2 | 3 | 3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
Item | A | A | B | B | B | C | C | C | C | D | D | D |
Request to which it belongs | 1 | 2 | 2 | 3 | 3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
Genome 1 / Assigned batch | 2 | 3 | 2 | 3 | 3 | 1 | 1 | 3 | 1 | 1 | 1 | 3 |
Genome 2 / Position in sequence | 2 | 1 | 1 | 3 | 5 | 1 | 3 | 4 | 5 | 4 | 2 | 2 |
Genome 1 | Genome 2 | ||||||||||||||||||||||
2 | 3 | 2 | 3 | 3 | 1 | 1 | 3 | 1 | 1 | 1 | 3 | 2 | 1 | 1 | 3 | 5 | 1 | 3 | 4 | 5 | 4 | 2 | 2 |
Batch | Item (Request) | ||||
1 | C (1) | D (3) | C (1) | D (2) | C (2) |
2 | B (2) | A (1) | |||
3 | A (2) | D (3) | B (3) | C (2) | B (3) |
1: Load Input % information of requests, the lay-out of the storage center and parameters of the algorithm. |
2: nBatch ← nBatchMin 3: while nBatch < nBatchMax 4: t ← 0; 5: P(t) ← InitPop(input); 6: FitP(t) ← EvalPop(P(t)); 7: For t ← 1 a MaxNumGen 8: Q(t) ← SelecBreeders (P(t), FitP(t)); 9: Q(t) ← HybridCrossover(Q(t)); 10: Q(t) ← HybridMutation(Q(t)); 11: FitQ(t) ← EvalPop(Q(t)); 12: P(t) ← SelSurviv(P(t), Q(t), FitP(t), FitQ(t)); 13: FitP(t) ← EvalPop(P(t)); 14: if TermCond(P(t), FitP(t)) 15: break; 16: end 17: end 18: nBatch ← nBatch + 1; 18: end |
DS0 | DS1 | DS2 | DS3 | DS4 | DS5 | DS6 | |
Problem size | Small | Small | Medium | Large | Small | Medium | Large |
Number of requests | 25 | 40 | 80 | 200 | 40 | 100 | 250 |
Number of different items | 30 | 80 | 160 | 300 | 80 | 200 | 400 |
Lay-out type | 2D | 2D | 2D | 2D | 3D | 3D | 3D |
Average total weight (kg.) | 18584 | 13704 | 37152 | 158784 | 12424 | 54048 | 295784 |
Capacity of pick-up teams (kg.) | 7000 | 10000 | 10000 | 20000 | 10000 | 10000 | 50000 |
Request | Items:quantities | Deadline |
P1 | (4:2) (5:9) (18:5) (40:4) (55:5) (62:6) (67:5) | 17:38:41 |
P2 | (1:6) (11:7) (13:1) (16:3) (18:4) (20:2) (58:6) (59:9) (60:5) (64:8) (68:6) (76:3) (77:2) | 17:11:44 |
P3 | (7:1) (21:10) (27:5) (31:4) (38:7) (41:8) (42:5) (44:4) (46:8) (51:7) (60:7) (78:5) | 15:56:12 |
P4 | (23:4) (35:4) (53:9) (54:8) (62:4) (64:8) (70:7) (80:8) | 17:57:13 |
P5 | (10:2) (33:7) (38:8) (39:1) (41:7) (46:7) (52:7) (53:5) (63:3) (71:10) | 15:15:02 |
P6 | (11:5) (19:3) (44:9) (59:2) (72:7) (80:8) | 15:52:38 |
P7 | (11:10) (18:4) (26:5) (34:4) (37:4) (53:4) (54:4) | 14:22:30 |
... | ... | ... |
P38 | (17:10) (34:3) (47:4) (49:3) | 14:35:54 |
P39 | (15:2) (23:10) (31:9) (45:8) (59:9) (66:2) (69:6) (76:6) | 15:24:01 |
P40 | (9:2) (29:1) (37:6) (49:6) (58:3) (74:2) (76:1) | 16:36:54 |
Request | Items:quantities | Deadline |
P1 | (15:9) (34:6) (107:10) (120:4) (134:7) (178:2) (184:1) (192:6) | 15:05:09 |
P2 | (1:6) (7:8) (40:7) (62:2) (85:1) (98:10) (121:8) (123:6) | 16:10:57 |
P3 | (6:1) (19:10) (44:4) (113:9) (115:2) (124:10) (132:5) (160:6) (167:10) (195:5) (198:2) | 16:24:33 |
P4 | (57:6) (78:1) (85:9) (89:1) (94:2) (107:7) (133:3) (143:4) (166:8) (180:9) (199:2) | 15:27:07 |
P5 | (7:10) (21:8) (33:5) (37:1) (50:6) (74:2) (119:4) (171:3) (176:5) | 16:42:02 |
P6 | (11:3) (15:4) (34:5) (37:2) (48:2) (69:8) (155:6) (174:9) (176:9) (177:8) (182:9) (188:9) | 15:38:01 |
P7 | (73:1) (145:9) (191:7) (193:6) | 15:25:51 |
... | ... | ... |
P98 | (44:1) (57:8) (65:7) (79:5) (121:3) (157:3) (189:7) | 14:47:52 |
P99 | (34:10) (52:5) (120:8) (133:1) (160:2) | 15:29:12 |
P100 | (7:8) (13:6) (28:10) (38:2) (51:8) (86:2) (121:5) (127:3) (183:10) | 14:58:35 |
Request | Items:quantities | Deadline |
P1 | (10:2) (87:5) (126:7) (172:1) (207:4) (276:4) (314:1) (351:8) (396:7) | 14:46:43 |
P2 | (54:1) (107:4) (157:3) (255:7) (328:2) | 15:31:42 |
P3 | (141:5) (152:10) (171:7) (243:7) (306:5) | 15:16:38 |
P4 | (35:1) (68:7) (194:3) (228:6) (313:8) (321:2) (335:4) (359:8) (375:7) (391:6) | 14:13:20 |
P5 | (54:9) (70:9) (85:7) (115:3) (154:6) (280:8) (370:2) (399:4) | 15:30:15 |
P6 | (45:5) (64:4) (111:7) (150:1) (161:6) (166:5) (346:10) | 15:26:27 |
P7 | (84:8) (151:10) (313:9) (353:2) (400:4) | 14:06:20 |
... | ... | ... |
P248 | (43:4) (157:4) (313:10) (362:2) | 15:01:47 |
P249 | (66:8) (99:10) (114:4) (140:4) (174:9) (178:10) (195:5) (196:3) (292:7) | 16:17:18 |
P250 | (26:6) (56:8) (97:4) (106:6) (107:1) (126:4) (186:6) (228:4) (254:3) | 17:27:49 |
Multiple-GA [2] | HEA [3] | |||||
DS4 | DS5 | DS6 | DS4 | DS5 | DS6 | |
Dtotal | 948.00 | 4905.00 | 17799.00 | 1036.74 | 4470.20 | 19448.89 |
nLot | 8.00 | 15.00 | 23.00 | 8.00 | 14.00 | 22.00 |
Dmed | 118.50 | 327.00 | 773.87 | 129.59 | 319.30 | 884.04 |
Dstd | 8.26 | 18.96 | 24.35 | 11.26 | 24.55 | 59.94 |
ETtime | 1790.00 | 6826.00 | 25500.00 | 1700.50 | 6552.96 | 22440.00 |
TOC | 1322.20 | 4431.03 | 14546.63 | 1281.58 | 3672.14 | 14317.82 |
DS4 | DS5 | DS6 | Average | |
Dtotal(Multiple-GA)/Dtotal(HEA) | 0.914 | 1.097 | 0.915 | 0.976 |
TOC(Multiple-GA)/TOC(HEA) | 1.032 | 1.207 | 1.016 | 1.085 |
Request | Item | Total | |||
A | B | C | D | ||
1 | 1 | 0 | 2 | 0 | 3 |
2 | 1 | 1 | 2 | 1 | 5 |
3 | 0 | 2 | 0 | 2 | 4 |
Total | 2 | 3 | 4 | 3 | 12 |
Item | A | A | B | B | B | C | C | C | C | D | D | D |
Request to which it belongs | 1 | 2 | 2 | 3 | 3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
Item | A | A | B | B | B | C | C | C | C | D | D | D |
Request to which it belongs | 1 | 2 | 2 | 3 | 3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
Genome 1 / Assigned batch | 2 | 3 | 2 | 3 | 3 | 1 | 1 | 3 | 1 | 1 | 1 | 3 |
Genome 2 / Position in sequence | 2 | 1 | 1 | 3 | 5 | 1 | 3 | 4 | 5 | 4 | 2 | 2 |
Genome 1 | Genome 2 | ||||||||||||||||||||||
2 | 3 | 2 | 3 | 3 | 1 | 1 | 3 | 1 | 1 | 1 | 3 | 2 | 1 | 1 | 3 | 5 | 1 | 3 | 4 | 5 | 4 | 2 | 2 |
Batch | Item (Request) | ||||
1 | C (1) | D (3) | C (1) | D (2) | C (2) |
2 | B (2) | A (1) | |||
3 | A (2) | D (3) | B (3) | C (2) | B (3) |
1: Load Input % information of requests, the lay-out of the storage center and parameters of the algorithm. |
2: nBatch ← nBatchMin 3: while nBatch < nBatchMax 4: t ← 0; 5: P(t) ← InitPop(input); 6: FitP(t) ← EvalPop(P(t)); 7: For t ← 1 a MaxNumGen 8: Q(t) ← SelecBreeders (P(t), FitP(t)); 9: Q(t) ← HybridCrossover(Q(t)); 10: Q(t) ← HybridMutation(Q(t)); 11: FitQ(t) ← EvalPop(Q(t)); 12: P(t) ← SelSurviv(P(t), Q(t), FitP(t), FitQ(t)); 13: FitP(t) ← EvalPop(P(t)); 14: if TermCond(P(t), FitP(t)) 15: break; 16: end 17: end 18: nBatch ← nBatch + 1; 18: end |
DS0 | DS1 | DS2 | DS3 | DS4 | DS5 | DS6 | |
Problem size | Small | Small | Medium | Large | Small | Medium | Large |
Number of requests | 25 | 40 | 80 | 200 | 40 | 100 | 250 |
Number of different items | 30 | 80 | 160 | 300 | 80 | 200 | 400 |
Lay-out type | 2D | 2D | 2D | 2D | 3D | 3D | 3D |
Average total weight (kg.) | 18584 | 13704 | 37152 | 158784 | 12424 | 54048 | 295784 |
Capacity of pick-up teams (kg.) | 7000 | 10000 | 10000 | 20000 | 10000 | 10000 | 50000 |
Request | Items:quantities | Deadline |
P1 | (4:2) (5:9) (18:5) (40:4) (55:5) (62:6) (67:5) | 17:38:41 |
P2 | (1:6) (11:7) (13:1) (16:3) (18:4) (20:2) (58:6) (59:9) (60:5) (64:8) (68:6) (76:3) (77:2) | 17:11:44 |
P3 | (7:1) (21:10) (27:5) (31:4) (38:7) (41:8) (42:5) (44:4) (46:8) (51:7) (60:7) (78:5) | 15:56:12 |
P4 | (23:4) (35:4) (53:9) (54:8) (62:4) (64:8) (70:7) (80:8) | 17:57:13 |
P5 | (10:2) (33:7) (38:8) (39:1) (41:7) (46:7) (52:7) (53:5) (63:3) (71:10) | 15:15:02 |
P6 | (11:5) (19:3) (44:9) (59:2) (72:7) (80:8) | 15:52:38 |
P7 | (11:10) (18:4) (26:5) (34:4) (37:4) (53:4) (54:4) | 14:22:30 |
... | ... | ... |
P38 | (17:10) (34:3) (47:4) (49:3) | 14:35:54 |
P39 | (15:2) (23:10) (31:9) (45:8) (59:9) (66:2) (69:6) (76:6) | 15:24:01 |
P40 | (9:2) (29:1) (37:6) (49:6) (58:3) (74:2) (76:1) | 16:36:54 |
Request | Items:quantities | Deadline |
P1 | (15:9) (34:6) (107:10) (120:4) (134:7) (178:2) (184:1) (192:6) | 15:05:09 |
P2 | (1:6) (7:8) (40:7) (62:2) (85:1) (98:10) (121:8) (123:6) | 16:10:57 |
P3 | (6:1) (19:10) (44:4) (113:9) (115:2) (124:10) (132:5) (160:6) (167:10) (195:5) (198:2) | 16:24:33 |
P4 | (57:6) (78:1) (85:9) (89:1) (94:2) (107:7) (133:3) (143:4) (166:8) (180:9) (199:2) | 15:27:07 |
P5 | (7:10) (21:8) (33:5) (37:1) (50:6) (74:2) (119:4) (171:3) (176:5) | 16:42:02 |
P6 | (11:3) (15:4) (34:5) (37:2) (48:2) (69:8) (155:6) (174:9) (176:9) (177:8) (182:9) (188:9) | 15:38:01 |
P7 | (73:1) (145:9) (191:7) (193:6) | 15:25:51 |
... | ... | ... |
P98 | (44:1) (57:8) (65:7) (79:5) (121:3) (157:3) (189:7) | 14:47:52 |
P99 | (34:10) (52:5) (120:8) (133:1) (160:2) | 15:29:12 |
P100 | (7:8) (13:6) (28:10) (38:2) (51:8) (86:2) (121:5) (127:3) (183:10) | 14:58:35 |
Request | Items:quantities | Deadline |
P1 | (10:2) (87:5) (126:7) (172:1) (207:4) (276:4) (314:1) (351:8) (396:7) | 14:46:43 |
P2 | (54:1) (107:4) (157:3) (255:7) (328:2) | 15:31:42 |
P3 | (141:5) (152:10) (171:7) (243:7) (306:5) | 15:16:38 |
P4 | (35:1) (68:7) (194:3) (228:6) (313:8) (321:2) (335:4) (359:8) (375:7) (391:6) | 14:13:20 |
P5 | (54:9) (70:9) (85:7) (115:3) (154:6) (280:8) (370:2) (399:4) | 15:30:15 |
P6 | (45:5) (64:4) (111:7) (150:1) (161:6) (166:5) (346:10) | 15:26:27 |
P7 | (84:8) (151:10) (313:9) (353:2) (400:4) | 14:06:20 |
... | ... | ... |
P248 | (43:4) (157:4) (313:10) (362:2) | 15:01:47 |
P249 | (66:8) (99:10) (114:4) (140:4) (174:9) (178:10) (195:5) (196:3) (292:7) | 16:17:18 |
P250 | (26:6) (56:8) (97:4) (106:6) (107:1) (126:4) (186:6) (228:4) (254:3) | 17:27:49 |
Multiple-GA [2] | HEA [3] | |||||
DS4 | DS5 | DS6 | DS4 | DS5 | DS6 | |
Dtotal | 948.00 | 4905.00 | 17799.00 | 1036.74 | 4470.20 | 19448.89 |
nLot | 8.00 | 15.00 | 23.00 | 8.00 | 14.00 | 22.00 |
Dmed | 118.50 | 327.00 | 773.87 | 129.59 | 319.30 | 884.04 |
Dstd | 8.26 | 18.96 | 24.35 | 11.26 | 24.55 | 59.94 |
ETtime | 1790.00 | 6826.00 | 25500.00 | 1700.50 | 6552.96 | 22440.00 |
TOC | 1322.20 | 4431.03 | 14546.63 | 1281.58 | 3672.14 | 14317.82 |
DS4 | DS5 | DS6 | Average | |
Dtotal(Multiple-GA)/Dtotal(HEA) | 0.914 | 1.097 | 0.915 | 0.976 |
TOC(Multiple-GA)/TOC(HEA) | 1.032 | 1.207 | 1.016 | 1.085 |