Sébastien Carrère
email: sebastien.carrere@inrae.fr

Jérôme Gouzy

Frédéric Debellé

William Marande

Bernadette Julier²

Philippe Barre²

Medicago sativa cv. Mercedes genome sequence

An alfalfa (or lucerne) genome reference sequence is an essential tool for breeding of this major legume species. A clone of Flemish origin has been sequenced and the genome assembly has been carried out with NRGene protocols. A total of almost 190 000 scaffolds have been generated and this genome assembly reaches 2.6 Gb (80% of the 3.2 Gb expected). Genome annotation has provided 233 049 protein-coding genes and 36 752 non-protein coding genes. A genome portal based on JBrowse has been developed for searching the annotated genome (https://medicago.toulouse.inra.fr/MsatMercedes-NRGENE-20181029/).

Introduction

Alfalfa or lucerne (Medicago sativa) is an autotetraploid species (2n = 4x = 32) whose total genome size approximates 3.2 Gb. The allogamy of this species generates a high heterozygosity that complexifies genome assembly. The genome of Medicago truncatula, a wild diploid related model species, has long been used as a reference sequence for alfalfa genomic studies. Indeed, the two species are highly syntenic (Choi et al 2003;[START_REF] Julier | Construction of two genetic linkage maps in cultivated tetraploid alfalfa (Medicago sativa) using microsatellite and AFLP markers[END_REF]. For example, GBS reads have been mapped on M. truncatula to identify polymorphic markers [START_REF] Li | A saturated genetic linkage map of autotetraploid alfalfa (Medicago sativa L.) developed using genotyping-bysequencing is highly syntenous with the Medicago truncatula genome. G3-Genes Genomes[END_REF][START_REF] Annicchiarico | Assessment of cultivar distinctness in alfalfa: a comparison of genotyping-by-sequencing, simple-sequence repeat marker, and morphophysiological observations[END_REF][START_REF] Julier | Use of GBS markers to distinguish among lucerne varieties, with comparison to morphological traits[END_REF]. Thirty percent of reads are being mapped only, probably because the non-coding portions are poorly conserved, so the marker density is not as high as expected.

A reference alfalfa genome sequence is needed to progress in alfalfa genetics and genomics. In EUCLEG project (www.eucleg.eu) funded by European Union, a genome sequence has been obtained and is made available on this website: (https://medicago.toulouse.inra.fr/MsatMercedes-NRGENE-20181029/).

Material and method

The alfalfa clone Mercedes2.11 that has been used as a parent of a mapping population [START_REF] Julier | Construction of two genetic linkage maps in cultivated tetraploid alfalfa (Medicago sativa) using microsatellite and AFLP markers[END_REF], has been chosen. This clone originates from the French variety Mercedes, a representative of the Flemish (Flamande) germplasm from North of France.

The sequencing has been conducted by the private company NRGene. NRGene has set up a whole genome sequencing and assembly service that had given excellent results on several species with a complex genome (wheat, maize, Italian ryegrass, strawberry, ...).The service is based on a classical genome sequencing (that provided by Illumina) with special conditions that enhance the quality of the sequences. More importantly, NRGene has developed a genome assembly software (DeNovoMAGICTM-3.0) that enables the genome assembly of the most complex genomes (including heterozygous and polyploid ones as alfalfa is). High-quality DNA of Mercedes2.11 was provided to NRGene.

Description of the assembly

The second generation sequencing offered a mean depth coverage of 131, considering a monoploid genome of x = 0.8 Gb (2n = 4x). In addition, third generation sequencing was obtained with a coverage of 17. After assembling, the total number of scaffolds was 189 167, obtained from 296 844 contigs (Table 1). This genome assembly is far from the 32 expected pseudomolecules, probably because of high heterozygosity that hampers genome assembly. However, this genome assembly reaches 2.6 Gb (3.2 Gb expected), meaning that 80% of the genome has been obtained. To further estimate the completeness of the genome, we used two independent complementary approaches. Mapping of full-length mRNA transcripts obtained by PacBio single-molecule long-read sequencing technology (IsoSeq transcripts, [START_REF] Chao | Analysis of transcripts and splice isoforms in Medicago sativa L. by single-molecule long-read sequencing[END_REF] indicated that more than 98% of these transcripts can be mapped on the assembly at 95% identity. In addition, BUSCO (Benchmarking Universal Single Copy Orthologs, [START_REF] Simão | BUSCO: assessing genome assembly and annotation completeness with single-copy orthologs[END_REF] analysis of the genome assembly indicated that 93 % of the genes in a BUSCO set of single copy genes were found in the assembly (Table 2).

Most of these genes are present in 1 to 4 copies (Table 3). This is in accordance to the autotetraploidy of alfalfa. It also confirms that the assembling procedure was able to recover the 4 haplotypes when they were different. The structural and functional annotation process of the M.sativa Mercedes genome has been based on an automatic pipeline, the integrative gene finder EuGene that integrates more than 200 RNAseq datasets [START_REF] Sallet | EuGene: An Automated Integrative Gene Finder for Eukaryotes and Prokaryotes[END_REF]). As a total, we found 233 049 protein-coding genes and 36 752 nonprotein coding genes.

Web portal and genome browser

This genome portal has been developed to browse and search genome annotation. It is built upon JBrowse genome browser and ElasticSearch search engine.

We annotated protein coding genes using various methods:

-Blastp vs. A. thaliana, M. truncatula, P. vulgaris, L. japonica, G. max proteomes -InterProsScan -Blast2Go.

All these annotation results have been merged into annotation sheets that are searchable using keywords or accession numbers through the genome portal.

The portal link: https://medicago.toulouse.inra.fr/MsatMercedes-NRGENE-20181029/

Table 1 .

 1 Scaffold statistics summary

	# of	Min	Max length
	scaffolds	length	(nt)
		(nt)

N50 (nt): 50% of the assembly is contained in scaffolds larger than this value # of scaffolds larger than N50 N90 (nt): 90% of the assembly is contained in scaffolds larger than this value # of scaffolds larger than N90 Mean scaffold length Median scaffold length Assembly size (nt) # of Ns

	All	189 167 1 000 15 212 363 1 289 735	547	3 578	28 273	13 976 1 577 2 643 922 996 45 316 006
	scaffolds
	Scaffolds	18 154 5 000 15 212 363 1 500 367	436	157 915	1 895 128 742 8 656 2 337 185 696 44 954 302
	 5000nt

Table 2 .

 2 Busco statistics (Busco3: release 3.0.2, embryophyta_odb9 dataset)

	Busco type	Number	Percent
	Complete BUSCOs (C)	1380	95.8%
	Complete and single-copy BUSCOs (S)	154	10.7%
	Complete and duplicated BUSCOs (D)	1226	85.1%
	Fragmented BUSCOs (F)	16	1.1%
	Missing BUSCOs (M)	44	3.1%
	Total BUSCO groups searched	1440

Table 3 .

 3 Estimation of the number of gene copies

	Number of gene copies Number of genes identified
	1	212
	2	284
	3	393
	4	442
	5	5
	6	2
	>6	4

Acknowledgements

This alfalfa genome assembly in part of EUCLEG project (www.eucleg.eu). This project has received funding from the European Union's Horizon 2020 Programme for Research & Innovation under grant agreement n°727312.

A joint plant breeding programme to decrease the EU's and China's dependency on protein imports"

EUCLEG.eu

This project has received funding from the European Union's Horizon 2020 Programme for Research & Innovation under grant agreement n°727312.


Sizing of a heterogeneous fleet of robots in a logistics warehouse* Achraf Rjeb 1 , Jean-Philippe Gayon 2 and Sylvie Norre 3 ** Abstract-We are interested in a fleet sizing problem with several types of robots. The operations are divided into several phases: loading, loaded travel, unloading and empty travel. The purpose is to determine the size of the robot fleet, that is, to determine the optimal types and number of robots for each type. We first consider the case where loads are all of the same type (homogeneous) before generalizing to several types of loads (heterogeneous). In both cases, we show that the problem can be formulated by an integer linear program. In the case of homogeneous loads, we consider a relaxation of the problem where the number of robots can be a real number. For this approximation, we show that it is optimal to use a single type of robot. It is also near-optimal when the number of robots must be an integer number.

I. INTRODUCTION

Robotics has become an essential concept in industry today and a major concern in research [START_REF] Hazan | Coordination de robots pour le transport d'objets[END_REF]. Indeed, it allows to increase robustness, flexibility and efficiency of manufacturing systems. In addition, the existence of robotic industrial platforms in an industrial unit reflects the level of its performance and reliability. After a remarkable evolution of industrial robotics, the concept of Multi-Robot System (MRS) appeared in 1989 in order to replace a large robot by a set of small robots [2]. Logistics warehouses are essential in any supply chain and are a factor of success or failure of any business [START_REF] Frazelle | Supply chain strategy: the logistics of supply chain management[END_REF]. Finally, MRS are considered an essential tool for any logistics warehouse to have a high performance for its industrial future [START_REF] Vivaldini | Integrated tasks assignment and routing for the estimation of the optimal number of AGVS[END_REF].

The literature on MRS in warehouses has since been enriched by addressing several problems such as: guidepath design, sizing of vehicle fleets, planning of transport operations, positioning, battery management, conflict management. The number of vehicles plays a very important role in the performance of MRS. We focus on the fleet sizing problem, which consists in determining the optimal number of vehicles capable of carrying out requested transport operations in a given time limit at minimum cost [START_REF] Sinriech | An economic model for determining AGV fleet size[END_REF].

In the literature, several works deal with the fleet sizing problem with different methods. According to [START_REF] Choobineh | Fleet sizing of automated guided vehicles: a linear programming approach based on closed queuing networks[END_REF], the design models treated in the literature can be classified into four categories:

------------------------------*Thesis co-financed by the European Union within the framework of the European Regional Development Fund ERDF **LIMOS UMR CNRS 6158 -Université Clermont-Auvergne, Campus Universitaire des Cézeaux, 63178 AUBIERE -FRANCE 1 Achraf Rjeb achraf.rjeb@uca.fr 2 Jean-Philippe Gayon j-philippe.gayon@uca.fr 3 Sylvie Norre sylvie.norre@uca.fr 1) Discrete and continuous event simulation models [START_REF] Kasikingam | Vehicle requirements model for automated guided vehicle systems[END_REF]- [START_REF] Asef-Vaziri | Dual track and segmented single track bidirectional loop guidepath layout for AGV systems[END_REF]; 2) Calculus approaches including a set of simple computations [START_REF] Vivaldini | Integrated tasks assignment and routing for the estimation of the optimal number of AGVS[END_REF], [START_REF] Sinriech | An economic model for determining AGV fleet size[END_REF], [START_REF] Egbelu | The use of non-simulation approaches in estimating vehicle requirements in an automated guided based transport system[END_REF]- [START_REF] Chawla | Material handling robots fleet size optimization by a heuristic[END_REF]; 3) Deterministic operations research models including linear and integer programming [START_REF] Maxwell | Design of automatic guided vehicle systems[END_REF]- [START_REF] Rajotia | Determination of optimal AGV fleet size for an FMS[END_REF]; 4) Stochastic models including queuing theory [START_REF] Tanchoco | Determination of the total number of vehicles in an AGV-based material transport system[END_REF]- [START_REF] Koo | Estimation of part waiting time and fleet sizing in AGV systems[END_REF].

The seminal paper of Egbelu [START_REF] Egbelu | The use of non-simulation approaches in estimating vehicle requirements in an automated guided based transport system[END_REF] calculates the number of robots in the fleet by dividing the total operating time by the time limit. Although this model takes into account several constraints (empty circulation of vehicles, number of loading / unloading stations per zone, etc), it is optimistic as waiting times are not taken into consideration. [START_REF] Choobineh | Fleet sizing of automated guided vehicles: a linear programming approach based on closed queuing networks[END_REF] presents an analytical model to estimate the size of an AGV fleet in a Closed Queuing Network (CQN) system. This model is based on linear programming in order to minimize the number of robots required. A comparison part was presented in order to compare the analytical results with those found by simulation. In addition, [START_REF] Vivaldini | Integrated tasks assignment and routing for the estimation of the optimal number of AGVS[END_REF] treats the problem of sizing an AGV fleet in a warehouse. The goal is to solve this problem while ensuring efficient assignment of tasks and minimum operational cost. The study is carried out on two warehouse configurations. It consists in initially estimating the number of robots to calculate the total service time, the distance traveled by each robot and the number of tasks for each robot. Then a meta-heuristic on the initial solution is implemented in order to optimize the size of the fleet.

More recently, [START_REF] Chawla | Automatic guided vehicles fleet size optimization for flexible manufacturing system by grey wolf optimization algorithm[END_REF] deals with the problem of sizing a robot system in a FMS (Flexible Manufacturing System) with the aim of optimizing the fleet size of robots for FMS with different dimensions. The authors compare the results obtained by an analytical model and by a Grey wolf optimization algorithm for three different sizes of FMS. [START_REF] Chawla | Material handling robots fleet size optimization by a heuristic[END_REF] tackle the same problem with a particle swarm optimization algorithm.

Contributions: All papers deal with the problem of sizing a homogeneous fleet of robots, that is, a fleet of identical robots. The notion of heterogeneity has not been addressed in any of these works. Through this paper, we deal with the problem of sizing a fleet of heterogeneous robots in a logistics warehouse.

In section II, we treat the problem with a set of homogeneous loads to be transported and show that it is nearoptimal to use a single type of robots. In section III, we assume that the loads are heterogeneous. In both models, we formulate our problem as an Integer linear program (ILP) to optimize the fleet size based on the cost expressions of each configuration.

II. TRANSPORT OF HOMOGENEOUS LOADS

In this part, we want to determine the size of a heterogeneous fleet of robots allowing the transport of homogeneous loads from a zone A to a zone B.

Assumptions and notations

We will make the following assumptions:

-The robots are stored at point A; -The transport is unitary: each robot carries at most a single load at a given time; -The loads to be transported are always available and there is no waiting time before loading and unloading; -Deadlock during travel and idleness of robots are not taken into account; -The battery charging problem is not taken into account.

We will use the following notations :

• n: number of homogeneous loads to transport • D: round trip distance between A and B • T : time limit

p k = D 2 • 1 v k l + 1 v k e + t k l + t k u • Cost structure :
α k : fixed cost per robot linked to the hardware part of the system (connectors, chargers, batteries, etc.). β k : fixed cost linked to the type k of robots used, independent of the number of robots. This is the software part of the system that manages the robots operations (planning, routing, etc.). γ k : cost per distance traveled by a robot of type k. The cost of a fleet of m k robots of type k to carry n k loads is

C k (m k , n k ) = α k m k + β k 1{m k > 0} + γ k n k D
The cost of a fleet of K types of robots is then

C( - → m, - → n ) = K k=1 C k (m k , n k ) = K k=1 (α k m k + β k 1{m k > 0} + γ k n k D)
where

- → m = (m 1 , • • • , m K ) and - → n = (n 1 , • • • , n K ) A.

ILP formulation

We use the following indexes :

-i = 1, • • • , n : loads -j = 1, • • • , n : robots (there are at most n robots) -k = 1, • • • , K : robots types
We can formulate our problem by an ILP. Using the following binary variables:

x ijk =    1 if the load i is carried by the robot j of type k 0 otherwise y jk = 1 if the robot j is of type k and is used 0 otherwise z k = 1 if a robot of type k is used 0 otherwise
Therefore, we have :

m k = n j=1 y jk n k = n i=1 n j=1
x ijk

The optimization problem can then be written as an ILP :

C * = min   K k=1   α k n j=1 y jk + β k z k + γ k D n i=1 n j=1 x ijk     s.t. n j=1 K k=1 x ijk = 1 ∀i (1)
K k=1 n i=1 x ijk • p k ≤ T ∀j (2)
x ijk + x i jk ≤ 1 ∀i , ∀i , ∀j , ∀k = k (3) y jk ≥ x ijk ∀i , ∀j , ∀k (4)
z k ≥ x ijk ∀i , ∀j , ∀k (5)
x ijk ∈ {0, 1} , y jk ∈ {0, 1} , z k ∈ {0, 1} (6)
Constraints meaning :

-Constraint (1) : each load must be carried by only one robot -Constraint (2) : each robot must be able to transport all the loads assigned to it within the time limit T -Constraint (3) : each robot j is of a single type k -Constraint (4) : if a load i is carried by a robot j of type k, this robot is used -Constraint (5) : if a load i is carried by a robot of type k, robots of type k are used B. Heuristic : Using a single type of robot

As a simple heuristic, we propose-to use a single type of robot, the one that minimizes the cost. If we only use robots of type k, the optimal cost is, according to [START_REF] Rjeb | Fleet-sizing of robots in a logistics warehouse -Transport operation between reception area and storage area[END_REF],

C * k = C k (m * k , n) with m * k =     n T p k    
.

It follows that

C * k = α k     n T p k     + β k + γ k nD
The heuristic consists in choosing a type of robot k minimizing

C * k , i.e. k ∈ arg min k∈{1,••• ,K} C * k .
The heuristic cost is therefore :

C + = min k∈{1,••• ,K} C * k .
We can, through a simple example, show that this heuristic is not always optimal. Table I presents a counterexample with 2 possible types of robots and 3 loads.

(n = 3, T = 10, K = 2) k p k α k β k γ k 1 6 3 0 0 2 4 5 0 0
Table II presents the optimal solutions according to authorized types of robots. In the above example, the optimal solution is to use both types of robots.

C. Relaxation

If we relax the integrity constraint on the number of robots and loads carried by a robot, we show that it is then optimal to use only a single type of robot. If the number of loads and robots can be real numbers, the number of robots m k can be expressed as a function of the number of loads carried by robots of type k:

m k = n k • p k T (7)
The cost of a fleet with m k robots of type k can then be expressed as

C k (m k ) = α k + γ k D T p k m k + β k z k = δ k m k + β k z k where δ k = α k + γ k D T p k .
The optimization problem can then be formulated as a MIP (Mixed Integer Programming) :

C -= min K k=1 δ k m k + β k z k (8) s.t. K k=1 m k p k ≥ n T ( 9
)
nz k ≥ m k ∀k = 1, • • • , K (10)
m k ≥ 0, z k ∈ {0, 1} ∀k = 1, • • • , K (11)
Constraints meaning :

-Constraint ( 9) : the number of robots must carry all the loads in the time limit T -Constraint (10) : if a load is carried by a robot of type k, robots of type k are used If we use robots of type k only, the optimal number of robots is

m * k = np k T
and the minimum cost is then

C * k = C k (m * k ) = n T δ k p k + β k
The following theorem establishes that it is optimal to have a homogeneous fleet of the type minimizing C * k .

Theorem 1: In the relaxed problem, it is optimal to use a single type of robots and the optimal cost is

C -= min k∈{1,••• ,K} n T δ k p k + β k .
Proof : : We first prove the result in the case where β k = 0 before relaxing this assumption.

β k = 0 : Suppose that β k = 0 for all k. Let u ∈ arg min k C * k and let - → m = (m 1 , • • • , m K ) be a feasible solution such that m u > 0 and m v > 0 with v = u.
By definition we have

C * u ≤ C * v . This implies that δ u p u ≤ δ v p v . Note also that robots of type v carry n v = mvT pv loads. Let - → m = (m 1 , • • • , m K ) be another feasible solution,
identical to -→ m except that the n v loads carried by robot of types v are now carried by robots of type u. More precisely :

m v = 0 m u = m u + n v p u T = m u + p u p v m v m k = m k , ∀k = u, v
The cost of solution -→ m is then

C( - → m ) = C( - → m) + δ u p u p v m v -δ v m v (12) = C( - → m) + (δ u p u -δ v p v ) m v p v (13)
≤ C( - → m) (14)
since

δ u p u ≤ δ v p v .
We have therefore built a solution -→ m of lower cost than -→ m, not using v robots. We can repeat the above process for all types of robots. We deduce that it is optimal to use only robots of type u.

β k ≥ 0 : Consider the more general case. Let a feasible solution - → m = (m 1 , • • • , m K ) with m u > 0 and m v > 0,
u = v, and as δ u p u ≤ δ v p v . The cost associated with robots of types u and v is then

C u (m u ) + C v (m v ) = δ u m u + δ v m v + β u + β v
From what has been shown previously (β k = 0), there is a solution using m u robots of type u, and no robots of type v, of lower variable cost (δ u m u ≤ δ u m u + δ v m v ). We have then

C u (m u ) + C v (m v ) ≥ δ u m u + β u + β v ≥ δ u m u + β u = C u (m u )
So we built a solution using only one type of robot and lower cost. We conclude that there is an optimal solution using a single type of robot.

D. Heuristic asymptotic optimality

We show that the heuristic introduced in Section II-B works very well when it is necessary to use a large number of robots and each robot is carrying a lot of loads. We first remind some notations :

• C * : optimal cost • C * k : optimal cost if we restrict ourselves to robots of type k • C + = min k C * k : heuristic cost • C -: optimal cost

in continuous approximation

The heuristic solution being a feasible solution of the ILP, the cost of the heuristic is an upper bound of the optimal cost. The continuous approximation also provides a lower bound of the optimal cost. So we have C -≤ C * ≤ C + which implies that

1 ≤ C + C * ≤ C + C -. (15)
Remind that

C -= min k α k np k T + β k + γ k nD (16)
C + = min k α k     n T p k     + β k + γ k nD (17)
If T is a multiple of p k and n is a multiple of T p k , then C -= C + = C * and the heuristic is optimal.

Otherwise, we can upper-bound the error by using the fact that x -1 < x ≤ x and that x ≤ x < x + 1. We have then

np k T ≤     n T p k     ≤ n T p k -1 + 1
which can be rewritten as

np k T ≤     n T p k     ≤ np k T 1 1 -p k T + T np k (18)
Note that the term T tends to 0 and T np k tends to 0.

Noting p min = min k p k and p max = max k p k and using the equations ( 15)-( 18), we have

C + C * T pmax →∞ ----------→ np min T →∞ 1
Consequently, the heuristic cost will be close (in relative value) to the optimal cost if the following conditions are met:

the number of robots required is large : n pmin T >> 1; -Each robot can carry many loads within the time horizon: T >> p max .

III. TRANSPORT OF HETEROGENEOUS LOADS

In this part, we extend the approach to the case of heterogeneous loads.

A. Assumptions and notations

We use the following notations:

• n : total number of loads

= D 2 • 1 v gk l + 1 v k e + t k l + t k u
We have the following relations for the numbers of loads:

n = G g=1 n g = K k=1 G g=1 n gk and n g = n i=1
w ig

For this transport model, we keep the same cost modeling as in the previous section. We therefore have the following expression describing the total cost :

C( - → m, - → n ) = K k=1 α k m k + β k 1{m k > 0} + γ k G g=1 n gk D
We use the following indexes :

-i = 1, • • • , n : for loads -j = 1, • • • , n : for robots -k = 1, • • • , K : for robots types -g = 1, • • • , G : for loads types

B. ILP formulation

We can formulate our ILP using the following binary variables : x ijk + x i jk ≤ 1 ∀i, i , ∀j, ∀k = k (22)

x ijk =    1 if
y jk ≥ x ijk ∀i, ∀j, ∀k (23)
z k ≥ x ijk ∀i, ∀j, ∀k (24)
x ijk ∈ {0, 1}, y jk ∈ {0, 1}, z k ∈ {0, 1}

Constraints meaning :

-Constraint (20) : each load must be carried by only one robot -Constraint (21) : each robot must be able to transport all the loads assigned to it in the time limit T -Constraint [START_REF] Mantel | Design and operational control of an AGV system[END_REF] : each robot j is of a single type k -Constraint (23) : if a load i is carried by a robot j of type k, this robot is used -Constraint (24) : if a load i is carried by a robot of type k, robots of type k are used

IV. CONCLUSIONS

This paper presents a fleet-sizing problem with several types of robots in a logistics warehouse. We show that the problem can be formulated by an integer linear program. In the case of homogeneous loads, we consider a relaxation of the problem under which it is optimal to use a single type of robot. We also show that it is near-optimal to use a single type of robots when the number of required robots is large

Fig. 1 .

 1 Fig. 1. Optimal solution of the instance with two types of robots

  to 1 when simultaneously p k

y

  the load i is carried by the robot j of type k 0 otherwisey jk = 1 if the robot j is of type k and is used 0 otherwise z k = 1 if a robot of type k is used 0 otherwiseOur optimization problem is then written : jk + β k z k + γ k D

x

  ijk • p gk • w ig ≤ T ∀j(21)

and each robot can carry many loads within the time horizon. An avenue for research would be to consider stochastic cycle times.


Martin Rodriguez-Vega
email: martin.rodriguez-vega@gipsa-lab.fr

Carlos Canudas
email: carlos.canudas-de-wit@gipsa-lab.fr

Urban network traffic state estimation using a data-based approach

Keywords: Traffic density estimation, Sensor location, Large networks, Turning ratios

come   L'archive ouverte pluridisciplinaire

Urban network traffic state estimation using a data-based approach

Martin Rodriguez-Vega * Carlos Canudas-de-Wit * Hassen Fourati *

INTRODUCTION

Traffic state estimation (TSE) is an important stage in the development of Intelligent Transportation Systems (ITS), as the knowledge of the evolution of traffic state variables such as flow and density for each road can be used to implement control strategies, or help in the decision taking stages for network design for better smart cities. This information can be used to calculate the mean traveling times for users, fuel consumption and vehicle emissions (important for air quality assessment), estimate the life of pavement, and many other applications. Because of this, accurate TSE is an active field in the transportation research literature [START_REF] Seo | Traffic state estimation on highway: A comprehensive survey[END_REF]].

According to Rostami [START_REF] Rostami Shahrbabaki | State estimation in urban traffic networks: A two-layer approach[END_REF], two main components of existing estimation methods are the modeling choice and the input data. The most commonly used model for traffic dynamics is the well-known Lighthill-Whitham [START_REF] Lighthill | On kinematic waves II. A theory of traffic flow on long crowded roads[END_REF]] and Richards [START_REF] Richards | Shock Waves on the Highway[END_REF]] (LWR) model, and its discrete counterpart, the Cell Transmission Model (CTM) [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF]]. This model is based on the vehicle conservation law, in addition with a empirical relationship between road density and traffic flow known as the Fundamental Diagram. In Highways, this approach for traffic state estimation is extensively used as in [START_REF] Tampère | An extended Kalman filter application for traffic state estimation using CTM with implicit mode switching and dynamic parameters[END_REF], [START_REF] Mihaylova | Freeway Traffic Estimation Within Particle Filtering Framework[END_REF], Canudas [START_REF] Canudas De Wit | Graph constrained-CTM observer design for the Grenoble south ring[END_REF], [START_REF] Canepa | Networked traffic state estimation involving mixed fixed-mobile sensor data using Hamilton-Jacobi equations[END_REF] and more recently in [START_REF] Takenouchi | Traffic state estimation and its sensitivity utilizing measurements from the opposite lane[END_REF]. The case of networks, requires additional modeling tools to describe vehicle interactions in intersections, [START_REF] Jabari | Node modeling for congested urban road networks[END_REF]. The extended version of the CTM developed in [START_REF] Daganzo | The cell transmission model, part II: Network traffic[END_REF] this problem via a flow maximization formulation under constraints provided by the fundamental diagram. This approach is widely used as can be seen in [START_REF] Lovisari | Density/Flow reconstruction via heterogeneous sources and Optimal Sensor Placement in road networks[END_REF] and [START_REF] Ladino | Density and flow reconstruction in urban traffic networks using heterogeneous data sources[END_REF].

However, the use of the fundamental diagram, specially in urban networks, is challenging as it requires the calibration of many parameters. Moreover, the presence of external factor such as traffic lights and pedestrian crossings, contradict the hypothesis of the LWR model that vehicle speed is only a function of its local density. Thus, data-based approaches that do not require a fundamental diagram have been proposed. The main tool in many methods, is to use probe vehicle that periodically send information about traffic conditions such as speed and headway, as showed in [START_REF] Bekiaris-Liberis | Highway Traffic State Estimation with Mixed Connected and Conventional Vehicles[END_REF], [START_REF] Wright | Fusing loop and GPS probe measurements to estimate freeway density[END_REF] for Highways and Rostami Shahrbabaki et al. (2020) in networks. These methods show promising results, but in some applications individual traces of probe vehicles might not be available due to privacy regulations.

In addition to these approaches, developments in new sensing technologies make available new information sources that can be used in TSE approaches. [START_REF] Abbott-Jard | Empirical evaluation of Bluetooth and Wifi scanning for road transport[END_REF]; [START_REF] Bhaskar | Fundamental understanding on the use of Bluetooth scanner as a complementary transport data[END_REF] proposed the use of WiFi and Bluetooth scanners for the evaluation of traffic conditions, and for the estimation of road traveling times. Another data source are mobile phone networks, which have been studied by [START_REF] Derrmann | How Road and Mobile Networks Correlate: Estimating Urban Traffic Using Handovers[END_REF]; [START_REF] Li | Urban arterial traffic status detection using cellular data without cellphone GPS information[END_REF]. Moreover, GPS traces of probe vehicles, also known as Floating Car Data (FCD) [START_REF] Treiber | Traffic flow dynamics: Data, models and simulation[END_REF]] can be more easily obtainable as they can be ensured to protect user privacy.

Our contribution in this paper is the proposal of a databased traffic state estimation method for general urban networks that requires little knowledge of input parameters. We make use of three different data sources: station-ary flow sensors, vehicle and FCD. Data provided by these sources is used to estimate the external inflows to a traffic network, the turning ratios for a selection of intersections, and the space mean speed of the road sections of the network. We take into account economical constraints by proposing a flexible sensor location scheme that identifies the optimal locations to measure the turning ratios. The results of the proposed methods are tested using microsimulations.

This paper is organized as follows. Section 2 defines the traffic variables and traffic evolution model that are used throughout the paper, and proposes an estimator for the density of each road of a traffic network. Section 3 discusses the location of different sensor technologies required by the estimator, and proposes a method to identify the most critical locations to instrument with sensors in order to reduce estimation error. Section 4 presents the use of simulated data to evaluate the performance of the models and algorithms described in the paper. Section 5 ends the paper with a conclusion.

MODEL

We define a traffic network as a directed graph G = {N, E} where the nodes N ⊂ N correspond to intersections and junctions, and the edges E ⊂ N × N correspond to road sections. Additionally, for every road section i, there are associated parameters such as the road length i , number of lanes Γ i , and maximum velocity v max i .

The traffic state refers to the collection of road densities, inflows and outflows for all roads, which we denote with vectors ρ(t), ϕ in (t), ϕ out (t) ∈ R |E| . Traffic dynamics are governed by the conservation law d dt

ρ(t) = L -1 (ϕ in (t) -ϕ out (t)) (1)
where L is a diagonal matrix containing the road lengths, i.e., L = diag( ).

Intersections are modeled as 0 dimensional points that do not store vehicles. To model the exchange of inflows and outflows of the different roads at the intersections we use the parameters called turning ratios. Let I(n) be the set of incoming roads to some intersection n ∈ N and O(n) be the set of outgoing roads from n. A turning ratio r i,j for i ∈ I(n) and j ∈ O(n) defines the proportion of vehicles exiting i that enters j. As intersections do not store vehicles, then the conservation of density implies that

j∈O(n) r i,j = 1 , ∀n ∈ N ∀i ∈ E \ E out (2)
where E out are outgoing roads at the boundary of the network, hence have no downstream roads. Let R ∈ R |E|×|E| be the turning ratio matrix with elements r i,j .

If there is no connection between roads i, j, then r i,j = 0. The input flows of each section can be expressed as a linear combination of the output flows of the preceding sections.

ϕ in (t) = R ϕ out (t) + ϕ ext (t)
(3) where ϕ ext (t) corresponds to the external inflows (also known as the input demands), which are the incoming flow for the roads which are at the boundaries of the network. Combining eqs. ( 1) and (3), we have

d dt ρ(t) = L -1 (R -I)ϕ out (t) + L -1 ϕ ext (t) (4)
Define v i (t) as the space-mean speed of road i, that is, the average of the speeds of vehicles inside road i at time instant t. Denote v(t) as the speed vector with elements v i (t). Using the hydrodynamic relation, we can approximate the outflows as ϕ out (t) ≈ V (t)ρ(t) (5) where V (t) = diag(v(t)). This relation applies accurately when considering very short distances, or when the spatial variations in vehicle speed and density is negligible. We make the following assumption, Hypothesis 1. The speed and density throughout a road section do not vary significantly in the spatial domain.

Therefore, (4) can be rewritten as

d dt ρ(t) = L -1 (R -I)V (t)ρ(t) + L -1 ϕ ext (t) (6) Consider the open-loop estimator d dt ρ(t) = L -1 ( R -I) V (t) ρ(t) + L -1 ϕ mea (t) (7)
where R, V (t), ϕ mea (t) are the measured turning ratios, road velocities, and flows, respectively. The measurement process is described in Section 3.

SENSOR LOCATION AND INPUT DATA

The use of the dynamic model ( 7) requires the knowledge of the turning ratio parameters r i,j , the measurement of space-mean speeds v(t), and flow measurements. We consider the following sources of information:

Floating car data

Consider that a fraction of the vehicles in the network are equipped with devices (e.g. a GPS navigator) that periodically report to a centralized server information about the vehicles trajectory, such as its position and velocity at a given time via FCD. However, because of privacy policies, only aggregated variables and not the raw vehicles are available.

Define by V i (t) the set of vehicles indexes that provide FCD that are inside road i at time t. The total number of vehicles in i cannot be estimated with this information as the penetration rate of vehicles that provide FCD is unknown. However, as the velocity of a vehicle is affected by the velocities of surrounding vehicles, this can be used to estimate the space-mean speed of the section. Let ν α be the speed of a vehicle indexed by α. We define the aggregated speed for road section i from FCD data by

v FCD i (t) = 1 |V i (τ )| α∈Vi(t) ν α (t) (8)
We assume in what follows that the aggregated speeds are available for all roads. In the case where the information is not available for some roads due to a lack of reporting vehicles, we use the value of the maximum speed (or speed limit) v max . Moreover, as the FCD speeds are direct measurements of the space-mean speed, we consider

V (t) = V (t) (9)

Stationary counting sensors

Counting sensors such as cameras, induction loops, radar, and others, are the most commonly used way to obtain traffic information. These sensors are placed in a fixed position in a road section, and collect information of the vehicles passing through that point. The collected data varies according to the technology, but generally variables such as length, speed, and time of passage are recorded. In some applications, technical constraints allow only aggregated data to be accessible, such as the total number of vehicles observed during a time interval, from which flow in the road section can be estimated.

We consider that sensors are located in the incoming roads at the boundary of the network, such that the external flows ϕ ext (t) are measured directly, ϕ mea (t) = ϕ ext (t) (10)

Turning ratio measurements

Turning ratio information can be obtained by different ways. One option is the use of vehicle identifier sensors such as Blutooth or WiFi taggers, and license plate readers can be located at the incoming and outgoing roads of intersections, such that an approximate count of the number of vehicles making each turn is obtained. Another option is manual collection of data during time periods, and extrapolate the recollected data for all times. However, using any of these methods for all intersections is unfeasible, as budgetary limits can be surpassed in networks with more than a few intersections.

Another approach is to use a priori values for these parameters, which are calculated using only the physical characteristics of the network with ad hoc heuristics, and can be used as working values to provide estimates. This however introduces large sources of error, as the a priori values can be very far from the real parameters. Nevertheless, this error can be reduced by measuring a selection of intersections.

Suppose that a limited number of sensors are available.

The selection of intersections should be done optimally to minimize the error in density estimation caused by deviations between the real and estimated turning ratios.

For this, we propose a method to identify the intersections that generate the highest error given some perturbations in its turning ratios.

Estimation error Let ri,j be the a priori value proposed for some turning ratio. Let the deviation between this and the actual value be given by ξ i,j such that, ri,j = r i,j + ξ i,j (11) The deviations ξ i,j will cause an error in the state estimation e(t) = ρ(t) -ρ(t). ( 12) Define R and Ξ as matrices with elements ri,j and ξ i,j , respectively. Note that R = R + Ξ. To quantify the sensitivity of the turning ratios in the error, we neglect the effects of time variations of the external flows and velocities, that is V (t) = V and ϕ ext (t) = ϕ ext . We want to express the effect of the turning ratio perturbations Ξ in the reconstruction error e(t). To simplify the notation, let M = (I -R )V and M = (I -R )V , such that M = M -Ξ V . Under the assumption that section speeds are constant, the dynamics ( 6) and ( 7) become time-invariant, for which a closed-form solution is known,

ρ(t) = e -L -1 M t ρ(0) + t 0 e -L -1 M τ d L -1 ϕ ext ρ(t) = e -L -1 M t ρ(0) + t 0 e -L -1 M τ d L -1 ϕ ext (13)
Therefore, the error can be written explicitly as

e(t) = e -L -1 M t ρ(0) -e -L -1 M t ρ(0) + t 0 e -L -1 M τ -e -L -1 M τ dτ L -1 ϕ ext (14)
In Rodriguez-Vega et al. ( 2019), we showed that I -R is an invertible M-matrix, with all eigenvalues having positive real parts. Therefore, it can be shown that -L -1 M has eigenvalues with negative real parts, so it is a stable matrix. Thus, the asymptotic error is

e = lim t→∞ e(t) = (M -1 -M -1 )ϕ ext (15)
where we have used the facts that the exponential function of a stable matrix goes to zero as time goes to infinity, and that

∞ 0 e At dt = -A -1 (16)
for any stable matrix A.

Sensitivity of turning ratio deviations Suppose that the deviations ξ i,j are small, and that we want to calculate the error resulting from small nudges in a single value,

∂e ∂ξ i,j = ∂ ∂ξ i,j (M -1 -M -1 )ϕ ext = - ∂ ∂ξ i,j M -1 ϕ ext (17)
Consider the following theorem. Theorem 2. [START_REF] Magnus | Matrix Differential Calculus with Applications in Statistics and Econometrics[END_REF]) Let A(t) be an invertible matrix that depends on a scalar parameter t.

Then, dA -1 dt = -A -1 dA dt A -1 (18)
Using Theorem 2, ( 17) can be written as

∂e ∂ξ i,j = M -1 ∂Ξ ∂ξ i,j V M -1 ϕ ext (19)
Assume that the turning ratio deviations are independent from each other. Thus,

∂Ξ ∂ξ i,j = u j u i (20)
where u i is the i-th column of the identity matrix of suitable dimensions. Hence,

∂e ∂ξ i,j = M -1 u j u i V M -1 ϕ ext (21)
Selection of intersections Consider an intersection n ∈ N with incoming roads I(n) and outgoing roads O(n). Let ξ i = {ξ i,j } j∈O(n) for each i ∈ I(n). To quantify the effect of the perturbations ξ i,j on the error e we propose the following procedure:

(1) Calculate the Jacobian matrix

J i = ∂e ∂ξ i (22)
for each incoming road i ∈ I(n).

(2) Calculate the error "energy" due to perturbations in the turning ratios of i using the Frobenius norm of the Jacobian,

||J i || 2 F = k∈E j∈O(n) ∂e k ∂ξ i,j 2 . ( 23
)
(3) Calculate the intersection weight as the total error energy due to its incoming roads,

w n = i∈I(n) ||J i || 2 F ( 24
)
(4) Locate the available sensors in intersections with the highest values of w n .

Note that the intersection weight can be simplified to

w n = i∈I(n) j∈O(n) k∈E   p∈E M -1 k,j M -1 i,p v i ϕ ext p   2 (25)
This heuristic procedure is a greedy approach as it assumes that deviations in the turning ratio values are independent from each other.

SIMULATION AND VALIDATION

To evaluate the performance of the estimator, we consider a zone of downtown Grenoble, France, as seen in Fig. 1.

The traffic state was obtained by simulating vehicle traces using the well-known microscopic traffic simulator Aimsun presented in [START_REF] Barceló | Dynamic Network Simulation with AIMSUN[END_REF]. This software models the position, speed and acceleration of each vehicle according to the interaction with the other vehicles in each section and intersection. The real network layout was recreated in Aimsun as shown in Fig. 2. The layout contains information about the number of lanes, speed limit, direction, possible turns at intersections, and length. Note: the simulated layout does not contain traffic lights. To run the simulation, an arbitrary but realistic timevarying flow profile was applied at the network incoming boundaries. The turning ratios were set arbitrarily using the following formula

ri,j = v max j Γ j k∈O(n) v max k Γ k (26)
where Γ i is the number of lanes of road i. This heuristic formula is based on the intuition that roads with higher capacity receive a higher vehicle count.

As outputs of the simulation, the position and speed of all vehicles were recollected, at each time instant. To deploy the estimator (7), average road speeds where calculated using (8) directly from vehicle traces. The input flows at the network boundaries ϕ ext (t) where also calculated directly by counting the number of vehicles entering these roads during a time interval of 10 minutes. For validation, the ground-truth density of road i is calculated as the average number of vehicles in the road during a time interval

ρ i (t) = 1 i ∆t t t-∆t |V i (τ )|dτ. ( 27
)
Furthermore, the ground-truth flow for road i is obtained from counting the number of vehicles that exited the road during the time interval ∆t.

First, we consider the case where all turning ratios are known, R = R. Figure 3 shows the evolution of the real and estimated densities for one particular road of the network. For this road, the density estimates follow closely the real values, whereas the flow is underestimated. In both cases, the real values present peaks of high variations, which are due to the effect of individual vehicle behavior, which are unable to be captured by the macroscopic model in Section 2. For evaluation, we consider the metrics Mean Error (ME) and Relative Mean Error (RME) for road i, defined as

ME ρ i = 1 T T 0 (ρ i (t) -ρi (t))dt (28)
RME ρ i = ME ρ 1 T T 0 ρ i (t)dt (29)
which measure the deviation between the mean trajectories of the real and estimated quantities, and the metrics Absolute Error (AE) and Relative Absolute Error (RAE), defined as

AE ρ i = 1 T T 0 |ρ i (t) -ρi (t)|dt (30) RAE ρ i = AE ρ i 1 T T 0 ρ i (t)dt (31)
which measure the total error between the two trajectories, as it not only consider the difference between their means, but also the higher frequency variations of one signal respect the other.

Figure 4 shows the Cumulative Distribution Function (CDF) for the RME and RAE for flow and density. This is the percentage of roads that have an error less than As a second scenario, we consider the case where the turning ratios in the simulation do not coincide with the estimates in eq. ( 26). This was done by adding noise to all turns, with a uniform distribution between -10% and 10% around the a priori estimates. To include turning ratio measurements, a set of intersections was selected using the approach described in Section 3.3.

Fig. 5 shows the distribution of the intersection sensitivity using the a priori values and maximum values of the input demands and road velocities, which are known. Note that the sensitivity weight decreases very quickly, so it is expected that diminishing returns will be observed as more sensors are located. Thus, a few number of intersections could provide a value trade-off. As an illustrating example, 20 intersections are selected such that the turning ratio for each turn is measured directly, which is approximately a 4% of the total intersections. Fig. 6 shows the location of the turning ratio sensors. Figure 7 shows the resulting CDF of the error in the density estimation. For comparison purposes, the results are also shown for the base case where no turning ratios in intersections are measured, and the best-case scenario where all turning ratios are known. As expected, allratios-known case out-performs significantly the other methods, specially in the ME. Nevertheless, this case is generally unfeasible due to practical and budgetary limitations. In contrast, the no-measurements case is the worst case scenario, and gives a lower-bound to the error. The error obtained using the proposed sensor location scheme presents an improvement of around 3% when compared with the base case.

CONCLUSION

In this paper, we proposed a method to estimate the dynamical evolution of flow and density in large urban traffic network by using heterogeneous data sources: counting sensors, turning ratio measurements, and floating car data.

The method requires little parameters to be known, as there is no explicit modeling of the road outflows in terms of the current density, so no Fundamental Diagram is required. However, the knowledge of the turning ratios for every intersection is required. To simplify this requirement, we introduce a turning ratio sensor location scheme that takes as input a priori values for these parameters to identify the intersections for which small perturbations in the turning ratio values would generate the highest error. We tested the proposed methods using microsimulations over the city of Grenoble. The results show that the estimator performs well, as it is able to reconstruct the overall trajectory of the traffic state and has many roads presenting little errors. The approaches we propose are also flexible, as they can be applied for varying budgets. In addition, the approach allows the inclusion of new data, so the previous information can be used to improve the location of turning ratio sensors to increase the performance of the estimator.

Fig. 1 .

 1 Fig. 1. Traffic network in Downtown Grenoble.

Fig. 2 .

 2 Fig. 2. Simulated layout of the Grenoble downtown zone in Aimsun.

Fig. 3 .

 3 Fig. 3. Time series for the trajectories of the real and estimated density and flow for one road.

Fig. 4 .

 4 Fig. 4. CDF of the RME and RAE for flow and density.

Fig. 5 .

 5 Fig. 5. Sensitivity weight of each intersection. Intersection identifiers were sorted according to the weight.or equal to a given value. Note from the figure that overall, the mean trajectory of the vehicles is correctly reconstructed: 90% of the roads present an error less than 8%. The AE shows the effect of the high variability of individual vehicle decisions, which increases the error to 40% for 90% of the roads. Note that the results for flow and density have approximately the same performance.

Fig. 6 .

 6 Fig. 6. Location of turning ratio sensors. Green nodes represent unmeasured intersections, whereas nodes in dark-red are the measured ones.

Fig. 7 .

 7 Fig. 7. Relative error for the density reconstruction according to turning ratio information.


Nicolas Piluso

Gabriel Colletis

A Keynesian reformulation of the WS-PS model: Keynesian unemployment and Classical unemployment

Keywords: bargaining, trade unions, wages, unemployment, previous demand. JEL Codes: J01. J60. J88

published or not. The documents may come

A Keynesian reformulation of the WS-PS model: Keynesian unemployment and Classical unemployment

Introduction

The WS-PS model [START_REF] Layard | Unemployment, macroeconomic performance and the labour market[END_REF] is the macroeconomic expression of a set of microeconomic models accounting for an endogenous rigidity of real wage rates and the appearance of what is known as "involuntary" unemployment. It can be regarded as the New Keynesian response to the natural rate of unemployment (NRU) devised by Friedman and the monetarists (which, in turn, was a criticism of the neo-Keynesian interpretation of the Phillips curve). While the NRU is based on the assumption of perfect competition, the nonaccelerating inflation rate of unemployment (NAIRU) is based on the assumption of imperfect markets, in the same wat as the (equivalent) concept of Imperfect Competition Equilibrium (ICE) rate of unemployment identified by the WS-PS model. However, several criticisms have been evoked against this model [START_REF] Blanchard | Why is Unemployment so high in Europe? Beyond the natural rate hypothesis[END_REF]Sterdyniac, 1998, Zajdela and[START_REF] Laurent | Emploi, salaire et coordination des activités[END_REF][START_REF] Piluso | Chômage et marché financier[END_REF][START_REF] Lavoie | Postkeynesian economics : new foundations[END_REF].

In our opinion, it is necessary to reformulate the model by reintroducing some of Keynes' most fundamental teachings on the theory of unemployment. First of all, we need to reaffirm the hypothesis of an asymmetry between employers and employees [START_REF] Glustoff | On the existence of a Keynesian Equilibrium[END_REF][START_REF] Cartelier | Chômage involontaire d'équilibre : Asymétrie entre salariés et nonsalariés, la loi de Walras restreinte[END_REF][START_REF] Piluso | Chômage involontaire et rationnement du crédit : une relecture de la relation salaire-emploi[END_REF], thus restoring the role of the principle of effective demand in determining the level of employment. We aim to show that the equilibrium unemployment rate as determined in the traditional WS-PS model is only one case among many others, including the more general model presented here which incorporates the possibility of equilibria in Keynesian involuntary unemployment. The originality of our article is that it gives an account of Classic unemployment and Keynesian unemployment without making the assumption of fixed prices as in the literature of the 1960s and 1970s [START_REF] Barro | A general disequilibrium model of income and employment[END_REF]Clower,1965). Layard's WS-PS model is certainly a flexible price model, but, as discussed here, it cannot account for truly Keynesian unemployment.

Therefore, the theoretical challenge here is to account for Keynesian and classical unemployment in the same model (which is impossible with the traditional WS-PS model) in the absence of a fixed price assumption (unlike the Barro and Grossman model).

First, we justify our approach to the reformulation of the WS-PS model by highlighting some of the criticisms that have been made against this model. Secondly, we explain our methodology for introducing involuntary unemployment following the teachings of Keynes in General Theory. In a third step, we outline the structure of the model. Finally, in a fourth section, we highlight the properties of the model.

1.

Justification of our approach: some criticisms of the traditional WS-PS model

In the WS-PS model of Kyotaki and Blanchard (1987), Keynesian economic policies have no effect on employment levels. This is highlighted by [START_REF] Laurent | Emploi, salaire et coordination des activités[END_REF]. Let is suppose an expansionary Keynesian monetary policy aimed at increasing the level of employment. What happens when there is an increase in the exogenous money supply M? The increase in the money supply is associated with a proportional increase in wages and prices.

As a result of this increase in the money supply, firms encounter a rise in demand for goods, as shown by ( 15). All firms want to increase their relative price (as shown in equation (12')) and the way to do this is to increase their own price. Since all firms behave in the same way, the real money supply gradually decreases until it is equivalent to its starting value. Once this process is complete, the supply and demand for goods return to their original levels. Employment remains at the same level. It depends only on the parameters of the firm's technology, consumer preferences, and imperfect competition in the goods market.

Kyotaki and Blanchard show that it is only by introducing nominal price rigidities that money becomes active. If prices do not adjust in the short run because the cost of changing them is too high, then the exogenous increase in the money supply leads to a change in the real cash position that increases the demand for goods and the level of employment. However, this effect can only be transitory. Once the price of goods adjusts, real cash flow and aggregate income return to their initial levels.

However, the "menu costs" hypothesis is not based on explicit microeconomic foundations and can be considered as ad hoc. In this perspective, [START_REF] Laurent | Emploi, salaire et coordination des activités[END_REF] assert that the New Keynesians have reached a threefold impasse with this model:

 technical, because the ad hoc nature of the "menu costs" hypothesis appears indisputable;  methodological, because the New Keynesians have finally shown that real wage rigidity is necessary to obtain unemployment;  empirical, because these models are not validated by the facts.

In view of this impasse, O. [START_REF] Blanchard | Why is Unemployment so high in Europe? Beyond the natural rate hypothesis[END_REF] contest the merits of the "new labour market theories" and the WS-PS model which is their macroeconomic expression. To defend their point of view, these authors consider the case of the United Kingdom. They argue that the new labour market theories are invalid since they are incorrectly based on the belief that economies would return to their "natural" unemployment rates after disinflation (O. [START_REF] Blanchard | Why is Unemployment so high in Europe? Beyond the natural rate hypothesis[END_REF]. Indeed, nine years after the start of this economic policy in the UK, accompanied moreover by a liberalization of the labour market, the unemployment rate had risen very sharply: from 5% in 1979 to 11.6% in 1988.

The WS-PS model suggests that factors of a structural nature affecting free competition in the labour market are at the origin of "equilibrium" unemployment. However, the policy of the Thatcher government was to liberalize the labour market in depth through attacks on trade union power, limitations on the actions of the welfare state and changes in labour legislation. Yet the UK experienced more unemployment between 1979 and 1987 than in the forty years preceding the 1980s. Marc Lavoie (1998) makes the same observation with regard to the empirical tests of the WS-PS model applied to the case of France. Theoretical models attribute responsibility for increases in the long-term equilibrium unemployment rate to the generosity of the unemployment benefit programmes, even though empirical tests do not validate this result. Blanchard and Summers, as well as Marc [START_REF] Lavoie | Postkeynesian economics : new foundations[END_REF], conclude that the standard framework generally used to make unemployment understandable cannot be accepted because of its lack of explanatory power. Thus, according to Sterdyniac (1998), "For these theories to explain the existence in Europe of growing mass unemployment, it would be necessary to admit that competitive imperfections in the labour market increased sharply between the 1960s and the 1990s, which is not easy to establish, given the increased flexibility of wages and jobs in Europe during the 1980s; or it must be concluded that past imperfections and rigidities have led, particularly during oil shocks, to a rise in unemployment which has gradually fossilized into equilibrium unemployment. These theories might have seemed relevant in the period 74-84, when rising unemployment in Europe was accompanied by a high level of the wage share in value added. Since then, however, the unemployment rate rose from 8.4 to 10.4 per cent in Europe between 1990 and 1994, while the wage share declined from 70.7 to 68.8 per cent. The level of wages is still difficult to incriminate" (Sterdyniac, 1998, p. 940).

Finally, the literature has challenged the involuntary nature of unemployment in the WS-PS model. For the New Keynesians, equilibrium unemployment is Keynesian unemployment in the sense that it is involuntary: "If wages are flexible, those who want to work at prevailing wages will be in work, and the remainder will be 'voluntarily unemployed'; if wages are set above market clearing levels, some of those wanting work will not get for it and they will be 'involuntarily unemployed'" (Layard and Nickell, 1991, p. 145). In other words, once workers wish to work for the prevailing real wage, but this is not directly applicable [at the place of work], there is involuntary unemployment. According to these authors, unemployment thus results from a combination of imperfect competition and markup behaviour in both the labour and goods markets (Layard and Nickell, 1991, p. 146). Piluso (2006) challenges this analysis. The involuntary nature of unemployment is debatable. Certainly, some workers would like to work at the prevailing real wage rate but remain unemployed. However, it should be borne in mind that the unemployment suffered by these agents is the result of an excessivlely high real wage level; the basis of wage rigidity is linked to the active behaviour of workers claiming excessively high wages, either through trade unions or their labour productivity. The New Keynesians thus enriched the classical theory of unemployment rather than the thinking of Keynes. This is far removed from Keynes' conjecture that the possibility of equilibrium of involuntary unemployment is due to the rejection of the second classical postulate, or, in other words, to the asymmetry between entrepreneurs and employees. Here, there is no asymmetry arising from the nature of the capital-labour relationship; on the contrary, it is asserted that workers have too much weight in the wage relationship. The asymmetry is inherent in the WS-PS-type models of an informational nature. Involuntary unemployment can disappear as soon as entrepreneurs can solve the principal/agent problem other than by raising wages.

All these criticisms lead us to consider that we need to reformulate this model in a way that is more in line with Keynes' teachings.

2. Methodology for reformulating the model: how to introduce the hypothesis of asymmetry into the wage relation? What are the consequences for the model?

Starting from the second chapter of the General Theory, Keynes rejects the second classical postulate according to which employees are able to adjust the marginal disutility of the volume of employment to the real wage rate. According to Keynes, wage earners are unable to equalize the marginal disutility of labour with the real wage: they are not on their labour curve when there is unemployment in the economy [START_REF] Cartelier | L'économie de Keynes[END_REF]. Entrepreneurs have the initiative of spending to initiate production activity and they impose their employment decision unilaterally [START_REF] Piluso | Chômage involontaire et rationnement du crédit : une relecture de la relation salaire-emploi[END_REF]. While entrepreneurs have the opportunity to maximize their profit, employees do not always have the opportunity to maximize their utility, as the level of employment decided by entrepreneurs alone may be lower than the level of employment desired by workers.

In order to model such a change of assumption in the neoclassical labour market model, Glustoff and Cartelier replace the budget constraint of employees by the demand of firms for the labour supply. Firms are thus taking control of the employee's budget constraint.

In doing so, entrepreneurs who decide on the level of employment can implement a level of production below that needed to ensure full employment. Keynes then discusses in Chapter 3 what can make this simple possibility effective. He then shows that it is the inadequacy of anticipated demand that is the cause of unemployment made possible by the asymmetry of status between entrepreneurs and employees.

Therefore, in Keynesian labour market modelling, the level of output corresponds to the aggregate demand anticipated by entrepreneurs.

Keynes' logic is therefore as follows: the anticipated global demand being known, entrepreneurs set their production level. The latter being known, employment is determined. However, as the first classical postulate is accepted by Keynes, the equality between marginal labour productivity and real wages must be verified. Therefore, since the level of employment is known, marginal labour productivity is also known.

The real wage for this volume of employment is therefore determined by marginal productivity.

Keynesian logic therefore requires that any increase in the volume of employment should be considered as a decrease in the real wage. Thus, a decrease in unemployment leads to a decrease in the real wage [START_REF] Piluso | Chômage involontaire et rationnement du crédit : une relecture de la relation salaire-emploi[END_REF].

As [START_REF] Glustoff | On the existence of a Keynesian Equilibrium[END_REF] and [START_REF] Cartelier | L'économie de Keynes[END_REF] have shown, it is quite possible to obtain Keynes' result of involuntary unemployment in a perfect competition framework. Certainly, the WS-PS model is a model of imperfect competition (both for the labour market and the goods market). In principle, the NAIRU can be reduced by reforms not only of the labour market but also the goods market. Nevertheless, as Piluso (2010) points out, "with regard to the cause of unemployment, it seems obvious that imperfect competition in the goods market is not responsible for unemployment in the WS-PS model, even if it modulates the level of unemployment. Without imperfect competition in the labour market, imperfect competition in the goods market would produce no unemployment outcome since the real wage would not suffer from any rigidity or fixity. It only reduces the level of employment" (Piluso,p.47). Moreover, it is quite possible to construct a PS curve in a context of perfect competition, while maintaining the existence of an equilibrium unemployment rate (Piluso, 2012). This is why, in order to simplify the modelling and to remain faithful to the spirit of Keynes, we make the hypothesis that the goods market is in perfect competition (which authorizes the equalization of real wages and marginal labour productivity).

Finally, the use of utility functions in our model may appear not to follow Keynes' purely macroeconomic approach. Nevertheless, we consider it is not contrary to removing the minimum number of hypotheses of standard theory so the causes of the results can be put back back into perspective. Our approach is not to produce a model which is totally faithful to Keynes' General Theory, but rather to enrich the WS-PS model with Keynesian teachings.

Construction of the model: reformulation of the PS curve and construction of the WS curve

Our model comprises two types of economic agents: the representative firm and the trade union monopoly. In the traditional WS-PS model, the firm and the union enter into a Nash bargaining game that always results in success, i.e. an agreement where a real wage is set in such a way that the product of the net gains of each stakeholder is maximized. In our model, the negotiation is not formalized by a Nash bargaining process (which maximizes the product of the participants' net gains). Our article does not claim to provide a new microeconomic model of bargaining; we simply represent the negotiations in terms of a confrontation between the reformulated WS and PS curves. Equilibrium, i.e., the point of intersection between WS and PS, is not necessarily reached. This is the originality of our approach, which contrasts with the standard WS-PS model where an equilibrium is always achieved in the negotiations.

The firm and the reformulated PS curve

The firm is assumed to have a Cobb-Douglas production function Y AL   , with Y representing the total production, L the quantity of labour units, A product per unit of labour, and  the output elasticity of labour. We consider that the production function includes only one factor because the quantity of capital used in the short run is considered fixed and does not play a determining role in the causal relations.. The effective demand principle adopted here indicates that the level of production, and thus employment, is determined by the anticipated aggregate demand for goods denoted g D . The level of production depends on the entrepreneurs' expectations and is assumed to be exogenous. The type of anticipation (rational, adaptive or other) is irrelevant for our purpose. However, the expectations can be considered rational.

We thus have:

(1)

g Y D 
From which we obtain:

(2)

1 1 g D Y L A A                
Nevertheless, Keynes adopts the first classical postulate: we should therefore check for equality between the marginal productivity of labour and real wages. However, in contrast to the traditional neoclassical approach, it is not the real wage that determines the level of employment but the opposite: since the anticipated aggregate demand is fixed, and thus also the level of employment, it follows that there is a real wage denoted here as w.

' 1 L Y w AL w      
We thus obtain a standard decreasing relationship between the level of employment and the real wage, the only change being that it is the level of employment that determines wages:

(3)

1 1 1 A w AL L w               
To obtain the labour demand curve linking real wages, w, with the unemployment rate u, we simply write:

1 L N L u N N     1
From this, given (3), we can deduce that:

1 1 A N w u N           
After rearranging the terms, we obtain:

(4) 1/1 [ ] ( (1 )) A w PS N u     
This yields the PS curve for the goods market, which reflects/?points to a positive correlation between unemployment rate and real wages.

According to [START_REF] Keynes | Théorie générale de l'emploi, de l'intérêt et de la monnaie[END_REF], the wage is the explained variable and the unemployment rate is the explanatory variable. This results from the anticipated demand for goods and so from the aggregate equilibrium product determined on the goods market as indicated by equation (2').

We find an identical logic in the models of [START_REF] Piluso | Chômage involontaire et rationnement du crédit : une relecture de la relation salaire-emploi[END_REF] and [START_REF] Cartelier | L'économie de Keynes[END_REF], who highlight the following sequence:

Anticipated demand  Level of production  level of employment  Marginal productivity of employment level  Real wage

In classical economics, the equation of the PS curve is interpreted traditionaly as follows: the real wage level explains the level of unemployment.

The trade union and the WS curve

The union utility function contains the arguments of employment level L and the real wage supplement (w-w r ), where w r denotes the reservation wage.

ln( ) ln( )

r U L w w    
This utility function is derived from the WS-PS model of Piluso and Colletis (2012), itself taken from labour economics textbooks [START_REF] Cahuc | Economie du travail[END_REF].

The parameter  represents the weight given to employment in the union's objective. This maximizes its utility with respect to the wage claim. The problem can be written:

1 1 1 1 ln( ) ln( ) . ln ln( ) 0 0 r r A A Max L w w s t L Max w w w w w w                                    
We obtain:

1 r w w w        whence (5) 1 r w w   
To plot the WS curve, let us make the standard assumption that the reserve wage of the worker (the rate below which he or she does not accept work) is equal to a weighted mean of the wage that could obtained in another firm and the unemployment benefit. Let us write:

(6) (1 ) r w u w uB   
where u is the unemployment rate, B is the unemployment benefit, and w is the average wage rate in the economy. If the worker looks for another job in the economy, the probability of finding one is (1-u), and that of being unemployed is u. At equilibrium, the negotiations in each employment area lead to the same real wage if i w =w, so, from equations ( 4) and ( 5), it can be stated that:

(6 ') [ ] u w B WS u   
This gives a WS curve for wage demand showing that unemployment rate falls as a function of real wages.

Classical and Keynesian disequilibria of the reformulated WS-PS model

The confrontation between the firm's objective (to maximize its profit) and the union's objective (to maximize its utility, which itself depends on the real wage obtained for the employees) is expressed by the ?different shapes of the PS and WS curves. The specific logic of each participant differs from and may prove impossible to reconcile with that of the others.

If the effective demand is insufficient (downturn in the economic situation), firms are in a strong position to impose wage and employment levels (Keynesian logic). The unions are unable to situate themselves on their WS curve. On the contrary, if the effective demand is high and firms cannot hire all the workforce they are looking for (buoyant activity), the

Effective demand is such that the unemployment rate is higher than the level sought by the union. Since the marginal product of labour is decreasing, this level of employment determines a real wage that is higher than that sought by the union. The disequilibrium may last for some time because completely different factors determine the employment level set by the firms and that desired by the unions: for the firm, the determining factor is the effective demand, while, for the union, it is the weight attached to employment together with the level of unemployment benefit. The only way to get back to equilibrium would be for the union to accept the employer's wishes and reduce the weight of employment in the union's objectives. Alternatively, the state can intervene in the economy to increase demand on firms.

In the case of a failure in trade union action, it is indeed the firm which unilaterally fixes the level of employment and thus the level of real wages (asymmetry hypothesis). The firm has no reason to give in to the union's demands since the firm maximises its profit. In this configuration, the firms reach their objective (they are on their PS curve), which is not the case for the unions and employees (who are unable to be on their WS curve). It is therefore a disequilibrium (and not a sub-optimal equilibrium) that can become long-lasting if the state does not intervene.

We can illustrate the situation with Figure 2. In a context of a deteriorated economic situation, the demand encountered by firms is depressed. Firms unilaterally set levels of production and employment that are low. The unemployment rate is set at the U ps level (fixed via the demand for goods by firms, according to the Keynesian principle). Since employment is known, the marginal productivity of the volume of employment determines the real wage W ps . Trade unions are unable to position themselves on their WS curve: for the actual employment volume they want a real wage W ws (lower than the actual wage W ps ), and for the wage level W ps determined on the goods market by marginal labour productivity they want the unemployment rate Uws (lower than the actual unemployment U ps )2 ,. But firms have no interest in deviating from their strategy because they maximize their profit. The State must necessarily intervene to increase the demand for goods and thus the levels of production and employment.

Success of union action: classical macroeconomic disequilibrium

Classical macroeconomic disequilibrium is symmetrical with Keynesian disequilibrium. In this case, we can write the following expression for the wage rate:

1 1/1 ( (1 )) PS WS AK u w w B N u u           
and, for the unemployment rate:

1 1 1 g PS WS D N A w u u N w B                         
The effective demand is such that the employment level desired by the firm is higher than that sought by the union, and the wage offered by the firm is lower than that hoped for by the union. In this case, it is the firm that is under a constraint; union members can refuse to work for the current salary offer, the firm is rationed on the labour market in the sense that it cannot hire all the labour force it wants. Hence, the firm is obliged to lower its production and raise real wages. The unemployment rate and real wages rise until equilibrium is again achieved between firms and unions (point of intersection between the WS and PS curves).

The equilibrium unemployment rate returns to its standard level: it is indeed the union that, through its action, helps to set a higher actual wage.

In this classical unemployment situation, the firm reduces production under the pressure of the "classical forces" of unemployment. In the classical system, it is the amount of union pressure and unemployment benefit that determine the real wage as well as the level of employment. Here, the disequilibrium is characterized by the fact that the union is on its WS curve, unlike the firm, which cannot reach its WS curve.

We can illustrate the situation with Figure 3.

In this configuration, the weight/?influence of the trade union is such that it manages to impose a real wage equal to W ps . For this real wage, firms are rationed on the labour market: they want the unemployment rate to be at U ps but the actual unemployment rate is higher, at the Uws level. The classical logic that prevails here is that the real wage determines the level of employment and therefore the unemployment rate. For the firm to reach the desired employment level and unemployment rate in U ps , the wage would have to be Wws. But this salary is too high because the firm would not maximise its profits.

This classical disequilibrium is transitory, contrary to the Keynesian disequilibrium. Indeed, the union can perfectly well agree to increase the real wage gradually so that the point of intersection between the PS and WS curves is reached. The failure of the negotiations would therefore only be temporary and would not require state intervention. The classic type of disequilibrium is therefore only temporary and leads to a situation of equilibrium unemployment.

Conclusion

In contrast to the traditional WS-PS model which only accounts for one type of unemployment with essentially classical properties, our WS-PS model has two original features: it accounts for situations where negotiations between firms and trade unions have failed and highlights two types of unemployment: Keynesian unemployment, whose level depends on the demand encountered by firms; classic unemployment, whose level depends mainly on the level of real wages. In the WS-PS model, unemployment is only caused by a downward rigidity of real wages, while our model is able to highlight unemployment linked to the asymmetry between entrepreneurs and employees (firms unilaterally set the level of employment) and insufficient demand.

Although our study presents a kind of disequilibrium model, it also differs from the Barro and Grossman model because we do not need to assume price fixity.

It is worth bearing in mind that this reformulated model could provide a basis for econometric estimates to identify the nature of unemployment in the contemporary economies of the different countries studied. Piluso N., Colletis G., [2012], "Shareholder value and equilibrium rate of unemployment", Economics Bulletin, 32(4): 3233-3242. Here, the equilibrium unemployment rate, similar to that highlighted in the standard WS-PS model, is reached at the point of intersection of the WS and PS curves.

Figure 1 :

 1 Figure 1: Equilibrium unemployment rate.

Figure 2 -Figure 3 -

 23 Figure2-Keynesian disequilibrium: the actual unemployment and actual wages (denoted respectively as U ps and W ps ) are both higher than the levels sought by the union.

The labour force size is denoted N.

The model leads to an apparently paradoxical result, where employers pay a high actual wage W ps to employees who would have accepted a lower wage w ws (see Figure1). What is to prevent employers from reducing actual wages? In reality, the problem cannot be posed in these terms. In the model, the actual wage determined at the macroeconomic scale corresponds to the wage that maximizes profit given the effective demand. Lowering actual wages supposes that, upstream, the effective demand is higher (given the diminishing performance of the labour factor). However, in the model, such a rise in demand cannot be imposed at will.

unions have the upper hand and are able to impose the corresponding wage and employment rate (classical logic). In the end, the equilibrium defined by the point at which WS and PS intersect is unforeseeable and may be either classical or Keynesian in nature.

Three types of unemployment can thus be distinguished.

4.1 Equilibrium corresponding to the point of intersection between the WS and PS curves: firms and trade unions negotiate successfully...

Equilibrium exists when the level of production, Y, is such that the unemployment rate and real wages correspond to the point where the WS and PS curves intersect. The equilibrium unemployment rate can then be expressed by following the equation:

and is given by the expression

The determinants of the equilibrium unemployment rate are in line with classical analysis, including the reserve wage, the product per unit of labour and the output elasticity of labour (see Figure 1).

Keynesian disequilibrium: failure of trade union action

Keynesian disequilibrium exists when anticipated aggregate demand is such that actual unemployment is higher than the equilibrium unemployment rate and that, correspondingly, actual wages in force are higher than the real "equilibrium" wage (higher than the level claimed by the union).

We then have, for the wage rate:

and for the unemployment rate: