Christine Solnon

Combining two Pheromone Structures for Solving the Car Sequencing Problem with Ant Colony Optimization

Keywords: Ant Colony Optimization, Car Sequencing Problem, Multiple Pheromone Structures PACS:

The car sequencing problem involves scheduling cars along an assembly line while satisfying capacity constraints. In this paper, we describe an Ant Colony Optimization (ACO) algorithm for solving this problem, and we introduce two different pheromone structures for this algorithm: the first pheromone structure aims at learning for "good" sequences of cars, whereas the second pheromone structure aims at learning for "critical" cars. We experimentally compare these two pheromone structures, that have complementary performances, and show that their combination allows ants to solve very quickly most instances.

Introduction

The car sequencing problem involves scheduling cars along an assembly line in order to install options (e.g., sun-roof or air-conditioning) on them. Each option is installed by a different station, designed to handle at most a certain percentage of the cars passing along the assembly line, and the cars requiring this option must be spaced so that the capacity of the station is never exceeded. This problem is NP-hard [START_REF] Kis | On the complexity of the car sequencing problem[END_REF]. It has been formulated as a constraint satisfaction problem (CSP), and is a classical benchmark for constraint solvers [START_REF] Dincbas | Solving the carsequencing problem in constraint logic programming[END_REF][START_REF] Gent | Csplib: a benchmark library for constraints[END_REF][START_REF] Tsang | Foundations of Constraint Satisfaction[END_REF]. Most of these CSP solvers use a complete tree-search Email address: christine.solnon@liris.cnrs.fr (Christine Solnon).

Preprint submitted to Elsevier Science approach to explore the search space in a systematic way, until either a solution is found, or the problem is proven to have no solution. In order to reduce the search space, this approach is combined with filtering techniques that propagate capacity constraints to reduce variables' domains. In particular, a dedicated filtering algorithm has been proposed for handling capacity constraints [START_REF] Regin | A filtering algorithm for global sequencing constraints[END_REF]. This filtering algorithm is very effective to solve some hardly constrained feasible instances, or to prove infeasibility of some overconstrained instances. However, on some other instances, it cannot reduce domains enough to make complete search tractable.

More recently, [START_REF] Gravel | Review and comparison of three methods for the solution of the car-sequencing problem[END_REF] has proposed an integer programming model where the objective is to find a sequence that minimizes the number of violated constraints subject to a set of linear integer constraints. This approach makes it possible to rather quickly find solutions to difficult instances that are feasible. However, it requires much longer computation times for reaching best-known solutions for infeasible instances.

Hence, different incomplete approaches have been proposed, that leave out exhaustivity, trying to quickly find approximately optimal solutions in an opportunistic way, e.g., local search [DT99,LLW98,PG02,MH02,GPS03,EGN05], large neighbourhood search [START_REF] Perron | Combining forces to solve the car sequencing problem[END_REF], IDWalk [START_REF] Neveu | Id walk: A candidate list strategy with a simple diversification device[END_REF], evolutionary algorithms [START_REF] Warwick | Tackling car sequencing problems using a genetic algorithm[END_REF], or Ant Colony Optimization [START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF][START_REF] Gravel | Review and comparison of three methods for the solution of the car-sequencing problem[END_REF].

Ant Colony Optimization

The basic idea of Ant Colony Optimization (ACO) [DD99,DCG99,DS04] is to model the problem to solve as the search for a minimum cost path in a graph, and to use artificial ants to search for good paths. The behavior of artificial ants is inspired from real ants: artificial ants lay pheromone on components (edges and/or vertices) of the graph and each ant chooses its path with respect to probabilities that depend on pheromone trails that have been previously laid by the colony; these pheromone trails progressively decrease by evaporation. Intuitively, this indirect stigmergetic communication means aims at giving information about the quality of path components in order to attract ants, in the following iterations, towards the corresponding areas of the search space. Indeed, for many combinatorial problems, a study of the search space landscape shows a correlation between solution quality and the distance to optimal solutions [JF95, [START_REF] Merz | Fitness landscapes and memetic algorithm design[END_REF][START_REF] Stützle | MAX-MIN Ant System[END_REF].

Artificial ants also have some extra-features that do not find their counterpart in real ants. In particular, they are usually associated with data structures that contain the memory of their previous actions, and they may apply some "daemon" procedures, such as local search, to improve the quality of computed paths. In many cases, pheromone is updated only after having constructed a complete path, and not during the walk, and the amount of pheromone deposited is usually a function of the quality of the complete path. Finally, the probability for an artificial ant to choose a component often depends not only on pheromones, but also on some problem-specific local heuristics.

The first ant algorithm to be applied to a discrete optimization problem has been proposed by Dorigo in [START_REF] Dorigo | Optimization, Learning and Natural Algorithms[END_REF]. The problem chosen for the first experiments was the Traveling Salesman Problem and, since then, this problem has been widely used to investigate the solving capabilities of ants [START_REF] Dorigo | Ant System: Optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | Ant colony system: A cooperative learning approach to the traveling salesman problem[END_REF]. The ACO metaheuristic, described in [DD99,DCG99,DS04], is a generalization of these first ant based algorithms, and has been successfully applied to different hard combinatorial optimization problems such as quadratic assignment problems [GTD99,MC99], vehicle routing problems [BHS99,GTA99], constraint satisfaction problems [START_REF] Solnon | Ants can solve constraint satisfaction problems[END_REF], maximum clique problems [START_REF] Solnon | A study of aco capabilities for solving the maximum clique problem[END_REF], or graph matching problems [START_REF] Sammoud | Ant algorithm for the graph matching problem[END_REF].

Motivations and overview of the paper

We have proposed in [START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF] a first ACO algorithm dedicated to permutation constraint satisfaction problems -the solution of which is a permutation of a given tuple of values. Performances of this algorithm have been illustrated, among other problems, on the car sequencing problem. In this first ACO algorithm for the car sequencing problem, pheromone is laid on couples of consecutive cars in order to learn for promising sequences of cars.

Then, in [START_REF] Gottlieb | A study of greedy, local search and ant colony optimization approaches for car sequencing problems[END_REF], we have proposed and compared different heuristics for solving the car sequencing problem in a greedy randomized way. These heuristics aim at favoring the choice of critical cars during greedy constructions of sequences: these critical cars require hardly constrained options and should be sequenced as soon as possible. We have shown that this very simple greedy approach is able to solve many instances very quickly. We have also shown that these greedy heuristics can be integrated within the ACO algorithm of [START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF] in a very straightforward way. These greedy heuristics are very efficient and greatly help ants to solve the car sequencing problem. However, designing such problem-dependent heuristics is a difficult task that requires a good knowledge of the problem to solve. Hence, a main objective of this paper is to answer the following question:

Would it be possible to use ACO to identify these critical cars, and solve the car sequencing problem without integrating problem-dependent heuristics?

To answer this question, we introduce a new pheromone structure, that aims at identifying critical cars, and we compare it with the greedy heuristic of [START_REF] Gottlieb | A study of greedy, local search and ant colony optimization approaches for car sequencing problems[END_REF]. We also study the integration of this new pheromone structure with the pheromone structure introduced in [START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF] and that aims at identifying promising sequences of cars.

The paper is organized as follows. Section 2 formally defines the car sequencing problem we are considering here. Section 3 recalls the basic features of the greedy randomized approach of [START_REF] Gottlieb | A study of greedy, local search and ant colony optimization approaches for car sequencing problems[END_REF]. Section 4 describes the first pheromone structure introduced in [START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF] and that aims at identifying promising sequences. Section 5 introduces a new pheromone structure that aims at identifying critical cars and Section 6 shows how these two pheromone structures may be combined. We experimentally compare the different pheromone structures and the greedy heuristic in Section 7, and we compare our results with two recent state-of-the-art local search approaches in Section 8.

The Car Sequencing Problem

We consider here the classical car sequencing problem introduced in [START_REF] Dincbas | Solving the carsequencing problem in constraint logic programming[END_REF]. A complete description of this problem and some benchmark instances may be found in CSPlib [START_REF] Gent | Csplib: a benchmark library for constraints[END_REF]. This problem is a special case of the car sequencing problem proposed by Renault for the ROADEF challenge in 2005 [START_REF] Nguyen | Le problème du car sequencing renault et le challenge roadef[END_REF][START_REF] Solnon | Editorial: The car sequencing problem: overview of state-of-the-art methods and industrial case-study of the roadef'2005 challenge problem[END_REF]. In particular, the challenge problem introduces two different priority levels for capacity constraints, and it introduces paint batching constraints. Considering the classical car sequencing problem allows us to focus on heuristics for dealing with capacity constraints.

Definition of a Car Sequencing Problem

A car sequencing problem is defined by a tuple (C, O, p, q, r) such that

• C = {c 1 , .., c n } is the set of cars to be produced; • O = {o 1 , .., o m } is the set of different options;
• p : O → N and q : O → N define capacity constraints, i.e., for every option o i ∈ O, each subsequence of q i consecutive cars on the line must not contain more than p i cars that require option o i (see 2.2 for complete definition); • r : C × O → {0, 1} defines option requirements, i.e., for each car c i ∈ C and for each option o j ∈ O, r ij = 1 if o j must be installed on c i , and r ij = 0 otherwise.

Solution of a Car Sequencing Problem

Solving a car sequencing problem involves finding an arrangement of the cars in a sequence, defining the order in which they will pass along the assembly line, such that the capacity constraints are met. We shall use the following notations to denote and manipulate sequences:

• a sequence, noted π =< c i 1 , c i 2 , . . . , c i k >, is a succession of cars;

• the set of all sequences that may be built with a set of cars C is noted Π C ;

• the length of a sequence π, noted |π|, is the number of cars that it contains;

• the concatenation of two sequences π 1 and π 2 , noted π 1 • π 2 , is the sequence composed of the cars of π 1 followed by the cars of π 2 ; • a sequence π 1 is a subsequence of another sequence π 2 , noted π 1 ⊆ π 2 , if there exists two (possibly empty) sequences π 3 and π 4 such that π 2 = π 3 • π 1 • π 4 ; • the cost of a sequence π is the number of violated capacity constraints, i.e.,

cost(π) = o i ∈O π k ⊆π so that |π k |=q i violation(π k , o i ) where violation(π k , o i ) =        0 if <c l >⊆π k r li ≤ p i ; 1 otherwise.
We can now define the solution process of a car sequencing problem (C, O, p, q, r) as the search of a minimal cost sequence composed of all the cars to be produced.

3 Greedy randomized construction of sequences Figure 1 describes a greedy randomized algorithm for constructing sequences: starting from an empty sequence1 , cars are iteratively added at the end of the sequence until all cars have been sequenced. At each step, the set of candidate cars (cand) is restricted to the set of cars that introduce the smallest number of new constraint violations (line 4)2 . To break symetries, we also

Input: an instance (C, O, p, q, r) of the car sequencing problem a transition probability function p : restrict the set of candidate cars to cars that require different options (line 5). Then, given this set of candidate cars, the next car is chosen with respect to a transition probability function p: given a candidate car c i ∈ C, a set of candidate cars cand ∈ P(C) (where P(C) is the set of all subsets of C), and a partial sequence π ∈ Π C , this transition function returns the probability of actually choosing c i . This probability may be defined in different ways, and Sections 4, 5 and 6 propose three different definitions for it, based on different pheromone structures.

C × P(C) × Π C →]0; 1] Output: a sequence π that contains each car of C once 1-π ←<> 2-while | π |≤| C | do 3- let C-π denote the set of cars of C that are not yet sequenced in π 4- cand ← {c k ∈ C-π|∀c j ∈ C-π,cost(π. < c k >) ≤ cost(π. < c j >) and 5- (∀o i ∈ O, r ki = r ji ) ⇒ (k ≤ j) } 6- choose c i ∈ cand w.r.t. probability p(c i , cand, π) 7- π ← π• < c i > 8-end while 9-return π
In this section, we define the probability transition function proportionally to a heuristic function η that locally evaluates the "hardness" of a candidate car c i , i.e.,

p(c i , cand , π) = [η(c i , π)] β c k ∈cand [η(c k , π)] β
where β is a numerical parameter which allows one to tune the weight of the heuristic in the transition policy: the higher β, the greedier the policy.

We have introduced and compared in [START_REF] Gottlieb | A study of greedy, local search and ant colony optimization approaches for car sequencing problems[END_REF] five different definitions for the heuristic function η. These definitions are based on utilization rates of required options and aim at favoring the choice of cars requiring options that have high demands with respect to capacities. The heuristic function of [START_REF] Gottlieb | A study of greedy, local search and ant colony optimization approaches for car sequencing problems[END_REF] that obtained the best average results is defined by the sum of the utilization rates of the options required by the car, i.e.,

η(c i , π) = o j ∈O r ij • utilRate(o j , C -π)
where utilRate(o j , C -π) is the utilization rate of option o j with respect to the set C -π of cars that are not yet sequenced in π. This utilization rate is the percentage of cars of C -π requiring o j with respect to the maximum number of cars in a sequence of length |C -π| which could have o j while satisfying its capacity constraint, i.e.,

utilRate(o j , C -π) = q j • c k ∈C-π r kj p j • | C -π |
An utilization rate close to 1 (resp. 0) indicates that the demand is very high (resp. low) with respect to the capacity of the station.

A first pheromone structure for identifying good car sequences

Solving an instance (C, O, p, q, r) of the car sequencing problem involves finding a permutation of the set of cars C that satisfies capacity constraints. This problem can easily be modelled as the search for a best hamiltonian path in a graph that associates a vertex with each car. Such hamiltonian path finding problems are classical applications for the ACO metaheuristic: for these problems, ants lay pheromone on the graph edges in order to learn for promising sequences of vertices. Based on this principle, we have proposed in [START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF] a first ACO algorithm for the car sequencing problem, and we briefly recall its main features here.

Basically, the algorithm follows the MAX-MIN Ant System scheme [START_REF] Stützle | MAX-MIN Ant System[END_REF]. First, pheromone trails are initialized to a given upper bound τ max 1 . Then, at each cycle every ant constructs a sequence, and pheromone trails are updated.

To prevent premature convergence, pheromone trails are bounded within two given bounds τ min 1 and τ max 1 such that 0 < τ min 1 < τ max 1 . The algorithm stops iterating either when an ant has found a solution, or when a maximum number of cycles has been performed.

Pheromone structure

Pheromone is laid on couples of cars. For every couple of different cars (c i , c j ) ∈ C × C, we associate a pheromone trail τ 1 (c i , c j ). Intuitively, this pheromone trail represents the learnt desirability of scheduling c j just after c i .

Construction of sequences by ants

At each cycle every ant constructs a sequence, following the greedy randomized algorithm of Figure 1. To choose the next car c i to be added at the end of the current sequence π, the transition probability function depends on two factors: a pheromone factor which evaluates the learnt desirability of adding c i at the end of π, and the heuristic factor η introduced in section 3, i.e.,

p(c i , cand, π) = [τ 1 (c j , c i )] α 1 • [η(c i , π)] β c k ∈cand [τ 1 (c j , c k )] α 1 • [η(c k , π)] β if the last car of π is c j p(c i , cand, π) = [η(c i , π)] β c k ∈cand [η(c k , π)] β if π =<>
As usually in ACO algorithms, α 1 and β are numerical parameters that are used to determine the relative weights of the two factors.

Pheromone updating step

Once every ant has constructed a sequence, pheromone trails are updated. First, all pheromone trails are decreased in order to simulate evaporation, i.e., for each couple of different cars (c i , c j ) ∈ C × C, the quantity of pheromone τ 1 (c i , c j ) is multiplied by a factor (1 -ρ 1 ) where ρ 1 is the evaporation rate such that 0 ≤ ρ 1 ≤ 1.

Then, the best ants of the cycle deposit along their paths a trail of pheromone which is inversely proportional to the number of violated constraints: for each sequence π constructed during the cycle, if the cost of π is minimal for this cycle then, for each couple of consecutive cars < c j , c k >⊆ π, we increment τ 1 (c j , c k ) by 1/cost(π).

Finally, pheromone trails that are lower (resp. greater) than τ min 1 (resp. τ max 1 ) are set to τ min 1 (resp. τ max 1 ). The goal of this pheromone bounding step is to favor a better exploration of the search space by preventing the relative differences between pheromone trails from becoming too extreme during processing [START_REF] Stützle | MAX-MIN Ant System[END_REF].

A second pheromone structure for identifying critical cars

The heuristic function η combined with the first pheromone structure in the transition probability function defined in Section 4 aims at favoring the choice of critical cars, i.e., cars that require options with high utilization rates so that they can hardly be scheduled without violating capacity constraints. We now introduce a new pheromone structure for identifying these critical cars with respect to past experiences of the colony.

Pheromone structure

Different cars may require a same subset of options, and all these cars are equivalent with respect to the hardness of sequencing them. Hence, we group the cars requiring the same options into classes, and we associate a pheromone structure with every different class.

More formally, we define the class of a car c i ∈ C as the set of options required by c i , i.e., classOf The second pheromone structure introduced here is not managed according to the MAX-MIN Ant System of [START_REF] Stützle | MAX-MIN Ant System[END_REF]. Indeed, imposing lower and upper bounds on pheromone trails and initializing them to the upper bound favor a larger exploration of the search space at the beginning of the search but, as a counterpart, increase the time spent before converging towards good solutions. However, first experiments showed us that it is necessary to quickly identify critical cars to build good solutions: without such identification (e.g., when running the greedy algorithm of Figure 1 with the β parameter set to zero), the constructed sequences violate hundreds of capacity constraints. Hence, to favor a quicker feedback on the critical cars we only introduce a lower bound τ min 2 (that ensures that the probability of choosing a car cannot become null), and pheromone trails are initialized to the lower bound τ min 2 at the beginning of the search.

(c i ) = {o j ∈ O|r ij = 1},

Construction of a sequence by an ant

Ants incrementally build sequences following the algorithm described in Fig. 1. To choose the next car c i to be added at the end of the current sequence π, the transition probability function only depends on a pheromone factor which evaluates the learnt hardness of the class of c i , i.e.,

p(c i , cand , π) = [τ 2 (classOf (c i ))] α 2 c k ∈cand [τ 2 (classOf (c k ))] α 2
where α 2 is a numerical parameter which allows one to tune the weight of the pheromone factor.

Pheromone updating step

Ants lay pheromone on car classes during the construction of sequences: each time no more cars can be scheduled without introducing some new constraint violations, some pheromone is added on the classes of the cars that still have to be scheduled (thus indicating that the cars of this class should have been scheduled earlier). The quantity of pheromone added is equal to the number of new constraint violations introduced by the cars of this class. More precisely, we modify the algorithm of Figure 1 by inserting between lines 5 and 6 the following lines:

if ∀c i ∈ cand , cost(π. < c i >) > cost(π) then for every car class cc ∈ {classOf (c i ) | c i ∈ C -π} do τ 2 (cc) ← τ 2 (cc) + cost(π. < c i >) -cost(π)
(where c i is a car of the class cc)

Note that this pheromone laying procedure occurs during the construction step, and not after all ants have completed their construction step, like in most ACO algorithms. Indeed, the quantity of pheromone laid does not depend on the global quality of the sequence but on the local evaluation of the car class with respect to the partial sequence that is currently built. Note also that every ant adds pheromone, and not only the best one(s) of the cycle.

Finally, pheromone is evaporated after every sequence construction. This is done by multiplying the quantity of pheromone τ 2 (cc) laying on each car class cc ∈ classes(C) by a factor (1 -ρ 2 ) where ρ 2 is the evaporation rate such that 0 ≤ ρ 2 ≤ 1.

Combining the two pheromone structures

The two proposed pheromone structures achieve two complementary goals: the first one aims at identifying promising subsequences of cars; the second one aims at identifying critical car classes. Hence, one can easily combine these two complementary pheromone structures:

• Ants lay pheromone on couples of cars (c i , c j ) ∈ C × C and the quantity of pheromone τ 1 (c i , c j ) represents the past experience of the colony with respect to sequencing car c j just after car c i . For this first pheromone structure, pheromone trails are bounded within the interval [τ min 1 ; τ max 1 ] and they are initialized to the upper bound τ max 1 . Pheromone trails are updated at the end of each cycle, once every ant of the colony has computed a complete sequence, and only the best ants of the cycle lay pheromone.

• Ants also lay pheromone on car classes cc ∈ Classes(C) and the quantity of pheromone τ 2 (cc) represents the past experience of the colony with respect to the difficulty of sequencing cars of this class without violating constraints. For this second pheromone structure, a lower bound τ min 2 is imposed and pheromone trails are initialized to this lower bound. Pheromone is laid by every ant while it constructs a sequence, and the evaporation step occurs at the end of every sequence construction by an ant.

The algorithm followed by ants to build sequences is the same as the one displayed in figure 1. To choose the next car c i to be added at the end of the current sequence π, the transition probability function depends on two different pheromone factors, i.e.,

p(c i , cand, π) = [τ 1 (c j , c i )] α 1 • [τ 2 (classOf (c i ))] α 2 c k ∈cand [τ 1 (c j , c k )] α 1 • [τ 2 (classOf (c k ))] α 2 if the last car of π is c j p(c i , cand, π) = [τ 2 (classOf (c i ))] α 2 c k ∈cand [τ 2 (classOf (c k ))] α 2 if π =<>
As usual, α 1 and α 2 are numerical parameters that are used to determine the relative weights of the two pheromone factors.

Note that the greedy heuristic function η introduced in section 3, and combined with the first pheromone structure in section 4 is no longer used in this new transition probability. Indeed, this heuristic factor, that aims at identifying critical cars, has been replaced by the second pheromone structure.

7 Experimental comparison of the pheromone structures and the greedy heuristic

Considered algorithms and test suites

To compare the pheromone structures τ 1 and τ 2 and the greedy heuristic function η, we consider four different versions of the greedy randomized algorithm of Figure 1, based on four different definitions of the transition probability function p:

• in Greedy(η) the transition probability function is based on the greedy heuristic function η as described in Section 3; • in ACO(τ 1 , η) the transition probability function is based on a combination of the first pheromone structure τ 1 and the greedy heuristic function η as described in Section 4; • in ACO(τ 2 ) the transition probability function is based on the second pheromone structure τ 2 as described in Section 5; • in ACO(τ 1 , τ 2 ) the transition probability function is based on a combination of the two pheromone structures τ 1 and τ 2 as described in Section 6.

All algorithms have been implemented in C and run on a 2GHz Pentium 4.

These four different versions are experimentally compared on a test suite of 82 instances generated by Perron and Shaw and described in [START_REF] Perron | Combining forces to solve the car sequencing problem[END_REF]. In this test suite, all instances have |O| = 8 options and |Classes(C)| = 20 different car classes; capacity constraints are randomly generated while ensuring that ∀o i ∈ O, 1 ≤ p i ≤ 3 and p i < q i ≤ p i + 2. The number of cars |C| to be sequenced varies between 100 and 500: 32 (resp. 21 and 29) instances have 100 (resp. 300 and 500) cars. All instances are feasible and have at least one solution that satisfies all capacity constraints.

Parameter settings

Each run of each considered algorithm is limited to 150000 constructions of sequences: for ACO(τ 1 , η) and ACO(τ 1 , τ 2 ) we have fixed the maximum number of cycles to 5000 and the number of ants to 30; for Greedy(η) and ACO(τ 2 ) we have fixed the maximum number of cycles to 150000 as a single sequence is built at each cycle. Note that the construction of 150000 sequences roughly corresponds to 20 (resp. 50 and 100) seconds of CPU time on a 2GHz Pentium 4 for instances with 100 (resp. 300 and 500) cars.

The setting of the other parameters is summarized in Table 1 and is discussed Heuristic η 1 st pheromone structure 2 nd pheromone structure

β α 1 ρ 1 τ min 1 τ max 1 α 2 ρ 2 τ min 2 Greedy(η) 6 - - - - - - - ACO(τ 1 , η) 6 2 1% 0.01 4 - - - ACO(τ 2 ) - - - - - 6 3% 1 ACO(τ 1 , τ 2 ) - 2 1% 0.01 4 6 3% 1
below. To tune parameters, we have run algorithms on a subset of the test suite instances that contains 32 instances (9 instances with 100 cars, 7 instances with 300 cars and 16 instances with 500 cars). These 32 instances have been selected for tuning parameters because they appeared to be the most difficult ones for the greedy algorithm (other instances were trivially solved).

Both Greedy(η) and ACO(τ 1 , η) use the greedy heuristic η in their probability transition function and have to set the parameter β that determines the weight of this heuristic. Experiments have been done with different values for β, ranging between 1 and 10. The best average results have been obtained when it is fixed to 6 (eventhough rather equivalent results were obtained when β ∈ [4; 8]).

The three ACO variants use the pheromone structures τ 1 and/or τ 2 in their probability transition functions and have to set the pheromone factor weight α, the pheromone evaporation rate ρ, and the bounds τ min and τ max associated with these pheromone structures. Setting these parameters makes it possible to balance between two dual goals when exploring the search space: on the one hand, one has to intensify the search around the most "promising" areas, that are usually close to the best solutions found so far; on the other hand, one has to diversify the search and favor exploration in order to discover new, and hopefully more successful, areas of the search space. Diversification may be emphasized in ACO algorithms by decreasing α -so that ants become less sensitive to pheromone -or by decreasing ρ -so that pheromone evaporates more slowly-or by decreasing the difference between τ min and τ max -so that the relative difference between pheromone factors decreases. When increasing the exploratory ability of ants in this way, one usually finds better solutions, but as a counterpart it takes longer to find them. This duality has been observed on many different combinatorial problems such as, e.g., maximum clique problem [START_REF] Solnon | A study of aco capabilities for solving the maximum clique problem[END_REF] or constraint satisfaction problem [START_REF] Solnon | Boosting ACO with a preprocessing step[END_REF].

We have chosen two different parameter settings for the two pheromone structures τ 1 and τ 2 . Indeed, as pointed out in Section 5, the identification of critical cars appears to be essential for building good solutions, so that one has to set α 2 and ρ 2 to values that favor intensification in order to have a quick feedback, i.e., α 2 = 6 and ρ 2 = 0.03. On the contrary, we have chosen a setting that ensures a good diversification of the search for the first pheromone structure, i.e., α 1 = 2 and ρ 1 = 0.01 (as discussed in [START_REF] Gottlieb | A study of greedy, local search and ant colony optimization approaches for car sequencing problems[END_REF]).

Note that the performances of the three ACO variants are rather stable with respect to these pheromone parameter settings. For example, when running ACO(τ 1 , τ 2 ) with different values for α and ρ (with α 1 ∈ {1, 2, 3, 4}, ρ 1 ∈ {0.5%, 1%, 2%, 3%}, α 2 ∈ {4, 6, 8, 10}, and ρ 2 ∈ {1%, 2%, 3%, 5%}), the final success rates (over 50 runs on each of the 82 instances) vary between 85.3% for the worth configuration and 94.7% for the best one, whereas the average is 91.3%.

Experimental comparison

Figure 2 displays the evolution of the percentage of successful runs (that have found a solution) of the four considered algorithms with respect to CPU time.

Let us first compare Greedy(η) with ACO(τ 2 ), as both algorithms build sequences with respect to a greedy heuristic that evaluates the hardness of car classes, but differ on the way this estimation is done: Greedy(η) considers the sum of the utilization rates of the required options, whereas ACO(τ 2 ) "learns" this with respect to past experiences of the colony. Figure 2 shows that the success rate of ACO(τ 2 ) is always more than 10% as high as the success rate of Greedy(η): after 0.05 seconds of CPU-time, Greedy(η) and ACO(τ 2 ) have respectively solved 42.5% and 55.8% of the runs, whereas after 100 seconds of CPU-time, they have respectively solved 65.6% and 77.6% of the runs.

Let us then compare Greedy(η) with ACO(τ 1 , η) (resp. ACO(τ 2 ) with ACO-(τ 1 ,τ 2 )) to evaluate the benefit of integrating the first pheromone structure τ 1 within the transition probability function. Figure 2 shows that at the beginning of the solution process, the success rates of Greedy(η) and ACO(τ 1 , η) (resp. ACO(τ 2 ) and ACO(τ 1 , τ 2 )) are very close. Indeed, the setting of the parameters for managing τ 1 has been chosen in order to favor exploration so that during the first cycles τ 1 does not significantly influence transition probabilities: at the beginning of the search process, pheromone trails are initialized to the upper bound, τ max 1 , so that after k cycles, the quantity of pheromone is bounded between τ max 1 • (1 -ρ 1 ) k and τ max 1 . Then, after five hundred or so cycles (roughly corresponding to two, five, and ten seconds for instances with 100, 300 and 500 cars respectively), the first pheromone structure actually influences ants so that the success rate of ACO(τ 1 , η) (resp. ACO(τ 1 , τ 2 )) becomes significantly higher than the success rate of Greedy(η) (resp. ACO(τ 2 )).

As a conclusion, let us note that the second pheromone structure τ 2 allows ants to solve very quickly (in less than 0.05 seconds) more than half of the runs. The first pheromone structure τ 1 needs more time to guide ants towards better sequences (around two, five and ten seconds for instances with 100, 300, and 500 cars respectively), but actually improves the solution process so that, at the end of the solution process, the combination of the two pheromone structures allows ants to solve nearly 95% of the runs.

8 Comparison with other approaches

Considered approaches

We now compare the best performing of our four variants, ACO(τ 1 , τ 2 ), with two recent local search approaches, i.e., IDWalk and VFLS.

IDWalk [START_REF] Neveu | Id walk: A candidate list strategy with a simple diversification device[END_REF] is a new metaheuristic based on local search that appears to obtain better results than other metaheuristics -such as tabu search and simulated annealing-for solving the car sequencing problem among other problems. Besides the maximum number of moves (MaxMv), this approach introduces only one parameter, called Max, that determines the maximum number of neighbours that are considered before performing every move. At each iteration IDWalk chooses the first non decreasing neighbour, and if all the Max considered neighbours deteriorate the current solution, IDWalk chooses the best one over them. The Max parameter is automatically determined at the beginning of the search by performing a few short walks (of 2000 moves) with different possible values. This value is also reactively adapted during the solution process when the length of the walk reaches some given limits. In the case of the car sequencing problem, the neighbourhood is defined by the set of all sequences that can be obtained by swaping any pair of cars that have different car classes and such that at least one car is involved in one or more constraint violations; the car that is involved in constraint violations is chosen with respect to a probability that is proportional to the number of constraints it violates. The initial sequence of cars from which the local search is performed is constructed in a greedy way, using the η heuristic described in Section 3.

VFLS (for "Very Fast Local Search") [START_REF] Estellon | Ordonnancement de véhicules : une approche par recherche locale à grand voisinage[END_REF][START_REF] Estellon | Real-life car sequencing: very large neighborhood search vs very fast local search[END_REF] is the algorithm that won the ROADEF challenge on the car sequencing problem [START_REF] Nguyen | Le problème du car sequencing renault et le challenge roadef[END_REF][START_REF] Solnon | Editorial: The car sequencing problem: overview of state-of-the-art methods and industrial case-study of the roadef'2005 challenge problem[END_REF].

In addition to capacity constraints, the ROADEF problem contains some extra constraints that are related to car colors and that aim at minimizing solvents. The implementation of VFLS considered in this comparison is an adaptation of the one that have won the challenge, where data structures have been optimized to focus on capacity constraints only. The VFLS algorithm is based on a local search approach similar to the one proposed in [START_REF] Gottlieb | A study of greedy, local search and ant colony optimization approaches for car sequencing problems[END_REF]: starting from an initial sequence that is constructed in a greedy way using a heuristic based on utilization rates, the algorithm chooses at each iteration the first neighboor of the current solution that does not increase its cost. The considered neighbourhood is defined by a set of five transformations (exchange of two cars, insertion of a car backward or forward, and mirror and random permutations of subsequences). The probability of choosing each of these transformations respectively is 0.6, 0.13, 0.13, 0.13, and 0.01.

Test suite and experimental setup

We compare the three approaches on the 82 instances of the test suite provided by Perron and Shaw. However, to discuss scale-up properties, we have gouped these instances into three subsets with respect to the number of cars |C| to be sequenced: the first group contains the 32 instances with 100 cars; the second one contains the 21 instances with 300 cars; and the third one contains the 29 instances with 500 cars.

The three algorithms have been implemented in C or C++, and have been run on the same 2GHz Pentium 43 . Each algorithm has been run 50 times on each instance.

Experimental Results

Figures 3, 4, and5 show the evolution of the success rates with respect to CPU time on instances with 100, 300, and 500 cars respectively. On the three figures, we note that for very short CPU time limits ACO(τ 1 , τ 2 ) is better than IDWalk, which itself is better than VFLS: after 0.1 second of CPU time, ACO(τ 1 , τ 2 ) has solved more than 60% of the runs while VFLS and IDWalk have respectively solved 6% and 25% of the runs. However, the success rate of VFLS increases more steeply than the success rates of IDWalk and ACO(τ 1 , τ 2 ). Therefore, after a few seconds of CPU time, VFLS has clearly surpassed IDWalk. Finally, at the end of the processing time, VFLS has reached the success rate of ACO(τ 1 , τ 2 ) for the instances with 100 and 300 cars, whereas VFLS has outperformed ACO(τ 1 , τ 2 ) for the instances with 500 cars.

The fact that ACO(τ 1 , τ 2 ) is outperformed by VFLS at the end of the processing time for the largest instances that have 500 cars brings to the fore the differences in the time complexities of these algorithms. Indeed, if there are |C| = n cars to sequence and |classes(C)| = k different car classes, then the complexity of constructing one sequence by an ant is in O(nk), the complexity of the pheromone laying step is in O(n) and the complexity of the evaporation step is in O(n 2 ). As a comparison, the time complexity of performing one move, in both IDWalk and VFLS, does not depend on the total number of cars to be sequenced: each move is locally evaluated by considering only a subsequence of cars and the time complexity of one move mainly depends on the sizes (q i ) of the gliding subsequences on which the capacity constraints must be checked. In the test suite we have considered here, these sizes are bounded between 2 and 5 for all instances.

Conclusion

We have introduced a new pheromone structure for solving the car sequencing problem. This pheromone structure aims at identifying critical cars and experimental results have shown us that it obtains better results than the greedy heuristic based on utilization rates. We have also shown that this new pheromone structure may be combined with another pheromone structure that aims at identifying good subsequences of cars. This double pheromone structure may be related to previous work on multiple pheromone matrices for solving other combinatorial optimization problems. In particular, [START_REF] Iredi | Bi-criterion optimization with multi-colony ant algorithms[END_REF] introduces two different pheromone structures to solve bi-criteria optimization problems, where each pheromone structure is tailored to one optimization criteria. [MR02] also introduces two different pheromone structures, one for intensifying the search around good solutions, and one for diversifying the search around apparently poorer areas of the search space. Multi colony approaches such as, e.g., [START_REF] Middendorf | Multi colony ant algorithms[END_REF][START_REF] Chu | Ant colony system with communication strategies[END_REF], also consider multiple pheromone matrices. However, in these approches the different pheromone matrices have an homogeneous structure, as these different pheromone matrices are used by different ant colonies that work in parallel to solve a combinatorial optimization problem.

We have shown in this paper that the combination of two complementary pheromone structures makes it possible to obtain very competitive results on the car sequencing problem, being able to solve many instances much quicker than VFLS, the local search based algorithm that won the ROADEF 2005 challenge. However, on the largest instances and for longer time limits, ACO is outperformed by VFLS. Hence, further work will mainly concern the integration of local search techniques within our "double" ACO algorithm. Indeed, local search may be combined with the ACO metaheuristic in a very straightforward way: ants construct solutions exploiting pheromone, and local search improves their quality by iteratively performing local moves. Actually, the best-performing ACO algorithms for many combinatorial optimization problems are hybrid algorithms that combine probabilistic solution construction by a colony of ants with local search [DG97,SH00,Sol02a,SF06,SSSG06].

Finally, even if it is not a criteria for comparing approaches, let us point out the simplicity of our double ACO algorithm which is very easy to implement: the C code corresponding to ACO(τ 1 , τ 2 ) contains less than 300 lines (including input/output issues). This is generally not the case of local search approaches which have to use more sophisticated data structures in order to incrementally evaluate moves.

Fig. 1 .

 1 Fig. 1. Greedy randomized construction of a sequence of cars.

  and we denote by classes(C) the set of all different car classes, i.e., classes(C) = {classOf (c i )|c i ∈ C}. Given a car class cc ∈ classes(C), we note τ 2 (cc) the quantity of pheromone laying on it. Intuitively, this quantity represents the past experience of the colony concerning the difficulty of sequencing cars of this class without violating capacity constraints.

Fig. 2 .

 2 Fig.2. Comparison of Greedy(η), ACO(τ 1 , η), ACO(τ 2 ), and ACO(τ 1 , τ 2 ). Each curve plots the evolution of the percentage of successful runs (over 50 runs on each of the 82 instances) with respect to CPU time (in logscale).

  Fig. 3. Evolution of the percentage of successful runs with respect to CPU time for ACO(τ 1 , τ 2 ), VFLS, and IDWalk, on the 32 instances with 100 cars.

  Fig. 4. Evolution of the percentage of successful runs with respect to CPU time for ACO(τ 1 , τ 2 ), VFLS, and IDWalk, on the 21 instances with 300 cars.

  Fig. 5. Evolution of the percentage of successful runs with respect to CPU time for ACO(τ 1 , τ 2 ), VFLS, and IDWalk, on the 29 instances with 500 cars.

Table 1

 1 Parameter settings.

The sequence π could be initialized to a non empty sequence in order to take into account the last cars sequenced on the line the previous day, as it is the case in the problem proposed by Renault for the ROADEF challenge.

Note that this elitist strategy, that discards cars introducing more constraint violations, may not be optimal for solving over-constrained instances. To solve such over-constrained instances, it may be preferable not to discard cars introducing more constraint violations but to decrease the probability of selecting them, as proposed in[START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF][START_REF] Gravel | Review and comparison of three methods for the solution of the car-sequencing problem[END_REF].

The code of IDWalk and VFLS have been kindly sent by their authors, and the obtained results have been validated by the authors.

Acknowledgements. Many thanks to Bertrand Estellon, Frédéric Gardi and Karim Nouioua for giving the code of VFLS, and to Bertrand Neveu and Gilles Trombettoni for giving the code of IDWalk.


Rebecca Gentek

Marc Bajénoff
email: bajenoff@ciml.univ-mrs.fr

Lymph node stroma dynamics and approaches for their visualization

Lymphoid stromal cells are best known as the architectural cells of lymphoid organs. For decades, they have been considered as inert elements of the immune system but this view has changed dramatically in recent years, when it was discovered that they are endowed with critical immuno-regulatory functions. It is now accepted that without them, the adaptive immune response would be compromised, if not abrogated entirely. Here, we review the function of the major lymphoid stromal cell types, the way they remodel upon inflammation, discuss the available tools to track their behavior and introduce several methodological approaches that we believe will help improving our knowledge of these pivotal cell types.

Lymphoid stromal cells: versatile and re-configurable 3D immunological networks

Secondary lymphoid organs such as lymph nodes (LNs) are organs in which adaptive immune responses develop. They are composed of 95% motile leukocytes and 5% sessile stromal cells [START_REF] Mueller | Stromal cell contributions to the homeostasis and functionality of the immune system[END_REF]. In 1984, Nossal wrote ''A readership consisting of primarily anatomists has every right to question the favorite sport of research workers in cell immunology. This is to take a lymphoid tissue and totally destroy its beautiful and elaborately designed architecture to obtain simple cell suspension of lymphocytes, which are then asked to do more or less all the jobs of the original anatomic masterpiece''. In recent years, it was discovered that lymphoid stromal cells are not merely passive architectural cells. Instead, these cells are endowed with immunoregulatory functions. Within lymphoid organs, various stromal cell subsets create dense threedimensional (3D) cellular networks that: (i) produce lymphocyte survival signals, (ii) generate 'roads' on which lymphocytes migrate, (iii) assemble a rigid backbone of fibers that transports the lymph throughout the LN and (iv) continuously provide the nutrients, soluble factors, antigens as well as the various immune cells required for 'immunological surveillance' and the development of adaptive immune responses [START_REF] Mueller | Stromal cell contributions to the homeostasis and functionality of the immune system[END_REF][START_REF] Koning | Interdependence of stromal and immune cells for lymph node function[END_REF][START_REF] Roozendaal | Stromal cell-immune cell interactions[END_REF] (Figure 1 and table 1). Thus, despite their relatively low abundance, lymphoid stromal cells are key regulators of the immune system. Without them, LNs would not exist and adaptive immunity would be highly compromised.

Therefore, understanding the immunobiology of these stromal cells is key to our full comprehension of the immune system. Unlike most organs, LNs are not rigid structures with a fixed size. Instead, they rapidly and transiently enlarge (up to 10 fold) during an immune response, a process that takes only a few days. This remodeling is crucial not only to meet the increased metabolic needs of the developing immune response, but also to generate new microenvironments mandatory for the proper maturation of this response (e.g germinal centers or medullary cords). This is quite a challenging accomplishment, particularly when considering that some LN stromal cells such as blood endothelial cells need to expand without compromising their sealed tubular structure.

Recent studies have sought to understand the cellular and molecular details of this remodeling. These reports have revealed an impressive level of complexity that regulates LN remodeling and subsequent return to homeostasis. Here, we highlight the work that helped shaping our current understanding of this transient remodeling as well as the recent technological improvements to visualize this process.

Function and remodeling of the main lymphoid stromal cell subsets

Fibroblastic Reticular Cells (FRCs)

FRCs are contractile myofibroblasts that form the major mesenchymal stromal cell network of the T cell zone. Through secretion of chemokines such as CCL21 and CCL19, they delineate the boundaries of the T cell zone and physically support lymphocyte migration into that zone [START_REF] Bajenoff | Stromal cell networks regulate lymphocyte entry, migration, and territoriality in lymph nodes[END_REF][START_REF] Katakai | Lymph node fibroblastic reticular cells construct the stromal reticulum via contact with lymphocytes[END_REF]. At steady state, FRCs secrete IL-7 and B-Cell Activating factor (BAFF), the main survival factors for T and B cells, respectively [START_REF] Cremasco | B cell homeostasis and follicle confines are governed by fibroblastic reticular cells[END_REF][START_REF] Link | Fibroblastic reticular cells in lymph nodes regulate the homeostasis of naive T cells[END_REF]. Sure enough, FRC network ablation results in marked alterations in LNs, with significant reduction in organ size, weight and cellularity [START_REF] Cremasco | B cell homeostasis and follicle confines are governed by fibroblastic reticular cells[END_REF][START_REF] Novkovic | Topological Small-World Organization of the Fibroblastic Reticular Cell Network Determines Lymph Node Functionality[END_REF]. FRCs produce and ensheat the conduit system, a network of tiny pipes that transport the lymph throughout the T cell zone [START_REF] Gretz | Cords, channels, corridors and conduits: critical architectural elements facilitating cell interactions in the lymph node cortex[END_REF][START_REF] Sixt | The conduit system transports soluble antigens from the afferent lymph to resident dendritic cells in the T cell area of the lymph node[END_REF]. FRCs are also able to induce peripheral tolerance through presentation of peripheral tissue-restricted antigens [START_REF] Fletcher | Lymph node fibroblastic reticular cells directly present peripheral tissue antigen under steady-state and inflammatory conditions[END_REF]. Upon inflammation, LNs rapidly enlarge to accommodate the massive influx of naive leukocytes. This initial swelling phase is triggered by the engagement of podoplanin expressed on FRCs with its ligand CLEC-2 present on migrating dendritic cells (DCs). Podoplanin signaling in FRCs induces their relaxation, hence decreasing the tension of the network and the concomitant swelling of the LN [START_REF] Acton | Dendritic cells control fibroblastic reticular network tension and lymph node expansion[END_REF][START_REF] Astarita | The CLEC-2-podoplanin axis controls the contractility of fibroblastic reticular cells and lymph node microarchitecture[END_REF]. This stretching phase is followed by a late phase of FRC expansion regulated by the engagement of lymphocyte-and DC-derived LIGHT and LTαβ (lymphotoxinαβ) on FRCs [START_REF] Benahmed | Multiple CD11c+ cells collaboratively express IL-1beta to modulate stromal vascular endothelial growth factor and lymph node vascular-stromal growth[END_REF][START_REF] Chyou | Fibroblast-type reticular stromal cells regulate the lymph node vasculature[END_REF][START_REF] Kumar | A dendritic-cell-stromal axis maintains immune responses in lymph nodes[END_REF]. Revealing an additional function of FRCs, it was shown more recently that FRCs regulate intestinal inflammation via their production of the cytokine IL-15 and its ability to control group 1 innate lymphoid cells (ILCs) in Peyer's patches and mesenteric LNs [START_REF] Gil-Cruz | Fibroblastic reticular cells regulate intestinal inflammation via IL-15mediated control of group 1 ILCs[END_REF].

Follicular Dendritic Cells (FDCs) and Marginal Reticular Cells (MRCs)

FDCs and MRCs are the main mesenchymal cell populations of primary B cell follicles. At steady state, FDCs occupy the center of the B cell follicles. FDCs extend multiple long centrifugal processes that secrete the B cell follicle homing chemokine CXCL13 and constitute a cellular scaffold for B cell migration [START_REF] Bajenoff | Stromal cell networks regulate lymphocyte entry, migration, and territoriality in lymph nodes[END_REF][START_REF] Allen | Follicular dendritic cell networks of primary follicles and germinal centers: phenotype and function[END_REF][START_REF] Cyster | Follicular stromal cells and lymphocyte homing to follicles[END_REF][START_REF] Wang | Follicular dendritic cells help establish follicle identity and promote B cell retention in germinal centers[END_REF]. MRCs are located in the outer follicle, just below the subcapsular sinus. They are thought to be the adult counterparts of the lymphoid tissue organizer (LTo) cells, but their exact functions remain elusive in quiescent LNs [START_REF] Katakai | Marginal reticular cells: a stromal subset directly descended from the lymphoid tissue organizer[END_REF]. During immune responses, FDCs act as antigen-presenting and -retaining cells that remodel the primary follicular network into germinal centers (GCs), a specialized structure in which B cells proliferate, undergo somatic hypermutation, and carry out class switching [START_REF] Allen | Germinal-center organization and cellular dynamics[END_REF][START_REF] Garin | Toll-like receptor 4 signaling by follicular dendritic cells is pivotal for germinal center onset and affinity maturation[END_REF][START_REF] Victora | Germinal centers[END_REF]. Recent reports indicate that the additional FDCs generated during GC formation can originate from both, perivascular mesenchymal cells and the differentiation of MRCs [START_REF] Jarjour | Fate mapping reveals origin and dynamics of lymph node follicular dendritic cells[END_REF][START_REF] Krautler | Follicular dendritic cells emerge from ubiquitous perivascular precursors[END_REF].

Blood Endothelial Cells (BECs)

The blood vasculature of the LN is composed of capillary blood endothelial cells (cBEC) and high endothelial venules (HEV). Capillaries are small blood vessels in charge of providing nutrients and oxygen to the surrounding cells while HEVs are the entry doors of blood lymphocytes into the LN parenchyma [START_REF] Anderson | Lymphocyte emigration from high endothelial venules in rat lymph nodes[END_REF][START_REF] Girard | High endothelial venules (HEVs): specialized endothelium for lymphocyte migration[END_REF][START_REF] Mionnet | Identification of a new stromal cell type involved in the regulation of inflamed B cell follicles[END_REF]. During an immune response, LN expansion relies on the transient remodeling of its vasculature [START_REF] Anderson | Microvascular changes in lymph nodes draining skin allografts[END_REF][START_REF] Kumar | Optical projection tomography reveals dynamics of HEV growth after immunization with protein plus CFA and features shared with HEVs in acute autoinflammatory lymphadenopathy[END_REF][START_REF] Webster | Regulation of lymph node vascular growth by dendritic cells[END_REF]. The remodeling of the LN vasculature is controlled by multiple cell types and is divided into sequential, overlapping phases. In the first days, the blood vasculature undergoes rapid proliferative growth that is initially dependent on IL-1β secreting CD11c + cells and their ability to stimulate vascular endothelial growth factor (VEGF) by the FRC network located in the T cell zone of the LN [START_REF] Benahmed | Multiple CD11c+ cells collaboratively express IL-1beta to modulate stromal vascular endothelial growth factor and lymph node vascular-stromal growth[END_REF][START_REF] Webster | Regulation of lymph node vascular growth by dendritic cells[END_REF]. This initiation phase is followed by a T cell-and B cell-dependent expansion phase and ends with the re-establishment of quiescence of the LN [START_REF] Dasoveanu | Regulation of Lymph Node Vascular-Stromal Compartment by Dendritic Cells[END_REF].

Lymphatic Endothelial Cells (LECs)

LECs assemble to form the afferent, efferent and cortical lymphatics of the LN. Afferent lymphatics convey tissue-derived lymph to the LN where they discharge their content into the subcapsular sinus. Cortical lymphatic sinuses located in the LN parenchyma constitute the exit doors for lymphocytes. They discharge their content into the efferent lymphatics situated in the medulla [START_REF] Drayson | Afferent lymph and lymph borne cells: their influence on lymph node function[END_REF][START_REF] Ohtani | Fluid and cellular pathways of rat lymph nodes in relation to lymphatic labyrinths and Aquaporin-1 expression[END_REF][START_REF] Young | The physiology of lymphocyte migration through the single lymph node in vivo[END_REF]. The primary function of lymphatics is to continuously project the immunological status of a peripheral tissue to its draining LN and to bring efferent LN cells back into the circulation. Occlusion of the afferent lymph flow to the LN severely decreases the ability of HEVs to recruit blood circulating lymphocytes, suggesting that an unknown lymphatic-derived signal is continuously delivered to the HEVs [START_REF] Mebius | The influence of afferent lymphatic vessel interruption on vascular addressin expression[END_REF]. Additional functions of LECs such as antigen presentation have been described [START_REF] Cohen | Lymph node-resident lymphatic endothelial cells mediate peripheral tolerance via Aire-independent direct antigen presentation[END_REF]. During an immune response, lymphatics expand to accommodate the growth of the LN in a process known as lymphangiogenesis. B lymphocytes orchestrate this expansion via secretion of VEGF-A that in return supports increased migration of DCs from the periphery to the LN [START_REF] Angeli | B cell-driven lymphangiogenesis in inflamed lymph nodes enhances dendritic cell mobilization[END_REF].

Studying LN stromal cells: a technical challenge

Stromal cells regulate the immune system on several levels. Yet, our understanding of their biology is rather limited. This limitation of knowledge largely results from technical challenges inherent to the isolation and the culture of LN stromal cells, the inability to model the complexity of LN organization in vitro and the paucity of animal models dedicated to their study. Stromal cells are attached to each other, forming interconnected 3D networks. The 3D nature of all stromal cell networks is key to their functional properties: BECs and LECs assemble in vessels while FDCs and FRCs form complex 3D meshworks. Stromal cell networks display a highly organized structure in which the density, the diameter, the length and the angles of the branches or vessels are precisely defined to perform their functions [START_REF] Novkovic | Topological Small-World Organization of the Fibroblastic Reticular Cell Network Determines Lymph Node Functionality[END_REF]. Mimicking this complex anatomy is currently impossible in vitro. In addition, stromal cells such as FRCs rapidly de-differentiate in culture and progressively lose their ability to produce chemokines. Therefore, we believe that the dynamics and behavior of stromal cells can only be fully understood from studying them in situ, in their natural micro-environment. To meet this aim, dedicated animal models are required. Stromal cell immunology is a recent field that does not have a large collection of mouse models comparable to the one that has been engineered to study T or B cell responses. Several strains of reporter mice expressing fluorescent reporters and/or Cre recombinase under the control of « stromal cell » promoters have been generated (Table 2). Unfortunately, however, most of these models are not specific and label multiple lymphoid stromal cell types and/or also mark hematopoietic cells. As an example, Lyve-1 Cre mice label LECs, but also a fraction of lymphocytes and myeloid cells while Complement Receptor-2 (CR2) Cre reporter mice label FDCs and B cells [START_REF] Jarjour | Fate mapping reveals origin and dynamics of lymph node follicular dendritic cells[END_REF][START_REF] Kraus | Survival of resting mature B lymphocytes depends on BCR signaling via the Igalpha/beta heterodimer[END_REF][START_REF] Pham | Lymphatic endothelial cell sphingosine kinase activity is required for lymphocyte egress and lymphatic patterning[END_REF]. Moreover, with rare exceptions, most of the Cre reporter mice used to study LN stromal cells also affect their counterparts in non-lymphoid organs, preventing the use of classical deletion tools such as the conditional Rosa 26-Diphteria Toxin Receptor (DTR) mouse (Table 2). These models have been critical in unravelling some of the most important functions of LN stromal cells. For example, the presence of FRCs in the T cell zone has been reported decades ago, but their in vivo function remained elusive since then [START_REF] Gretz | Cords, channels, corridors and conduits: critical architectural elements facilitating cell interactions in the lymph node cortex[END_REF][START_REF] Kelly | Functional anatomy of lymph nodes. I. The paracortical cords[END_REF]. In 2013, the group of B. Ludewig engineered a bacterial artificial chromosome (BAC)-transgenic mouse model that utilizes the Ccl19 promoter to target the Cre recombinase specifically to FRC in the LNs of adult mice [START_REF] Chai | Maturation of lymph node fibroblastic reticular cells from myofibroblastic precursors is critical for antiviral immunity[END_REF]. Taking advantage of this mouse, two groups generated Ccl19-Cre x Rosa26-diphtheria toxin receptor (DTR) mice for conditional ablation of FRCs in vivo. FRCs were rapidly and efficiently depleted in these mice upon diphtheria toxin administration. Depletion of FRCs in Ccl19-Cre x Rosa26-DTR mice appeared selective, as other stromal cell populations were spared. Using this model, FRC ablation markedly altered T cell homeostasis and compartmentalization, causing profound defects in the activation, migration, expansion and effector function of viral antigen-specific T cells [START_REF] Cremasco | B cell homeostasis and follicle confines are governed by fibroblastic reticular cells[END_REF][START_REF] Novkovic | Topological Small-World Organization of the Fibroblastic Reticular Cell Network Determines Lymph Node Functionality[END_REF]. To further complicate matters, LEC and BEC derive from a common ancestor [START_REF] Srinivasan | Lineage tracing demonstrates the venous origin of the mammalian lymphatic vasculature[END_REF], as do all mesenchymal LN stromal cells [START_REF] Katakai | Marginal reticular cells: a stromal subset directly descended from the lymphoid tissue organizer[END_REF].

Therefore, reporter mice that express Cre recombinase in these precursors also label their progeny, precluding specificity of targeting. While this does not represent a key issue for imaging studies, it does induce putative caveats when these mice are used to conditionally delete « floxed » genes to assess their functions in LN development or remodeling. Conditional Cre expressing lines such as Cre ERT2 or Tet on/off models partially overcome some issues related to constitutive Cre expressing lines by allowing a temporal activation of Cre in a given subset of stromal cells upon injection of Tamoxifen or Doxycycline.

Stromal cell heterogeneity: understanding the LN stroma at the single cell level

As summarized above, FDCs, FRCs, MRCs, LECs and BECs are considered the major LN stromal cell populations. Nonetheless, additional subsets have been described, including CXCL12producing follicular stromal cells, integrin α7-expressing pericytes and Versatile stromal cells (VSCs) [START_REF] Mionnet | Identification of a new stromal cell type involved in the regulation of inflamed B cell follicles[END_REF][START_REF] Bannard | Germinal center centroblasts transition to a centrocyte phenotype according to a timed program and depend on the dark zone for effective selection[END_REF][START_REF] Malhotra | Transcriptional profiling of stroma from inflamed and resting lymph nodes defines immunological hallmarks[END_REF] (Table 1 and2). It is currently unknown if all these lymphoid stromal cell subsets represent true distinct populations or different anatomical flavors of a single mesenchymal stromal cell. Despite having provided critical insights into their biology, most past studies have been restricted to the analysis of stromal cells at the population level. Thus, we critically lack information on the behaviors of individual stromal cells. Why is this important? During an infection, CD4 T cells originating from a single clone differentiate into several subsets (TFh, Treg, Th17, Th1…) that collectively mount a protective immune response [START_REF] Dong | Helper T-cell heterogeneity: a complex developmental issue in the immune system[END_REF]. We currently do not know if stromal cells display a similar heterogeneity within their subsets. Flow cytometry represents an appealing technique to analyze the phenotype and proliferative history of single cells. While the isolation of LN stromal cell populations based on surface markers and/or transgene expression is routinely performed, it should be mentioned that stromal cells represent the most difficult cell types to extract from LNs. As a result, their recovery yields are ranging from good (LEC and BEC) to poor (FRC) and even extremely poor (MRC, FDC) [START_REF] Jarjour | Fate mapping reveals origin and dynamics of lymph node follicular dendritic cells[END_REF][START_REF] Fletcher | Reproducible isolation of lymph node stromal cells reveals site-dependent differences in fibroblastic reticular cells[END_REF][START_REF] Usui | Isolation and characterization of naive follicular dendritic cells[END_REF]. This technical caveat should be kept in mind when extrapolating the results obtained from such low cell numbers to the entire population of a given stromal cell type. Moreover, flow cytometry experiments using BrdU and EdU incorporation measurements are classically employed to monitor the proliferative history of stromal cells [START_REF] Gratzner | Monoclonal antibody to 5-bromo-and 5-iododeoxyuridine: A new reagent for detection of DNA replication[END_REF][START_REF] Salic | A chemical method for fast and sensitive detection of DNA synthesis in vivo[END_REF]. However, this approach fails to differentiate a cell that has divided once from a single cell that has divided e.g. twenty times. In summary, analyzing stromal cells at the population levels using flow cytometry bears inherent limitations that might prevent the community from (a) identifying putative proliferative stem cells, (b) unravelling precursor-product relationships amongst stromal subsets and (c) gathering critical anatomical details that would help explaining the process of interest.

Inspiration from neurosciences: multicolor lineage tracing models

Unlike most immunologists who work on cells that can be adoptively transferred or replaced by bone marrow grafting, neurobiologists face the same basic challenges as immunologists studying lymphoid stromal cells: neurons assemble in various, complex and intermingled 3D networks. It is impossible to graft, remove or replace these networks in vivo. Neuroscientists had thus no choice but to generate new models to study neurons in their natural, complex 3D environment in vivo. The recent development of multicolor fate mapping systems based on the Brainbow approach has improved the existing lineage tracing systems and created new tools to study cell dynamics in situ [START_REF] Ghigo | Multicolor fate mapping of Langerhans cell homeostasis[END_REF][START_REF] Livet | Transgenic strategies for combinatorial expression of fluorescent proteins in the nervous system[END_REF][START_REF] Snippert | Intestinal crypt homeostasis results from neutral competition between symmetrically dividing Lgr5 stem cells[END_REF]. The Brainbow strategy enables combinatorial expression of three or four fluorescent proteins in a stochastic manner. Using incompatible lox variants, these fluorescent proteins (FPs) can be expressed by stochastic recombination using Cre-mediated inversion (Figure 2). When three transgenes of a Brainbow construct expressing three (Brainbow-1.0) or four (Brainbow-2.1) "FPs" are introduced into a mouse, independent recombination of those transgene copies can generate six or ten distinct color combinations. The use of multiple colors within one cell population allows for a shift in the types of questions that can be asked using standard reporter models. Labeling strategies often use a given promoter to drive one-color expression for all members of that particular cell type, which distinguishes that cell type from others. While this strategy is ideal to investigate the behavior of cells at the population level, it cannot reveal the behavior of single cells within that very population. The Brainbow approach distinguishes amonglike cells and is ideal for following individual cells over time and space. As the Brainbow colors are inheritable, an initial pool of progenitor cells that is labeled in specific colors produces labeled progeny that reflect their cellular lineage, hence allowing the establishment of parentage relationship between different cell types.

Multicolor lineage tracing models to study stromal cells

Far from being fancy tools, Brainbow models have allowed seminal discoveries in the fields of developmental, cancer and stem cell biology in several species (zebrafish, drosophila and mouse) [START_REF] Ghigo | Multicolor fate mapping of Langerhans cell homeostasis[END_REF][START_REF] Livet | Transgenic strategies for combinatorial expression of fluorescent proteins in the nervous system[END_REF][START_REF] Snippert | Intestinal crypt homeostasis results from neutral competition between symmetrically dividing Lgr5 stem cells[END_REF][START_REF] Hampel | Drosophila Brainbow: a recombinase-based fluorescence labeling technique to subdivide neural expression patterns[END_REF]. How about immunology? Brainbow models are retrospective tools that allow the reconstruction of the proliferative and migratory history of an individual cell and its progeny by measuring the color, location and size of clones at a given time. By definition, this system only applies to cell types in which the progeny of a labeled cell does not further migrate (Figure 3). In summary, Brainbow models are not adapted to study motile lymphocytes but very well suited to investigate the dynamics of lymphoid stromal cells both during the development of LNs and their inflammation induced remodeling. Using this approach, two studies investigated the dynamics of stromal cells during an immune response. In the first one, the ontogeny and dynamics of murine LN FDCs were studied.

Because FDCs are very difficult to extract from the LNs of untreated animals, this work combined the Brainbow approach with multiple Cre lines to study FDCs in situ [START_REF] Jarjour | Fate mapping reveals origin and dynamics of lymph node follicular dendritic cells[END_REF]. By inducing Cre recombination during development or at steady state, this work revealed that LN FDC networks arise from the clonal expansion and differentiation of MRCs. This study also showed that during an immune response, neither the recruitment of circulating progenitors nor the division of local mature FDCs significantly contributes to the accumulation of FDCs in GCs.

Rather, the evidence suggested that newly generated FDCs also arise from the proliferation and differentiation of MRCs, thus unraveling a first critical function of this poorly defined stromal cell population.

In a more recent study, the behavior of BECs during LN expansion and subsequent return to homeostasis was tracked using such multicolor fluorescent fate mapping models [START_REF] Mondor | Clonal Proliferation and Stochastic Pruning Orchestrate Lymph Node Vasculature Remodeling[END_REF]. Because conventional tissue sections are too thin to unravel the complexity of vasculature trees, a novel technique for obtaining thick, but optically transparent LN tissue samples was developed, enabling high-resolution imaging and reconstruction of the LN vascular tree with high resolution. Applying this technique, it was reported that LN vasculature expansion relies on the sequential assembly of endothelial cell proliferative units. This segmented growth seemed to be sustained by the clonal proliferation of HEV cells that behaved as local progenitors to create capillaries and HEV neovessels at the periphery of the LN. This work also suggested that the return to homeostasis was accompanied by the stochastic death of pre-existing and neosynthesized LN endothelial cells. Thus, as for the fields of neurosciences, development and stem cells, multicolor fate-mapping studies emerge as promising tools to decipher the complex dynamics of stromal cells.

Limitations and Future directions

Better mouse models

Stromal cell immunobiology is a relatively young field that heavily relies on animal models.

Paradoxically, however, suitable models are critically lacking. As an example, specific genetic deletion or fate mapping of lymphoid stromal cell subsets is currently impossible in the mouse (Table 2). How can we improve that? Precisely defining the roles of specific cell types is a challenging task within an entire organism. To this aim, biologists have engineered an important repository of genetically-encoded mouse models in which a reporter gene is inserted under the control of a given promoter. However, targeting these tools with adequate specificity remains challenging: most cell types are best defined by the intersection of two or more genetic features such as active promoter elements. Thus, a key challenge of broad significance is to increase the specificity of cell-type targeting. To target immune cells more specifically, several groups have combined two genes; neither of which alone were specific for the cell types of interest. As an example, transgenic mice that carry a BAC encoding a DTR-mCherry fusion protein (DTR-mCherry) preceded by a loxP-flanked transcriptional Stop element under the control of the Csf1r promoter (Csf1r LsL-DTR mice) were generated and crossed with mice that express Cre recombinase under the control of LysM (Lysm Cre mice).

LysM-expressing cells in Lysm Cre x Csf1r LsL-DTR mice delete the Stop element, which permits transcription of DTR-mCherry specifically in LysM and Csf1r double-positive cells (i.e. macrophages and monocytes), but not in conventional DCs [START_REF] Schreiber | Intestinal monocytes and macrophages are required for T cell polarization in response to Citrobacter rodentium[END_REF]. To further improve the precision of selective cell targeting, several alternative, complimentary approaches were developed by the neuroscience field. These Intersectional methods are based on two to three genes or other cell features and exploit distinct recombinases [START_REF] Dymecki | Mapping cell fate and function using recombinase-based intersectional strategies[END_REF][START_REF] Fenno | Targeting cells with single vectors using multiple-feature Boolean logic[END_REF][START_REF] Madisen | Transgenic mice for intersectional targeting of neural sensors and effectors with high specificity and performance[END_REF]. As an example, intersection of Cre and Flp (Flippase) lines driven by two marker genes target more restricted GABAergic subpopulations [START_REF] He | Strategies and Tools for Combinatorial Targeting of GABAergic Neurons in Mouse Cerebral Cortex[END_REF]. We believe that these strategies could be used to achieve better targeting and deletion of LN stromal cell subsets in which single genes are routinely shared by many cell types.

Better imaging tools

Although such improved mouse models would allow for more selective targeting ofthe LN stroma, they remain inherently difficult to analyze. As stromal cells associate in large 3D networks, improving imaging techniques to visualize stromal cell networks in situ is also key to the field. Conventional confocal/fluorescence imaging studies achieve a cellular resolution when imaging 8-30µm thick tissue sections. However, these samples are too thin to visualize the complex 3D stromal cell networks and obtain full appreciation of their organization.

Macroscopic imaging techniques such as Optical Projection Tomography (OPT) allow the reconstruction of the vascular tree but lack the resolution to image its individual cellular components [START_REF] Kumar | Optical projection tomography reveals dynamics of HEV growth after immunization with protein plus CFA and features shared with HEVs in acute autoinflammatory lymphadenopathy[END_REF]. Light sheet fluorescence microscopy (LSFM) functions as a non-destructive microtome and microscope that uses a plane of light to optically section and view whole tissues. This method is well suited for imaging deep within transparent tissues or within whole living organisms. However, LSFM currently lacks the submicron resolution of confocal microscopy and is therefore not very well suited to examine the fine details of highly dendritic stromal cell networks such as FRCs or FDCs [START_REF] Santi | Light sheet fluorescence microscopy: a review[END_REF]. Why is it so important to reconstruct an entire LN when studying LN stromal cells? Ontogenic studies of LN development and multicolor fluorescent lineage tracing studies suggest that all the LN mesenchymal cell subsets derive from a pool of LTo cells. According to this model, few LTo cells extensively divide to generate the entire mesenchymal network of the LN. Evaluating the extent of this proliferation, the location and the competition of the various clones are key to our understanding of LN development. Similar reasoning applies to the LN remodeling that occurs after an infection. As the extensive proliferation of few cells can in principle generate gigantic clonal populations, only the reconstruction of an entire LN bears the potential to reveal the « global picture » of these two phenomena.

The scattering of light in heterogeneous tissues remained a limiting factor, preventing researchers from achieving high-resolution 3D renderings of thick tissue. The source of the scattering is a diverse set of cellular constituents including ribosomes, nuclei, lipid droplets, and components of the cytoskeleton and extracellular matrix. Recently, several procedures have been developed to obtain optically transparent tissue samples for imaging, which, importantly, are also compatible with imaging endogenous fluorescent proteins [START_REF] Chung | CLARITY for mapping the nervous system[END_REF][START_REF] Dodt | Ultramicroscopy: three-dimensional visualization of neuronal networks in the whole mouse brain[END_REF][START_REF] Erturk | Three-dimensional imaging of solvent-cleared organs using 3DISCO[END_REF][START_REF] Hama | Scale: a chemical approach for fluorescence imaging and reconstruction of transparent mouse brain[END_REF][START_REF] Susaki | Whole-brain imaging with single-cell resolution using chemical cocktails and computational analysis[END_REF].

Together with advances in data acquisition and storage capacity, these improved clearing techniques become increasingly used to gain anatomical details of fundamental biological processes. However, these approaches are time-and resources-consuming: imaging an entire LN typically requires several hours, and so does the post-acquisition treatment on powerful custom-made work stations equipped with expensive imaging software. It is to be hoped that better clearing techniques, faster imaging devices and more affordable software solutions will contribute to the democratization of this approach in the near future.

Concluding remarks

Our knowledge on the origin and function of LN stromal cells has tremendously increased in recent years. However, we still lack a comprehensive view of the stromal cell dynamics that accompany and sustain LN growth during an immune response. A central and still unresolved question concerns the existence of an adult LN mesenchymal stromal cell progenitor. Similar to embryonic LTo during development, such a putative progenitor would extensively divide in the course of an immune response to fuel the pool of mesenchymal LN stromal cells. MRC have been suggested as candidate adult LN mesenchymal stem cells, but dedicated animal models to test this hypothesis are currently lacking [START_REF] Katakai | Marginal reticular cells: a stromal subset directly descended from the lymphoid tissue organizer[END_REF]. Intriguingly, a growing body of evidence suggests that pericytes can act as mesenchymal stem cells in various tissues [START_REF] Da Silva Meirelles | Mesenchymal stem cells and their relationship to pericytes[END_REF]. As a result, pericytes might represent a source of mesenchymal cells in inflamed LNs. In a recent study, Prados and colleagues described a transgenic mouse strain that expresses Crerecombinase under the CollagenVI promoter (ColVI-Cre mouse) [START_REF] Prados | CollagenVI-Cre mice: A new tool to target stromal cells in secondary lymphoid organs[END_REF]. In this mouse, pericytes, but not other mesenchymal stromal cells were targeted in all the secondary lymphoid organs (SLO) in the naïve state, suggesting that pericytes do not give rise to other LN stromal cell subsets at steady state. Whether additional mesenchymal LN stromal cells are labeled in the LNs of these mice upon inflammation, however, remains to be determined.

As all LN stromal cell subsets are assembled in complex 3D structures, merely increasing the number of LN stromal cells is not sufficient to enable the enlargement of the LN during an immune response. Topological studies have described the complex organization of the conduit system and its surrounding FRC-network [START_REF] Katakai | Lymph node fibroblastic reticular cells construct the stromal reticulum via contact with lymphocytes[END_REF][START_REF] Novkovic | Topological Small-World Organization of the Fibroblastic Reticular Cell Network Determines Lymph Node Functionality[END_REF][START_REF] Gretz | Cords, channels, corridors and conduits: critical architectural elements facilitating cell interactions in the lymph node cortex[END_REF][START_REF] Sixt | The conduit system transports soluble antigens from the afferent lymph to resident dendritic cells in the T cell area of the lymph node[END_REF][START_REF] Katakai | A novel reticular stromal structure in lymph node cortex: an immuno-platform for interactions among dendritic cells, T cells and B cells[END_REF]. FRCs have precisely defined intercellular distances and number of connected protrusions per cell, allowing the network to function as a cellular « sponge » that creates extracellular spaces for lymphocytes, while offering adhesive migration substrates for them. When 70% of the FRC network is genetically ablated, T cell migration and proliferation is affected [START_REF] Novkovic | Topological Small-World Organization of the Fibroblastic Reticular Cell Network Determines Lymph Node Functionality[END_REF]. These data suggest that the physical properties of this topological 'small-world ' organization are key to its function and that maintaining the precise dimensions of the FRC network is mandatory for a proper immune response. Conduits made by the FRC network create the 3D backbone of the LN while conveying the lymph throughout the T cell zone. FRCs ensheath them in a way that most of the conduits are shielded from the lymphoid and myeloid cells situated in the surrounding space. During an immune response, FRCs divide and produce new conduits to sustain the growth of the LN [START_REF] Katakai | Lymph node fibroblastic reticular cells construct the stromal reticulum via contact with lymphocytes[END_REF]. Interestingly, the additional FRCs and their associated conduits are added to the existing network in a fractal way (our unpublished results). Identifying the molecular, cellular and physical mechanisms that orchestrate this highly organized remodeling represents an important question, not only for the FRC network but also for other lymphoid stromal subsets such as LECs and BECs, whose biological functions are tightly linked to their physical properties. We believe that a combination of flow cytometry, high resolution imaging approaches, improved lineage tracing models, mathematical modeling and genetic manipulation will be required to understand the complex stromal dynamics that accompany the enlargement of LNs during immune responses. (nuclear GFP/YFP and RFP/CFP) are placed head to head. This construct can be excised and inverted as long as Cre is active. When it stabilizes, the fluorescent protein encoding gene ending in a sense orientation is expressed. Note that if a cell constitutively expresses Cre in Brainbow-2.1 mice, it will keep changing its color for its entire lifespan. This precludes the use of Brainbow-2.1 mice for genetic fate mapping purposes. On the contrary, an individual Cre expressing cell will acquire a single color for its entire lifespan in Brainbow-1.0 mice. As each Brainbow copy behaves independently from the others, the presence of multiple copies yields additional color combinations (here, two copies of Brainbow-1.0 resulting in six possible outcomes). In (A), Ag-specific T cells divide and then resume their migratory behavior, preventing their color-based tracking. In (B) and (C), FRCs and BECs proliferate. As they are immotile, their progeny generates monocolored foci (F) of various sizes, providing quantitative and qualitative anatomical details of this phenomenon [START_REF] Mondor | Clonal Proliferation and Stochastic Pruning Orchestrate Lymph Node Vasculature Remodeling[END_REF].

Figure 1 :

 1 Figure 1 : Anatomical distribution of the main lymph node stromal cell subsets.

Figure 2 :

 2 Figure 2: Principle of Brainbow strategies.

Figure 3 :

 3 Figure 3: Multicolor lineage tracing to study lymphoid stromal cells in vivo.

Figure 3

 3 Figure 3

Acknowledgments

This work was supported by a grant from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program grant agreement N° 647384-STROMA.

Trends Box

Lymphoid stromal cells are more than architectural cells: they are pivotal regulators of adaptive immunity.

While we begin to understand the functions of lymphoid stromal cells at the population level, we critically lack information on the heterogeneity of individual stromal cells.

Stromal cells are difficult to study: animal models are rare and flow cytometry approaches are limited.

Neuroscientists face similar technical limitations and have developed tools to decipher and manipulate the neuronal network: let them be an inspiration to us.

Outstanding Questions Box

During an immune response, stromal cells divide and remodel to accompany LN growth. Are all stromal cells able to divide equally or do equivalents to embryonic LTo exist as quiescent precursors in the adult?

An increasing number of lymphoid mesenchymal subsets is being identified. Are all these stromal cells truly different populations or do they represent subtle adaptations of a single mesenchymal cell type to distinct LN microenvironments?

Which mechanisms drive re-establishment of LN stromal cell quiescence at the end of an immune response?

Upon return to LN quiescence, superfluous stromal cells need to be deleted. Is this pruning stochastic or selective?