Lucie Pansart
email: lucie.pansart@g-scop.grenoble-inp.fr

Nicolas Catusse
email: nicolas.catusse@g-scop.grenoble-inp.fr

Hadrien Cambazard
email: hadrien.cambazard@g-scop.grenoble-inp.fr

Exact algorithms for the picking problem

Keywords: picking, integer programming, Steiner TSP, compact formulation, cuts

Introduction

Warehouse Management Systems (WMS) are dedicated to help companies to reduce their logistical costs. They currently use heuristic to solve the picking problem, which is aimed at finding the shortest tour to collect every items of a picking list in a warehouse. Given (a) a warehouse with v vertical aisles containing the slots where the items are stored and blocks separated by h horizontal cross-aisles, (b) a depot and (c) a picking list giving the location (block and aisle) of n items to collect, the objective is to minimize the tour of the order picker, beginning and ending at the depot and collecting every ordered items. Figure 1 gives an example of an instance. It is a particular case of the Traveling Salesman Problem (TSP). Current exact algorithms to solve this problem use dynamic programming [START_REF] Cambazard | Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane[END_REF][START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF]. We focus here on Mixed Integer Linear Programming (MILP). It is well-known that two important factors for a MILP formulation to be effective are the space of the solutions and the strength of the linear relaxation. This work proposes a compact formulation and improvements to strengthen the linear relaxation. Moreover, our algorithm has the advantage to be flexible, meaning side constraints specific to a company can be easily added. The algorithm proposed can be integrated to WMS, which usually contain a linear solver.

Modeling

We model the problem with a Steiner graph G(V = R ∪ T, A). The set R of required vertices represents the items and the depot: they must be visited in the tour. The set T of Steiner vertices represents intersections between vertical and horizontal aisles: they can be visited in the tour. An arc corresponds to an existing path between two vertices in the warehouse. Each arc (ij) has a cost d ij , equal to the distance between the vertices i and j. We define the variables, for each arc (ij): x ij = 1 if the tour uses the arc (ij), 0 otherwise. The objective is to minimize the cost of the tour

(ij)∈A d ij x ij .
We use a formulation using the flow principle: the order picker leaves the depot with n units of a commodity and delivers one unit each time he picks an item. This formulation uses a polynomial number of constraints but suffers from its compacity: the lower bound given by its linear relaxation is lower than the exponential formulation lower bound [START_REF] Adam N Letchford | Compact formulations of the steiner traveling salesman problem and related problems[END_REF].

Our contribution is made on several sides: we create a preprocessing that reduces the size of the Steiner graph and adds cuts to the MILP formulation to increase the linear relaxation. The preprocessing keeps the minimal number of vertices and arcs used to solve the problem. Cuts are inspired by the exponential formulation. They are defined as (S, S), partitioning the warehouse into two subsets such as each subset contains at least one required vertex. It implies that there must be at least one arc going from S to S (and one from S to S). We therefore add the constraints x S : S ≥ 1. To keep the compacity of our formulation, we add a polynomial number of cuts, relevantly chosen based on the warehouse structure.

Results

To solve our formulation, we used CPLEX 12.6. We apply it on 120 instances, split into 12 classes, of a benchmark proposed by Theys et al. [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF]. We compared our algorithm with three other exact approaches: dynamic programming [START_REF] Cambazard | Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane[END_REF], TSP solver Concorde [1] and a compact TSP formulation (i.e., with a complete graph and not a Steiner graph) also solved with CPLEX.

The first result is that adding preprocessing and cuts improves the Steiner formulation: the gap between the linear relaxation and the optimal solution moves from 41.7% to 1.1%. In average, our algorithm is slower than Concorde and the dynamic programming. However, on many instances the computing time is reasonable: smaller than 1 second for 5 classes and smaller than 30 secondes for 4 other classes. Finally our formulation solves more instances than the TSP formulation in the time limit: in 30 minutes, our algorithm solved 110 instances while the TSP formulation solved only 77 instances.

Note also that the adaptation of our preprocessing for Concorde leads to the resolution of each instance of the entire benchmark in less than 5 minutes, which is a big improvement on this benchmark [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF].

Conclusion and perspectives

This work proposes a new approach to solve the picking problem: a compact and flexible MILP formulation based on a Steiner graph and improvements to reinforce this formulation, easy to implement in a WMS embedding a MILP solver. On an academic point of view, our contribution was to solve the entire benchmark very efficiently without the need of heuristics.

Tracks for further work are mainly to get stronger reasoning on the structure of the data to get more efficient algorithm. It would be moreover desirable to obtain an industrial benchmark to test our algorithm on real instances. Finally, it may be interesting to link this problem with other warehouse issues such as storage policy or batching.

FIG. 1 :

 1 FIG.1: An example of a warehouse with 2 blocks (= 3 cross-aisles) and 8 aisles. The depot is the bigger square. Black slots represent items to collect. The edges show the shortest tour for this instance.