Valeria Loscrí
email: valeria.loscri@inria.fr

Giuseppe Ruggeri
email: giuseppe.ruggeri@unirc.it

Anna Maria Vegni
email: annamaria.vegni@uniroma3.it

Ignazio Cricelli

Social Structure Analysis in Internet of Vehicles

Internet, in its most recent evolution, is going to be the playground where a multitude of heterogeneous interconnected "things" autonomously exchange information to accomplish some tasks or to provide a service. Recently, the idea of giving to those smart devices the capability to organize themselves according to a social structure, gave birth to the socalled paradigm of the Social Internet of Things. The expected benefits of SIoT range from the enhanced effectiveness, scalability and speed of the navigability of the network of interconnected objects, to the provision of a level of trustworthiness that can be established by averaging the social relationships among things that are "friends". Bearing in mind the beneficial effects of social components in IoT, we consider a social structure in a vehicular context i.e., Social Internet of Vehicles (SIoV). In SIoV, smart vehicles build social relationships with other social objects they might come into contact, with the intent of creating an overlay social network to be exploited for information search and dissemination for vehicular applications. In this paper, we aim to investigate the social behavior of vehicles in SIoV and how it is affected by mobility patterns. Specifically, through the analysis of simulated traffic traces, we distinguish friendly and acquaintance vehicles based on the encounter time and connection maintenance.

I. INTRODUCTION

The term Internet of Vehicles (IoV) has emerged to indicate an interconnected set of vehicles providing information for common services, such as traffic management and road safety. As the technologies advances vehicles are becoming more and more connected and, in the next future, they will be able both to communicate on a short range with nearby vehicles (i.e., V2V links) and infrastructure (i.e., V2I links) by means of IEEE 802.11and to remotely access to the Internet by using cellular systems. Vehicular communications are a key enabler for many automotive applications. As an instance, we may enumerate safety related operations, predictive maintenance, crowdsourcing, and many others [1].

Recently the idea of Social Internet of Things (SIoT) brought out in the academic community receiving a great consensus [START_REF] Atzori | The social internet of things (siot) -when social networks meet the internet of things: Concept, architecture and network characterization[END_REF], thanks to its benefits deriving from the convergence of typical technologies and solutions of the IoT and the Social Networks domains. Applying social networking principles to the IoT definitely leads to advantages that span (i) from the enhanced effectiveness, scalability and speed of the navigability of the network of the future billions of objects that will populate the IoT (ii) to the provision of a level of trustworthiness that can be established by leveraging the social relationships among things that are "friends", (iii) to the interoperability between objects that are very heterogeneous from one another.

Following the framework of SIoT [START_REF] Nitti | On adding the social dimension to the internet of vehicles: Friendship and middleware[END_REF], also IoV networks are moving towards a social networking structure, where vehicles can share data information based on social ties that can be built everyday during the own journey. This has led to the concept of Social Internet of Vehicles (SIoV), aiming to create an overlay social network to be exploited for information search and dissemination for vehicular applications [START_REF] Vagni | Scarf: A social-aware reliable forwarding tech nique for vehicular communications[END_REF]. In SIoV a group of vehicles may have common interests, preferences or needs in a context of temporal, and spatial proximity on the roads. In this context, social-based protocols are able to identify socially-similar nodes to share common interests with e.g., a group of people all driving to a football game can experience traffic on the route to the stadium, and are also highly expected to encounter others with similar interests.

In this paper, we aim to investigate the SIoV framework in a real traffic scenario. Specifically, we analyse the ability of vehicles to form a vehicular social networks, based on SIoT social relationships. We assume that a pair of vehicles will form a social tie (e.g., they are friends) if the encounter time will last a given threshold. The paper is organized as follows. Section II gives an overview of SIoT and how it can influence SIoV framework, and describes some relevant use cases in the IoV domain. In Section III present a simulation framework specifically tailored to evaluate SIoT in the context of IoV. In section IV we will present some preliminary simulation results, expressed in terms of number of social vehicles connected, obtained in a real traffic simulation framework. We assess that in a SIoV scenario, vehicles (and more in general, objects) can form social ties in a reliable manner, based on the encounter time. Finally, conclusions are drawn at the end of this paper.

II. BACKGROUND AND MOTIVATIONS

According to SIoT "social-like" relationships mimicking humans, friendship ties are built between the objects in the IoT [START_REF] Atzori | The social internet of things (siot) -when social networks meet the internet of things: Concept, architecture and network characterization[END_REF] and are used to (i) limit the search only to those nodes with mutual social relations and to (ii) increase the trustworthiness in the exchange of each piece of information provided by the devices in the network. So far, five relationship types have been defined in SIoT [START_REF] Atzori | The social internet of things (siot) -when social networks meet the internet of things: Concept, architecture and network characterization[END_REF]: Besides the above mentioned relationships, as in most human social networks, it is also possible to define special groups that include devices bounded by some common features or finalities.

The application of SIoT toward IoV context has been also investigated. In [START_REF] Nitti | On adding the social dimension to the internet of vehicles: Friendship and middleware[END_REF], the authors firstly reviewed the relationships which can be established between the vehicles and between the vehicles and the road side units (RSUs) and proposed a middleware that extends the functionalities of the Intelligent Transportation Systems Station Architecture [START_REF][END_REF] to support the creation of SIoT like relationship between vehicles and the objects surrounding them. This paper goes further w.r.t. to [START_REF] Nitti | On adding the social dimension to the internet of vehicles: Friendship and middleware[END_REF] by evaluating how well the original design of SIoT fits with the requirements of automotive services.

Connected vehicles can be used as mobile probes to infer information about the environment where they move such as the average speed on road segments they traverse during their journey, the weather condition they experience (i.e. temperature, humidity, pressure, etc.) and the pollution levels [1]. The information collected, although valuable might be affected by a poor quality or may be maliciously corrupted by rogue vehicles to some purpose. SIoV can offer a framework to assess the trustworthiness of each contributing vehicle [START_REF] Nitti | Trustworthiness management in the social internet of things[END_REF], [START_REF] Vegni | A survey on vehicular social networks[END_REF]. Also, SIoV offers a framework to improve the quality of the shared information, so that vehicles belonging to a given social group can provide a better information to others. As an instance, a traffic information message transmitted by a vehicle that usually travels on a given itinerary is expected being particularly precise due to its familiarity with the itinerary and thus ability to find the quickest path in a congested area.

The types of social relations so far defined for SIoT can hardly be applied to bound vehicles that usually commute in the same path. The closest matching to such a relation is the SOR (Social Object Relation) that is created among objects that frequently meet to each other; also, a SOR can bound vehicles frequently parked in the same parking area, as well as vehicles that frequently travel on the same street at the same time.

A. Data Dissemination in SIoV

In general, the IoV is used to feed the vehicles with constantly updated information to help them during their journey. However, not all the vehicles are interested to all the information provided. In this context, SIoV can offer a framework to group the vehicles according to the information they can be interested to. As an example, the news about the scheduled closure of a road due to maintenance should be firstly sent to vehicles that usually drive that path, as well as heavy vehicles might be interested to a news about a weight restriction on a given road segment. From the latter example, it clearly emerges the need to address all the vehicles belonging to a given category (i.e., the trucks). Again, SIoV might offer a framework to drive the information to the most appropriate recipients. However, once again the types types of social relations so far defined for SIoT fail to to capture some relevant aspects of SIoV and none of them can be used to connect all the vehicles belonging to the same category (i.e the trucks). The the types of social relationship originally defined for SIoT such as POR can be also considered in the SIoV context. Specifically, POR allows vehicles belonging to the same automaker and originated in the same period to be "socially" connected. POR provides useful information about the status of a vehicle for diagnostic services and remote maintenance.

Indeed, vehicles with similar characteristics and common features are usually affected by similar failures. By mining the information about the failures shared by similar vehicles, a predictive maintenance program could be arranged for each vehicle. However, the automotive sector is a little more complicated then IoT. So, it might happen that the same engine might be mounted on several models of different brands. The same applies to many other components. Hence, to fully exploit the benefits of SIoV it is necessary to extend the POR to capture the formerly evidenced peculiarities of the automotive market.

III. THE SIMULATION FRAMEWORK

In the former section we have discussed the applicability of SIoT to IoV and we have pointed out some pros and cons. However, to get a deeper insight on this issue it is necessary to run some experiments and get some numerical results. This call for the implementation of a simulation environment capable to take in to consideration the peculiarities of both: the IoV and SIoT. Among all the types of social bounds so far defined, the SOR is the hardest to be simulated. PORs, OORs, C-WORs and C-LORs depend on the intrinsic characteristics of the objects or depend on their purpose. Therefore they are static and deterministic. On the contrary, SORs depend on the random meeting among the objects, hence they are stochastic in nature and depend on the mobility pattern of the objects. Although, appropriate mobility models for the smart objects, are still lacking in many applicative scenarios [START_REF] Asl | How often social objects meet each other? analysis of the properties of a social network of iot devices based on real data[END_REF], this is not the case of IoV where several mobility models for vehicles have been developed in time [START_REF] Harri | Mobility models for vehicular ad hoc networks: A survey and taxonomy[END_REF]. Also, considering only the vehicles is not enough, the environment where they move is always populated by other smart objects which might enter in their social network and exchange information with them. Therefore the simulation framework should take in to account at least the most relevant object surrounding the vehicles such as Road Side Units (RSU) and whatever other device that may produce or consume information related to the vehicles. To implement our simulation framework we followed the flowchart shown in Figure 1. The first step consists in producing accurate mobility traces to take in to account the mobility pattern of vehicles. A plethora of vehicular mobility simulator are available. Among those simulator we chose "Simulation of Urban MObility" (SUMO) which is an open source, highly portable, microscopic and continuous road traffic simulation package designed to handle road networks on a city scale [START_REF] Krajzewicz | Recent development and applications of SUMO -Simulation of Urban MObility[END_REF]. Sumo takes in to account several parameters ranging from real road maps, speed limits, traffic signals and vehicle characteristics thus producing very accurate mobility traces. SUMO might produce the output in many formats, we chose the FCD (floating car data) format that reports the position of each vehicle in time. The second step of our flowchart consists in determining the number and the position of the smart object to be included in the simulation. Depending on the objective of the simulation many kind of smart objects can be considered. Accordingly many strategies might be followed to identify and positioning them. If we restrict our attention to Wi-Fi access points located along the road, then there are many option. the first one is to use one of the many open data repository such as [11], [START_REF]Mylnikov project[END_REF]. A second option would be to randomly positioning them by using some realistic distribution. If this latter approach is followed, a random topology generator such as NPart [START_REF] Milic | NPART -node placement algorithm for realistic topologies in wireless multihop network simulation[END_REF] might be used. Once the positions of the smart objects has been determined, the third step in our flowchart consists in integrating those positions in the SUMO output file. Smart Object are inserted in the output file at the beginning of it by using the same syntax SUMO uses for parked vehicles and their positions is never changed. To accomplish this step we used a custom software written in Phyton. The fourth step consists in processing the merged file containing the position of both the objects and the vehicles. During this phase the rule of SIoT are applied [START_REF] Asl | How often social objects meet each other? analysis of the properties of a social network of iot devices based on real data[END_REF] to seek out the insurgence of SOR relationships. Specifically, two entities (either vehicles or smart objects) establish a SOR relationship after having experienced one or more contacts for a cumulative contact time of at least T [min] [START_REF] Asl | How often social objects meet each other? analysis of the properties of a social network of iot devices based on real data[END_REF]. To determine the reciprocal contact between two entities we have assumed that they enter

IV. SOME PRELIMINARY SIMULATION RESULTS

To test our framework we carried out a simulation campaign whose setting are summarized in Table I. Specifically, we downloaded the map of the city of Reggio Calabria (Italy) from [START_REF]Open street map[END_REF], represented in Figure 2, and we used it as an input to SUMO. We considered 3000 vehicles and 100 access points randomly deployed. Since, we assumed that all the access points belong to the municipality we considered all of them bounded by an OOR while we hourly monitored the creation of SOR relationship between objects and vehicles for a cumulative observation time of 9 Figure 3 shows how many entities (either vehicles or smart objects) have joined the SIoT network varying the simulation time. At the beginning of the simulation only the access points are connected by means of OOR relations. As time evolves, an increased number of entities is included due to the SOR created following their frequent reciprocal meetings. At the end of simulation, after 9 [h], the SIoV network includes about 220 objects out of the 3100 considered in the simulation. Such a relatively small number of connected objects can be justified by considering the short simulation time and the highly dynamic environment. The Diameter of a SIoV network is defined as the longest chain of acquaintances connecting two objects. Figure 4 shows how this value evolves in time in our experiment. At the beginning of our simulation the only objects included in the SIoV network are the access points that are directly connected by OOR and hence 1 hop each other. This corresponds to a network diameter of 1. Along time, more and more objects are connected to the SIoV network creating longer chains of acquaintances. At the end of simulation, the network diameter increases to about 9.

V. CONCLUSIONS

In this paper, we focused on the SIoV paradigm and evaluated the temporal dynamics that govern the SIoV network, in a real context of the city of Reggio Calabria. We assumed the OOR and SOR relationships in order to build social ties among vehicles. This type of analysis is of paramount importance in order to give an insight of the specific features characterizing an highly evolving scenario like SIoV.

1 ) 2 ) 3 ) 5 )

 1235 Ownership object relationship (OOR): relation bounding heterogeneous objects belonging to the same user; Parental objects relationship (POR): relation established between homogeneous devices produced by the same manufacturer and belonging to the same production batch; Co-work objects relationship (C-WOR): relation set up between objects cooperating towards the provision of the same IoT application; 4) Co-location objects relationship (C-LOR): relation bounding devices that are always used in the same place; Social object relationship (SOR): relationship established between objects that come into contact, either sporadically or continuously, because their owners come in touch each other.

Figure 1 .

 1 Figure 1. The simulation workflow.

  into contact whenever they are closer then D[m]. Where D[m]is the sensing range of their IEEE802.11 wireless cards. In our framework the social network connecting N objects is represented by a symmetric, N -by -N binary adjacency matrix where the elements (i, j) and (j, i) are set to 1 if a social relationship exists between object i ad object j. Hence, the output of the fourth step consists in a binary matrix where the elements have been set to 1 according to the SORs that have been discovered. To carry out this phased we used a custom software written in phyton. The adjacency matrix is finally amended in the fifth step by including all the other types of social relationship (i.e., OOR, POR, C-LOR, C-WOR) that deterministically bind the objects according their characteristics. Of course this step might be accomplished only if additional information concerning the objects and vehicle are available. As an example, if a group of vehicle is assumed to belong to the same fleet, then a OOR relationship is created between them. If a group of smart devices is supposed to cooperating to the same task then a C-WOR relationship is created among them. The adjacency matrix obtained at the end of the fifth step fully represents the social network connecting all the object in the simulation scenario.

  [h]. Finally, we considered a sensing range D = 100 [m] and a cumulative time T required to create a SOR of 10 [min].

Figure 2 .

 2 Figure 2. The simulation area.

Figure 3 .

 3 Figure 3. Time Evolution of Social Connected Objects (Vehicles and Access Points) in the SiOV network.

Figure 4 .

 4 Figure 4. SiOV Network Diameter.

Table I PARAMETER

 I SETTINGS USED IN SIMULATION RESULTS.

	Parameter	Value
	Simulation Area	City of Reggio Calabria
	Number of Vehicles	3000
	Number of fixed Access Points	100
	Time to establish a SOR T	10 [m]
	Sensing Distance D	100 [m]
	Simulation Time	9 [h]


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

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

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

Gautier Stauffer
email: gautier.stauffer@kedgebs.com

Kidney Exchange Problem: models and algorithms

Keywords: kidney exchange problem, integer programming, column generation

Introduction

Kidney transplant is often the only effective treatment to cure end stage renal disease, affecting one out of thousand European citizens. Waiting for a compatible deceased donor can be really long and uncertain, so living donor transplant is a good alternative: a close relation can give one of its kidneys to a patient. As approximately 40% of living donors are incompatible with their specified recipient, several countries have independently developed kidney exchange programs to overcome this issue. In such a program, a patient with an incompatible donor can "swap" its donor with another patient in a similar position (see Figure 1a). More generally, an exchange can involve several incompatible pairs donor-patient by permutation of donors, creating cycles of donation (see Figure 1b). It can also include altruistic donors who give their kidney without waiting another one in return for a relative. Such a donor creates a chain of donation (see Figure 1c). A Kidney Exchange Program seeks for an optimal exchange. The objective of the KEP can be defined by different criteria (number of transplants, weight of exchanges, probability of success...).

(b) π(i) is the new donor of patient i: (π(p 1 ), π(p 2 ), π(p 3 ), π(p 4 )) = (d 4 , d 1 , d 2 , d 3 )

Problem

We define the kidney exchange problem (KEP) as the problem of finding an optimal (here of maximal weight) kidney exchanges in a pool of pairs donor-patient.

Let's define a directed graph, called compatibility graph, G = (V = P ∪ N, A) with a weight function on arcs w : A → R + . The vertices P are the incompatible pairs donors-patient, the vertices N are the altruistic donors. We add a weighted arc between vertices u and v if the donor u can give its kidney to patient v. w(uv) = medical benefit of the transplant.

Thus, a solution to KEP is a set of disjoint walks (cycles and chains) of maximum weight in graph G (walks must be disjoint because a donor can only give once and a patient must receive only one kidney). Moreover, in practice a cycle of donation must have a limited size k since it implies 2k simultaneous surgical operations. A chain of donation can have a limited size l, but no consensus exists on this parameter. So solving the KEP is equivalent to solving a Maximum Weighted ≤ k-Cycle and ≤ l-Chain Packing Problem, which is the problem of finding disjoint cycles of size at most k and chains of size at most l of maximal weight.

Complexity Solving the KEP is N P -hard for k ≥ 3 [START_REF] David J Abraham | Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges[END_REF][START_REF] John P Dickerson | Position-indexed formulations for kidney exchange[END_REF].

Solving with integer programming

Many integer programs (IP) exist for this problem [START_REF] Constantino | New insights on integer-programming models for the kidney exchange problem[END_REF]. We consider the one called Cycle& Chain formulation: C is the set of all cycles and chains of size at most k and l in G, we define the binary decision variables x c = 1 if walk c is chosen in the solution, 0 otherwise. The objective is to maximize the total weight of selected walks and the constraints are that each vertex must be selected in at most one walk. The Cycle&Chain Formulation is then:

(CF) max c∈C w c x c ( 1
)
st c∈C:v∈c x c ≤ 1 ∀v ∈ V (2) x c ∈ {0, 1} ∀c ∈ C (3)
Unfortunately, the number of variables grows exponentially with l and k. To tackle this problem, we can use a Branch-and-Price (B&P) algorithm, which mixes Branch-and-Boundthe standard algorithm solving IP -with Column Generation (CG) [START_REF] David J Abraham | Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges[END_REF]. The column generation solves the linear relaxation on a subset of walks, which grows when a new column (=a new variable) is generated.

When we add a variable to the set of current variables, we want to choose a variable which may improve the current solution. Thus, we search a variable (= a feasible walk) with a positive reduced cost. The problem of finding such a walk is called the pricing problem. Finding a cycle of size at most k and of positive reduced cost can be done in polynomial time with a modified Bellman-Ford algorithm [START_REF] Glorie | Iterative branch-and-price for large multi-criteria kidney exchange[END_REF]. Finding a chain of size at most l beginning with an altruistic donor of positive reduced cost is N P-complete [START_REF] Plaut | Hardness of the pricing problem for chains in barter exchanges[END_REF].

No implementation of a KEP solver using the Cycle&Chain formulation has been done in practice to handle large instances to the best of our knowledge. Indeed, it cannot scale when it is implemented without column generation and the use of CG is complex due to the hardness of the pricing problem. The purpose of our work is to provide this solver, thanks to numerous improvements such as heuristics, dual bound, filtering and cutting planes, as well as reasoning with other formulations, including an independent set formulation.

donor d 1 donor d 2 patient p 1 patient p 2 exchanges donor d 1 donor d 2 patient p 1 patient p 2 (

 12121212 Possible

donor d a donor d 1 donor d 2 donor d 3 patient p 1 patient p 2 patient p 3 (

 123123 FIG. 1: Examples of kidney exchanges. Black edge = compatibility; red and thick edge = chosen transplant. Donor d i is a relative of patient p i .


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 order picking problem

Keywords: integer programming, order picking, Steiner TSP, TSP, dynamic programming

Exact algorithms for the order picking problem

Lucie Pansart, Nicolas Catusse, Hadrien Cambazard

Introduction

The order picking activity lies at the heart of logistic. It consists in collecting products from storage in a specific quantity given by a customer order. This process is often considered as the most important warehousing process since it is estimated that it accounts for 55% of the total operational warehouse costs [START_REF] Tompkins | Facilities planning[END_REF]. Many order picking systems are currently used in warehouses. The methods are classified following who picks the orders (humans or machines), who moves (picker or products) and the strategy used. We focus here on manual systems where the order picker moves in a regular rectangular warehouse.

An efficient way to optimize order picking in this case is to reduce picker travel time. Thus, we are concerned with the following issue: how to optimize the routing time in the warehouse? This problem is called order picking problem, picker routing problem, or picking problem for sake of simplicity. To the best of our knowledge, this problem cannot be solved in polynomial time, except when the number of cross-aisles is bounded [START_REF] Cambazard | Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane[END_REF][START_REF] Kees | Routing order pickers in a warehouse with a middle aisle[END_REF].

We show in this paper that the problem can be efficiently solved optimally with mixed integer programming using a sparse formulation as well as adequate preprocessing and valid inequalities. Moreover, we extend a dynamic programming algorithm initially proposed by Ratliff and Rosenthal for 2 cross-aisles [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF], to any number of cross-aisles and evaluate it experimentally. It turns out to scale for a number of cross-aisles large enough to deal with real-life warehouses. This approach is however less suited to accommodate side-constraints.

This article begins with a description of the picking problem and a literature review (section 2). Section 3 presents different ways of preprocessing the data to improve algorithms efficiency. Two exact algorithms are then presented in sections 4 and 5. Finally, we report experimental results in section 6.

Problem description and literature review

We consider a regular rectangular warehouse with a single depot used to take the order and to drop it off. The warehouse is made of v vertical aisles and h horizontal cross-aisles. Products are located on both sides of vertical aisles. Cross-aisles do not contain any products but enable the order picker to navigate in the warehouse (see Figure 1(a)). We make two common hypothesis on the warehouse: Hypothesis 1. Aisles are narrow (the distance for crossing is considered null). Hypothesis 2. All aisle's lengths are equal. All cross-aisle's lengths are equal.

An order is given by a picking list, i.e. a set of n products, indexed from 1 to n and described by their location in the warehouse. We define by R the indexes of all locations to visit (the products) including 0 which is the index of the depot so R = {0, . . . , n}. The set I denotes the indexes of intersections between aisles and cross-aisles of the warehouse, excluding the depot. The set of all relevant locations in the warehouse is therefore V = I ∪ R. The problem is stated as follows: given n products to pick in a rectangular warehouse, what is the shortest tour (beginning and ending at the depot) to collect all these products?

It is a particular case of the Traveling Salesman Problem (TSP), the wellknown N P-hard [START_REF] Richard | Reducibility among combinatorial problems[END_REF] problem, where the salesman is the order picker and cities are products to collect. This problem, introduced by Dantzig, Fulkerson and Johnson in 1954 [START_REF] Dantzig | Solution of a large-scale travelingsalesman problem[END_REF], is one of the most studied in Operations Research. The survey of Orman and Williams [START_REF] Aj Orman | A survey of different integer programming formulations of the travelling salesman problem, Optimisation, economics and financial analysis[END_REF] gives an overview of integer programming formulations for the TSP. Efficient exact algorithms have been designed for the TSP and Concorde is one of the best exact solver (see Hahsler and Hornik [START_REF] Hahsler | Tsp infrastructure for the traveling salesperson problem[END_REF] or Mulder and Wunsch [START_REF] Samuel | Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks[END_REF]). To solve the specific case of picking problem, many heuristics have been proposed in particular by Hall [START_REF] Hall | Distance approximations for routing manual pickers in a warehouse[END_REF]. Some performance analysis of the most popular heuristics were made by Petersen [START_REF] Charles G Petersen | An evaluation of order picking routeing policies[END_REF] and by Roodbergen and De Koster [START_REF] Kees | Routing methods for warehouses with multiple cross aisles[END_REF]. Theys, Bräysy, Dullaert and Raa [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF] proposed to combine classical TSP heuristics with picking heuristics and provided a benchmark which is used in this work. An exact approach using dynamic programming has been proposed for the first time by Ratliff and Rosenthal in the case of a single block (i.e., 2 crossaisles) in 1983 [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF]. It was extended by Roodbergen and De Koster [START_REF] Kees | Routing order pickers in a warehouse with a middle aisle[END_REF] in the case of three cross-aisles. These algorithms are polynomial in the number of aisles and products of the warehouse and used in heuristics for cases with more than three cross-aisles [START_REF] Kees | Routing methods for warehouses with multiple cross aisles[END_REF][START_REF] Vaughan | The effect of warehouse cross aisles on order picking efficiency[END_REF]. Cambazard and Catusse developed a dynamic programming approach which can solve any rectilinear TSP [START_REF] Cambazard | Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane[END_REF]. This algorithm can be applied to the picking problem for any rectangular warehouse with h cross-aisles, but it is exponential in h. Although this extension was suggested in several articles [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF][START_REF] Kees | Routing order pickers in a warehouse with a middle aisle[END_REF], it has never been detailed nor implemented. The reason is that the extensive analysis made by [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF][START_REF] Kees | Routing order pickers in a warehouse with a middle aisle[END_REF] of the possible states of the dynamic program does not easily generalize beyond three cross-aisles. We give in section 5 a simple and general version of this exact algorithm for any number of cross-aisles to use it as a baseline in the experiments.

Practical comparisons have been performed between heuristics and exact algorithms, notably by De Koster and Van der Poort [START_REF] René | Routing orderpickers in a warehouse: a comparison between optimal and heuristic solutions[END_REF]. They compared the dynamic program with the commonly used S-shape heuristic and conclude that "the numerical results suggest that the savings in travel time may be substantial when using the optimal algorithm instead of the S-shape heuristic". This result strengthens the motivation for exact and efficient algorithms.

The problem can be seen as a Steiner TSP [START_REF] Scholz | A new mathematical programming formulation for the single-picker routing problem[END_REF] which is a variant of the TSP proposed independently by Fleischmann [START_REF] Fleischmann | A cutting plane procedure for the travelling salesman problem on road networks[END_REF] and Cornuéjols, Fonlupt and Naddef in 1985 [START_REF] Cornuéjols | The traveling salesman problem on a graph and some related integer polyhedra[END_REF] although Orloff introduced the idea some years before [START_REF] Cs Orloff | A fundamental problem in vehicle routing[END_REF]. Burkard et al. [START_REF] Burkard | Well-solvable special cases of the traveling salesman problem: a survey[END_REF] categorized the picking problem applied to the case of series-parallel graph in well-solvable special cases of the TSP, which includes warehouses with 2 cross-aisles [START_REF] Cornuéjols | The traveling salesman problem on a graph and some related integer polyhedra[END_REF]. Our Mixed Integer Linear Programming (MILP) model is based on the compact MILP formulations proposed by Letchord, Nasiri and Theis [START_REF] Adam N Letchford | Compact formulations of the steiner traveling salesman problem and related problems[END_REF].

The Steiner TSP (also known as subset TSP) is stated in a directed graph D = (V, A) (see Figure 1(b)) where V is the set of vertices and A is the set of arcs, defined as follows: ∀i, j ∈ V, (ij) ∈ A ⇔ one of the following conditions holds:

1. i and j are horizontally adjacent intersections (e.g. 4 and 5 in Figure 1(b)).

2. i and j are extreme intersections of an empty sub-aisle (e.g. 4 and 8).

3. j is an extreme products and i the adjacent intersection (e.g. 3 and 16).

4. i and j are adjacent products (e.g. 2 and 3).

Each arc (ij) is weighted by d ij , the distance between i and j in the warehouse. We study here the symmetric TSP, which means the graph D is such that ∀(ij) ∈ A : (ji) ∈ A and d ij = d ji . We generalize this distance by defining the function d : V × V → N as follows: d(i, j) is the distance of a shortest path between vertices i and j.

We define by P ij the set of all shortest paths between the two products i and j. More formally,

P ij = {P = (v 0 v 1 v 2 ...v K )|v 0 = i, v K = j, (v k-1 v k ) ∈ A ∀k = 1...K and K k=1 d v k-1 v k = d(i, j)}. The set of neighbors of a vertex i is denoted Γ(i) so that Γ(i) = {j ∈ V |(ij) ∈ A}.
Note that we don't need to distinguish the successeurs and predecessors of a vertex since they are the same by construction of D.

Preprocessing

The size of the problem can be considerably reduced, which is a good lever to reduce computation time. First, we can reduce the size of the picking list, i.e., the number of vertices in R. Then, we show how to reduce the number of arcs in the graph, keeping a sufficient set of arcs to find an optimal solution. Figure 2 shows an example of the impact of the preprocessing.

Reducing the number of vertices

In this part, we describe two preprocessings reducing the number of products without changing the problem. The first algorithm must be used only when the solver accepts additional constraints while the second one is general. Both algorithms are based on the following result due to Ratliff and Rosenthal: in an optimal solution, there exists six unique ways to traverse a sub-aisle (shown in Figure 3) [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF]. Case (e) is the only configuration that might not be unique. However, only configurations where the gap between black and white groups is the largest will occur in an optimal solution. The largest gap of a sub-aisle is defined as the longest empty distance between two vertices of a subaisle. Several configurations can still exist if the largest gap is not unique in the sub-aisle, but they will all have the same cost in an optimal solution.

Additional constraints available

In any case, the black vertices are all picked in one go (one after the other) and the white vertices as well. So, for both subsets, we can keep only extreme products and impose an arc to be taken between these two extreme products. (h) Figure 3: To the left: The six ways to traverse a sub-aisle. We distinguish two groups (black and white vertices) where all vertices of one group are taken in one go. In the middle: the result after preprocessing 3.1.1. Dashed vertices are removed from the problem and lines show mandatory paths. To the right: the result after preprocessing 3.1.2

Definition 1 (Preprocessing

Note that S and T can be empty or singletons (t S = b S ). Figure 3(g) shows the result after preprocessing the sub-aisle depicted. The vertices of set S are drawn in black whereas the vertices of T are white. Note that the six configurations have either (t S b S ) or (b S t S ) (or both) on one side and either (t T b T ) or (b T t T ) (or both) on the other side, hence the constraints added by the preprocessing.

Remark 1. The preprocessing does not change the value of the optimal solution and leaves at most 4 products by sub-aisle.

A similar preprocessing was proposed independently by Scholz et al. [START_REF] Scholz | A new mathematical programming formulation for the single-picker routing problem[END_REF], using different constraints to force all the products of one set (S or T) to be picked together.

With a distance matrix

When it is not allowed to add constraints, for example when using Concorde, we can still suppress some vertices. Indeed, the constraints (1) added by the preprocessing are required only if the removal of vertices changes the position of the largest gap in the sub-aisle. Thus, we can still suppress vertices as long as the largest gap remains between b T and t S (see Figure 3(h)).

Reducing the number of arcs

Let's now focus on the arcs. We compute the minimum 1-spanner in terms of number of edges, i.e., we are looking for a subset of the arcs preserving at least one original shortest path between any pairs of required vertices. The rationale is that any solution of the picking problem gives a tour where two products picked successively are linked by a shortest path. So any optimal solution can be found in a 1-spanner of G.

Definition 2. A k-spanner of a graph G is a sub-graph H ⊂ G such that:
• H contains all the vertices of G.

• The distance between each pair of vertices in H is at most k times their distance in G.

In our case, we search for a minimum "1-spanner" in the Steiner graph, restricted to the required vertices, which can also be seen as a particular case of the Minimum Manhattan Network. Let's consider the undirected graph G = (V = I ∪ R, E) where E is defined as A by removing orientation. We search for a subgraph of G such that between each pair (i, j) of required vertices there exists a shortest path which keeps the initial distance d(i, j). Namely we search a graph

H = (V H , E H ) such that: R ⊂ V H , V H ⊂ V , E H ⊂ E and ∀i, j ∈ V H : ∃ a (i, j)-path P ∈ H| (uv)∈P d uv = d(i, j).
To compute a minimum 1-spanner, we choose the minimum set of edges with respect to the preceding properties. We use an integer linear program to solve the problem of the 1-spanner, based on a model for the Minimum Manhattan Network from Benkert et al. ([2]). The resulting set of selected edges E * forms the 1-spanner which can be used to state the Steiner TSP.

The Minimum Manhattan Network is N P-hard [START_REF] Francis Yl Chin | Minimum manhattan network is NP-complete[END_REF] but its resolution with MILP turns out to be really fast in practice for the benchmark considered. Finally, note that we don't need to compute the optimal network and any feasible 1-spanner can be used for preprocessing.

MILP formulation

The Steiner variant of the TSP was proposed by Cornuéjols, Fonlupt and Naddef in 1985 [START_REF] Cornuéjols | The traveling salesman problem on a graph and some related integer polyhedra[END_REF]. It was introduced especially to solve problems where the graph is sparse. The principle is that the graph contains some required vertices which must be visited and some Steiner vertices which can be visited. Moreover, in a Steiner Traveling Salesman Problem (STSP), the graph is not complete and edges as well as vertices can be visited more than once. In this section, we apply a Steiner approach to the picking problem.

We define the Steiner graph from the directed graph modeling an instance (see Figure 1(b)): the required vertices are the products plus the depot and the Steiner vertices are the intersections in the warehouse. We look for a shortest tour in this graph, going through all the required vertices at least once.

Flow-based formulation

We can use the compact single commodity flow formulation proposed by Letchford, Nasiri and Theis [START_REF] Adam N Letchford | Compact formulations of the steiner traveling salesman problem and related problems[END_REF]. It follows the flow principle: the order picker leaves the depot with n units of a commodity and delivers one unit each time he picks a product.

We define the variables:

∀(ij) ∈ A x ij =
1 if the tour uses the arc (ij) 0 otherwise y ij = amount of commodity passing through arc (ij).

The solution of the STSP is then found by solving the following mixedinteger linear program further called SCFS, standing for Single Commodity Flow Formulation for a Steiner TSP:

(SCF S) z * = min (ij)∈A d ij x ij (1) s.t. j∈Γ(i) x ij ≥ 1 ∀i ∈ R (2) j∈Γ(i) x ij = j∈Γ(i) x ji ∀i ∈ V (3) j∈Γ(i) y ji - j∈Γ(i) y ij = 1 ∀i ∈ R \ {0} (4) j∈Γ(i) y ji - j∈Γ(i) y ij = 0 ∀i ∈ V \ {R} (5)
y ij ≤ nx ij ∀(ij) ∈ A (6) x ij ∈ N ∀(ij) ∈ A (7) y ij ≥ 0 ∀(ij) ∈ A (8)
Constraints (2) ensure that each required vertex is visited at least once. Constraints (3) ensure that the tour arrives in any vertex as many times as it leaves it. The flow constraints are different depending on whether a vertex is required or not: constraints (4) impose that the order picker delivers one unit of the commodity to each product while constraints [START_REF] Francis Yl Chin | Minimum manhattan network is NP-complete[END_REF] impose that the flow stays the same through a non-required vertex. Constraints (6) link the y to the x variables so that if some flow transits through (ij) then the arc (ij) is chosen.

Remark 2. The variables y are real variables (8) but the optimal solution will be integer due to the fact that y represent a flow. Remark 3. We know from Lemma 1 in Letchford, Nasiri and Theis [START_REF] Adam N Letchford | Compact formulations of the steiner traveling salesman problem and related problems[END_REF] that every optimal solution of the STSP uses an arc at most once and thus satisfies

x ij ≤ 1, ∀(ij) ∈ A.
It is therefore sufficient to define x as a positive integer (constraints [START_REF] Dantzig | Solution of a large-scale travelingsalesman problem[END_REF]). So the linear relaxation amounts to x ij ≥ 0. This formulation is compact and really sparse, especially thanks to the preprocessings described above. However, we notice that the quality of the lower bound given by the linear relaxation is weaker than the one given by a more standard formulation as it is explained below.

Theoretical study of the formulation

In this section, we compare the formulation described above with a standard flow-based formulation for the TSP. We consider the problem of finding a shortest tour in the complete and directed graph composed of all the products and where the distance between two vertices is the shortest distance in the warehouse. For sake of simplicity, we use the directed version of the TSP. Thus, we compare the standard single-commodity flow formulation for the TSP (as defined by Gavish & Graves [START_REF] Gavish | The travelling salesman problem and related problems[END_REF]) with the single-commodity flow formulation described above for the Steiner TSP.

We recall the Gavish and Graves formulation (denoted by SCF), adapted to a directed graph:

(SCF ) z * = min i,j∈R i =j d(i, j)x ij (9) s.t. j∈R j =i x ij = 1 ∀i ∈ R ( 10
)
j∈R j =i x ji = 1 ∀i ∈ R (11) j∈R j =i y ji - j∈R j =i y ij = 1 ∀i ∈ R \ {0} (12)
y ij ≤ nx ij ∀i, j ∈ R, i = j (13) x ij ∈ {0, 1} ∀i, j ∈ R, i = j (14) y ij ≥ 0 ∀i, j ∈ R, i = j (15)
Constraints ( 10) and ( 11) are usual assignment constraints ensuring that each vertex is visited exactly once. Constraints [START_REF] Hall | Distance approximations for routing manual pickers in a warehouse[END_REF] ensure that, except for the depot, the salesman deliver one unit at each vertex and retains the rest of the flow. Constraints [START_REF] Helsgaun | An effective implementation of the lin-kernighan traveling salesman heuristic[END_REF] are Big-M constraints linking y and x. Finally, the objective ( 9) is to minimize the total distance of the tour.

To compare both formulations, we define a projection proj which projects a fractional solution of (SCF) in the space of (SCFS) by keeping the distance value. The idea is to divide the value x between two required vertices on all the shortest paths.

Definition 3 (Projection proj). proj : R |R|

2 →R |A| x →x ( 16
)
Where proj(x ) is defined by:

x uv = i,j∈R P ∈Pij (uv)∈P x ij |P ij | ∀(uv) ∈ A ( 17
)
By construction, the conservation is checked at each vertex (property ( 19)) and each required vertex is "visited" at least as many times as in the standard TSP solution (property [START_REF] Aj Orman | A survey of different integer programming formulations of the travelling salesman problem, Optimisation, economics and financial analysis[END_REF]). A required vertex can be visited more if it lies on a shortest path between two other required vertices.

Remark 4 (Properties of proj). Let x ∈ R |R| 2 and x = proj(x ). Then:

(i) j∈Γ(i) x ij ≥ j∈R x ij ∀i ∈ R ( 18
) (ii) j∈Γ(i) x ij = j∈Γ(i) x ji ∀i ∈ V ( 19
) (iii) (ij)∈A x ij d ij = i,j∈R
x ij d(i, j)

Lemma 1. The linear relaxation of the Steiner single commodity flow formulation (SCFS) is weaker than the linear relaxation of the standard TSP single commodity flow formulation (SCF).

Proof. Every projection of an optimal solution of SCF is feasible in SCFS, so z * LP ≥ z * LP and there exists a case for which z * LP = z * LP so that SCF is a better formulation than SCFS. The two cases are detailed below:

• z * LP ≤ z * LP Let (x , y
) an optimal fractional solution of the linear relaxation of (SCF) and (x, y) = (proj(x ), proj(y )). Then (x, y) is a feasible solution for the linear relaxation of (SCFS) since:

-Assignment constraints (2) are respected due to the property (18) of proj.

-Conservation constraints are respected due to the property [START_REF] Charles G Petersen | An evaluation of order picking routeing policies[END_REF] of proj.

-For the same reasons, the flow constraints (4) and ( 5) are respected.

-Constraints ( 6) is respected: since the transformation is the same on x and y to obtain x and y, the ratio is kept:

yuv xuv = y ij x ij
≤ n so y uv ≤ nx uv ∀(uv) ∈ P ij , ∀i, j ∈ R Thus, (x, y) is feasible for SCF S and z LP = z LP .

• z * LP = z *

LP

We consider an example with 3 products and show that z * LP ≤ 18 < z * LP = 20. Figure 4(a) shows the representations of this example with the Steiner graph and with the complete graph. Solving the linear relaxation of (SCF) leads to z * LP = 20 because of constraints [START_REF] Gavish | The travelling salesman problem and related problems[END_REF] and [START_REF] Hahsler | Tsp infrastructure for the traveling salesperson problem[END_REF]. On the other side, we can easily build a feasible solution of the linear relaxation of (SCFS) with a cost 18 as shown on Figure 4(b). Thus, in this example we have z * LP < z * LP .

In the following, we introduce improvements to offset the weakness of the initial formulation and get closer, or overcome, the quality of the Standard TSP single-commodity flow formulation. 6) are big-M constraints that make the formulation quite weak and can be improved following Letchford, Nasiri and Theis [START_REF] Adam N Letchford | Compact formulations of the steiner traveling salesman problem and related problems[END_REF].

Without loss of generality, we can assume that the order picker delivers the unit of commodity due to each required vertex at his first visit. Due to the warehouse structure, a minimum number n R (i) of required vertices might have to be visited before visiting vertex i (in particular after preprocessing). We can apply a shortest path algorithm to compute n R (i) and reinforce the bound on y ij . Constraints [START_REF] Cornuéjols | The traveling salesman problem on a graph and some related integer polyhedra[END_REF] are replaced by:

y ij ≤ (n -n R (i)) x ij ∀i ∈ V, j ∈ Γ(i) (20)

Additional cuts

The Dantzig-Johnson-Fulkerson formulation based on sub-tour elimination constraints is the most well known formulation of the TSP and exhibits a very strong linear relaxation. We consider here a polynomial number of sub-tour elimination constraints depending on the warehouse dimensions rather than the number of products. In the single-flow formulation, the connectivity between all the required vertices is guaranteed. However, because of the big-M constraints [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF], the fractional value of x can be really small. Many sets of vertices are violating the sub-tour elimination constraints in practice. We focus on sets defined as cuts (S, S) partitioning the warehouse into two subsets S, S ⊂ V where S ∩ R = ∅ and S ∩ R = ∅. In other words, each subset contains at least one required vertex. Thus, there must be at least one arc going from S to S and at least one arc going from S to S. The following valid inequality is added for each cut (S, S):

x S : S ≥ 1 (21) We introduce the following cuts (see Figure 5):

• Line cuts: horizontal (resp. vertical) cuts C = (S, S) separating the warehouse horizontally (resp. vertically). See cuts (a) and (b) on Figure 5.

• Corner boxes cuts: we can combine horizontal and vertical cuts to create boxes attached to a corner of a warehouse. See cut (c) on Figure 5.

• Sub-aisle connexity: we define S ⊂ V as a set of adjacent vertices in the same sub-aisle (|S| ≥ 2). See cut (d) on Figure 5. There exists at most 6 sets of adjacent vertices in a sub-aisle since there are at most 4 products.

• Cross cuts: S is defined as the interval between the highest product and the lowest product of two adjacent sub-aisles in the same aisle. See cut (e) on Figure 5.

Note that the total number of cuts considered is polynomial in the size of the warehouse (complexity in O(hv)). We can also add valid inequalities implied by the structure of the graph:

• Intersection connexity: a path reaching an intersection (except the depot) can not immediately backtrack in an optimal solution. Namely, if an arc comes in an intersection, i.e, a Steiner vertex, by one side, an arc must go out by another side. Thus, we add the following constraints:

x ij ≤ k∈Γ(i)\{j}
x ki ∀i ∈ I, j ∈ Γ(i)

x ji ≤ k∈Γ(i)\{j}
x ik ∀i ∈ I, j ∈ Γ(i)

• Patterns: we can identify logical implications from the 6 ways to go through a sub-aisle. We recall that a sub-aisle is surrounded by two intersections (denoted s and t) and, after the preprocessing, contains at most 4 products (denoted a,b,c,d). x sd ⇒ x dc and x ds ⇒ x cd

x ta ⇒ x ab and x at ⇒ x dc

x cb ⇒ x dc ∧ x ba and x bc ⇒ x ab ∧ x cd They are added as linear constraints thanks to the following scheme: Finally, notice that any tour leads to a symmetric one by reversing the direction of traversal. Although constraints can be added to break this symmetry, it did not pay off in our experiments and they were removed.

P ⇒ Q is linearized into P ≤ Q and P ⇒ Q ∧ R is linearized into z ≥ Q + R -1, z ≤ Q, z ≤

Dynamic programming

A dynamic programming algorithm has been proposed by Ratliff and Rosenthal for the picking problem in a rectangular warehouse with two cross-aisles in 1983 [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF]. It was extended in 2001 to the case of three cross-aisles by Roodbergen and De Koster [START_REF] Kees | Routing order pickers in a warehouse with a middle aisle[END_REF]. More generally, the rectilinear TSP can be solved by dynamic programming using the very same ideas. An algorithm, proposed by Cambazard and Catusse [START_REF] Cambazard | Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane[END_REF], is proved to have a O(hn7 h ) (or more precisely O(hv7 h )) runtime complexity where n cities are located on h horizontal lines and v vertical lines. The distance considered between any pair of cities is the l 1 (rectilinear or manhattan) distance. This algorithm is directly applicable to the picking problem which can be seen as a specific case. We will now give the key ideas and a summary of this approach in the present section. We refer the reader to [START_REF] Cambazard | Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane[END_REF] for the details and in particular the proofs of correctness and complexity analysis.

We consider the problem in an undirected grid graph such as the one shown in Figure 1(b). The set of vertices located on a vertical aisle or two adjacent vertical aisles is a planar separator of this grid graph (e.g. {5, 9, 14}, {d, 9, 14} or {d, 10, 14} are separators in the graph of Figure 1(b)). The rationale of the dynamic programming algorithm is that the problem can be split into two subproblems, to the right and to the left of a separator by considering all the possible configurations of the separator (degree parity of the vertices and connected components described below). The algorithm builds a tour subgraph that can be directed as a post-processing step to obtain a picking tour. An example of such tour subgraph is shown on Figure 6.

States

A state of the dynamic program is a possible configuration of a separator. In the following, such a state ω is denoted ω = {(x 1 , . . . , x h ), (c 1 , . . . , c h )} where x i ∈ {U, E, 0} and c i are respectively the parity label and the connected component of the i-th vertex of ω. We use the same notation as Ratliff and Rosenthal [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF] to describe degree parities: even = E, odd = U (uneven) and zero = 0. Connected components are described by their indices or "-" for a zero degree. Figure 6 gives an example of a state where all vertices have an even degree and belong to two distinct connected components.

Transitions

There are two types of transitions between states: vertical and horizontal transitions, corresponding to the decisions made on vertical or horizontal edges of the grid graph. Horizontal transitions are of three kinds: no edge, a single edge or a double edge. Vertical transitions are of the six kinds identified by Ratliff and Rosenthal [START_REF] Ratliff | Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem[END_REF]: no edge, a single edge, a single double edge, two double edges connected to the top vertex, two double edges connected to the bottom vertex and four double edges defined by the largest gap (see Figure 3).

Outline of the algorithm

Algorithm 1 processes the edges of the grid graph from bottom to top and then from left to right (line 3). Typically on Figure 1(b), the edges would be considered in the following order: (4,8), [START_REF] René | Routing orderpickers in a warehouse: a comparison between optimal and heuristic solutions[END_REF][START_REF] Helsgaun | An effective implementation of the lin-kernighan traveling salesman heuristic[END_REF], [START_REF] Cambazard | Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane[END_REF][START_REF] Francis Yl Chin | Minimum manhattan network is NP-complete[END_REF], [START_REF] René | Routing orderpickers in a warehouse: a comparison between optimal and heuristic solutions[END_REF][START_REF] Fleischmann | A cutting plane procedure for the travelling salesman problem on road networks[END_REF], [START_REF] Helsgaun | An effective implementation of the lin-kernighan traveling salesman heuristic[END_REF][START_REF] Richard | Reducibility among combinatorial problems[END_REF], [START_REF] Francis Yl Chin | Minimum manhattan network is NP-complete[END_REF][START_REF] Fleischmann | A cutting plane procedure for the travelling salesman problem on road networks[END_REF] and so on. All the states obtained after adding l transitions (denoted Layer l ) belong to the l-th layer and the algorithm can be seen as a shortest path algorithm in a layered graph (see Figure 7). From any state (line 5), the possible transitions are considered (line 6); three or six depending if the edge considered is a vertical or horizontal one. We denote by T (ω, l) the value of the shortest path to reach state ω located on layer l. Lines 7-14 update the possible states of the next layer (l+1) by extending the considered state ω of layer l with the considered transition tr. The new state ω might not be a valid tour subgraph and it is checked line 8. For instance, a partial tour subgraph is not valid if a vertex is l ← l + 1 16: w opt ← argmin ω∈L hv T (ω, hv) 17: return w opt Algorithm 1: Dynamic Programming algorithm for rectangular picking left with an odd number of incident edges, if a product is not collected (zero degree) or if it has more than one connected component on the last layer (since the final tour subgraph must be connected). A shortest partial tour subgraph might be already known to reach ω and this is checked line 10.

An illustrative execution of the algorithm is given Figure 7, where a particular path is outlined showing the relation between states and partial tour subgraphs.

Experimental results

Implementation

We used the CPLEX Java API (version 12.6) to solve the different linear programs. An initial upper bound is given as "warm start" and obtained with the Lin-Kernighan heuristic [START_REF] Helsgaun | An effective implementation of the lin-kernighan traveling salesman heuristic[END_REF] implemented in the software LKH (freely available at http://webhotel4.ruc.dk/~keld/research/LKH/). This gives a better comparison with the TSP solver Concorde that takes advantage of an initial accurate upper bound [START_REF] Applegate | Chained lin-kernighan for large traveling salesman problems[END_REF]. The instances solved come from an academic benchmark proposed by Theys, Dullaert and Herroelen [START_REF] Theys | Routing order pickers in multiple block warehouses[END_REF]. Some of these instances seem bigger than realistic data, but allow to test the limits of the algorithms and to perform a comparison with previously published results on the exact same instances [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF]. Experiments were performed on an Intel Xeon E5-2440 v2 @ 1.9 GHz processor and 32 GB of RAM. The experiments ran with a memory limit of 8 GB of RAM. l=1 l=2 l=3

(0 0 0) (---) (0 U U) (-1 1) (0 E E) (-1 2) (0 E E) (- 1 1)
(0 0 E) (--1) (0 E 0) (-1 -) (E E E) (1 1 1) (0 E E) (- 1 1
)

(E E E) (1 2 2) (U U E) (1 1 1) (U U 0) (1 1 -) (U U E) (1 1 1)

Description of the instances

The benchmark of Theys et al. contains 108 classes of instances, where a class is defined by 5 parameters described in Table 1. The storage policy is either random-based or volume-based. A random policy means the products are randomly affected in the warehouse. A volume-based policy means a twenty percent of the most demanded items are located near the first cross-aisle. For more details on the instance, see Theys et al. [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF].

Early experiments showed that the location of the depot (central or decentral) does not affect the efficiency of our models. Thus, we report our results on the 54 classes with a central depot where each class contains 10 instances.

Results

The performances of the following algorithms are compared: • SCFS: the basic Steiner single commodity flow formulation

• SCFS_PP: SCFS with preprocessing of section 3

• SCFS+: SCFS with preprocessing and the additional valid inequalities

• SCF+: the standard single commodity flow formulation with vertex preprocessing 3.1.1

• CDE: Concorde

• CDE+: Concorde with preprocessed input (described in section 3.1.2)

• PDYN: dynamic programming (section 5)

To start with, we report an analysis of the problem's size, which is the biggest advantage of the SCFS formulation. Then, we look at the strength of the linear relaxation of each formulation and note that SCFS strongly benefits from the improvements proposed. In the end, we compare resolution times. The tables report the average value of the quantity studied (size, gap, cpu times) for all instances restricted to the value of the parameter given as the column header.

Size analysis. Table 2 shows the number of arcs in the TSP case (complete graph) and in the Steiner graph with and without the preprocessing 3. The lines "Evolution" show the percentage of arcs removed when the preprocessing is applied. We notice that the preprocessing is really more efficient in the TSP case due to the completeness of the graph. We also notice that the number of aisles, cross-aisles and products have an opposite effect depending on the solver.

Finally note that the number of arcs in the Steiner graph is much smaller than in the complete graph which significantly improve the memory scaling of the MILP formulations. Analysis of lower bounds. Table 3 compares the average gap between the linear relaxation and the optimal value for each parameter and for the different single-commodity flow formulations. The gap is computed as

z * -z * LP z * ×100.
The results clearly demonstrate that the improvements proposed are very effective to strengthen the linear relaxation. The gap moves from 46% to 1% in average without increasing significantly the computing time which moves from 0.07 second to 0.2 second in average. To compare our results to Concorde (see Table 4), we observe the gap between the lower bound at the root node of the search tree and the optimal value. This lower bound is better than the linear relaxation since CPLEX and Concorde apply many techniques to improve it.

SCFS+ has a strong linear relaxation despite the fact that the initial formulation SCFS is weaker than all the other ones. In practice, we observe that the linear relaxation of the improved Steiner single commodity flow formulation (SCFS+) is significantly stronger than the linear relaxation of the improved standard single commodity flow formulation (SCF+).

Performances. We set a time-limit of 30 minutes for SCFS+ and SCF+. Some instances were unsolved in this time limit. Table 5 shows the number of unsolved instances after 30 minutes of processing depending on the different parameters.

The improved Steiner formulation completely outperforms the standard compact TSP formulation. It still cannot solve some instances but they are from only 5 classes from the biggest ones and only with a random policy (15_11_240_R, 5_11_240_R 60_11_240_R, 60_3_240_R, 60_6_240_R). On the other hand, instances from 16 classes cannot be solved by the SCF solver. The only param- eter guaranteeing an optimal resolution is # products = 15. Moreover, as the Table 6 shows, the gap between the lower and upper bounds is really smaller for the SCFS+, which indicates that the upper bound can be used as a good feasible solution.

The dynamic program solves all the instances with less than 11 cross-aisles. This is a known limitation of this approach since the algorithm has an exponential complexity in the number of cross-aisles.

To compare resolution time, we choose the instances solved in less than 30 minutes by solver SCFS+. Formulation SCF+ has too many unsolved instances after this time limit so it appears irrelevant to include it in the comparison. Table 7 shows the numerical results. For each parameter, SCFS+ is slower than Concorde and dynamic programming. However, on many instances the computing time is reasonable. We also included results for solver CDE to show the impact of the preprocessing on the Concorde solver. Note that, with the preprocessing, any instance of the entire benchmark of [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF] can be solved optimally in less than 1 minute by Concorde. The dynamic programming approach is the quickest since all the accepted instances are solved in less than a second. The parameters are given in table 8 and form 30 classes of instances. For each one of their classes, we generated 10 instances of the same size. As expected, since these instances have only one block, the dynamic program is extremely efficient and solves any instance optimally in less than a second. Our MILP model also provides optimal solution for all instances almost instantaneously. Indeed, the maximal time of resolution is 6.7 seconds for the biggest instance Discussion. A number of fast heuristics have been proposed in the past to solve the order picking problem without any guarantee of optimality. And some of these heuristics have been improved to achieve better solution at the expanse of their running time [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF]. Note that the dynamic program proposed in this paper can solve instances up to 6 cross-aisles with an average time of 0.27 seconds i.e., the same order of running time reported in Theys et al (between 0.34 and 0.43 seconds for 3 and 6 cross-aisles) for advanced heuristics. We also showed that the use of Concorde with the preprocessing we propose in this paper gives excellent results even beyond 6 cross-aisles. In average, the computation time is less than 2 seconds to compute an exact solution and this method can be applied on instances of any size. The use of heuristics is therefore not relevant in our opinion if we are only concerned with minimizing the distance of the tour, since the dynamic program or Concorde with preprocessing provide an exact solution in a really small amount of time. However, these methods share a weakness with the dedicated heuristics: they cannot easily accommodate side-constraints. Our MILP model is not as efficient as the other methods but it outperforms previously proposed MILP and solve many instances in a reasonable amount of time. Thus, it is relevant to employ it when the user wants an exact solution and has specific requirements that can be modeled with linear constraints.

Instances from

Conclusion

We have studied two exact algorithms for the picking problem based on dynamic programming and mixed integer linear programming. The first approach was previously proposed for warehouses with up to three cross-aisles. We extend it to any number of cross-aisles which has often been mentioned but never done before. This algorithm proves to be extremely efficient for realistic size of warehouses. However, it can not accommodate side constraints such as precedences, flow directions or multiple depots: a MILP is better suited to deal with these requirements.

With this in mind, we showed that, on one hand, the compact formulations based on modeling the problem as a TSP do not scale in memory and are unable to solve realistic size instances. On the other hand, a flow based formulation modeling the problem as a Steiner TSP is very sparse but has a weak linear relaxation. As a result, it is also inefficient in practice. Scholz et al. proposed a new formulation, with improvement by preprocessing. However, their model is rather complex and does not yet provide convincing results regarding its efficiency when the layout grows [START_REF] Scholz | A new mathematical programming formulation for the single-picker routing problem[END_REF]. We thus propose a number of improvements by taking advantage of the warehouse structure. These improvements are based on valid inequalities and procedures to significantly reduce the instance's size without loosing optimality. The resulting model remains sparse and exhibits a strong linear relaxation in practice. It outperforms the compact TSP model and solves very large instances almost as efficiently as dedicated TSP approaches on the benchmark studied.

Note finally that some of the ideas proposed here can be applied to improve the efficiency of Concorde. The entire benchmark proposed by Theys, Bräysy, Dullaert and Raa [START_REF] Theys | Using a tsp heuristic for routing order pickers in warehouses[END_REF] can thus be solved to optimality very efficiently without the need of the heuristics proposed by the same authors.

The analysis of the results showed that the improvement was stronger when the products were stored with a volume policy. It may be a promising track to solve the picking problem jointly with other warehouse issues such as storage policy or batching. Valle et al. follow this track in a recent paper [START_REF] Cristiano | Modelling and solving the joint order batching and picker routing problem in inventories[END_REF] as did Won and Olafsson a few years ago [START_REF] Won | Joint order batching and order picking in warehouse operations[END_REF].

  Layout description of the considered warehouse

Figure 1 :

 1 Figure 1: Example of a warehouse. A representation of the different parameters of a layout and the corresponding Steiner graph are overlaid on the warehouse structure.

Figure 2 :

 2 Figure 2: Example of an instance and its preprocessing. Red edges show edges forced by the node preprocessing. The instance has 105 vertices and 270 arcs while the preprocessed instance has 65 vertices and 156 arcs.

18 Figure 4 : 4 . 3 .

 18443 Figure 4: Example with z * LP < z * LP

Figure 5 :

 5 Figure 5: Examples of the different cuts in a warehouse

  R and P ≤ z, where P , Q, R and z are boolean variables.

Figure 6 : 4 : 5 : 6 :ω ← ω + tr 8 : 9 :T 14 :

 64568914 Figure 6: The black edges represent a partial tour subgraph and the dashed edges represent one possible completion to a complete tour subgraph. The white vertices in the gray area represents the current state {(E,E,E)(1,1,2)}.

Figure 7 :

 7 Figure 7: Example of the graph underlying the dynamic programming algorithm. Each layer is identified with a value of l. Three transitions are possible from each state. The partial toursubgraph obtained by following the black path is shown on the bottom right corner. parameter values the number of vertical aisles { 5, 15, 60 } the number of cross-aisles { 3, 6, 11 } the number of products in the picking list { 15, 60, 240 } the storage policy { volume (V), random (R) } the location of the depot in the warehouse { central, decentral }

Table 1 :

 1 Parameters and values of the instances

Table 2 :

 2 Average number of arcs in TSP graph and Steiner graph, with and without preprocessing

		Total	Storage policy R V	5	# aisles 15	60	3	# cross-aisles 6	11	15	# products 60	240
	TSP	20580	20580 20580 20580 20580 20580 20580 20580 20580	240	3660	57840
	TSP+	6676	9228	4123	2319	6042	11665	3744	7238	9046	217	2350	17460
	Evolution	-68%	-55%	-80%	-89%	-71%	-43%	-82%	-65%	-56%	-9%	-36%	-70%
	Steiner	768	790	746	192	481	1633	355		705	1245	678	743	884
	Steiner+	474	543	405	157	347	917	267		456		698	216	446	760
	Evolution	-38%	-31%	-46%	-18%	-28%	-44%	-25%	-35%	-44%	-68%	-40%	-14%
		Total	Storage policy R V	5	# aisles 15	60	3		# cross-aisles 6	11	15	# products 60	240
	SCFS	46.4%	43.12% 49.68% 34.85% 45.8% 58.53% 41.95% 47.13% 50.11% 46.9% 45.24% 47.05%
	SCFS_PP	39.32%	37.41% 41.22% 24.49% 38.91% 54.55% 33.23% 40.68% 44.03% 44.74% 40.55% 32.65%
	SCFS+	1.4%	1.68% 1.13% 2.7%	1.05% 0.46% 1.72% 1.28% 1.21% 0.4%	1.21% 2.6%

Table 3 :

 3 Average gap of linear relaxations for single-commodity flow formulations

Table 4 :

 4 Average gap of root node relaxations for single-commodity flow formulations and Concorde

		Total	Storage policy R V	5	# aisles 15	60	3	# cross-aisles 6	11	15	# products 60	240
	SCFS+	0.65%	1.01% 0.29% 1.33% 0.36% 0.27% 0.81% 0.53% 0.61% 0.04% 0.34% 1.59%
	SCF+	6.44%	7.47% 5.48% 2.39% 4.73% 13.3%	7.6%	6.27% 5.34% 0.37% 5.09% 15.36%
	CDE+							< 0.1%
			Total	Storage policy R V	5	# aisles 15	60		3	# cross-aisles 6	11	15	# products 60	240
	SCFS+		18	18	0	1	4	13		1	2		15	0	0	18
	SCF+		136	88	48	19	34	83		51	41		44	0	26	110
	PDYN		180	90	90	60	60	60		0	0		180	60	60	60
	# instances	540	270	270	180	180	180	180	180		180	180	180	180

Table 5 :

 5 Number of unsolved instances after 30 minutes

Table 6 :

 6 Average gap between best upper and lower bounds for unsolved instances

		Total	Storage policy R V	5	# aisles 15	60	3	# cross-aisles 6	11	15	# products 60	240
	SCFS+	1.3%	1.3%	-	0.85% 0.46% 1.59% 0.23% 0.29% 1.51%	-	-	1.3%
	SCF+	19.63%	19.1% 20.51% 10.19% 18.8% 23.45% 16.37% 21.19% 23.91%	-	7.79% 23.47%

Table 7 :

 7 Average time of optimal resolution (in seconds) for instances solved in less than 30 minutes with each solver

Table 8 :

 8 Scholz et al. Scholz et al. introduced other instances for the case of a single-block layout[START_REF] Scholz | A new mathematical programming formulation for the single-picker routing problem[END_REF]. Parameters and values of the Scholz instances

	parameter	values
	number of products in a sub-aisle	45
	number of cross-aisles	2
	number of vertical aisles	{ 5, 10, 15, 20, 25, 30 }
	number of products in the picking list	{ 30, 45, 60, 75, 90 }
	location of the depot in the warehouse	decentral

Table 9 :

 9 Average time of optimal resolution (in seconds) for "Scholz instances", solved in less than 30 minutes with each solver (30 aisles and 90 products) and the average on all the instances is 0.28 seconds. Moreover, the model introduced by Scholz et al. fails to find the optimal solution for 44 instances. Table9details the computation time to find the optimal solution for these solvers. Please note that our instances are not exactly the same than those solved by Scholz et al. but were generated with the same parameters.

		Total	5	10	# aisles 15 20	25	30	30	45	# products 60	75	90
	Scholz	167.7	0.11	1.21	10.54	170.91 314.56 508.87 45.53	87.56	149.03 233.24 323.14
	SCFS+	0.28	0.06	0.09	0.13	0.34	0.54	0.54	0.07	0.13	0.25	0.38	0.6
	PDYN	< 0.001						< 0.001

In the MILP (see section 4) it translates into the following constraints:x t S b S + x b S t S ≥ 1 if t S = b S and x t T b T + x b T t T ≥ 1 if t T = b T