
Citation: Diego Ardila, Dorsa Sanadgol, Didier Sornette. Out-of-sample forecasting of housing bubble tipping points[J]. Quantitative Finance and Economics, 2018, 2(4): 904-930. doi: 10.3934/QFE.2018.4.904
[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 |
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] | Antipa P, Lecat R (2010) The Housing Bubble and Financial Factors: Insights from a Structural Model of the French and Spanish Residential Markets. Housing Markets in Europe. Springer, Berlin, Heidelberg 161–186. |
[2] |
Anundsen AK (2015) Econometric regime shifts and the us subprime bubble. J Appl Econ 30: 145–169. doi: 10.1002/jae.2367
![]() |
[3] | Anundsen AK, Jansen ES (2011) Self-reinforcing effects between housing prices and credit. J Hous Econ 22: 192–212. |
[4] |
Ayuso J, Restoy F (2006) House prices and rents: An equilibrium asset pricing approach. J Empir Financ 13: 371–388. doi: 10.1016/j.jempfin.2005.10.004
![]() |
[5] | Barsky RB (2009) The japanese bubble: A 'heterogeneous' approach. NBER Working Paper No. 15052. |
[6] |
Berry M, Dalton T (2004) Housing prices and policy dilemmas: a peculiarly australian problem? Urban Policy Res 22: 69–91. doi: 10.1080/0811114042000185509
![]() |
[7] |
Black A, Fraser P, Hoesli M (2006) House prices, fundamentals and bubbles. J Bus Finan Account 33: 1535–1555. doi: 10.1111/j.1468-5957.2006.00638.x
![]() |
[8] | Blanchard OJ, Watson MW (1982) Bubbles, rational expectations and financial markets. NBER Working Paper No. 945. |
[9] | Bourassa SC, Hoesli M, Oikarinen E (2016) Measuring house price bubbles. Real Estate Econ 1–30. |
[10] | Brunnermeier MK, Oehmke M (2012) Bubbles, financial crises, and systemic risk. Handbook of The Econ of Financ 2: 1221–1288. |
[11] | Busetti F, Taylor A (2004) Tests of stationarity against a change in persistence. J of Econ 1: 33–66. |
[12] | Cameron G, Muellbauer J, Murphy A (2006) Was there a British house price bubble? evidence from a regional panel. CEPR Discussion Paper No. 5619. |
[13] |
Campbell JY, Shiller RJ (1988) The dividend-price ratio and expectations of future dividends and discount factors. Rev Financ Stud 1: 195–228. doi: 10.1093/rfs/1.3.195
![]() |
[14] | Case KE, Shiller RJ (2003) Is there a bubble in the housing market? Brook Pap Econ Act 299–342. |
[15] |
Christensen I, Li F (2014) Predicting financial stress events: A signal extraction approach. J Financ Stab 14: 54–65. doi: 10.1016/j.jfs.2014.08.005
![]() |
[16] |
Connor G, Flavin T, O'Kelly B (2012) The us and irish credit crises: Their distinctive differences and common features. J Int Money Finan 31: 60–79. doi: 10.1016/j.jimonfin.2011.11.005
![]() |
[17] |
Claussen CA (2013) Are swedish houses overpriced? Int J Hous Mark Analysis 6: 180–196. doi: 10.1108/IJHMA-12-2011-0056
![]() |
[18] | Dam NA, Hvolbøl TS, Pedersen EH, et al. (2011) Developments in the market for owner-occupied housing in recent years–can house prices be explained. Danmarks Nationalbank, Monetary Rev, 1st Quarter 1–82. |
[19] | Das S, Gupta R, Kanda R (2011) International articles: Bubbles in south african house prices and their impact on consumption. J of Real Estate Literature 19: 69–91. |
[20] |
Davidson R, MacKinnon JG (1981) Several tests for model specification in the presence of alternative hypotheses. Econ 49: 781–793. doi: 10.2307/1911522
![]() |
[21] | Drehmann M, Borio CE, Tsatsaronis K (2012) Characterising the financial cycle: don't lose sight of the medium term! BIS Working Papers No 380. |
[22] |
Drehmann M, Juselius M (2014) Evaluating early warning indicators of banking crises: Satisfying policy requirements. Int J Forecast 30: 759–780. doi: 10.1016/j.ijforecast.2013.10.002
![]() |
[23] | Edison HJ (2003) Do indicators of financial crises work? An evaluation of an early warning system. Int J of Financ & Econ 8: 11–53. |
[24] |
Feigenbaum JA, Freund P (1996) Discrete scale invariance in stock markets before crashes. Int J of Modern Physics B 10: 3737–3745. doi: 10.1142/S021797929600204X
![]() |
[25] |
Filimonov V, Sornette D (2013) A stable and robust calibration scheme of the log-periodic power law model. Physica A 392: 3698–3707. doi: 10.1016/j.physa.2013.04.012
![]() |
[26] | Flood RP, Hodrick RJ (1990) On testing for speculative bubbles. J Econ Perspect 4: 85–101. |
[27] | Francke M, Vujic S, Vos GA (2009) Evaluation of house price models using an ecm approach: the case of the netherlands. OFRC Working Paper No. 2009–05. |
[28] | Gençay R, Gradojevic N (2010) Crash of 87 was it expected?: Aggregate market fears and long-range dependence. J Empir Financ 17: 270–282. |
[29] | Giglio S, Maggiori M, Stroebel J (2014) No-bubble condition: Model-free tests in housing markets. NBER Working Paper No. w20154. |
[30] |
Gisler M, Sornette D (2009) Exuberant innovations: the Apollo program. Society 46: 55–68. doi: 10.1007/s12115-008-9163-8
![]() |
[31] | Gisler M, Sornette D (2010) Bubbles everywhere in human affairs. Swiss Financ Institute Res Paper 137–153 |
[32] |
Gisler M, Sornette D, Woodard R (2011) Innovation as a social bubble: The example of the human genome project. Res Policy 40: 1412–1425. doi: 10.1016/j.respol.2011.05.019
![]() |
[33] | Gjerstad SD, Smith VL (2014) Rethinking housing bubbles: The role of household and bank balance sheets in modeling economic cycles.Cambridge: Cambridge University Press. |
[34] | Glindro ET, Subhanij T, Szeto J et al. (2011) Determinants of house prices in nine asia-pacific economies. J Cent Bank 7: 163–204. |
[35] | Homm U, Breitung J (2012) Testing for speculative bubbles in stock markets: a comparison of alternative methods. J of Financ Econ 10: 198–231. |
[36] |
Hort K (1998) The determinants of urban house price fluctuations in sweden 1968–1994. J of housing Econ 7: 93–120. doi: 10.1006/jhec.1998.0225
![]() |
[37] |
Hott C (2012) The influence of herding behaviour on house prices. J of European Real Estate Res 5: 177–198. doi: 10.1108/17539261211282046
![]() |
[38] |
Hott C, Monnin P (2008) Fundamental real estate prices: an empirical estimation with international data. J Real Estate Financ Econ 36: 427–450. doi: 10.1007/s11146-007-9097-8
![]() |
[39] |
Hüsler A, Sornette D, Hommes CH (2013) Super-exponential bubbles in lab experiments: evidence for anchoring over-optimistic expectations on price. J Econ Behav Organ 92: 304–316. doi: 10.1016/j.jebo.2013.06.005
![]() |
[40] | Jacobsen DH, Naug BE (2005) What drives house prices? Norges Bank. Econ Bulletin 76: 29–41 |
[41] | Johansen A, Ledoit O, Sornette D (2000) Crashes as critical points. Int J of Theoretical and Applied Financ 3: 219–255. |
[42] | Johansen A, Sornette D (1999) Predicting financial crashes using discrete scale invariance. J Risk 1: 5–32. |
[43] | Jordà Ò, Schularick M, Taylor AM (2015) Leveraged bubbles. J Monetary Econ 76: S1–S20. |
[44] |
Kim BH, Min HG (2011) Household lending, interest rates and housing price bubbles in Korea: Regime switching model and kalman filter approach. Economic Modelling 28: 1415–1423. doi: 10.1016/j.econmod.2011.02.001
![]() |
[45] | Kim JY (2000) Detection of change in persistence of a linear time series. J of Econ 95: 97–116. |
[46] |
Kittler J, Hatef M, Duin RP et al. (1998) On combining classifiers. IEEE Trans Pattern Anal Mach Intell 20: 226–239. doi: 10.1109/34.667881
![]() |
[47] | Laeven L, Valencia F (2008) Systemic banking crises: a new database. IMF Working Paper No. 08/224. |
[48] |
Leiss M, Nax HH, Sornette D (2015) Super-exponential growth expectations and the global financial crisis. J Econ Dyn Control 55: 1–13. doi: 10.1016/j.jedc.2015.03.005
![]() |
[49] |
Lin L, Sornette D (2013) Diagnostics of rational expectation financial bubbles with stochastic mean-reverting termination times. Eur J Financ 19: 344–365. doi: 10.1080/1351847X.2011.607004
![]() |
[50] | Lux T, Sornette D (2002) On rational bubbles and fat tails, Journal of Money, Credit and Banking, Ohio State University Press, 589–610. |
[51] | Mack A, Martínez-García E (2011) A cross-country quarterly database of real house prices: a methodological note. Globalization and Monetary Policy Institute Working Paper NO.99 |
[52] | Mason SJ, Graham N (2002) Areas beneath the relative operating characteristics (roc) and relative operating levels (rol) curves: Statistical significance and interpretation. Q J R Meteorol Soc 128: 2145–2166. |
[53] | Mikhed V, Zemčík P (2009) Do house prices reflect fundamentals? aggregate and panel data evidence. J Hous Econ 18: 140–149. |
[54] | Misina M, Tkacz G (2009) Credit, asset prices, and financial stress. Int J Cent Bank 5: 95–122. |
[55] |
Muellbauer J, Murphy A (1997) Booms and busts in the UK housing market. The Econ J 107: 1701–1727. doi: 10.1111/j.1468-0297.1997.tb00076.x
![]() |
[56] |
Narayan PK, Sharma SS, Phan DHB (2016) Asset price bubbles and economic welfare. Int Rev Financ Anal 44: 139–148. doi: 10.1016/j.irfa.2016.01.011
![]() |
[57] |
Neal L, García-Iglesias MC (2013) The economy of spain in the euro-zone before and after the crisis of 2008. The Quarterly Rev of Econ and Financ 53: 336–344. doi: 10.1016/j.qref.2013.01.002
![]() |
[58] | Nobili A, Zollino F (2012) A structural model for the housing and credit markets in italy. Bank of Italy Temi di Discussione Working Paper No. 887. |
[59] |
Palan S (2013) A review of bubbles and crashes in experimental asset markets. J Econ Surv 27: 570–588. doi: 10.1111/joes.12023
![]() |
[60] | Pavlidis E, Yusupova A, Paya I, et al. (2013) Episodes of exuberance in housing markets: in search of the smoking gun. J Real Estate Financ Econ 53: 1–31. |
[61] |
Phillips PC, Wu Y, Yu J (2011) Explosive behavior in the 1990s nasdaq: When did exuberance escalate asset values? Int Econ Rev 52: 201–226. doi: 10.1111/j.1468-2354.2010.00625.x
![]() |
[62] |
Phillips PC, Yu J (2011) Dating the timeline of financial bubbles during the subprime crisis. Quant Econ 2: 455–491. doi: 10.3982/QE82
![]() |
[63] |
Sarn L, Taylor MP (2003) An empirical investigation of asset price bubbles in latin American emerging financial markets. Applied Financ Econ 13: 635–643. doi: 10.1080/09603100210124597
![]() |
[64] | Scatigna M, Szemere R (2015) Bis collection and publication of residential property prices. Irving Fisher Committee Bulletin 39: 1–8. |
[65] | Schatz M, Sornette D (2018) Inefficient bubbles and efficient drawdowns in financial markets. Swiss Finance Institute Research Paper No. 18-49. |
[66] |
Scheinkman J, Xiong W (2004) Heterogeneous beliefs, speculation and trading in financial markets, In: Carmona R.A., Çinlar E., Ekeland I., Jouini E., Scheinkman J.A., Touzi N., Author, In Paris-Princeton Lectures on Mathematical Finance 2003, Springer, Berlin, Heidelberg, 1847: 217–250. doi: 10.1007/978-3-540-44468-8_3
![]() |
[67] |
Schularick M, Taylor AM (2012) Credit booms gone bust: Monetary policy, leverage cycles, and financial crises, 1870–2008. Am Econ Rev 102: 1029–1061. doi: 10.1257/aer.102.2.1029
![]() |
[68] | Shi S (2017) Speculative bubbles or market fundamentals? an investigation of us regional housing markets. Econ Model 66: 101–111. |
[69] | Sørensen PB (2013) The swedish housing market: Trends and risks. Finanspolitiska rdet, 1–77. |
[70] |
Sornette D (2002) "Slimming" of power law tails by increasing market returns. Physica A 309: 403–418. doi: 10.1016/S0378-4371(02)00614-3
![]() |
[71] |
SornetteD, Johansen A, Bouchaud JP (1996) Stock market crashes, precursors and replicas. J Phys I Franc 6: 167–175. doi: 10.1051/jp1:1996135
![]() |
[72] | Stevenson S (2008) Modeling housing market fundamentals: Empirical evidence of extreme market conditions. Real Estate Econ 36: 1–29. |
[73] | Timmermann A (2006) Forecast combinations, Handbook of economic forecasting, Elsevier, 135–196. |
[74] | Valencia F, Laeven L (2012) Systemic banking crises database: An update. IMF Working Paper No. 12/163. |
[75] |
Walks A (2014) Canada's housing bubble story: Mortgage securitization, the state, and the global financial crisis. Int J Urban Reg Res 38: 256–284. doi: 10.1111/j.1468-2427.2012.01184.x
![]() |
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 |