This paper presents a hybrid approach that aims at solving the Capacitated Vehicle Routing Problem (CVRP) by means of combining Constraint Programming (CP) with Lagrangian Relaxation (LR) and Probabilistic Algorithms. After introducing the CVRP and reviewing the main literature in this area, the paper proposes the use of a multistart hybrid Variable Neighbourhood Search (VNS) algorithm. This algorithm uses a randomised version of the classical Clarke and Wright savings heuristic to generate a starting solution to a given CVRP. This starting solution is then improved through a local search process which combines: (a) LR to optimise each individual route, and (b) CP to quickly verify the feasibility of new proposed solutions. Some results on well-known CVRP benchmarks are analysed and discussed.
Road transportation is nowadays the predominant way of transporting goods in many parts of the world. Direct costs associated with this type of transportation have experienced a signi¯cant increase since 2000.
There is a need for developing e±cient models and methods that support decision-making processes in the road transportation arena so that optimal (or quasi-optimal) strategies can be chosen. This necessity for optimising road transportation, which a®ects both the public and private sectors, constitutes a major challenge for most industrialised regions.
The class of logistic problems dealing with the issues presented in the
previous paragraph are usually known as the Vehicle Routing Problem (VRP).
This is among the most popular research areas in combinatorial
optimisation. It was ¯rst de¯ned by Dantzig and Ramser in 1959 [
For this paper, the CVRP has been chosen. It is mainly because there are a huge amount of models, techniques, benchmarks and research | in general | done before (See Section 3). Hence, results given by the presented methodology can be compared with a number of previous ones.
The paper presents a general VNS structure whose local search process is supported by Constraint Programming (CP) and lagrangian Relaxation (LR). A probabilistic Clarke and Wright Savings (CWS) constructive method is used to generate initial solutions.
The remainder of this article is structured as follows. Next sections provide a general overview of CVRP formulation and a few words on previous work.An introduction to the CVRP mathematical model and the technologies used in this research are presented in sections 4 and 5 respectively. Section 6 is devoted to the proposed method, based on the VNS metaheuristic; the general algorithm, moves used within its structure and the adapted LR-method are introduced in this section. Next, computational results are presented and discussed. Finally, some conclusions, remarks and future research topics are outlined in the last section. 2
The Capacitated Vehicle Routing Problem The CVRP is de¯ned over a complete graph GfI; Eg connecting the vertex set I = f1; 2; : : : ; ng | clients to be served and the depot | through a set of edges E = f(i; j)ji; j 2 Ig | roads, streets, etc. Edges eij 2 E have an associated a travel cost cij , which is supposed to be the lowest cost route connecting node i to node j. Usually, to simplify it (not the complexity but the problem de¯nition), edges cost is assumed as symmetric (cij = cji). Each vertex i 2 Inf1g has a nonnegative demand qi, while, vertex 1 corresponds to the depot, which does not have an associated demand.
A ¯xed °eet of m identical vehicles, each one with capacity Q, is available at the depot to accomplish the required tasks. Solving the CVRP consists of determining a set of m routes whose total travel cost is minimised and such that (a) each customer is visited exactly once by a single vehicle, (b) each route starts and ends at the depot, and (c) the total demand of the customers assigned to a route does not exceed the vehicle capacity Q.
Therefore, a solution to the CVRP is a set of m cycles sharing a common starting and ¯nishing vertex (i.e. the depot).
Previous work on the Capacitated Vehicle Routing Problem CWS constructive algorithm [4] is probably the most cited heuristic to solve the CVRP. The CWS is an iterative method that starts out by considering an initial dummy solution in which each customer is served by a dedicated vehicle. Next, the algorithm initiates an iterative process for merging some of the routes in the initial solution.
The CWS algorithm usually provides relatively good solutions, especially
for small and medium-size problems. Many variants and improvements of
the CWS have been proposed in the literature [
Using constructive heuristics as a basis, metaheuristics became popular
for the VRP during the nineties. Some early examples are the Tabu Route
method by Gendreau et al. [
Monte Carlo Simulation (MCS) can be de¯ned as a set of techniques that
make use of random numbers and statistical distributions to solve certain
stochastic and deterministic problems [
Another way to face the VRP has been the use of complete methods,
which ensure not only to ¯nd the solution but also, to prove its optimality.
The main drawback of these techniques is that they may only deal with
small instances, up to 100 customers [
In the proposed model, the CVRP has been divided into two subproblems, concerning customers' allocation and routing optimisation separately. The ¯rst is aimed to assign customers to the minimum number of required vehicles ful¯lling capacity limitations. The latter is used to solve each independent route to optimality, giving the best solution for a particular allocation. 4.1
Capacity problem The proposed customers' allocation subproblem uses two lists of variables. A list R of size n, with integer domains Ri 2 [1::m]ji = 1; :::; n, indicates which vehicle is serving the ith customer. Given a vehicle v, Qv is a list of m variables with real domain Qv 2 [0::Q] used to trace the cumulative capacity at each one of the m routes. Therefore, capacity constraints are enforced through domains de¯nition since Qv cannot get higher values than the maximum capacity Q.
A set of m £ n binary variables B has been introduced to relate R and Qv values. For each vehicle v 2 V , a list of n binary variables Bvi j i 2 I is de¯ned, taking value 1 whenever customer i is assigned to vehicle v and 0 otherwise. Since each customer i is visited by a single vehicle, for all values of v the binary variable Bvi can take value 1 only once.
The binary set B and allocation variables R are related through the following statement:
Cumulative capacities can be traced simply by using Eq.2.
Ri = ri ! Brii = 1 8i 2 I
Qv =
X Bviqi 8v 2 V i2I (1) (2) 4.2
Routing Problem The routing problem, tackled for each vehicle separately, can be viewed as a TSP instance. For each vehicle v, the related TSP can be considered as a complete undirected graph G = (Iv; Ev), connecting assigned customers Iv = fi 2 IjRi = vg through a set of undirected edges Ev = f(i; j) 2 Eji; j 2 Ivg. The solution is a path connected by edges belonging to Ev that starts and ends at the depot (i = 1) and visits all assigned customers.
The proposed mathematical formulation requires de¯ning the binary variable xe to denote that the edge eij 2 Ev is used in the path. That is xe = 1 if customer j is visited immediately after i; otherwise xe = 0. Thus, the formulation for the TSP problem is as follows: subject to min
X cexe e2Ev X xe = 2 ;
8i 2 Iv e2±(i)
X e2Ev(S) xe ·j S j ¡1 ;
1 8S ½ Iv ; j S j· 2 j Iv j (3) (4) (5) where ±(i) = fe 2 Ev : 9j 2 Iv; e = (i; j) or (j; i)g represents the set of arcs whose starting or ending node is i; Ev(S) = feij 2 Ev : i; j 2 Sg represents the set of arcs whose nodes is in the subset S of vertices; nv = jIvj; and ce is the associated cost to the undirected edge eij (eji).
Constraint (4) states that every node i 2 Iv must be visited once, that is, every customer must have two incident edges. Subtour elimination constraint (5) states that the tour must be a Hamiltonian path, so it cannot have any subcycle. Then a feasible solution of the TSP should, by de¯nition, also satisfy constraints (a) and (b) of the CVRP, minimising the total travel cost of the route. 5 5.1
Probabilistic Clarke and Wright Savings Algorithm CWS is an iterative method that starts out by considering an initial dummy solution in which each customer is served by a dedicated vehicle. Next, the algorithm initiates an iterative process for merging some of the routes in the initial solution. Merging routes can improve the expensive initial solution so that a unique vehicle serves the nodes of the merged route. The merging criterion is based upon the concept of savings. Roughly speaking, given a pair of nodes to be served, a savings value can be assigned to the edge connecting these two nodes. This savings value is given by the reduction in the total cost function due to serving both nodes with the same vehicle instead of using a dedicated vehicle to serve each node.This way, the algorithm constructs a list of savings, one for each possible edge connecting two demanding nodes. At each iteration of the merging process, the edge with the largest possible savings is selected from the list as far as the following conditions are satis¯ed: (a) the nodes de¯ning the edge are adjacent to the depot, and (b) the two corresponding routes can be feasibly merged | i.e. the vehicle capacity is not exceeded.
The selection process should be done without introducing too many parameters in the algorithm. To do it, di®erent geometric statistical distributions during the randomised CWS solution-construction process are employed: every time a new edge is selected from the list of available edges, a value ® is randomly selected from a uniform distribution in (a; b), where 0 < a · b < 1. This parameter ® de¯nes the speci¯c geometric distribution that will be used to assign exponentially diminishing probabilities to each eligible edge according to its position inside the sorted savings list. That way, edges with higher savings values are always more likely to be selected from the list, but the exact probabilities assigned are variable and they depend upon the concrete distribution selected at each step. 5.2
Constraint Programming
CP is a powerful paradigm for representing and solving a wide range of
combinatorial problems. Problems are expressed in terms of three entities:
variables, their corresponding domains and constraints relating them. The
problems can then be solved using complete techniques such as depth-¯rst
search for satisfaction and branch and bound for optimisation, or even
tailored search methods for speci¯c problems. Rossi et al. present a complete
overview of CP modelling techniques, algorithms, tools and applications [
Lagrangian Relaxation
LR is a well-known method to solve large-scale combinatorial optimisation
problems. It works by moving hard-to-satisfy constraints into the objective
function associating a penalty in case they are not satis¯ed. An excellent
introduction to the whole topic of LR can be found in [
LR exploits the structure of the problem, so it reduces considerably
problem's complexity. However, it is often a major issue to ¯nd optimal
Lagrangian multipliers. The most commonly used algorithm is the Subgradient
Optimisation (SO). The main di±culty of this algorithm lays on choosing a
correct step-size ¸k in order to ensure algorithm's convergence [
Therefore, the proposed method combines the SO algorithm with a heuristic to obtain a feasible solution from a dual solution. It can get a better upper bound U B, so it improves the convergence on the optimal solution departing from an initial U B obtained with a Nearest Neighbour Heuristic. If the optimal solution is not reached at a reasonable number of iterations, the proposed method is able to provide a feasible solution with a tight gap between the primal and the optimal cost. 5.4
Variable Neighbourhood search
A general VNS, as explained in [
The VNS starts from an initial solution x. A new point is generated at random from the kth neighbourhood Nk(x) of x in order to diversify the search. If the valley surrounding the solution x is large, a thorough diversi¯cation should be done aiming to avoid getting trapped in a local optimum. For this reason, the shaking process is repeated.
The local search process for each neighbourhood Nl(x0) performs an exhaustive exploration with a best-accept strategy. Finally, the best neighbour x00 is chosen in terms of its solution value f (x00) = Pv2V U Bv. If its value is lower than the original f (x0), the solution is updated and neighbourhoods exploration is restarted.
When the VND process reaches a local optimum, no solution improvement may be found according to de¯ned neighbourhoods. If this local optimum is better than the incumbent, it is accepted as the current solution x à x00 and the search is restarted from the ¯rst shaking neighbourhood. Otherwise, the algorithm keeps x as the best solution found so far and continues exploring the next neighbourhood. If there are no remaining neighbourhoods to be explored, the process is restarted until the stopping condition is met. 6
The described problem has been tackled using a hybrid approach. The
proposed methodology combines CP and LR within a metaheuristics framework
in order to improve algorithm's performance. As mentioned, even the most
basic VNS algorithm, known as VND, has provided promising results when
solving di®erent VRP variants. In the proposed approach, a general VNS
framework has been chosen to embed selected paradigms. Within the VNS
general framework, CP and LR are used in di®erent processes. During
algorithm's initialisation, a Probabilistic CWS method has been used to ¯nd
an initial feasible solution [
CP is used to check solutions feasibility within diversi¯cation and local search processes. In turn, a tailored LR method is applied to calculate routes every time a partial solution is generated either during initialisation, diversi¯cation or local search processes. Using LR allows reducing the computation time when compared to other routing post-optimisation methods, such as a VND with single-route classical moves. So, the proposed LR approach provides optimal routes in very low times and, at the same time, allows reducing algorithm's de¯nition and complexity. 6.1
Lagrangian Relaxation Method Applied The LR-based method is used within the local search process to solve the routing problem to optimality. It can be considered a speci¯cation of the Lagrangian Metaheuristic presented on Boschetti and Maniezzo [2]. It uses the SO algorithm combined with a heuristic. Aiming to improve algorithm's convergence to the optimum, a heuristic is introduced in order to obtain a feasible solution from the dual variable. This method tries to improve the U B with the values of these feasible solutions, so a better convergence is obtained. Eventually, this solution may be provided as the best solution if the method is stopped. The stopping criterion is based on the maximum number of iterations (k < maxiterations) and also on a °oating-point exception (°k < 10¡15). The proposed LR-based method algorithm is shown in Table 1. Calculate the step-size ¸k = ±k L¡k°Lk(ku2k) Update the multiplier uk+1 = uk + ¸k°k k à k + 1
The proposed heuristic to improve the U B is applied when the solution is nearly a route. That is, if it satis¯es k ° k2< » (step 8). As any solution is a 1-tree, this criterion means that the solution has few vertices without two incident edges. This heuristic replaces an edge e = (i; j) where j has some extra edges for an edge e = (i; l) where l has one single edge. Before applying the exchange, the heuristic checks if the new solution is a 1-tree. Otherwise, the heuristic can divide it into more trees having some subtours. The chosen vertices i; j; l minimise the cost of the exchange: fi; j; lg = argminncil ¡ cij j °j < 0; °l > 0; (i; j) 2 T; (i; l) 2 E r T o (6)
The parameter » depends on the number of variables. A good estimation of » value would avoid increasing the computation time excessively. First, its value may be large, for instance nv=2, but it should be updated whenever a feasible solution is found according to » =k °k k2 . If this parameter is not correctly updated, the heuristic becomes time consuming. Eventually, the heuristic could ¯nd the optimal solution without detecting it, so the method would continue iterating until LB = U B.
As mentioned, algorithm's convergence is critically in°uenced by the step-size ¸k . This value relies on either the LB or the U B, which are normally unknown or bad estimated. Therefore, convergence may not be assured for all cases. In order to overcome this limitations, the use of a parameter L, such that LB · L · U B , is proposed. By de¯nition, this parameter corresponds to a better estimation of L¤ than those obtained for LB and U B. The calculation of the step-size turns into: ¸k = ±k
L ¡ L(uk)
k °k k2
Convergence is guaranteed if the term L ¡ L(uk) tends to zero. In turn, convergence e±ciency can be improved as long as the new L parameter gets closer to the (unknown) optimal solution. The main idea is very simple: as the algorithm converges to the solution, new better lower bounds are known and new better upper bounds estimations can be obtained by using the heuristic designed to get feasible solutions. Therefore, the parameter L is updated according to the following conditions: It is initialised L = L(u0) + ®L(U B ¡ L(u0)) with 0 < ®L < 1; if L(uk) > L, it is updated L = L(uk) + ®L(U B ¡ L(uk)), and if L > U B, then L = U B.
Finally, the parameter ±k is initialised to the value 2 and is updated as Zamani and Lau [25] suggest. If the lower bound is not improved, ±k is decreased, using the formula ±k+1 = ±k½ with 0 < ½ < 1. On the other hand, if the lower bound is improved, then its value is increased according to the formula ±k+1 = ±k 3¡2 ½ . 6.2
Inter-route Moves
VNS metaheuristic is based on exploring alternatively di®erent
neighbourhoods around a known feasible solution. In order to establish these
neighbourhoods, di®erent moves are to be de¯ned. In the presented approach,
four di®erent inter-routes classic moves [
As mentioned, using LR for solving the routing subproblems allows
avoiding the de¯nition of intra-route moves. Since results provided by the
LR method are optimal, no routing optimisation process is needed.
Usually, a post-optimisation method based on intra-route moves is applied to
improve each single route quality [
Variable Neighbourhood Search Framework
A general VNS framework, as explained in Hansen and Mladenovic [
10 0 Initialisation. Select the set of neighbourhood structures Nk, for k = 1; : : : ; kmax, that will be used in the shaking phase, and the set of neighbourhood structures Nl for l = 1; : : : ; lmax that will be used in the local search; ¯nd an initial solution x; choose a stopping condition; 1 Repeat the following sequence until the stopping condition is met: 2 Set k à 1; 3 Repeat the following steps until k = kmax : 4 (a) Shaking. Generate a point x0 at random from the kth neighbourhood Nk(x) of x; 5 (b) Local search by VND. 6 (b1) Set l à 1 ; 7 (b2) Repeat the following steps until l = lmax ; 8 - Exploration of neighbourhood. Find the best
neighbour x00 of x0 in Nl(x0); 9 - Move or not. If f (x00) < f (x0) set x0 à x00 and l à 1; otherwise set l à l + 1; (c) Move or not. If this local optimum is better than the incumbent, move there (x à x00), and continue the search with N1(k à 1); otherwise, set k à k + 1;
In step 0, neighbourhood structures to be used within shaking (Nk) and local search (Nl) processes are selected. In this case, all four described moves have been selected to be used in both neighbourhoods. Furthermore, a randomised CWS algorithm is used in order to ¯nd a good initial solution for the search.
In step 4, a new point is generated at random from the kth neighbourhood Nk(x) of x in order to diversify the search. Its feasibility is immediately checked using CP. Solutions' values are ignored until the last iteration, when routes are recalculated using LR to provide a complete solution.
Steps 5 to 9 contain the VND algorithm used to perform the local search.
Within the VND algorithm, an exhaustive exploration of the lth neighbourhood Nl(x0) of x0 is performed in step 8. Departing from the solution x0, the lth move is applied and new solution's feasibility is checked using CP. Whenever it is proved feasible, LR is used to recalculate only modi¯ed routes. This approach permits to consider only two routes per solution, reducing the computation time. Finally, the best neighbour x00 is chosen in terms of its solution value f (x00) = Pm v=1 U Bv. 7
The methodology described in the present paper has been implemented in Java and linked to the open-source CP software system ECLiPSe 6.0 [1]. All tests have been performed on a non-dedicated server with an Intel i5 processor at 2.66GHz and 16GB RAM. In general, ¯ve to seven processes were launched in parallel to solve di®erent problems.
A total of 93 CVRP benchmark instances from www.branchandcut.org have been used to test the e±ciency of the proposed approach. Only those instances whose distance is de¯ned as Euclidean or Geographic have been selected, in order to ensure triangular inequality's ful¯lment. Table 3 shows the total number of problems chosen from each class, as well as for how many the best known solution has been reached. This table also shows the average gap (% Aver. Gap) from best published values for those problems where the best known solution could not be reached after 40 iterations. A low deviation, under 1 %, is observed for most problem sets, comparable to results obtained by means of other metaheuristics.
Class A B E F G M P TSPLib
The use of LR ensures the partial optimality of all solutions from the routing perspective. The reason is that the proposed approach can optimally solve all TSP instances, due to the number of associated customers is always low. LB and UB converge rapidly, keeping their gap between 0 and 10¡10 and guaranteeing so the solution optimality. In addition, LR solves all routes in negligible times. Thus, LR has demonstrated to be an e±cient alternative for intra-route optimisation processes.
The initial solution may be obtained by means of di®erent methods. Table 4 presents a comparative of results for some problems of class A using di®erent techniques to get an initial solution. First, it may be obtained by solving separately capacity and routing problems, using the proposed problem's decomposition in a CP/LR scheme (2). This approach is able to provide a low-quality quick solution, since both subproblems are easily solved but variables are unlinked. This solution may be highly improved applying a VND method, providing an initial solution whose value is usually close to the ¯nal result (1). The initial solution may also be obtained by means of the presented RCWS algorithm (3). This algorithm provides a good initial solution in negligible times, but the maximum number of available vehicles might not be always respected. For this reason, it may be forced to execute iteratively until a solution ful¯lling this requirement is reached (4).
It can be stated from results presented in Table 4 that RCWS is clearly faster than the other methods to get a good initial solution. Even when it is forced to iterate to reach a given number of vehicles, it may provide a solution quickly. It is remarkable that this algorithm eventually ¯nds a better initial solution than the CP/LR + VND in a much lower time, becoming so a better alternative. For small problems, the RCWS + VNS scheme outperforms the CP/LR + VNS method, reaching best known values in lower times. On the other hand, times are comparable for larger problems. The reason might be found in the use of exhaustive local search for all de¯ned moves. This fact also justi¯es the time spent on calculating the initial solution when the CP/LR + VND method is used. For small problems, feasible points around a given solution may be usually low, while the solution space may grow dramatically as the problem size increase, and so it does the time needed to explore it. Probably, the use of heuristics within local search processes would reduce the total time needed to solve problems signi¯cantly.
Using RCWS to get an initial solution allows solving to the best known value 15 of 27 problems from class A. The same number of problems are solved departing from an initial solution obtained by means of the CP/LR scheme without VND. Instead, CP/LR + VND allows solving only 13 problems. This method uses all four de¯ned moves to reach a minimum. As they are also used in the VNS algorithm, the initial solution is a local optimum for all moves de¯ned in its local search processes. Thus, a more thorough shaking would be mandatory to get a better algorithm's performance and avoid getting trapped in local minima. Moreover, the algorithm fails to successfully solve the same problems, regardless which method is used to get the initial solution. Again, a poor shaking might be the main reason for this behaviour. Table 4 also shows the gap between the ¯nal solution and the best known value, when it is not reached. It can be observed it is usually lower when a good initial solution is provided.
RCWS has been used to get the initial solution for all tested instances due to its performance. Table 5 shows results obtained using RCWS combined with VNS for some representative instances of di®erent sizes.
This methodology performs similarly both for small and large instances. It is remarkable that the algorithm eventually reaches the optimal solution for smaller problems (50 customers or less), but it stops near the optimum for larger instances. Thus, its applicability is not restricted. Nevertheless, the time required to solve all instances is prohibitive when compared to stateof-art methodologies. For this reason, some research needs to be addressed to improving local search processes in order to get competitive results.
Notice that results for the largest selected test instance G-n262-k25 is
1.95% lower than its best value published in [
Use of multiple agents or algorithm's instances | each of them initiated with a di®erent random-generator seed or a di®erent value for the statistical distribution parameter | can signi¯cantly diminish computational times to obtain pseudo-optimal solutions. Larger problems might need either more computation resources or larger computational times to be solved.
In such scenarios, one possible approach to allow for real-time decisionmaking could be to employ modern GPUs. This is one of the most promising research lines we are currently exploring. However, use of GPUs requires advanced algorithmic and programming skills, since developing e±cient code in CUDA is not a trivial task and, in the case of our algorithm, some problems related to memory management must be addressed yet before obtaining competitive results. An alternative approach is to use a distributed problemsolving approach. This way, pseudo-optimal solutions for large and complex real-life problems might be obtained in nearly real time at an inexpensive monetary cost.
In e®ect, a standard small and medium enterprises (SMEs) use a large number of commodity computers distributed among their di®erent departments and/or facilities. Most of these personal computers o®er more computing capabilities than required to complete their daily activities (i.e. text processors, spreadsheets, e-mail, etc.). Moreover, they happen to be underutilized during nightly hours. Our proposal gathers the spare resources from each computer and aggregates them into a computational environment where hundreds or even thousands of instances of our algorithm can be run simultaneously. These cloned agents can either use a global collaborative memory or several local collaborative memories, depending on the characteristics of the distributed system.
This work was supported in part by the IN3-UOC Knowledge Community Program under grant HAROSA09.
[1] K. Apt and M. Wallace. Constraint Logic Programming using ECLiPSe.
Cambridge University Press, 2007. [2] M. Boschetti and V. Maniezzo. Benders decomposition, lagrangean relaxation and metaheuristic design. Journal of Heuristics, 15:283{312, 2009. [3] G. Buxey. The vehicle scheduling problem and monte carlo simulation.
Journal of Operational Research Society, 30:563{573, 1979. [4] G. Clarke and J. Wright. Scheduling of vehicles from a central depot to a number of delivering points. Operations Research, 12:568{581, 1964. [25] R. Zamani and S. Lau. Embedding learning capability in lagrangean relaxation: An application to the travelling salesman problem. European Journal of Operational Research, 201(1):82{88, 2010. Problem A-n32-k5 A-n33-k5 A-n33-k6 A-n45-k6 A-n46-k7 A-n54-k7 A-n55-k9 A-n65-k9 A-n69-k9 A-n80-k10 Problem A-n32-k5 A-n33-k5 A-n33-k6 A-n45-k6 A-n46-k7 A-n54-k7 A-n55-k9 A-n65-k9 A-n69-k9 A-n80-k10 Problem A-n32-k5 A-n33-k5 A-n33-k6 A-n45-k6 A-n46-k7 A-n54-k7 A-n55-k9 A-n65-k9 A-n69-k9 A-n80-k10 Problem B-n44-k7 B-n45-k5 B-n50-k7 E-n51-k5 E-n76-k8 E-n101-k8 F-n45-k4 F-n135-k7 G-n262-k25 M-n101-k10 M-n151-k12 P-n40-k5 P-n50-k7 P-n55-k8 P-n65-k10 P-n70-k10