A multistage heuristic for storage and retrieval problems in a warehouse with random storage

• DOI: http://doi.org/10.1111/itor.12454
• Published date: 01 May 2020
• Author: Francisco Ballestín,Ángeles Pérez,Sacramento Quintanilla
• Date: 01 May 2020

Intl. Trans. in Op. Res. 27 (2020) 1699–1728

DOI: 10.1111/itor.12454

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A multistage heuristic for storage and retrieval problems in a

warehouse with random storage

Francisco Ballest´

ın, ´

Angeles P´

erez and Sacramento Quintanilla

Facultad de Econom´

ıa, Dpto. de Matem´

aticas para la Econom´

ıa y la Empresa, Universitat de Val`

encia, Av. De los Naranjos

s/n, Val`

encia, Spain

E-mail: francisco.ballestin@uv.es[Ballest´

ın]; angeles.perez@uv.es [P´

erez]; maria.quintanilla@uv.es [Quintanilla]

Received 29 September 2016; receivedin revised form 22 May 2017; accepted 15 August 2017

Abstract

The warehouse is one of the essential components of logistics and supply chains. The efficiency of the whole

chain is affected by the performance of warehouseoperations and, more particularly, the storageand retrieval

of goods. This paper considers a storage and retrieval problem in a real warehouse with random storage

and different types of forklifts, depending on the locations they can access. The problem deals with selecting

locations to store/retrievea predefined set of pallets, assigning an adequately skilled forklift to each operation

and determining the order in which each forklift will perform its operationsso that the total employed time is

minimized. The problem is solved heuristically by decomposing it into three subproblems, each one handling

one of the three key decisions of the problem, and taking into account congestion considerations. The paper

also studies two modifications of the problem, adding secondary objective functions. Computational results

compare the effectiveness of the proposed algorithms for the different problems in a stochastic environment

via simulation.

Keywords:warehousing; picker-to-parts system; warehouse management;scheduling; storage location assignment; heuris-

tics; performance analysis

1. Introduction

Warehousesare a critical component of any supply chain. Warehousing concerns receiving, storing,

order picking, and shipping of goods. Several studies and surveys have estimated the importance

of order picking operations in relation to the total operating cost of a warehouse, placing it at

approximately 50% (Frazelle, 2002; De Koster et al., 2007). Furthermore, in many warehouses,

pickers/forklifts frequently face not only the picking of goods, but also the storing of products. If

we also consider the storage, the importance of these operations becomes even greater.

The speed at which order picking and storing can be performed depends heavily on the locations

where the goods to store or retrieve are situated or have to be situated. The number of possible

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1700 F. Ballest´

ın et al. / Intl. Trans. in Op. Res. 27 (2020) 1699–1728

locations for a pallet can be established from the type of storage policy followed in the warehouse.

Brynz´

er and Johansson (1996) distinguish among the following: dedicated storage, in which each

stock-keeping unit (SKU) has a set of designated locations; random storage, in which any SKU can

occupy any location; and class-based storage, in which a group of storage locations is allocated to

a class of SKUs and random storage is allowed within the group of storage locations.

This paper addresses a storage and retrievalproblem in a random warehouse where the SKUs are

pallets and the warehousing operations areperformed by means of a set of unequally skilled forklifts

(which means that not all forklifts can access the same set of locations). We will call this problem

the storage and retrieval location assignment problem with heterogeneous forklifts (SRLAP-HF).

The SRLAP-HF deals with selecting locations to store/retrieve a predefinedset of pallets, assigning

an adequate skilled forklift to each operation, and determining the order in which each forklift

will perform its operations so that the total employed time is minimized. The problem has been

motivated by the studyof a warehouse of a Spanish company that produces beauty products for one

of the most important supermarket chains in the country. In the paper, we develop a stylized model

that captures and generalizes the main characteristics of the structure and sequencing process.

The SRLAP-HF is NP-hard, as we will show later on. We have addressed it through decomposi-

tion. Each of the subproblems considered corresponds to one of the following three key decisions

to be made: (a) assign locations to operations,(b) assign forklifts to operations, and (c) schedule the

operations assigned to a forklift. Each subproblem has been solved either optimally or heuristically

with several procedures. The objectives and the resolution methods in each subproblem are estab-

lished thinking in the global evaluation function. The algorithms developed for each subproblem

have been combined by providing different algorithms for the SRLAP-HF. Although the three

subproblems are strongly interconnected, is common to solve them separately because the remain-

ing problems are still very difficult (Z¨

apfel and Wasner, 2006). Van den Berg (1999) states that the

use of these heuristics is motivated by the fact that most warehousing (sub)problems are NP-hard.

When multiple forklifts work simultaneously in narrow aisles with traffic restrictions, as in the

SRLAP-HF, congestion inevitably occurs. Congestion has recently been considered in designing

pickers’ routes to increase worker productivity (Pan and Wu, 2012; Chen et al., 2013; Sainathuni

et al., 2014). Methods that protect against congestion by distributing the locations assigned to

orders equitably among forklifts and working zones (WZs) are incorporated in the algorithms of

this paper.

The SRLAP-HF considers only a single objective: minimizing the flow time or workload, which

means the total time employed in storing and retrieving the predefined set of pallets. Usually,

however, warehouse managers are not concerned with just a single objective, which is why this

paper explores two modifications of the problem, adding two secondary objective functions: the

maximization of space availability and the minimization of production expiration date measures.

We present strategies to optimize these secondary objectives while managing the list of orders.

Finally, a nontrivial aspect of the problem is the stochastic nature of the real problem, due to

the randomness associated with the duration of the operations. For this reason, we have decided to

evaluate the behavior of the algorithms using a simulator designed in Ballest´

ın et al. (2013) for a

related problem.The algorithms described in this paper provide, through a deterministic setting, the

decisions to be followed in practice, which will be evaluated using the simulator. A brief description

of the simulator is provided in this paper. In Ballest´

ın et al. (2013), the same type of warehouse was

studied. However, pallets to be retrieved had a due date, and the objective function of the studied

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies