Florence Rodhain
email: florence.rodhain@isim.univ-montpi!.fr

Tacit to Explicit: Transforming Knowledge Through Cognitive Mapping -An experiment'

Keywords:

In the Information System field, the articulation of the mental models business managers use to make decisions is problematic because this knowledge is often tacit. Cognitive mapping can be used to transform tacit knowledge into explicit knowledge. The purpose of this paper is to demonstrate how this is achieved. It is argued here that cognitive mapping not only externalizes tacit knowledge, but also has an effect on the tacit knowledge itself: tacit knowledge can be transformed, reorganized, or reconstructed during the process of constructing an external representation.

INTRODUCTION

In the special issue "Knowledge and the Firm" of the California Mmagement Review, Holtshouse [ 191 identified three priorities for further research and experimentation if the field of knowledge management is to advance. One of these three major issues is how to make tacit knowledge, which is invisible and intangible by nature, visible and concrete. Attempting to understand how decisions are made in organizations can be a difficult task. Asking the actors about how they make decisions can lead to complete silence. In fact, the actors can have difficulties expressing a process leading to a decision [6] [S] [15] [31] [32], because the knowledge used to make the decision is tacit. Polanyi [START_REF] Polanyi | The Tacit Dimension[END_REF], who has introduced the useful distinction between tacit and explicit knowledge, explained that tacit knowledge is difficult to formalize and communicate, whereas explicit knowledge is transmittable in formal language. For example, researchers attempting to construct expert systems are constantly challenged to quantify how decisions are made, and embrace any tools or methods that convert tacit into explicit knowledge. In general, organizations need to access the actor's tacit mental models in order to file them Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for protit or commercial advantage and that copies bear this notice and the full citation on the first page. TO copy otherwise. to republish, to post on servets or to redistribute to lists, requires prior specific permission and/or a fee. SIGCPR '99 New Orleans LA USA Copyright ACM 1999 I-581 13-063-5/99/04...$5.00 in the organizational memory, so organizations need tools that permit access to these tacit mental models. Cognitive mapping is such a tool. Specifically, cognitive mapping incorporates the process of externalization [26] [27], the conversion of knowledge from tacit into explicit. This process will be demonstrated both by theoretical and practical arguments found in the literature and through the author's past application of cognitive mapping.

WHAT IS A COGNITIVE MAP?

A cognitive map is a graphic representation of an individual's or several individuals' mental models. It is composed of ideas and links between these ideas. Most of the links between ideas are causal links. Causal link A +B can be understood as followed: -A is the explanation of B, -B is the consequence of A, -A is the means and B is the goal. For example, the sentence: "I water the plants in order for them to grow" can be represented this way (figure 1):

The plants grow (B) P I water the &nts (A) Fimre 1 This sentence can be read in three different ways (figure 2): -the plants grow because I water them (A is the explanation of Bh -I water the plants, so they grow (B is the consequence of A), aim: make the plants grow; means: water them (B is an aim and A is a means). To design a cognitive map, it is necessary first to collect the information source to be coded, and then to code this information in the shape of a map. The information can be obtained from data that pre-existed the construction process of the cognitive map, or from data collected for the construction process of the cognitive map.

-Methods based on pre-existing data. In this case, documents written by the subject have to be studied. For example, it is possible to base a cognitive map on the re-transcription of a subject's discourse during political meetings [ 181. Axelrod and his colleagues [3] have applied this method to political science.

-Methods based on data collected for the construction process of the cognitive map. Except for the structured interview technique 'The Self-Q Technique", developed by Bougon [4] [S], no formal method of information gathering is found in the literature. Thus the method used by Eden's team [lo] [ll] is unstructured. No interviewing protocol exists to guide a researcher in gathering data to be coded. The formalism for the representation of cognitive maps adopted by Professor Eden's group, from Strathclyde University in Glasgow, is widely used by researchers. They used cognitive maps as a tool to assist a consultant attempting to resolve complex problems within a small group. As previously stated, the ideas are obtained from non-directing interviews. According to Ackermann et al. [ 11, an idea is a sentence expressed by an interlocutor that can number up to twelve words. It is better to present the ideas in an imperative form with an action verb, in order to build a dynamic map [l]. The ideas in the cognitive map can have different natures. In order to structure a problem, the method recommends distinguishing four kinds of ideas [l] [START_REF] Rakotoarivelo | Ameliorer la qualite des decisions prises en groupe : le recours au concept de carte mentale[END_REF]: -the goals. The goals express aims or desires to be reached. These ideas are located at the top of the map; -the Critical Success Factors (CSF) or strategic issues. The CSFs are constituted of central ideas that allow the identification of different processes to reach the goals. The ideas are located at the center of the map because they are intermediate between the goals and the potential means; -the actions or key options. These actions, located at the bottom of the map, make it possible to reach the CSFs; -the chains of argumentation. These constitute standard ideas, namely ideas that are neither identified as goals, CSFs, or actions. The next figure (figure 3) shows how such ideas are organized in a cognitive map:

Action Anion Actlion Action

A cognitive map can be constructed during the interview. In this case, the "facilitator" must be experienced in constructing cognitive maps. A cognitive map can also be directly constructed with the help of the "Decisions Explorer" software developed by Eden's research team. This software is useful because numerous ideas and links can be recorded and organized quickly into a readable form, which would normally be too difficult to organize on a piece of paper. Also, this software permits the performance of several types of analyses on the cognitive maps. The next figure (figure 4) shows a small part of a cognitive map constructed for a manager who was speaking about the strategy of his organization: The ideas are presented differently using italicized, underlined, and bold text. The purpose is to be able to differentiate between the different types of ideas easily. On a computer, using the Decisions Explorer software, the ideas are. also differentiated by the use of colors. The sohware attributes sequentially the numbers on each idea each time a new idea is entered.

The manager identified two goals (37 and 14). one CSF (38). two standard ideas (74 and 75) and one action (73). One idea is "bipolar" (37), meaning that, in the mental model of the manager, one side of the idea expresses a concept opposite of the other side's The two poles am separated by "....".

Figure 4

Among the useful functions the Decisions Explorer software performs is the identification of CSFs. This function measures the "centrality" of an idea, which is the criterion used to identify CSFs. It lists all the ideas that have a higher density of links. The centrality of an idea is measured as the software counts the number of arrows emanating to and from an idea. This centrality can be measured in seven levels. The arrows directly emanating from the idea belong to level 1. The software uses this measure: all links at level 1 have the coefficient 1, the links at level 2 have the coefficient l/2, the links at level 3 have the coefficient l/3, and so on, until the seventh level. The next figure (figure 5) shows a simple example of this function:

3 Fiaure

We can count three links at level 1 and five links at level 2. In this case, the centrality of level 2 is: 3*1 + 5*0.5 = 5.5. [20] [24]. Some research, more than others, demonstrate the transformation of tacit knowledge into explicit knowledge. For example, in political science, Axelrod [3] used cognitive mapping in an attempt to understand how politicians make decisions in order to help them improve their governance and consequently improve the resulting decisions. Individuals make decisions from mental models, but they are not always aware of them because the knowledge used to make decisions is tacit, not explicit. Axelrod's ambition is to help politicians to make timely, precise decisions and to teach them to be aware of the thought process they employ to make decisions. Since politicians are not always aware of the process they use to make decisions, cognitive mapping can be used to help them externalize their tacit knowledge. Another example is the use of cognitive mapping by Eden's research team [13]. According to Eden et al., business administrators are not aware of the apprenticeship processes they use. So they use cognitive mapping as a tool to allow the decision-makers to discover and organize their own thoughts, which in turn helps uncover the solutions to complex organizational problems. Another example of the use of cognitive mapping to externalize the knowledge can be found in a Montazemi and Conrath paper [START_REF] Montazemi | The Use of Cognitive Mapping for Information Requirements Analysis[END_REF] that describes an automatic Information System that was built for a large Canadian car insurance company. The managers of the company had expressed how difficult it was to evaluate their subordinates. The evaluation process was complex and subjective because each manager administered it the way he or she wanted to. The company wished to identify a system that would make it possible to evaluate each employee fairly. This was a complex issue because each manager was not aware of his or her own personal evaluating process. Using the cognitive mapping tool, the authors managed to formalize and explain the tacit processes used by managers to evaluate their subordinates. These examples are not exhaustive. The next point will show a more complete experiment using cognitive mapping and will show how tacit knowledge can become explicit and how it can be shared once it became explicit.

Externalization of business strategy mental models

The author built an IS (Information System) planning method", using cognitive mapping, allowing the discovery of a unique portfolio of projects. Four reasons to use the cognitive mapping tool for this project follow: First, cognitive mapping allows the modeling of mental models. This is important because IS requirements ensue from mental models. Second, cognitive mapping makes it possible to remove complex, vague and ill-structured problems --the activity of planning is typically ill-structured--because it allows clarification of the thought or the structuring of the thought [17] [21] [23]. The complex process that leads to the production of a cognitive map that is supposed to model the individual's thought, has an effect on the thought itself. The effect is that the thought is more structured, hence more clear. Since the IS requirements, which are often not clear, ensue from mental models, this second property of cognitive mapping is very useful because it allows the identification of requirements by clarifying the thought.

Third, cognitive mapping makes it possible to communicate ideas [7] [14] [17] [22]. Indeed, cognitive mapping can be used within a group acting in a collective way, and can become a vector to convey complex ideas between actors and eventually contribute to negotiation. This is particularly interesting because the activity of planning must lead to the production of one and only one portfolio of projects where several actors who have different views about the organization take part in the planning. This common portfolio of projects follows not only from an effort of communication of different individual mental models but also from a collective effort of discussion to find a common mental model, that will serve as a common ground. Fourth, the elaboration of a cognitive map allows consideration of possible lines of actions [ 1 l] [ 171. This function also seems to be pertinent to the planning of the IS. Indeed, the aim of planning is to achieve coherence between the strategy of an organization and the IS. The strategy is characterized by objectives that the organization tries to reach, and medium term actions, including IS ones, must be brought into operation to reach these objectives. A plan in the form of a cognitive map representing the strategy, is likely to induce the actor to consider lines of action that can be used to reach the identitied objectives and to find objectives that justify the use of such means.

Quick description of the method

The process is composed of three main phases (figure 6 During this first phase, each actor participating in the planning process thinks about his or her mental models of the organization. The participants build, with help from an intervening party, a representation of goals to reach, the main CSFs, and the IS projects that may judiciously be brought into operation. This phase results in the production of a cognitive map for each individual, that is composed of the goals, the CSFs, and the IS projects to be brought into operation for the next five years, according to the individual. The first phase is of primary importance because it enables the participants to peacefully contemplate their mental models without their colleagues being present.

-Phase 2: confrontation of mental models.

During this meeting, the actors are asked to imagine and describe the nature of their colleagues' mental models to the intervening party. The actors are asked to imagine:

-the way their colleagues discern the problem, -the actions and solutions that their colleagues should have stated.

This confrontation of mental models should make it possible to reduce the misunderstandings between actors. Moreover, this confrontation enables the actors to consider the areas where there is a potential conflict and where there is a potential consensus. In so doing, they are more aware of the differences that exist between their colleagues' mental models and their own. In such a context, before any collective meeting, the participants are made aware of the projects their colleagues proposed. Once this exercise is done, they are shown their colleagues' summarized cognitive map.

-Phase 3: construction of a collective mental model.

For the first time since the beginning of the process, all the participants are gathered together in order to agree on the portfolio of projects to retain. This last phase is composed of at least one meeting. The aim of the meeting is to construct a collective map that satisfies all the members of the group. Found on this map are the retained IS projects showing their priority and the links that attached them to the CSFs and to the goals. The process ends when the participants express satisfaction with the collective portfolio of projects.

During this meeting, it is supposed that:

-the actors are disposed to listen to their colleagues' point of view, because they want enlightenment on some points that they might not have understood during the second phase; -the actors' arguments become more structured and strengthened, because they have given them careful consideration during the previous phases.

Experiment and results

The method was applied within three organizations. It proved to be effective each time, because it converged on the a priori fixed goal, namely obtaining a portfolio of projects that satisfied the actors who participated in the experiment. After each experiment, a semi-directive interview was held with each participant in order to assess the method and the obtained results. From these interviews, the most prevalent idea was that cognitive mapping transforms knowledge from tacit to explicit. For example, Bob, a computer engineer, said': "Cognitive mapping enabled me to explain information that underlined my discourse and was obvious to me, but was not explicitly expressed." The treatment of the interviews shows clearly that, as expected, the use of cognitive mapping clarified the participants' mental model in regard to the strategy of the organization. Nevertheless, the result is not a simple transformation of tacit knowledge into explicit knowledge, because the process goes through many modifications. As the participants expressed, this clarification leads them to structure their thought. These results confirm previous research about cognitive mapping. To demonstrate this restructuring, let us look at different participants' evaluation transcripts. Although the interviewer does not use the word "clarifying", it appears spontaneously twice during interviews with Tom and Don. Tom explained that cognitive mapping seems extremely interesting and useful, because it formalizes and clarifies ideas. To him, it is important that the meetings for the construction of the individual maps are held far apart because " . . .it induces me to express myself again, clarifying my conversation." To Don, this clarification enabled him " . . . to have a better vision of things and a better message to express whatever may make the task easier." It is the content of the discussions that was most interesting to Bob. This participant explained that, during the first interview, he was " . . . allowed to be disorganized." Afterward, he was " . . . asked to be more Cartesian," hence he has "to clarify" his "ideas". He felt he had to do it " . . . when the model showed contradictions." In this case, he wondered about the foundation of the contradiction that induced him to clarify his thoughts. In the same way, Scott stated: "At the beginning, we bring everything to you in bulk, and then you bring back things rather organized, and then we make light of doing it, and finally it seems logical. Hence this first phase is a phase of mental construction. I guess it helps us a lot. It helps us specify and to finally obtain a rather clear vision of what we said before. In fact, you helped us clarify our thought. Sometimes, when things were a bit confused, it seems interesting to me because I was speaking confusedly and then you brought back your diagram and this enlightened me . . . ". Let us emphasize that Scott uses the words "mental construction" to express the process he experienced through the cognitive mapping even if the interviewer deliberately had not suggested it to him during the interview. Speaking about the impact of the discovery of his individual cognitive maps, Steve stated about his thought: "I saw it better now, that is to say as a whole, in a spatial way. Yes, it is more comfortable to visualize, to see, to perceive, hence I saw it better." Then Steve explained that when he thinks, it seems difficult to mobilize and to subdue many concepts, and even more difficult to keep in mind hierarchized concepts that are linked to one another. That is why cognitive mapping helped him 'see better". Later, Steve explained what he meant by "better". About the cognitive mapping, he testifies: "It gave me a vision perhaps more coherent than the one I had about the things I thought of "

According to Steve, to better see his thought is to see it more coherently. And later, Steve said:

"The process enables one to structure one's own reflection. One often has vague intuitions and ideas. But, at any given moment, one has to make them come into view more clearly. At this time, in the initial phase, when the interviewee has been brought his individual map, the tool is very important. The questions one wonders about during the elaboration of the map are precisely important elements of construction. And to me, this is something very positive. It is positive, because even when they have ideas, I think that few managers state these ideas clearly and carefully within a coherent diagram, except when they try to answer a partial question, then they try to find arguments. But in reality, we have rather few occasions to make this global analysis, except for planning. Here the support is important. I guess it is rather positive. . . I am not sure that the method led me to find out many things, but it helued me better understand and better explain what is in mv mind. No one knows. Whether the ideas were the same or new ones appeared, the action of stating them had an effect: it modified the thought, since Steve affirmed that it enlightened or structured his thought. One can verify then a modification of the thought through the act of stating. Steve's mental model about the strategy of the organization evolves through the exercise of constructing discursive representations that are supposed to represent the thought. Their thoughts became clearer according to the participants (and the information systems projects are a part of this representation) and so more communicable. These comments show that during the experiments the use of cognitive mapping allowed the structuring or clarification of the thought that led to a "better understanding of oneself' to again use a participant's words. This function of cognitive mapping was important in this experiment because, since the IS requirements proceed from mental models, a clear expression of these requirements demands a clear representation of the situation that they entail. So, in the case of IS planning, the clearer the individual's mental models of the organization's situation, the easier it is to determine the IS requirements.

CONCLUSION

This paper attempted to show that cognitive mapping transforms tacit knowledge into explicit knowledge. This process, known as the externalization process [START_REF] Nonaka | A Dynamic Theory of Organizational Knowledge Creation[END_REF], is very important in the IS field where the articulation of mental models remains a current problem. The problem is to develop an external representation of mental models. This process is very difficult because managers can have difficulties expressing the mental models they use when they act. Cognitive mapping can help this process. Nevertheless, the process of externalization is not neutral. In fact, IS researchers and practitioners should be aware that mental models are subject to change during the process of externalization. This also means that the action of the practitioners is not neutral. Therefore, the job of the practitioners is less to "extract" the tacit knowledge, than it is to "construct" an explicit knowledge based on the tacit knowledge.

37

  Keep the tvoe of jobs that we have... Move toward a less interestine iob I4 Work more with Eurouean commznies &oal: 25% of revenue). . 38 Develon work in collaboration with a network of foreign exnerts.. .

  Figure 5 4. PRACTICAL ILLUSTRATIONS OF EXTERNALIZATION Cognitive maps are diversely constructed and applied to resolve numerous and varied issues [2] [9][20] [24]. Some research, more than others, demonstrate the transformation of tacit knowledge into explicit knowledge. For example, in political science,Axelrod [3] used cognitive mapping in an attempt to understand how politicians make decisions in order to help them improve their governance and consequently improve the resulting decisions. Individuals make decisions from mental models, but they are not always aware of them because the knowledge used to make decisions is tacit, not explicit. Axelrod's ambition is to help politicians to make timely, precise decisions and to teach them to be aware of the thought process they employ to make decisions. Since politicians are not always aware of the process they use to make decisions, cognitive mapping can be used to help them externalize their tacit knowledge. Another example is the use of cognitive mapping by Eden's research team[13]. According to Eden et al., business administrators are not aware of the apprenticeship processes they use. So they use cognitive mapping as a tool to allow the decision-makers to discover and organize their own thoughts, which in turn helps uncover the solutions to complex organizational problems. Another example of the use of cognitive mapping to externalize the knowledge can be found in aMontazemi and Conrath paper [25] that describes an automatic Information System that was built for a large Canadian car insurance company. The managers of the company had expressed how difficult it was to evaluate their subordinates. The evaluation process was complex and subjective because each manager administered it the way he or she wanted to. The company wished to identify a system that would make it possible to evaluate each employee fairly. This was a complex issue because each manager was not aware of his or her own personal evaluating process. Using the cognitive mapping tool, the authors managed to formalize and explain the tacit processes used by managers to evaluate their subordinates. These examples are not exhaustive. The next point will show a more complete experiment using cognitive mapping and will show how tacit knowledge can become explicit and how it can be shared once it became explicit.

  : construction of individual mental models.

  still, I am not sure of having discovered really new things compared to what I had in mind but here the validity of my answer is limited, because what do we have in mind at the beginning? One does not necessarily have a clear and coherent diagram. Here is the unavoidable question: what do I mean? If I think this, what does it imply? Hence a kind of constraint that enables one to reason more rigorously is introduced, for example, the notion of links between ideas and, of course through the notion of Cn'tical Success Factors. It makes one pursue the analysis in a more structured way and at the same time, I think that one improves one's explanation with creativity."

"How can I know what I think before hearing what I say?' Weick wonders

[START_REF] Weick | The Social Psychology of Organizing[END_REF]

. Steve attested that cognitive mapping enabled him to enlighten his thought, to understand better what he had in his mind. He stated he did not think he found new ideas in comparison with what he thought before the beginning of the process. But once he stated it, he wondered about the veracity of this affirmation, because what was in his mind at the beginning?


Thibault Prunet
email: thibault.prunet@emse.fr

Nabil Absi
email: absi@emse.fr

Valeria Borodin
email: valeria.borodin@emse.fr

Diego Cattaruzza
email: diego.cattaruzza@centralelille.fr

Branch-Cut-and-Price Algorithm for an Integrated Storage Location Assignment and Picker Routing Problem

Introduction

Warehousing is one of the main components of any supply chain, and an essential lever of performance optimization in a logistic system. Order picking (OP), i.e. the action of retrieving items from storage locations according to customers orders, is the most laborintensive operation in a warehouse, and is considered as the main area for performance improvement [START_REF] Koster | Design and control of warehouse order picking: A literature review[END_REF]. Manual OP is still widely used for its involved flexibility, and due to the large investment cost of automation. The Operations Research literature on this topic focuses mainly on two main operations: storage and picker routing.

In this paper, we study the integration of these two problems: we aim at finding an efficient assignment of Stock Keeping Units (SKU, i.e. a collection of identical products) to storage locations that minimize the traveled distance for the OP. In the literature, the Storage Location Assignment Problem (SLAP) has mainly been tackled by using class-based storage and statistical information on SKU. The SLAP is thus mainly solved via policybased heuristics, like the widely-used Cube-per-order-index (COI) [START_REF] Koster | Design and control of warehouse order picking: A literature review[END_REF]. These approaches have several advantages: (i) adaptable to many situations, (ii) easy to implement, and

(iii) able to solve industrial-scale instances. However, the "pick-by-order" feature, where all items of one order are picked altogether in one route, is often not considered. Furthermore, the storage and routing problems are optimized separately, despite their strong connection. Few attempts have been made at tackling the problem with full information on demand and order structure. (Boysen and Stephan 2013 [START_REF] Boysen | The deterministic product location problem under a pick-by-order policy[END_REF]) is one of the only example, proving the NP-hardness of the problem. Recently (Silva et al. 2020 [START_REF] Silva | Integrating storage location and order picking problems in warehouse planning[END_REF]) tackled a similar problem with a metaheuristic approach. The SLAP presents an academic interest, to get a more thorough comprehension of the interactions between storage, layout and routing. It also has a practical interest to model the forward area, where the storage assignment changes dynamically in a very versatile context, increasing in this way the impact of operational considerations. The problem under study is called the Integrated Storage Location Assignment and Picker Routing Problem (ISLAPRP). The present work aims at addressing these research gaps with an exact solution method, based on a Dantzig-Wolfe reformulation of the problem.

In the problem studied throughout this paper, the aim is to assign a set of SKU S to a set of storage locations L. This assignment is represented by the binary decision variables ξ ls , equal to one if SKU s ∈ S is stored in location l ∈ L, 0 otherwise. The demand over the planning horizon is modeled by a set of orders O, each order being defined by a set of SKU to collect. Order batching is not considered in the model, but can be optimized beforehand, and batches used as input instead of single orders. The picking policy is pick-by-order, where one picker route corresponds to the preparation of one order. The objective is then to minimize the total walking distance to retrieve all orders. The function f (o, ξ) represents the walking distance to retrieve all SKU from order o ∈ O, according to storage assignment plan ξ. An explicit formulation of f require the introduction of new variables and constraints, depending on the routing policy and warehouse layout. The aforementioned model is given below.

min o∈O f (o, ξ) (1)
s.t. l∈L ξ ls = 1 ∀s ∈ L (2) s∈S ξ ls ≤ 1 ∀l ∈ L (3)
ξ ls ∈ {0, 1} ∀l ∈ L, s ∈ S (4)
The objective (1) is to minimize the total walking distance. Constraints (2) and ( 3) are assignment constraints. Constraints (4) define the definition domain of variables. For order o ∈ O, we note S(o) ⊂ S the set of SKU included in order o, and R o the set of all possible routes to serve this order. A route r corresponds to a set of visited storage locations, and is associated with a cost c or . This cost depends on the warehouse layout and the routing policy for pickers. A set of parameters a l or is associated with each route r ∈ R o , which equals to 1 if location l ∈ L is visited by the route, and 0 otherwise. The binary decision variable ρ or is associated with a route r ∈ R o , and equals to 1 if the route is selected in the plan, and 0 otherwise. The described model is presented below: min o∈O r∈Ro c or ρ or (5)

s.t. r∈Ro ρ or ≥ 1 ∀o ∈ O (6) s∈S ξ ls ≤ 1 ∀l ∈ L (7) l∈L ξ ls = 1 ∀s ∈ S (8) r∈Ro a l or ρ or ≥ s∈S(o) ξ ls ∀l ∈ L, o ∈ O (9) ρ or ∈ {0, 1} ∀o ∈ O, r ∈ R o ( 10
)
ξ ls ∈ {0, 1} ∀l ∈ L, s ∈ S (11)
The objective (5) is to minimize the total walking distance of all the routes included in the plan. Constraints (6) state that, for every order o ∈ O, at least one route is selected.

Constraints ( 7) and ( 8) are the assignment constraints. Constraints (9) link the routes to the assignment variables. For each order o ∈ O and location l ∈ L, if one SKU from this order is assigned to location l (right-hand side), then there must be at least one route servicing o that visits location l (left-hand side). Constraints (10) and (11) are domain definition constraints for the binary decision variables.

Branch-and-price framework

The extended formulation (5)-( 11) is well suited to column generation, since the exponential number of variables does not permit a tractable enumeration. The relaxation of the integrality constraints (10) and (11) leads to the master problem, then restricted to a subset of columns. Additional columns are integrated dynamically at each iteration, by looking for routes of negative reduced cost. The column generation is then integrated in a Branch-and-Bound framework to restore the variables integrality.

The highly structured constraint matrix of the problem leads to a natural decomposition for route generation. Indeed, one pricing problem needs to be solved for each order, and all problems are independent. The warehouse layout and routing policy for order pickers appear explicitly in these problems, so the formulation of the pricing changes depending on the characteristics of the problem at hand. The subproblems are modeled with an adapted resource-constrained shortest path problem, solved by dynamic programming.

Valid inequalities

A family of valid inequalities has been identified to strengthen the dual bound provided by the column generation. These inequalities are quite similar to the linking constraints (9), since they link the storage and routing decisions. However their number is exponential, and as such they are generated dynamically by an efficient separation procedure. Since they are non-robust with the pricing problem, a particular attention is paid to the design of an efficient management of the cut pool.

Results and Discussions

To study the performance of the proposed approach, a set of heterogeneous instances of different sizes and parameters has been generated. The solution approaches discussed in this paper are implemented on Julia, with the use of CPLEX 12.10. Preliminary experiments are run with a time limit of 20 minutes. Table 1 presents a comparison of CPLEX with an MIP formulation, the branch-and-price with dual bounds computed using Column Generation (CG), with and without the addition of valid inequalities. The first column shows the number of instances solved to optimality (out of 30), and the second the average gap between primal and dual bounds when the algorithm stops.

2 Methodology 2 . 1

 221 Extended formulationFormulated as a mixed-integer program, the ISLAPRP presented in model (1)-(4) has a very poor linear relaxation. Let us propose a novel extended formulation for this problem, based on a Dantzig-Wolfe reformulation. This extended formulation includes an exponential number of variables, added dynamically by a column generation technique. In this formulation, the warehouse layout and picker routing policy are still considered implicitly, with the relevant details convexified into the subproblem.

Table 1 :

 1 First results on a set of 30 benchmark instances

		# instances solved Average gap
	CPLEX	7	0.135
	Branch-and-Price	1	0.107
	Branch-Cut-and-Price	26	0.002