Jesus Gonzalez-Feliu
email: jesus.gonzales-feliu@let.ish-lyon.cnrs.fr

The N-echelon Location routing problem: concepts and methods for tactical and operational planning

Keywords: location-routing problems, multi-echelon distribution, cross-docking, combinatorial optimization, literature review

Freight transportation constitutes one of the main activities that influences economy and society, as it assures a vital link between suppliers and customers and is represents a major source of employment. Multi-echelon distribution is one of the most common strategies adopted by the transportation companies in an aim of cots reduction. Although vehicle routing problems are very common in operational research, they are essentially related to single-echelon cases. This paper presents the main concepts of multi-echelon distribution with crossdocks and a unified notation for the N-echelon location routing problem. A literature review is also presented, in order to list the main problems and methods that can be helpful for scientists and transportation practitioners.

Introduction

The freight transportation sector is continuously changing as a consequence of the growth and transformation of the economic activity. In recent years companies have changed their inventory and distribution strategies for better adapting them to the changing demand. Moreover, the new advances in technology have been a positive factor for the development of new markets and new consumer needs. In freight distribution three main shipping strategies are predominant. Direct shipping consists on delivering freight directly from the origin to the destination. Multi-echelon distribution with warehousing is the technical name given to systems made by one or more factories, a number of storage areas, known as warehouses, and the final destination of freight. Freight requests are made to warehouses, which have a stock of freight. These warehouses command freight in big quantities to factories. Multi-echelon transportation with cross-docking differs from the warehousing strategy in the fact that cross-docking platforms don't have the possibility to stock, but consent the consolidation and transshipment operations, and the commands are made directly to the origin of the freight, which is in general a factory or a warehouse. This work deals with multi-echelon distribution with cross-docking. We can find several examples of such systems [START_REF] Gonzalez-Feliu | Models and methods for the City Logistics : The Two-Echelon Vehicle Routing Problem[END_REF]:

 The press distribution sector usually has a transportation network where the products are distributed to the stores through a system of consolidation platforms, in which they are re-packaged to be sent to the corresponding retailer.  Logistic systems for urban freight distribution have also evolved into multi-echelon systems with consolidation platforms, called Urban Consolidation Centers (UCC). They are located in the periphery of the urban area and receive the freight entering the city to transship it into low-pollution vehicles that have access to the city centers.  Multimodal transportation, specifically the containerized distribution, is a classical example of a multi-echelon system with cross-docking where freight is conserved unaltered from its departure to the arrival at its final destination.  Grocery distribution is a field which presents an heterogeneous group of supply chains. The fresh food and daily products ones follow a  The home delivery services and e-commerce trends seem be close to such systems to improve the service quality and decrease operational costs, more precisely with the development of intermediary reception points.

Although multi-echelon transportation systems are very common in real cases, they are usually decomposed into an addition of single-echelon distribution cases. Moreover, most of the optimization tools used for tactical and operational planning derive from methods for the vehicle routing problem (VRP). This family of problems has been deeply studied, but refers essentially to single-echelon systems (for detailed surveys, see [START_REF] Toth | The vehicle routing problem[END_REF][START_REF] Toth | The vehicle routing problem[END_REF][START_REF] Golden | Vehicle routing: Latest advances and challenges[END_REF] In current planning practices, transportation cost optimization for a Nechelon system is usually made by splitting the system into N single-echelon problems then optimizing them, but some authors have started to analyze the advantages of considering the global costs of the system in the optimization process [START_REF] Crainic | City Logistics[END_REF] and several studies that deal with multi-echelon distribution optimization using global vehicle routing based approaches are found in literature. However, it is still to find and compare these optimization methods because each field uses a different notation. These problems derive from the hypothesized but not explicitly defined N-echelon location routing problem (NE-LRP).

The aim of this paper is to formalize the NE-LRP providing a unified notation as well as a generic formulation that englobes the main variants found in the scientific literature. In section 2, the notation and a set partitioning model are presented and discussed. Then, in order to illustrate and classify the main variants found in literature, we propose a synthetic review of NE-LRP related problems. Section 3 presents the main LRP-based approaches, and section 4 proposes other related problems which derive from other distribution problems, such as arc routing, location distribution and pick-up and delivery approaches. Main guidelines on further researches based on the literature review will also be enounced.

The NE-LRP: concepts and general formulation

Consider a N-echelon distribution system composed by N stages. To represent it into a graph G we define three types of nodes: depots, e-satellites and customers. The depots are defined as the starting points of the distribution. We define as e-satellite an intermediary facility associated to the stage e. At an e-satellite, the freight is transhipped and no inventory and warehousing activities are allowed. The customers are defined as the final destinations of the freight (in many real applications they are the stores or retailers, but also households in some home-delivery services). We use this definition analogously to vehicle routing optimization. The customers constitute the set of N-nodes on the graph. The overall transportation network can then be decomposed into N echelons:

 the 1st echelon, which connects the depots to the 1 st -echelon intermediary facilities;  N -2 intermediate echelons interconnecting the different intermediary facilities;  the N th echelon, where the freight is delivered from the (N-1) th echelon intermediary facilities to the final destinations.

To deliver the freight, a number of vehicle fleets are defined. Each echelon e usually has its own fleet of vehicles, defined by different characteristics (capacity, dimensions, speed), and can be heterogeneous or homogeneous. An e-echelon vehicle is a vehicle belonging to echelon e, i.e. travelling from an e-1-satellite to an e-satellite.

The depots will be represented by the set

  0 0 0 1 0 ..., , n s s V 
(the depots will be also known as 0-satellites) and the customers by the set

  n c c c V ..., , 1 
. For each echelon e the set of esatellites will be denoted by

 

e ne e e s s s V ..., , 1



. The e-satellites can be capacitated and this capacity can be noted as the maximum number e k ms of e+1 th echelon vehicles allowed to receive freight at the e-satellite e k s . Moreover, each customer i has associated a demand d i to be delivered. The demand of each customer can not be split among different vehicles only for the N th echelon. For the other stages, we consider that each e-satellite can be served by more than one e th echelon vehicle, so the aggregated freight assigned to each e-satellite can be split into two or more vehicles. Each e th echelon vehicle can serve more than one e-satellite in the same route, and it is considered that each e-satellite can be served by any number of e th echelon vehicles, or by none. The model presented below is mono-commodity, i.e. the volumes of freight belonging to different customers can be stored together and loaded in the same vehicle at all echelons. Moreover, each e th echelon vehicle has the same capacity K e .

We define as e th echelon route ie k y a Hamiltonian circuit made by a e th echelon vehicle which starts from e-1-satellite k, serves one or more e-satellites and ends at the departure node. The main question when modelling NE-LRP is how to connect the different echelons and to manage the dependence of each e th echelon from its predecessor. We present a Mixed Integer Programming Model for a generic NE-LRP. The presented formulation is based in setpartitioning problems, and three types of variables are used. The first type of variables are the route variables ie k y , a {0, 1} variable that shows if the route ie k y starting at e-1-satellite i is used or not. The model is defined as follows:  

Each route ie

Depot 1-satellite i-satellite N-satellite 1-route N-routes                 N e V
e ie k V h V k ie hk R i N e y e s e s            ; ..., , 1 1 1 1  (2)   e s V k R i ie k ie hk e h e h V h N e y l m e s e           ; ..., , 1 . 1  (3) e s V c c k V k d D c      0 (4)   N e D D e s e s V k e k V h e h ..., , 1 1 1          (5)   e s V k R i ie h ie kh e h V h N e y D e s e              ; ..., , 1 1 1 1 1  (6)   e s V k R i ie k ie hk e h V h N e y D e s e           ; ..., , 1 1  (7)           N e V k l N e V k D N e V k R i y e s e k e s e k e s e ie k ..., , 1 , 1 , 0 ..., , 1 , ..., , 1 , , 1 , 0 1 1 1 1                        (8)
The objective function to minimize (1) is the total cost resulting on the addition of transportation costs and the satellite's activation to those derived from the different operations at the satellite. Constraints (2) show that each customer is served by only one route. In case of customers having a demand that exceeds the capacities of the N-vehicles, they will be represented as a number of customers receiving full vehicles, plus one, receiving the remaining load. Constraints (3) show the limitation capacity of each satellite, and constraint (4) and ( 5) assures the demand's conservation, i.e. the overall load transported by all the vehicles of each echelon is the same as the overall customers' demand. Finally, constraints ( 6) and ( 7) assure the link between (e-1)-routes and e-routes. The nature of the decision variables is formulated in (8).

The problem is easily seen to be NP-Hard via a reduction to VRP, which is a special case of NE-LRP arising when just one echelon and one satellite (with no travel cost from the depot to the satellite) is considered.

According to the definition of NE-LRP, if the assignments between customers and satellites are determined, the problem reduces to VRP (1 for the first echelon and n se for each e th echelon, where n se is the number of e-satellites having freight allocated).

In literature, multi-echelon LRP solved by MIP resolution using a linear programming solver show the complexity of this family of combinatorial optimization problems: only instances with less than 30 customers [START_REF] Ambrosino | Distribution network design: new problems and related models[END_REF][START_REF] Gonzalez-Feliu | The two-echelon capacitated vehicle routing problem[END_REF] are solved to optimality. If a classical VRP is difficult to solve, a NE-LRP adds the difficulties and complexity related to the number of echelons and the necessity of find complementary routes to assure the connexion between two echelons of the entire system. In next section, the main methods for NE-LRP variants are reviewed, focusing on heuristics, which are in a more advanced state than exact methods.

NE-LRP variants and solving methods : a review of the scientific literature

We can find in literature different families of problems, which are very similar and can be considered as different variants of the NE-LRP. This problem is defined as the generalization to N-echelon distribution systems of classical LRP, and was firtsly introduced by Jacobsen and Madsen (1980) for a real decision problem for a two-echelon distribution system. [START_REF] Laporte | Location-routing problems[END_REF] hypothesized the NE-LRP in a general study of possible LRP variants.

The 2E-LRP [START_REF] Jacobsen | A comparative study of heuristics for a two-level routinglocation problem[END_REF] consists of determining the location of the satellites, allocating the customers to the best satellites and determining both fist-echelon and second-echelon routes. The authors propose three fast heuristics for solving a real case application where two newspaper editors combine their resources in terms of printing and distribution in order to decrease the overall costs. The authors propose three fast heuristics.

The first is the Three Tour Heuristic, which is based on the observation that if the last arc of each route, the problem becomes similar to a Steiner Tree Problem. This tree is constructed by a greedy one-arc-at-a-time procedure. The other two heuristics, which are sequential, combine heuristics for both VRP and Location-Allocation problem. The ALA-SAV heuristic is a three stage procedure composed from the Alternate Location Allocation (ALA) of Rapp and Cooper (1962) and the Savings algorithm (SAV) of [START_REF] Clarke | Scheduling of vehicles from a central depot to a number of delivery points[END_REF]. The third heuristic (SAV-DROP) is also a three stage procedure composed from the Clarke and Wright Savings algorithm and the DROP method of Feldman et al. (1966).

A NE-LRP variant that presents several simplifications respect to classical NE-LRP is the Nechelon Capacitated VRP (NE-CVRP). In this family of problems only one depot is considered and the intermediary facilities allow a limited number of vehicles for transshipments [START_REF] Gonzalez-Feliu | Models and methods for the City Logistics : The Two-Echelon Vehicle Routing Problem[END_REF]. The satellites do not present location costs and constraints but only allocation costs and capacity limitations related to the number of vehicles that can host. [START_REF] Gonzalez-Feliu | The two-echelon capacitated vehicle routing problem[END_REF] presented a first MIP formulation for the 2E-CVRP derived from multi-commodity network design to study the limits and the general behavior of the mathematical model. The model is tested on four sets of instances using Xpress linear programming solver. The instances, available at OR Library website [START_REF] Beasley | Or-library: distributing test problems by electronic mail[END_REF], cover several two-echelon distribution cases of different sizes (from 12 to 50 customers and 2 to 5 satellites). Optimal solutions are found for instances up to 21 customers and lower bounds are presented for all the instances. The authors also introduce some cuts which make the calculation time decrease. More lower bounds for this problem are proposed by [START_REF] Mancini | A branch-and-bound for the Two-Echelon Vehicle Routing Problem[END_REF]. First, the authors split the problem into two simpler sub-problems, one for each level; then, in a second phase, a global lower bound is computed by addition of the sub-problems costs without considering the interactions between both levels. [START_REF] Crainic | City Logistics[END_REF] proposed a two-phase heuristic algorithm based on a clustering first routing second procedure plus a classical local search procedure. This heuristic has been used to make a satellite location analysis in order to built instances up to 250 customers (Crainic et al., 2009a), providing also a first sub-optimal solution as a reference for further methods for the 2E-CVRP. [START_REF] Perboli | The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics[END_REF] propose another heuristic method. Starting from an improved version of the flow formulation [START_REF] Gonzalez-Feliu | The two-echelon capacitated vehicle routing problem[END_REF], the authors solve both a continuous and semi-continuous relaxation of the model in order to fix the assignment variables, then, when all customers are assigned to satellites, a maximum of n s CVRP are solved in order to obtain a quick sub-optimal solution. Crainic et al. (2009b) developed a theoretical route optimization methodology for the twoechelon freight distribution system in congested urban areas defined in [START_REF] Crainic | Advanced freight transportation systems for congested urban areas[END_REF].

The methodology is a support for day-before planning operations in a system where satellites are used as intermediate transshipment points for the freight distribution, and the synchronization between the vehicles of both echelons is one of the most constraining aspects of this problem. Two classes of models are proposed: a service network design model for the 1 st -echeon vehicles, which approximates the second echelon routing costs gives a first estimation of the overall costs; then a second model optimizes the 2 nd -echelon trip costs considering the first-echelon vehicle movements.

The road-train routing problem, also known as truck-and-trailer routing problem (TTRP), concerns defining a route for a road-train, which is a vehicle composed by a truck and a trailer (both with space for freight loading). Some of the roads are not accessible by the entire convoy, but only by the truck. In these cases, the trailer is detached and left at a customer's location (called a "root") while the truck visits a subset of customers, returning to pickup the trailer. The difference from the basic 2E-LRP variant is that is that in this case some customers can be served directly a 1-route. The first studies related to the TTRP were developed in the agricultural field, in order to optimize the milk collection operations, and were presented as applied solving methods for a real situation. The milk is collected at storage tanks on the farmyards every or every other day and must be transported to dairy plants. Some of the farmyards cannot be visited by a lorry-trailer combination because of space restrictions. [START_REF] Wren | Computers in Transport Planning and Operations[END_REF] and [START_REF] Brunswicker | Optimale Standort-und Tourenplanung fur die Rohmilcherfassung eines Molkereibetriebes Lit[END_REF] allow only one transshipment location per trailer and a fixed lorry-trailer assignment. In both cases, a 3-stage heuristic procedure is presented. In the first phase (clustering), customers are grouped considering the number of vehicles and their characteristics (mostly the capacity of each lorry-trailer convoy). The second phase (allocation) consist in determining, for each convoy, one transshipment location. The third and last stage is the routing phase. [START_REF] Semet | Solving real-life vehicle routing problems efficiently using tabu search[END_REF] formulate the TTRP as a Mixed Integer Program (MIP), and propose an algorithm based on tabu serach to solve it. An initial solution is obtained by a sequential algorithm and improved by tabu search, where customers are reallocated. This method do not distinguish between locational and routing moves. [START_REF] Semet | A two-phase algorithm for partial accessibility constrained vehicle routing problem[END_REF] proposed a clustering first routing second solution method. First customers are allocated to roots then the resulting routing problems are solved via Lagrangian relaxation. [START_REF] Gerdessen | Vehicle routing problem with trailers[END_REF] assumes that all customers have unit demand and each trailer is parked exactly once. Initial solutions are found using a number of sequential heuristics. These are then improved by a selection of VRP improvement heuristics. [START_REF] Chao | A tabu-search method for the truck and trailer routing problem[END_REF] developed a two-stage algorithm where in the first phase an initial solution is obtained with a cluster first route second heuristic and the second phase improves the initial solution using a tabu search algorithm with customer reallocation moves. [START_REF] Scheuerer | A Tabu Search Heuristic for the Truck and Trailer Routing Problem[END_REF] presents two new construction heuristics: a clusteringbased sequential insertion procedure and an adaptation of the well-known sweep algorithm by [START_REF] Gillett | A heuristic algorithm for the vehicle dispatch problem[END_REF] and a tabu search improvement procedure. Moreover, the author adapts these procedures to the multi-depot and the multi-period version of the problem. Hoff and Løkketangen (2007) have presented a case study for milk collection in Norway. The problem they consider is essentially a multi-depot, multi-period TTRP with heterogeneous vehicles and without trailer customers. They propose a sophisticated tabu search algorithm for solving their problem and report successful solution of real-world instances, improving on the existing tour plans used by their industry partner. [START_REF] Lin | Solving the truck and trailer routing problem based on a simulated annealing heuristic[END_REF] propose a simulated annealing (SA), then computational tests on the instances proposed by Chao (2003) are presented to compare the proposed SA algorithm to Chao's and Scheuerer's procedures. Drexl (2006) defined the VRP with Trailers and Transshipments (VRPTT) as the generalization of the TTRP when trailers can be pulled by different lorries on its itinerary and several transshipments are allowed. The author introduces also the notion of support vehicles, which are connecting the depots with the transshipment points without the possibility to visit any customers (1st-echelon vehicles). The problem is solved using branch-and-cut and branch-and-prize, which are the first exact methods developed for a variant of 2E-LRP. [START_REF] Tan | A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems[END_REF] applied a hybrid evolutionary algorithm (HMOEA) to the multi-objective variant of the VRPTT. The algorithm uses specialized genetic operators, a variable-length representation and a local search method. The authors compare it with a non-hybrid genetic algorithm (using only the proposed genetic operators) and a hybrid genetic algorithm where standard operators are used instead of those proposed by HMOEA. Yang and Xiao (2008) define the Vehicle Routing Problem with Transshipment Centers. In this problem, the planner has the option of use both direct shipping and two-echelon strategies, and have to choose for each customer the best strategy to produce a route configuration in order to reduce total transportation costs. Although some service characteristics, as periodicity and types of products are considered, the overall system consists on one supplier, one retailer and one transshipment center. This study is closer to supply chain management than to travel cost optimization.

Only one problem involving more than two echelons is found in literature. [START_REF] Ambrosino | Distribution network design: new problems and related models[END_REF] propose a mathematical programming formulation for a number of static and dynamic scenarios based on the general multi-echelon LRP. To explore the computational complexity of the models, linear programming approaches are used to find the optimal solution or at least provide lower bounds for problem instances based on a real-life case. Computational testing is limited to locating distribution and transshipment points and assigning large customers and customer zones to these distribution facilities. As such, the multiple echelon approach and routing considerations discussed in the earlier sections are not explored in the computational experiments. The optimal solution could only be found for the smallest problem instance, involving possible locations for 2 distribution centers, 5 transshipment points, 5 large customers and 25 customer zones. As the problem instances become larger, the gap between the best integer solution found, within a time limit of several days for the large instances, and the MIP lower bound provided by CPLEX increases rapidly up to more than 45%. As a result, heuristic approaches seem to be more appropriate, even for the scaled down problems used for the computational experiments.

Other multi-echelon transportation cost optimization variants

The NE-LRP is not the only approach used to model and optimize multi-echelon transportation systems. In fact, we observe other three approaches: the arc-routing variants, which are similar to 2E-LRP where the 2 nd echelon is modeled by a capacitated arc routing problem, the two-echelon location-distribution problems, that simplify one or more echelons approximating their costs, and the pick-up and delivery approaches. In this section we will present the main variants and methods belonging to these three categories.

Arc routing based variants

Arc Routing Problems (ARP), are routing problems where customers are not located on nodes but are defined by their density in the network. One ARP variant deals with multiechelon networks, the capacitated ARP with Mobile Depots (CARP-MD), also noted CARP with Refill-Profiles (CARP-RF). Two different combinatorial optimization problems are associated respectively to each echelon. The 1 st echelon vehicles delivering the possible mobile depots location points define a Pickup-and-Delivery Problem (PDP) for the fist echelon (where the capacity is the number of depots to move from one point to another). The 2 nd echelon ones follow a multi-depot CARP. The optimization problem's objective function is to minimize the total transportation cost of the systemDel [START_REF] Del Pia | A Variable Neighborhood Descent Algorithm for a Real Waste Collection Problem with Mobile Depots[END_REF] propose a Variable Neighborhood Descent heuristic algorithm. Starting from a local search procedure [START_REF] Hertz | A Variable Neighborhood Descent Algorithm for the Undirected Capacitated Arc Routing Problem Transportation[END_REF], the authors add a procedure which considers the vehicle synchronization. As an input to the procedure, they fix the total collection amount of the small vehicles on their routes and the part of the capacity of the large vehicles reserved for transshipments from the small vehicles. Then, they compute a route plan serving all edges of their network with the vehicles. After that, they make the resulting routes feasible by arranging transshipments. This step is performed sequentially: First, they choose a small vehicle for a transshipment. For this vehicle, they determine a part of its tour during which a transshipment is reasonable (because the vehicle has already collected some load) and necessary (because at the end of this subtour the vehicle is full). Second, they determine a large vehicle and a vertex on its tour such that the total increase in the duration of both routes, when performing a load transfer at this vertex, is minimal. The route plan is updated accordingly and the procedure repeats until all routes are feasible. The problem formulation can be found in [START_REF] Amaya | The capacitated arc routing problem with refill points[END_REF], which is solved by a cutting plane algorithm. [START_REF] Gendron | Formulations and relaxations for a multi-echelon capacitated location-distribution problem[END_REF] formulated the N-echelon location-distribution problem (NE-LDP), which differs from LRP in the cost estimation. In fact, no routing construction is made in the NE-LDP, but an estimated cost is defined to deliver a customer from a depot through a satellite. The authors propose a MIP formulation for the two-echelon variant of the family, and solve it using CPLEX. They also present a heuristic method based on variable neighborhood search. Following an initial greedy construction procedure, this method iterates over three phases. In the first phase (node+arc-based neighborhood descent) the authors propose four types of neighborhoods: four types of neighborhoods: (1) close one depot;

Cost approximation optimization variants

(2) close one satellite;

(3) serve one customer through a different satellite; (4) serve one satellite through a different depot. In the second phase (open depot+satellite neighborhood descent), two types of neighborhoods are used:

(1) open one depot and

(2) open one satellite. To evaluate the impact of each move of type (1), the authors first serve through the open depot every satellite connected to it, and then we perform phase 1, the node+arc-based neighborhood descent, on the resulting network. The evaluation of each move of type ( 2) is performed similarly. Then, a diversification phase is made using an adaptive memory that stores the best solutions found so far, selects some of these solutions and perturbs them by performing random moves in a large-scale neighborhood, defined by all moves that consist in closing k paths, replacing them by k alternative paths.

Another cost approximation approach is the vehicle routing problem with satellite facilities (VRP-SF). In this variant, the network includes facilities that are used to replenish vehicles during a route (Bard et al., 1998a(Bard et al., , 1998b;;Agnelelli and Speranza, 2002). When possible, satellite replenishment allows the drivers to continue the deliveries without necessarily returning to the central depot. However, the transportation cost of 1 st -echelon vehicles is not considered in the system, i.e. only the second-echelon cost is taken into account in the objective function. [START_REF] Crevier | The multi-depot vehicle routing problem with interdepot routes[END_REF] studied a variant of this problem where inter-satellite trips are allowed for satellite replenishment, presenting a model which considers the intersatellite transportation costs and a heuristic method to solve the problem. This method combines the adaptive memory principle and a tabu search procedure.

Pickup-and-delivery approaches

The Pickup and Delivery Problem (PDP) is a family of combinatorial optimization problems which deal with vehicle routing in which the same vehicles make both the pickup and the delivery requests. This is another approach that can be considered, since satellites can be defined as customers where a freight quantity have to be delivered by a fleet of vehicles and then it can be picked-up by vehicles of a different fleet. [START_REF] Berbeglia | Static pickup and delivery problems: A classification scheme and survey[END_REF] make a complete classification of the main PDP variants where this possibility is considered, proposing several problems where the same commodity delivered then picked up several times. However, most of these problems deal with one route systems or are applied to simplified or very small-sized problems.

An explicit multi-echelon variant of the PDP is the VRP with cross-docking operations, described in [START_REF] Wen | Vehicle Routing with cross-docking[END_REF]. Two types of vehicles are defined: one type make the delivery operations at a cross-docking platform and the other type is charged of picking up the freight and shipping it to customers. At each cross-docking platforms, delivery vehicles must arrive before pickup vehicles. The authors propose a mathematical formulation for instances with only one cross-docking platform and a Tabu Search heuristic procedure which uses two neighborhoods and is finally embedded within an Adaptative Memory Procedure (AMP), in order to reach better and most robust solutions. This problem is interesting because decisions for cross-docking operations (in terms of loading, unloading and consolidation) are taken into account. This decisions are acting on total travel time. However, no generalization to a multiplatform problem has been formulated.

Conclusions and research guidelines

In this paper a general conceptualization and notation for NE-LRP is proposed. A detailed review on the main variants of the problem, the proposed solving methods, as well as other modeling approaches, is presented. The main works deal with realistic cases of two-echelon systems, and the vehicle routing and location-routing approaches are dominant. Moreover, the system structure in multi-echelon distribution planning is becoming important in cost optimization approaches. The reviewed models and solving methods are mainly built to ask real tactical and operational planning questions, more precisely in two-echelon food and urban distribution applications.

Since nowadays no reference instances are used, the comparison among the various methods will be difficult. A standard notation and one or more sets of instances (for example, [START_REF] Chao | A tabu-search method for the truck and trailer routing problem[END_REF], Drexl 2006[START_REF] Gonzalez-Feliu | The two-echelon capacitated vehicle routing problem[END_REF], Crainic et al., 2009a) will facilitate the development of methods for these problems. Three main directions can be observed. The first, more conceptual, is related to modeling the different NE-LRP variants and similar approaches for realistic situations, focusing on advanced urban freight distribution systems and supply chain management decision support planning. The difficulties related to connecting two echelons have also to be studied, in a theoretical point of view, in order to develop more efficient solving procedures. The second direction is the development of exact methods, which are currently limited to some specific problems or to very small instances. Branch and bound and branch and cut are preferred to other methods, but also branch an prize has to be considered as a soling method for these problems. The third direction, which is the most advanced at the moment, is that of heuristics. However, the latest meta-heuristic advances in VRP have not been applied to more complex systems such as NE-LRP, and they would constitute an interesting research direction to meet the exigencies of real applications.

In any case, the NE-LRP seems to be a prominent optimization problem directly related to real transportation planning questions and stakes.

Fig. 1

 1 Fig. 1 Example of a N-echelon distribution network

ky

  is defined by its cost, the nodes that serve, respecting capacity and length constraints, among others, and the order they are visited. The attribute ie hk  indicates if e-node h is served by e-route i starting at e-1-node k. Moreover, the variable e k D is a real variable which shows the freight quantity that is delivered to e-satellite k. Finally, of e-satellite k.Three types of costs are considered: the cost of each route ie

Acknowledgments

Part of this work was started during the author's PhD. thesis while he was at Politecnico di Torino, Turin, Italy and CIRRELT, Montréal, Canada. A special acknowledgement is made to Roberto Tadei, Guido Perboli, Daniele Vigo and Teodor Gabriel Crainic for their guidance and help during this period.

The author also acknowledges Tai Yu Ma and Hector Lopez, from the Laboratoire d'Economie des Transports, for their helpful comments that improved the present version.