发布时间 : 星期三 文章立体仓库中英文对照外文翻译文献更新完毕开始阅读406956a67d1cfad6195f312b3169a4517723e583
where, mi is the total inventory of the ith type in the warehouse, and.
Having solved various problems by the enumeration algorithm and identifying the best solution that had the minimum amount of travel time, we found that the existing items in the current aisle (i.e. the aisle in which the S/R machine is in at the beginning of the retrieving process) are the key to the final solution. We develop an algorithm on the basis of the mentioned results, and call it the current-aisle heuristic (CAH) algorithm.
In the CAH algorithm, the existing items in the current aisle are selected first for retrieval. Afterwards, the remainder of the order (if any) is selected and all the various retrieval methods are studied. We can simplify the previous statements by stating that if r denotes the number of the ordered items existing in the current aisle, and if r = 0, the method then becomes similar to the enumeration algorithm. If r = 1, then the method first calculates the time traveled by the S/R machine, t1, for only one existing item in the current aisle, and removes that item from the list of ordered items, and then for the remaining items (if any), it proceeds as same as the enumeration algorithm to obtain the minimum travel time, t2. The total travel time of the S/R machine will be sum of t1 and t2 as the final solution.
If r > 1, then the method first assigns the picking sequence to pick up all r items which exist in the current aisle. After calculating the travel time, t1, it removes the items from the list of ordered items. Then, for the remaining items (if any), it proceeds like the enumeration algorithm, i.e. finding all feasible ways followed by calculating the travel time for each one and finally selecting the minimum value among them, t2. The total traveled time of the S/R machine will be sum of t1 and t2 as the final solution.
Khojasteh-Ghamari discussed in detail the method of assigning a picking sequence of the ordered items existing in the current aisle. If any ordered items exist in the current aisle, then the number of ways studied will be divided by the number of the items existing in the warehouse. Therefore, this task causes the total number of potential solutions to decrease dramatically, and hence, the CPU time (process time of the program) would be decreased as well.
3.1. Genetic algorithm
A genetic algorithm is an optimization process that employs genotypes (individuals or chromosomes) in a population, and the genotypes are made of units called genes arranged in linear succession. Each genotype would represent a potential solution to a problem; an evaluation process run on a population of chromosomes corresponds to a search through a space of potential solutions.
In each generation, we evaluate each chromosome, select a new population with respect to the probability distribution based on fitness values, and recombine the chromosomes in the new population by mutation and crossover operators. After a number of generations, when no further improvement is observed, the best chromosome represents an optimal (possibly the global) solution. The algorithm is often terminated after a fixed number of iterations depending on speed and resource criteria (Michalewicz). Representation
A chromosome represents a potential solution, where each one is viewed as a sequence of
items each with its own associated allele. By analogy, each gene in a chromosome represents the item type, and its associated allele represents the storage location. Therefore, each potential solution consists of a chromosome, in which the number of genes is equal to the number of items in the received order. An example is given in Figure 1.
Figure 1 shows a potential solution in which the items with codes A, B, C and D have been ordered. Item C with location number 5, item B with location number 7, item A with location number 4, and item D with location number 3 have been selected for retrieval.
Figure 1. Representation of a potential solution.
It should be noted that the sequence of picking items has also been considered in the representation. In this example, item C with location number 5 will be retrieved first, followed by items B, A, and, finally, D. Initialization
The initial population is randomly generated. Each chromosome consists of a randomly generated sequence of the ordered items. In each chromosome, a number is assigned to each item. It should be noted that the condition of feasibility for each solution is necessary. Therefore, in the population-generating process, a suitable procedure is required to make each solution feasible. Thus, in each chromosome, the ordered items are randomly distributed without repetition, and the location numbers for each item are randomly selected. The assigned numbers range from 1 to the total warehouse inventory of that item.
Suppose that the existing total number of items A, B, C and D within the warehouse is 6, 9, 7 and 4, respectively. In order to form the solution depicted in Figure 1, first the ordered items are randomly selected (C, B, A and D), then for item C, the selected integer number has been generated randomly between [1, 7], also for item B a number between [1, 9], for item A between [1, 6] and finally for item D, a number between [1, 4] has been randomly selected. Crossover
Among the described operators for permutation problems, the Partially Matched Crossover (PMX) is used for the order picking problem. Partially matched crossover is viewed as a crossover of permutations, which guarantees that all items are found exactly once in each offspring. That is, both offspring receive a full complement of genes, followed by the corresponding filling in of alleles from their parents. In Figure 2, there are two parents denoted by p1 and p2, and the crossover points are 1 and 3. According to the corresponding between [M,R] and [E,A], the repeated items are replaced. That is, A and E in the first parent are replaced by R and M, respectively; while in the second parent, R and M are replaced by A and E, respectively. The generated offspring are o1 and o2 (Figure 2).
Meanwhile, according to PMX for the order picking problem, the role of crossover operator in this problem is to change the sequence of the items in a chromosome, without changing the associated alleles.
Figure 2. PMX operator.
Mutation
Contrary to binary implementation that each gene is replaced with a complementary amount (0 with 1 and vice versa), in the order picking problem, the associated allele of each gene that has been selected by a mutation operator can be replaced with another allele in the range of total inventory of the item. This operator, on the other hand, does not have any role in changing the sequence of items, but can only select another number (storage location) for an item.
Suppose that in the o1, the third gene has been selected by mutation. Since the total number of item A in various storage locations within the warehouse is six, the mutation operator generates an integer random number between [1, 6] to replace the third gene (Figure 3). Of course, when the generated number is equal to the current number (namely 2), the operator repeats generating the random numbers until obtaining a number except 2. In this example, the number 4 has been generated. Evaluation and selection
During each generation, chromosomes are evaluated using some measure of fitness.
Figure 3. The mutation operator.
In most optimization applications, fitness is calculated based on the original objective function. In the order picking problem, the objective function is to minimize the travel time of the S/R machine. The total time traveled by the S/R machine is the criteria to select the chromosome for the next generation. Khojasteh-Ghamari explained the procedure for the calculation of travel time of the S/R machine.
Because this is treated as a minimization problem, we must convert the objective function value for each chromosome into a fitness value, so that a fitter chromosome has a larger fitness value. This can simply be done by the inverse of its value as follows (Cheng et al.):
where, eval(vk) is the fitness function for the k th chromosome and f(vk) is the total time traveled by the S/R machine for the k th chromosome. Population size (pop size) determines how many chromosomes should be in the population at any given time.
We use a roulette wheel as the basic selection method to reproduce the next generation based on the current enlarged population, in which a fitter chromosome has a large chance to be reproduced into the next generation. In this selection method, solutions with short travel times have higher probabilities of being chosen for the next generation.The roulette wheel is performed as follow:
1. Calculate the total time traveled by the S/R machine f(vk) for each chromosome vk(k = 1, 2, . . . , pop size)
2. Calculate the fitness value eval(vk) for each chromosome vk (k = 1, 2, . . . , pop size) 3. Find the total fitness of the population
4. Calculate the probability of a selection pk for each chromosome vk (k = 1, 2, . . ., pop size):
5. Calculate the cumulative probability qk for each chromosome vk (k = 1, 2, . . ., pop size):
The selection process is based on spinning the roulette wheel for pop size times; each time a single chromosome is selected for the new population in the following way. - Generate a real random number r between [0, 1];
- If r ≤ q1, then select the first chromosome v1; otherwise select the k th chromosome vk (2 ≤ k ≤ pop size) such that qk?1 < r ≤qk.
All chromosomes of the last population are then replaced by the newly generated chromosomes.
4. Simulation Results