Warehouse Pick Path Optimization Algorithm Analysis

1 Warehouse pick path Optimization Algorithm Analysis Ryan Key Anurag Dasgupta edinboro university of Pennsylvania edinboro university of Pennsylvania ABSTRACT Warehouse operational costs are heavily influenced by the efficiency in which workers are able to traverse the Warehouse and gather items on orders around the Warehouse that must be shipped to customers; this action accounts for over 50% of Warehouse operations expenses. The act of traversing the Warehouse is greatly optimized by following a designated pick path ; however, algorithms for pick path generation are complex and heavily unexplored by the industry.

2 Generating pick paths involves solving two common place graph theory problems: the shortest path problem and the traveling salesperson problem. We will analyze algorithms used for solving both of these problems and discuss the feasibility of generating pick paths through the use of the algorithms. We also introduce a simplified implementation to illustrate the viability of the described approaches. KEY WORDS Warehouse pick path Optimization , Traveling Salesperson Problem, Shortest path , Algorithm Comparison 1. Introduction A common goal of nearly all businesses is to reduce man-hours and increase the overall profit margin of the business. In Warehouse related businesses, optimizing the efficiency of order picking can lend itself to great reductions in the time it takes orders to ship out, as well as, improving the overall effectiveness of its workers.

3 Of all costs associated with Warehouse operations, 55-65% of the operational funds are allocated towards order picking [1] [2], showing the importance of optimizing this phase of the Warehouse process. To better understand the problem at hand, we will now describe a common scenario in a Warehouse and show how order picking fits into the mix. First, a Warehouse is comprised of 3 primary components: receiving, storage, and shipping [2], Receiving is responsible for checking things into the Warehouse ; this is the entryway for all items into the Warehouse stock. Once items have been received, they must be put away and stored. Storage can be of any form, although large shelving units, gaylords, and/or pallets are traditional options.

4 The storage area of a Warehouse is quite important and should be well organized to create an advantageous environment for order pickers. The final area, shipping, is similar to receiving. This is the exit for all items leaving the Warehouse ; any items ordered by customers of the Warehouse must pass through this area before arriving at the customer s location [2]; a customer of the Warehouse could be larger entities such as the operation of a large franchise storage Warehouse , or a single customer that is ordering products from an online store. After understanding the layout of a Warehouse , we must look at the tasks performed by a Warehouse . Nearly allactivities at a Warehouse are centered on receiving orders from customers.

5 As an order comes into the Warehouse , an individual in the Warehouse becomes responsible for the order; this is the order picker. The order picker is responsible for gathering all items on the order from around the Warehouse , also known as picking, and then placing them in the shipping area. Once in shipping, the order will be packaged in a box or pallet and shipped to the customer. The picking process can be time consuming and by far is the biggest operational expense of any Warehouse [2]. Picking items for orders is the most costly part of the process, because order pickers must traverse the Warehouse layout to find all items on the order, starting and ending in the shipping area; this is a pick path .

6 For example, an order picker will print an order from the shipping area with 10 items on it. If there is a 20,000 square foot Warehouse , it can be expected to have at least 500 unique storage locations throughout the Warehouse defining where items are stored. This means, the order picker must determine an efficient route through the 500 locations to get to the 10 locations identified on the order, where any location can be travelled to from any other location; we know this because any practical Warehouse layout will not create any isolated, or pendant, storage area. After the order picker has found all 10 items in the Warehouse , they must then bring the items back to the shipping area so the order can be shipped and the order picking process can be started fresh.

7 Now to Analysis this problem in terms of graph theory, finding a pick path involves solving two of the most common problems in graph theory; the Travelling Salesperson Problem (TSP) and the shortest path problem. The TSP is the problem of finding the shortest tour through n cities that visits every city exactly once, starting and ending in the same city [3]. Where in the case of pick path Optimization , we want to visit every location on the order exactly once, generally starting and ending in shipping. The shortest path /route problem comes in five varieties, two of which pertain to the work accomplished by this paper. The first being, finding the shortest path between some vertex, x, and some other vertex in the graph, y[4].

8 Depending on the implementation and algorithms used to optimize Warehouse pick paths, this scenario will come Int'l Conf. Foundations of Computer Science | FCS'15 |63into play such as, wanting to make it from some last location on the order back to the single shipping location. More often, it will be the case where the following shortest path is sought: the shortest path between some vertex and all others [4]. This is the shortest path most often sought during optimized pick path generation, as distances between the current vertex and all other locations on an order commonly need to be found. To summarize the TSP/Shortest path problem encountered when solving the pick path problem: we are solving a TSP between all locations on an order; starting and ending in the shipping area (which is also defined by a vertex).

9 Then as the TSP is being solved, at each location we encounter the further difficulty of finding the shortest paths between the current node and all remaining locations on the order. This occurs because we are solving a TSP which assumes a complete graph where all nodes are connected with one edge between them; however, this is not guaranteed to be the case in the Warehouse layout. We are guaranteed all locations will be reachable from any location in the graph, so we must define the shortest path to each of these vertices. After finding these shortest paths, we can then treat the problem like a normal TSP, where all edges defining the path between nodes are treated as one edge with one minimum distance associated with it.

10 Section 4 of this paper will focus on the algorithms and enhancements that can be used to find optimal pick paths by solving the TSP and shortest path problem. Section 5 will offer insight into an implementation for finding an optimal pick path . 2. Related Work There have been hundreds of papers published and dozens of algorithms developed around solving the shortest path problem alone, as a large number of mathematical Optimization problems are mathematically equivalent to the shortest path problem [4]. In the same respect, the TSP has been analyzed by dozens of professions, researched to no end, and proved to be a member of the NP-Complete problem set, with numerous heuristics developed that present polynomial time solutions within a fair degree of accuracy [3].