Charlene Ngassam Tounzoua

Bruno Grignard

Antoine Brege

Christine Jérôme

Thierry Tassaing

Raphael Mereau

Christophe Detrembleur
email: christophe.detrembleur@uliege.be

Charlene G Ngassam Tounzoua

Christine Jerome

A Catalytic Domino

Keywords: CO 2, polycarbonates, exovinylene cyclic carbonate, catalysis

published or not. The documents may come

They are typically synthesized by a 100 % atom efficiency carboxylative coupling of CO 2 to propargylic alcohols, [START_REF] Hu | Zinc(II)-Catalyzed Reactions of Carbon Dioxide and Propargylic Alcohols to Carbonates at Room Temperature[END_REF][START_REF] Qiu | Efficient Ionic-Liquid-Promoted Chemical Fixation of CO2into Α-Alkylidene Cyclic Carbonates[END_REF][START_REF] Song | Efficient Chemical Fixation of CO2promoted by a Bifunctional Ag2WO4/Ph3P System[END_REF][START_REF] Song | Robust Silver(I) Catalyst for the Carboxylative Cyclization of Propargylic Alcohols with Carbon Dioxide under Ambient Conditions[END_REF][START_REF] Gu | Ionic Liquid as an Efficient Promoting Medium for Fixation of CO 2: Clean Synthesis of α-Methylene Cyclic Carbonates from CO2 and Propargyl Alcohols Catalyzed by Metal Salts under Mild Conditions[END_REF] with some of them that are easily accessible from acetylene and industrial formaldehyde waste. [START_REF] Falbe | Aliphatic. Ullmann's Encyclopedia of Industrial Chemistry[END_REF] Unlike the conventional 5-membered cyclic carbonates, alkylidene 5-membered cyclic carbonates display a remarkable reactivity towards amines, alcohols and thiols to afford urethanes [START_REF] Magliozzi | Benefit of the Reactive Extrusion in the Course of Polyhydroxyurethanes Synthesis by Aminolysis of Cyclic Carbonates[END_REF] (oxazolidones or β-oxo-carbamates [START_REF] Song | Bifunctional Silver(I) Complex-Catalyzed CO2 Conversion at Ambient Conditions: Synthesis of α-Methylene Cyclic Carbonates and Derivatives[END_REF][START_REF] Qi | Efficient Synthesis of β-Oxopropylcarbamates in Compressed CO2 without Any Additional Catalyst and Solvent[END_REF] ), β-oxoalkylcarbonates, [START_REF] Joumier | Direct Access to β-Oxopropyl Carbonates from Bulky Alcohols[END_REF][START_REF] Hu | Synthesis of Asymmetrical Organic Carbonates Using CO2as a Feedstock in AgCl/Ionic Liquid System at Ambient Conditions[END_REF] and thiocarbonates or sulfur-containing tetrasubstituted ethylene carbonates, [START_REF] Gennen | Polymers CO2 -Sourced α-Alkylidene Cyclic Carbonates : A Step Forward in the Quest for Functional Regioregular Poly(Urethane)s and Poly(Carbonate)s[END_REF][START_REF] Ouhib | A Switchable Domino Process for the Construction of Novel CO2-Sourced Sulfur-Containing Building Blocks and Polymers[END_REF] respectively. The presence of the exocyclic olefin increases the ring-strain of the molecule and ensures the selective ring-opening by the nucleophiles with the formation of an enol intermediate which tautomerizes into a ketone, thus acting as the driving force for the reaction. The unique chemical features of CCs were exploited by our group to pioneer a novel route to CO 2 -sourced polycarbonates with unprecedented microstructures [START_REF] Gennen | Polymers CO2 -Sourced α-Alkylidene Cyclic Carbonates : A Step Forward in the Quest for Functional Regioregular Poly(Urethane)s and Poly(Carbonate)s[END_REF] that already showed relevance as solid electrolytes for Li-ion batteries. [START_REF] Ouhib | CO2-Sourced Polycarbonates as Solid Electrolytes for Room Temperature Operating Lithium Batteries[END_REF][START_REF] Ouhib | Influence of the Cyclic versus Linear Carbonate Segments in the Properties and Performance of CO2-Sourced Polymer Electrolytes for Lithium Batteries[END_REF] In contrast to the conventional synthesis of CO 2 -sourced polycarbonates by the direct ring-opening copolymerization of CO 2 with epoxides, [START_REF] Nakano | Selective Formation of Polycarbonate over Cyclic Carbonate: Copolymerization of Epoxides with Carbon Dioxide Catalyzed by a Cobalt(III) Complex with a Piperidinium End-Capping Arm[END_REF][START_REF] Poland | A Quest for Polycarbonates Provided: Via Sustainable Epoxide/CO2 Copolymerization Processes[END_REF][START_REF] Allen | High-Activity , Single-Site Catalysts for the Alternating Copolymerization of CO2 and Propylene Oxide[END_REF][START_REF] Inoue | Copolymerization of Carbon Dioxide and Epoxide[END_REF] our approach focused on the polyaddition of bis(-alkylidene cyclic carbonate)s (bis-CCs) to diols in the presence of an organobase as catalyst to afford regioregular and defects-free poly(β-oxo-carbonate)s at room temperature. Early this year, Schaub engineered a novel synthetic protocol to provide bisCCs and also demonstrated their utility for the fabrication of low molar mass poly(β-oxo-carbonate)s (Mn ~ 2,000 g/mol). [START_REF] Dabral | Synthesis and Polymerisation of α-Alkylidene Cyclic Carbonates Obtained from Carbon Dioxide, Epoxides and the Primary Propargylic Alcohol 1,4-Butynediol[END_REF] However, the synthetic routes to bisCCs are still tedious with demanding purification procedures. To push away these boundaries, we introduce in this work a novel domino terpolymerization approach to produce poly(β-oxo-carbonate)s from a mixture of CO 2 , bispropargylic alcohol and diols (Scheme 1b), some of them being selected for their ease of production from lignin biomass. If many publications focused on the one-pot domino synthesis of oxazolidinones and oxopropyl carbamates from CO 2 , propargylic alcohols and amines [START_REF] Song | Synthesis of β-Oxopropylcarbamates in a Recyclable AgBr/Ionic Liquid Catalytic System: An Efficient Assembly of CO2 under Ambient Pressure[END_REF][START_REF] Song | Upgrading CO2 by Incorporation into Urethanes through Silver-Catalyzed One-Pot Stepwise Amidation Reaction[END_REF][START_REF] Qi | Efficient Synthesis of β-Oxoalkyl Carbamates from Carbon Dioxide, Internal Propargylic Alcohols, and Secondary Amines Catalyzed by Silver Salts and DBU[END_REF][START_REF] Zhao | Ag(I)/(C2H5)4 NCl Cooperation Catalysis for Fixing CO2 or Its Derivatives into β-Oxopropylcarbamates[END_REF][START_REF] Song | Silver(I)-Catalyzed Synthesis of β-Oxopropylcarbamates from Propargylic Alcohols and CO2 Surrogate: A Gas-Free Process[END_REF][START_REF] Zhou | Green Catalysis for Three-Component Reaction of Carbon Dioxide, Propargylic Alcohols and Nucleophiles[END_REF] , only few examples reported the preparation of oxoalkyl carbonates by reacting propargylic alcohols, CO 2 and alcohols (Scheme 1a). The challenge lies in the identification of suitable catalysts capable of fixing CO 2 to propargylic alcohols to in-situ form CCs in a selective manner and to promote their alcoholysis.

Song reported on the synthesis of oxoalkyl carbonates with yields of 22-76 % using DBU/Zn salts (40:20 mol%) as catalytic systems at 80 °C, 10 bar in 16 h. [START_REF] Song | Selective Conversion of CO2 and Switchable Alcohols into Linear or Cyclic Carbonates via Versatile Zinc Catalysis[END_REF] Hu obtained yields up to 99 % with AgCl/butylmethylimidazolium acetate ([BMIm][OAc]) binary catalytic systems. However the ionic liquid was added in large amount (100 mol%) to promote the reaction at room temperature and atmospheric CO 2 pressure. [START_REF] Hu | Synthesis of Asymmetrical Organic Carbonates Using CO2as a Feedstock in AgCl/Ionic Liquid System at Ambient Conditions[END_REF] He's group used a combination of Ag 2 CO 3 and PPh 3 to catalyze the formation of oxoalkyl carbonates scaffolds with yields of 62-78 %. Working with a 0.5 eq excess in the alcohol was required to obtain higher yields (98 %). [START_REF] Zhou | Silver(I)-Catalyzed Three-Component Reaction of Propargylic Alcohols, CO2 and Monohydric Alcohols: Thermodynamically Feasible Access to β-Oxopropyl Carbonates[END_REF] Zhang reported high yields of 81-93 % and a large product scope using a silver sulfadiazine/EtNBr (5 mol%) dual system at 1 bar, 80 °C for 24 h. [START_REF] Li | Synergistic Ag(I)/nBu 4 NBr-Catalyzed Fixation of CO2 to β-Oxopropyl Carbonates via Propargylic Alcohols and Monohydric Alcohols[END_REF][START_REF] Li | Cascade Strategy for Atmospheric Pressure CO2 Fixation to Cyclic Carbonates via Silver Sulfadiazine and Et 4 NBr Synergistic Catalysis[END_REF] This later system suffers from the multi-step synthesis of sulfadiazine that is not a straightforward procedure. Although different catalytic systems exist to provide simple CCs and oxoalkyl carbonates, none of them has been utilized for both the quantitative synthesis of bisCCs and their in-situ transformation into poly(-oxocarbonate)s in a cascade reaction. In addition, as previously exemplified, none of them supported the features needed to respond to the requirements of a step-growth polymerization process that is extremely sensitive to the stoichiometry of the reaction. The bisCCs intermediate produced in-situ by carboxylative cycloaddition of CO 2 to bis(propargylic alcohol) will be directly involved in the polyaddition to the diol. Any side reactions will therefore result in a deviation from the perfect stoichiometry and cause the termination of the domino terpolymerization. To pursue our goal, it is therefore crucial to identify operating conditions and a catalytic system compatible for both steps, i.e. the selective formation of bisCC and its copolymerization with the diol.

In this work, we have developed a novel binary catalyst and evaluated its activity and selectivity on model compounds. Kinetic insights via operando FT-IR spectroscopy, correlated to mechanistic DFT calculations enabled us to understand and rationalize the mode of action of the catalyst. We then used it to selectively synthesize oxo-alkylcarbonates of different structures by the domino reaction between CO 2 , propargylic alcohols and mono-alcohols. Finally this process was exploited for the preparation of PCs under mild operative conditions. Scheme 1. One pot domino synthesis of (a) oxo-alkylcarbonates and (b) poly(β-oxo-carbonate)s

RESULTS AND DISCUSSION

Catalyst design and optimization of the reaction parameters. Model carboxylative coupling reactions of CO 2 with 2-methyl-3-butyn-2-ol to provide CC were first screened (Scheme 2).

We selected tetrabutylammonium phenolate ([TBA][OPh]) as the organocatalyst as we previously demonstrated its high efficiency for the envisioned reaction under moderate conditions. [START_REF] Grignard | Boosting the Catalytic Performance of Organic Salts for the Fast and Selective Synthesis of α-Alkylidene Cyclic Carbonates from Carbon Dioxide and Propargylic Alcohols[END_REF] This activity resulted from a good compromise between ion-pair separation controlled by steric effect and the basicity of the anion as evidenced in a previous benchmarking study. [START_REF] Grignard | Boosting the Catalytic Performance of Organic Salts for the Fast and Selective Synthesis of α-Alkylidene Cyclic Carbonates from Carbon Dioxide and Propargylic Alcohols[END_REF] Moreover, it is easily prepared from cheap phenol, a bio-based product derived from the fractionation of lignin. [START_REF] Yang | Ionic Liquid[END_REF] Scheme 2. Coupling of CO 2 to 2-methyl-3-butyn-2-ol.

The model reaction was carried out at 50 bar and 80 °C in acetonitrile with a low catalyst loading (5 mol%). Under these conditions, the expected CCs 2 was produced with 90 % yield in only 1 h (Table 1, entry 1). However, the main side reaction observed was the formation of the linear oxo-carbonate 2a by the addition of the propargylic alcohol to CCs. To extend the use of this catalytic system for the targeted domino reaction and prevent this side reaction, an optimization of both the reaction conditions and the catalyst structure was required. By decreasing the temperature to 60 °C, the reaction slowed down (6 h was required for full conversion) meanwhile the selectivity in 2 increased to 96 %, with 4 % of hydroxyketone formed from the hydrolysis of CC (Table 1, entry 3). When we further decreased the temperature to 40 °C, the reaction rate decreased considerably with propargylic alcohol conversion of only 6 % after 1h (Table 1, entry 4). Importantly, 2-methyl-3-butyn-2-ol was fully and selectively converted into the desired product 2 with no side product when the reaction time was extended to 24 h (Table 1, entry 5).

In order to improve the selectivity in CC 2 without excessively compromising the reaction rate, we considered the use of a cocatalyst that was expected to activate the alkyne for the carboxylative addition. Some metal-based catalysts (such as monovalent silver and copper salts) are capable of pi-coordination with the alkyne bond and are therefore expected to be beneficial for this reaction. S2). The difference in activity for the reactions carried out in the presence of the different silver salts (Ag 2 CO 3 , AgOAc and AgI) is at this stage difficult to rationalize. However, the different solubility of the silver salts in the reaction medium might be at the origin of this observation. Indeed, when preparing the reaction medium before pressurization with CO 2 , none of these cocatalysts were fully soluble. However, quantifying their solubility in the reaction medium under pressure was not possible. Verpoort 63 and Song [START_REF] Song | Robust Silver(I) Catalyst for the Carboxylative Cyclization of Propargylic Alcohols with Carbon Dioxide under Ambient Conditions[END_REF] .

We then screened some solvents using CuI as cocatalyst and found the reaction to be fastest in acetonitrile and slowest in DMSO (Table 2, entries 7 and 11), with the same selectivity in product 2 (100 %). S1 for the procedure).

In prelude of our subsequent study on the fabrication of poly(oxo-carbonate)s by the domino reaction, one selected DMSO as the solvent to continue our study. Unlike acetonitrile, its choice was justified by its capability to totally solubilize the bis-propargylic alcohol and provide homogeneous conditions at the initial stage of the reaction.

To benchmark the activity of the [TBA][OPh], CuI/[TBA][OPh] and AgI/[TBA][OPh] catalysts, we studied the kinetics of the reaction using online high-pressure FT-IR spectroscopy at 40 °C using both CuI and AgI. Figure 1a shows an overlay of the IR spectra at different times obtained with the [TBA][OPh]/AgI system. We observed a signal at 3300 cm -1 corresponding to the OH band of the alkynol which decreased gradually overtime and the concomitant formation of the cyclic carbonate and exovinylene group with characteristic vibrations of ν C=O at 1823 cm -1 and ν C=C at 1680 cm -1 . The CO 2 band at 2330 cm -1 was observed and remained constant due to the large excess of CO 2 under the investigated conditions. A similar profile was obtained with the with copper iodide as cocatalyst for this type of reaction. Although high yields were obtained (70-98 %), moderate to high temperatures (60-120 °C) were most often required [START_REF] Gu | Ionic Liquid as an Efficient Promoting Medium for Fixation of CO 2: Clean Synthesis of α-Methylene Cyclic Carbonates from CO2 and Propargyl Alcohols Catalyzed by Metal Salts under Mild Conditions[END_REF] . Room temperature operation was recently reported by using CuI in combination with phosphonium levulinate. However, a high pressure of CO 2 (pCO 2 = 100 bar) was required and the phosphonium salt was used in large amount (66 mol%). 61 Our system involving We initially explored the reaction pathway with [TBA][OPh] as catalyst only, which is composed of two elementary steps. From the van der Waals complex that exhibits hydrogen bonding between the oxygen atom of the phenolate anion and the hydrogen atom of the hydroxyl group of 2-methyl-3-butyn-2-ol, the first step consists of the deprotonation of the propargylic alcohol simultaneously to the nucleophilic attack onto the carbon atom of CO 2 with the formation of a carbonate anion intermediate (-11.2 kcal.mol -1 ). The activation barrier of this first step is calculated to be 5.9 kcal.mol -1 and, as the transition state associated to it is submerged with respect to the separated reactant limit (fixed at the zero Gibbs free energy), it is supposed to occur very quickly. The second step, which is the rate-determining step with a barrier height of

Figure 2. Gibbs free energy profiles for α-methylene carbonate formation with [TBA][OPh], [TBA][OPh]/CuI and [TBA][OPh]/AgI as catalytic system

In the presence of CuI or AgI as cocatalyst, the Gibbs free energy profile encountered an important exothermicity (about tens of kcal.mol -1 ), which considerably accelerated the reaction kinetics as observed experimentally. While the first step of the whole reaction is identical to the one with the sole [TBA][OPh] catalyst, the 2 remaining steps to form the target product 2 are thus : i) the ring formation from the carbonate anion together with the attack of the CuI (AgI) on the C≡C bond with an associated Gibbs free energy barrier of 24.5 kcal.mol -1 (18.8 kcal.mol -1 ),

ii) from the alkenyl metal intermediate a proto-demetallation takes place and the final product is formed by hydrogen proton transfer from PhOH. The Gibbs free energy activation barrier of this last step is calculated to be 10.1 kcal.mol -1 and 9.4 kcal.mol -1 for the cocatalysis with CuI and AgI, respectively.

To summarize, after the first step of the overall process (addition of CO 3, entry 2). The addition of AgI did not induce any side reaction, at least during the investigated reaction period. We have repeated this experiment for a shorter reaction time (15 min instead of 1h) and an identical conversion of 2 (100%) and selectivity for 3 (100%) were again noted. Although further experiments would be required, it suggests that the silver salt has no noticeable effect on the alcoholysis of the -alkylidene cyclic carbonate, in line with reports of Li and Han.

When using benzyl alcohol, the reaction carried out with [TBA][OPh] was also fast, quantitative and selective (Table 3, entry 4). In addition, the selectivity was still excellent, the conversion in CC dropped to 68% when using a less reactive secondary alcohol, 2-propanol, under identical conditions (Table 3, entry 5). No reaction was however noted with the tertiary alcohol, 2-methyl-2-butanol (Table 3, entry 6). The lower reactivity of the secondary and tertiary alcohol arose from their steric hindrance that decreased their nucleophilic character. While there is little to no reaction in the absence of AgI (Table 4, entries 1-3), full conversion of 1 was achieved at 40°C after 6h of reaction for the [TBA][OPh]/AgI system (Table 4, entry 4).

However, the main product was CC 2 (93%), with only 7% of the desired oxo-alkylcarbonate

3.

By raising the reaction temperature to 60 or 80°C, the yield in 3 was increased to 20 or 74%, respectively (Table 4, entries 5 and 6).

The influence of the working pressure on the yield and selectivity of the reaction was then evaluated by on-line IR spectroscopy at 60°C. Unfortunately, because the bands corresponding to the CC triple bond (890 and 960 cm -1 ) and the OH bond (3260 cm -1 ) of the propargylic alcohol overlapped with other bands, we could not follow the consumption of the propargylic alcohol over time. However, by analysing a sample of the reaction mixture at the end of each experiment by [START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF] H-NMR spectroscopy, we could confirm the total conversion of the propargylic alcohol for reactions performed at p CO2 of 1, 5 or 15 bar. We monitored the formation of CC 2 and its conversion into the oxo-alkylcarbonate 3 by following the evolution of the carbonyl band of the cyclic carbonate 2 at 1820 cm -1 and of the linear carbonate 3 at 1740 cm -1 (Figure 3a). The yields of each product are plotted vs time in Figure 3b. At 60 °C and 15 bar of CO 2 , the formation of the oxo-alkyl carbonate 3 was observed after about 2.5 h of reaction and was relatively slow.

After 20 h of reaction, a mixture of product 2 (45 %) and 3 (40 %) was collected. By decreasing the CO 2 pressure to 5 bar, the formation of CC 2 was faster and its conversion into 3 started after 45 min. After 20 h, the yield in 2 was only 3 % while the desired product 3 was formed with 87 % yield. Importantly, when the pressure was further reduced to 1 bar, CC 2 was rapidly formed and was simultaneously converted into 3. The domino reaction was complete in less than 10 h at 1 bar and selective towards the formation of 3. These kinetics studies clearly highlight that a low CO 2 pressure was required for an efficient domino reaction and for the selective production of 3. It was assumed that high CO 2 pressure favoured the carbonation of 1-butanol, consequently deactivating it for the alcoholysis of the in-situ formed CC 2. In all cases, all propargylic alcohols were fully consumed. The corresponding oxoalkylcarbonates were formed with a high yield ( 97 %) when primary alcohols such as 1butanol or benzyl alcohol were involved with the less sterically hindered propargylic alcohol, 2methyl-3-butyn-2-ol. When a secondary 2-propanol or tertiary alcohol 2-methyl-2-butanol was employed together with 2-methyl-3-butyn-2-ol, the yields in oxo-alkylcarbonate dropped to 60 % (product 3C) and 12 % (product 3D), respectively. Similarly, when 1-butanol was reacted with more sterically hindered propargylic alcohols such as 3-methyl-1-pentyn-3-ol and 3,5-dimethyl-1-hexyn-3-ol, very low yields (13 % for product 3E, and 11 % for product 3F), respectively, were obtained. The remaining percentage corresponded to the unreacted cyclic carbonate intermediate. Interestingly, by extending the reaction time to 72 h, the selectivity and yield in the target oxo-alkylcarbonates increased to 99 % for both 3E and 3F. 5). When carried out in DMSO at 1 bar of CO 2 , oligomers with a number average molar mass (M n ) of 1,000 g/mol were collected after 48 h at 60 °C (Table 5, entry 1). By increasing the CO 2 pressure to 15 bar, M n was increased to 1,500 g/mol, however no significant evolution was observed when the reaction time was extended to 72 h (Table 5, entries 2 and 3). When the reaction was performed under neat conditions, similar results were obtained.

Synthesis of poly(-oxo-carbonate)s by one

Interestingly the molar mass was almost doubled when using DMF as solvent (Table 5, entries 8-9). Increasing the reaction temperature to 80 °C was detrimental to the polymerization with the formation of oligomers of lower M n (Table 5, entries 4 and 5 in DMSO and entry 10 in DMF).

Several factors might be at the origin of this observation. First, we demonstrated that increasing the reaction temperature decreased the selectivity in the in-situ formed -alkylidene cyclic carbonate (Table 1), with the consequence that the stoichiometry between -alkylidene cyclic carbonate and alcohol groups is not respected. Second, some thermally induced side reactions (e.g. transcarbonation) might consume reactive groups and thus will provoke a deviation from the perfect stoichiometry, thus lowering the polymer molar mass.

The SEC elugrams obtained on the crude reaction media (in order to avoid any fractionation of the sample during purification) are presented in Figure S18-21. They show that polymers prepared in DMF were of higher molar mass compared to those produced in DMSO or in the bulk. In the two latter cases, dimers and trimers were clearly observed. Dispersities were rather low for a step-growth polymerization process but are the result of the low molar mass polymers. [START_REF] Luo | C-H Carboxylation of Aromatic Compounds through CO2 Fixation[END_REF] C-NMR spectra in DMSO-d 6 of purified poly(ß-oxo-carbonate)

B1D1

The structure of the poly(-oxo-carbonate) was evidenced by 1 H-NMR spectroscopy (Figure 4a) by the presence of a singlet at δ = 2.11 ppm typical of the methyl group in alpha position of the ketone, at δ = 1.44 ppm characteristic of the methyl group in alpha of the carbonate and at δ = 4.06 ppm characteristic of the methylene linked to the carbonate group. The 13 C-NMR (Figure 4b) analysis of the polymer evidenced the resonance of the ketone at δ = 206 ppm and the carbonate at δ = 153 ppm. All assignments were confirmed by COSY, HSQC and HMBC analysis (Figures S24-26).

The substrate scope was extended by testing other diols (primary D3 and secondary D2, D4) and a cycloaliphatic bis(propargylic alcohol) (B2) (Scheme 4). The corresponding poly(-oxocarbonate)s were obtained in all cases, with the structures that were confirmed by 1 H-NMR analyses (Figures S27-S31). Although the molar masses of the polymers cannot be compared (they are obtained based on a polystyrene calibration and the polymers are characterized by different hydrodynamic volumes), the highest M n of 2,700 g/mol (M w = 4,300 g/mol) was obtained for B1D1 (Scheme 4). Lower molar masses were collected for polymers prepared from the cycloaliphatic bis(propargylic alcohol) B2. As both B2D1 and B2D2 copolymers were only partly soluble in DMF at room temperature, and because no common organic solvent could totally dissolve them, fractionation of the samples occurred prior their analyses. Their molar masses determined by size exclusion chromatography were probably underestimated. Due to this lack of solubility, the determination of the degree of polymerization by 1 H-NMR spectroscopy was not performed.

CONCLUSIONS.

In this work, we have disclosed a domino approach to construct oxo-alkylcarbonate scaffolds and polycarbonates from CO 2 , propargylic alcohols and mono-alcohols under mild operating conditions (pCO 2 = 1-15 bar, T = 40-80 °C). The keystone lied in the design and the utilization of a binary catalyst composed of tetrabutylammonium phenolate that operated in synergy with a Ag(I) or Cu(I) salt. Remarkably, this dual catalyst (at 5 mol% loading) enabled to drive the fast, selective and quantitative formation of exovinylene cyclic carbonates by carboxylative coupling of CO 2 to various propargylic alcohols, and it also catalyzed the alcoholysis of the in-situ generated 5-membered cyclic carbonates, providing an efficient platform for the preparation of oxo-alkyl carbonates at high yield. Operando FT-IR spectroscopy correlated to DFT calculations provided kinetic and mechanistic insights that helped us to optimize the one-pot process via a rational comprehension of the reactivity, the efficiency and the selectivity of the binary catalytic system. When this catalytic system was used on mixtures of CO 2 , bis(propargylic alcohol)s and diols, poly(oxo-carbonate)s with M w up to 4,300 g/mol were produced by a new domino polymerization process under mild conditions (60°C, 15 bar). By varying the nature of the bis(propargylic alcohol) and the diol, various polycarbonates were successfully prepared, enlarging the scope of the process. Ongoing work focuses on the comprehension and the identification of the causes responsible for the moderate molar masses and the solutions to remove their hurdles.

EXPERIMENTAL SECTION

Materials. Ethynylmagnesium bromide (Acros), silver iodide, silver acetate, silver carbonate, copper chloride, copper bromide, copper iodide, zinc iodide, 2,5-hexandione, 1,4cyclohexandione, 1,6-hexandiol, 2,5-hexandiol, 1,4-butanediol, 1,4-cyclohexandiol (cis/trans mixture), 1-butanol, propan-2-ol, 2-methyl-2-butanol, 2-methyl-3-butyn-2-ol, 3-methyl-1pentyn-3-ol, 3,5-dimethyl-1-hexyn-3-ol were purchased from Aldrich. CO 2 (N27) was purchased from Air liquid, dimethyl sulfoxide (DMSO), dimethyl formamide (DMF), acetonitrile (ACN), methanol (MeOH), diethylether. DMSO was dried on a 3Å molecular sieve conditioned at 100°C under vacuum for 24h. All the other reagents were used as received without any further purification.

Analytical methods. In-situ IR spectroscopy experiments were conducted using a stainless steel reactor suitable for high-pressure measurements (up to 400 bar) and high temperature (up to 100 °C) coupled with a FT-MIR spectrometer from Brucker, equipped with an air-cooled globar source (12V), a KBr beam splitter, a mechanical rocksolid interferometer, permanently aligned, a diamond ATR fibre probe IN350-T (Ø 6 mm) and a liquid nitrogen cooled mercury cadmium telluride (MCT). Single beam spectra recorded in the spectral range (670-3500 cm -1 ) with a 4 cm -1 resolution were obtained after the Fourier transformation of 32 accumulated interferograms until the end of reaction time.

Screening of the reaction parameters for the carboxylative coupling of CO 2 to 3-methyl-2-

butyn-3-ol. In a clean dry reactor, equipped with a magnetic rod, a manometer and a gas inlet/outlet were introduced 3-methyl-2-butyn-3-ol (2 mL, 20.61 mmol), tetrabutylammonium phenolate [TBA][OPh] (0.3459 g, 1.031 mmol), CuI (0.1963g, 1.031 mmol) and acetonitrile (2 mL). The reactor was closed and placed in a silicon oil bath set heated at the desired temperature.

After 30 minutes, CO 2 gas was added at a constant pressure. The reaction ran for 1 h after which the reactor was depressurized and placed in a water bath to cool it down to room temperature.

The crude reaction mixture was characterized by 1 H-NMR spectroscopy in CDCl 3 . For the screening of the reaction parameters (T, solvent, catalyst), a similar protocol was applied

Monitoring of the carboxylative coupling of CO 2 to 3-methyl-2-butyn-3-ol by online FT-IR.

In a clean dry reactor of 80 mL equipped with a manometer, a heating mantle, gas inlet/outlets, a mechanical stirrer and a high pressure FT-IR probe were introduced 3-methyl-

General procedure for the synthesis of butyl-(2-methyl-3-oxobutan-2-yl) carbonate by alcoholysis of αCC 2.

In a clean dry glass reaction tube, equipped with a magnetic rod and a three-way stopcock were introduced; 4,4-dimethyl-5-methylene-1,3-dioxolan-2-one (0.5 g, 3.904 mmol), butanol (0.357 ml, 3.904 mmol), tetrabutylammonium phenolate [TBA][OPh] (0.0664 g, 0.1952 mmol) and DMSO (1 ml). The reaction tube was placed in a silicon oil bath set at 25 °C.

The reaction mixture was sampled after 15 min, 1 h, 2 h and 24 h, and characterized by 1 H NMR spectroscopy in DMSO-d 6 .

General procedure for the domino synthesis of butyl-(2-methyl-3-oxobutan-2-yl) carbonate from 2-methyl-3-butyn-2-ol, CO 2 and alcohol.

In a stainless-steel reactor of 12 mL equipped with a magnetic bar, a manometer and a gas inlet/outlet were introduced 3-methyl-

Monitoring of the synthesis of butyl-(2-methyl-3-oxobutan-2-yl) carbonate by on-line FT-IR.

In a clean dry reactor of 80 mL equipped with a manometer, a heating mantle, gas inlet/outlets, a mechanical stirrer and a high pressure FT-IR probe were introduced 3-methyl-

ASSOCIATED CONTENT

[ 1 (

 1 TBA][OPh]/CuI system (FigureS3). By following the evolution of the ν C=O band at 1823 cm -Figure1b) over time, the yield in exovinylene cyclic carbonate 2 was calculated for the reactions catalyzed by [TBA][OPh], [TBA][OPh]/CuI or [TBA][OPh]/AgI systems (Figure 1c, see supporting information for the quantification procedure).

Figure 1 .

 1 Figure 1. Synthesis of 4,4-dimethyl-5-methylene-1,3-dioxolan-2-one by organocatalyzed

[

  TBA][OPh]/CuI is thus competitive for operating under mild reaction conditions, at a low catalyst loading (5 mol%). The mechanism of the carboxylative cyclisation of 1 was then investigated by DFT calculations (Figure 2) with the help of the M062X functional (see ESI for details) where the Gibbs free energy of each structure is relative to the sum of the individual Gibbs free energy of the reactants for each pathway, i.e. : propargylic alcohol + CO 2 + [TBA][OPh] for the reaction catalyzed by the sole [TBA][OPh] ; propargylic alcohol + CO 2 + [TBA][OPh] + CuI (AgI) for the reaction catalyzed by [TBA][OPh] / CuI (AgI).

23. 2

 2 kcal.mol -1 , involves the intramolecular nucleophilic addition from the carbonate anion to the C≡C bond and the simultaneous protonation of the alkenyl anion by the PhOH leading to the formation of 2 and the regeneration of [TBA][OPh] catalyst.

Figure 3 .Scheme 3 .

 33 Figure 3. One pot domino synthesis of butyl-(2-methyl-3-oxobutan-2-yl) carbonate from CO 2 , 2-

  -pot domino terpolymerization. The reaction conditions were first optimized for the terpolymerization of 4,4'-(ethane-1,2-diyl)bis(4-methyl-5methylene-1,3-dioxolan-2-one) B1, 1,6-hexanediol D1 and CO 2 using [TBA][OPh]/AgI as binary catalytic system (Table

Figure 4 (

 4 Figure 4(a) 1 H-NMR and (b)[START_REF] Luo | C-H Carboxylation of Aromatic Compounds through CO2 Fixation[END_REF] C-NMR spectra in DMSO-d 6 of purified poly(ß-oxo-carbonate)

Scheme 4 .

 4 Scheme 4. One-pot domino synthesis of poly(-oxo-carbonate)s and reagent scope. M n and PDI

1 H

 1 NMR analyses were performed on Bruker Avance 400 MHz spectrometers in DMSO at 25 °C in the Fourier transform mode. 16 scans for 1 H spectra and 512 or 2048 scans for[START_REF] Luo | C-H Carboxylation of Aromatic Compounds through CO2 Fixation[END_REF] C spectra were recorded. Fourier transform infrared spectra were recorded using a Nicolet IS5 spectrometer (Thermo Fisher Scientific) equipped with a transmission or with a diamond attenuated transmission reflectance (ATR) device. Spectra were obtained in transmission or ATR mode as a result of 32 spectra accumulation in the range of 4000 -500 cm -1 , with a nominal resolution of 4 cm -1 .Number-average molecular weight (M n ) and dispersity (Đ) of the different polymers were determined by size exclusion chromatography (SEC) in dimethylformamide (DMF) containingLiBr (0.025 M) at 55 °C (flow rate: 1 mL/min) with a Waters chromatograph equipped with two columns dedicated to the analysis of low molar mass polymers (PSS gram analytical 100 Å, separation range 300-60000 Da) and a pre column (100 Å), a dual λ absorbance detector (Waters 2487) and a refractive index detector (Waters 2414). A previously established PS calibration curve was used.

  General procedure for the domino synthesis of poly(-oxocarbonate)s by terpolymerization.In a stainless-steel reactor of 12 mL equipped with a magnetic bar, a manometer and a gas inlet/outlet were introduced 4,4'-(ethane-1,2-diyl)bis(4-methyl-5-methylene-1,3-dioxolan-2-one) B1 (0.3g, 1.802 mmol) prepared following Gennen's protocol[START_REF] Gennen | Polymers CO2 -Sourced α-Alkylidene Cyclic Carbonates : A Step Forward in the Quest for Functional Regioregular Poly(Urethane)s and Poly(Carbonate)s[END_REF] , 1,6-hexandiol D1 (0.2130 g, 1.802 mmol), tetrabutylammonium phenolate (60.5 mg, 0.1802 mmol), AgI (42.3 mg, 0.1802 mmol) and DMF (1mL). The reactor was closed and placed in a silicon oil bath set at 60 °C.After 30 min, CO 2 was added at a constant pressure of 15 bar. The reaction ran for 24 h, after which the reactor was depressurized and placed in a water bath to cool it down to room temperature. A sample of the reaction mixture was characterized by 1 H-and[START_REF] Luo | C-H Carboxylation of Aromatic Compounds through CO2 Fixation[END_REF] C-NMR in DMSOd 6 to determine the conversion and by SEC in order to evaluate the molecular parameters of the polymer. Then the catalyst was removed by silica gel chromatography with CH 2 Cl 2 . The solvent was evaporated, and the sample washed 4 times with a mixture of water and CH 2 Cl 2 (5:1) to eliminate DMF. The organic phase was collected, and CH 2 Cl 2 removed under vacuum at room temperature.

Table 1 .

 1 Influence of the temperature on the carboxylative cyclisation of CO 2 with 2-methyl-3-

	butyn-2-ol catalyzed by [TBA][OPh]
	Entry	Temp.	Reaction time	Conv. of 1	Selectivity for 2

Conditions: 2-methyl-3-butyn-2-ol (2 mL, 0.02061mol),

[TBA]

[OPh] (5 mol%), acetonitrile (2 mL), CO 2

(50 bar)

. The conversions and selectivities were determined by

[START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF]

H-NMR spectroscopy in CDCl 3 .

  61,62 Various salts were tested and results are summarized in Table2. Adding

	silver(I) or copper(I) salts favored the reaction. The best catalytic activity was obtained when
	[TBA][OPh] was combined to CuI or AgI, with an increase in the conversion of 1 from 6%
	(without cocatalyst, Table 2, entry 1) to 81 % (with CuI, Table 2, entry 7) or 100 % (with AgI,
	Table 2, entry 3) in 1 h at 15 bar and 40 °C. Both [TBA][OPh]/CuI and [TBA][OPh]/AgI binary
	systems drove the reaction with a 100 % selectivity in the targeted product 2 as confirmed by 1 H-
	NMR spectroscopy (Figure

Table 2 .

 2 Screening

		of cocatalyst and solvents for the coupling of CO 2 to 2-methyl-3-butyn-2-ol
	catalyzed by [TBA][OPh]
	Entry	Cocatalyst	Solvent	Conv. of 1	Selectivity for 2
				(%)	(%)
	1	/	ACN	6	100

  Synthesis of oxo-alkylcarbonates. We then evaluated the capacity of the [TBA][OPh] and[TBA][OPh]/AgI dual systems to catalyze the alcoholysis of CC 2 into oxo-alkyl carbonates 3 at room temperature (T = 25°C) in DMSO. The reaction was tested for different alcohols and the results are summarized in Table3. Importantly, [TBA][OPh] (5 mol%) displayed sufficient basicity to enable the complete and selective conversion of CC 2 into the corresponding oxoalkylcarbonate 3 when reacted with 1-butanol for 1 h at 25 °C, while no reaction was noted without the catalyst (Table3, entries 1-2). The [TBA][OPh] acted as a hydrogen bond acceptor,

	by online FT-IR experiments. As the binary [TBA][OPh]/AgI systems displayed the highest
	catalytic activity, it was selected to pursue our objectives of domino reactions and
	polymerizations.

2 to the propargylic alcohol), the reactants have to overcome the highest energy transition state of +12 kcal/mol for the reaction only catalyzed by [TBA][OPh]. In contrast, in the presence of CuI (AgI), due to the strong exergonicity a significant part of the reactants might spontaneously react without any stabilization and accelerates the reaction kinetic compare to the case of the reaction only catalyzed by [TBA][OPh]. On the other hand, in the presence of CuI (AgI), the remaining part of the species that could be stabilized must undergo activation energies of 18.8 kcal/mol and 23.2 kcal/mol for the reactions co-catalyzed by AgI and CuI respectively, indicating that the reaction catalyzed by [TBA][OPh]/AgI is the fastest which is in good agreement with the kinetics studies thereby activating the alcohol molecule. When AgI was used as cocatalyst in combination to [TBA][OPh] CC 2 was selectively converted into the oxo-alkylcarbonate (Table 3, entry 3), similarly to the reaction performed with [TBA][OPh] only (Table

Table 3 .

 3 Alcoholysis of 4,4-dimethyl-5-methylene-1,3-dioxolan-2-one (CC, 2) catalyzed by secondary alcohols, we then evaluated its capacity to catalyze the one-pot cascade synthesis of the corresponding oxo-alkylcarbonate 3 from CO 2 , 2-methyl-3-butynol and 1butanol (Table4). The reactions were carried out at 15 bar for 6h, using 5 mol% of [TBA][OPh] with and without AgI, and different temperatures were screened. Results are presented in

	[TBA][OPh]
	Entry	Catalyst	Alcohol	Conv. of 2	Yield in 3
				(%)	(%)
	1	-	1-butanol	0	0
	2	[TBA][OPh]	1-butanol	100	100
	3	[TBA][OPh]/AgI	1-butanol	100	100
	4	[TBA][OPh]	benzyl alcohol	100	100
	5	[TBA][OPh]	propan-2-ol	68	100
	6	[TBA][OPh]	2-methyl-2-	0	/
			butanol
	Conditions: CC 2 (0.5 g, 3.904mmol), alcohol (3.904 mmol), [TBA][OPh] (66 mg, 5 mol%),
	cocatalyst (AgI or CuI: 5 mol%), DMSO (1 ml), T = 25°C, t = 1 h. The conversions and
	selectivities were determined by 1 H-NMR in DMSO-d 6 . (see Figure S4 for the procedure).

Cascade reaction on model compounds. As [TBA]

[OPh]/AgI was able to catalyze both the selective formation of DMACC by coupling CO 2 to 2-methyl-3-butyn-2-ol and its alcoholysis by primary and

Table 4 .Table 4 .

 44 Cascade synthesis of butyl (2-methyl-3-oxobutan-2-yl) carbonate from 2-methyl-3-

	butyn-2-ol, CO 2 and 1-butanol
	Entry	Catalyst	T (°C)	Conv. of 1	2 a (%)	3 b (%)
				(%)
	1	[TBA][OPh]	40	0	0	0
	2	[TBA][OPh]	60	0	0	0
	3	[TBA][OPh]	80	15	100	0
	4	[TBA][OPh]/AgI	40	100	93	7
	5	[TBA][OPh]/AgI	60	100	80	20
	6	[TBA][OPh]/AgI	80	100	23	74
	Conditions: 2-methyl-3-butyn-2-ol (2 ml, 0.02061 mol), 1-butanol (1.89 ml, 0.02065 mol),
	[TBA][OPh] (5 mol%), AgI (5 mol%), DMSO (2 ml), CO 2 (15 bar), 6 h.

a Selectivity for 2. b Selectivity for 3. The conversions and selectivity were determined by 1 H-NMR in DMSO-d 6 . (see Figure S5 for the procedure).

Table 5 .

 5 Screening of parameters for the one pot domino synthesis of poly(-oxo-carbonate)s

	Entry Solvent	P	T	Time	a Conv, of	a Conv, of	b M n	b M w	b PDI
			(bar)	(°C)	(h)	B 1 (%)	D1 (%)	(g/mol)	(g/mol)
	1	DMSO	1	60	48	100	20	<1000	-	-
	2	DMSO	15	60	24	100	61	1500	1900	1.3
	3	DMSO	15	60	72	100	55	1700	2300	1.3
	4	DMSO	15	80	24	100	44	1500	1900	1.3
	5	DMSO	15	80	72	100	50	1500	1800	1.2
	6	Neat	15	60	24	100	35	1400	1700	1.2
	7	Neat	15	60	72	100	62	2150	3100	1.4

  AgI, 8.225 mmol) and dried DMSO (16 ml). The reactor was closed and heated to the desired temperature after which the FT-IR acquisition was launched. Then CO 2 gas was added at constant flow. Spectra were recorded every 2 min. Once the reaction was complete, the reactor was cooled down to room temperature and depressurized. The crude mixture was recovered.

	4,4-dimethyl-5-methylene-1,3-dioxolan-2-one (2) 1 H NMR (400 MHz, DMSO-d 6 ) δ(in ppm) =
	4.79 (d, J = 3.8 Hz, 1H), 4.65 (d, J = 3.8 Hz, 1H), 1.60 (s, 6H).
	13 C NMR (100.6 MHz, DMSO-d 6 ) δ(in ppm) = 158.67, 151.28, 85.92, 85.56, 27.37.

2-butyn-3-ol (16 mL, 164.9 mmol), tetrabutylammonium phenolate [TBA][OPh] (2.7603 g, 8.225 mmol), the metal salt (

  H-NMR spectroscopy in DMSO-d 6 . Then the catalyst was removed by silica gel chromatography with CH 2 Cl 2 , and the product dried under vacuum at room temperature for 24h.

	2-butyn-3-ol
	(2 mL, 20.61 mmol), tetrabutylammonium phenolate [TBA][OPh] (0.3459 g, 1.031 mmol), AgI
	(0.2419 g, 1.031 mmol) and 1-butanol (1.88 mL, 20.55 mmol). The reactor was closed and
	placed in a silicon oil bath set at 60 °C. After 30 min, CO 2 was added at a constant pressure of 15

bar. The reaction ran for 6 h after which the reactor was slowly depressurized and placed in a water bath to cool it down to room temperature. The crude reaction mixture was characterized by

[START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF]

  ) and dried DMSO(12 mL). The reactor was closed and heated to the desired temperature after which the FT-IR acquisition was launched and recorded every 5 min. Then CO 2 gas was added at constant flow. Once the reaction was complete, the reactor was cooled down to room temperature and depressurized. The crude mixture was recovered and characterized by[START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF] H-NMR spectroscopy in DMSO-d 6 . MHz, DMSO-d 6 ) δ(in ppm) = 206.50, 153.92, 85.11, 67.90, 40.90, 30.55, 24.13, 23.33, 18.83, 13.92. These NMR data are in agreement with those reported in the scientific literature. NMR (100.6 MHz, DMSO-d 6 ) δ 206.43 (C=O), 153.77 (OC=OO), 135.78, 128.97, 128.89, 128.60, 85.50, 69.55, 24.18, 23.34. These NMR data are in agreement with those reported in the scientific literature. H NMR (400 MHz, DMSO-d 6 ) δ(in ppm) = 4.74 (p, J = 6.2 Hz, 1H), 2.11 (s, 3H), 1.43 (s, 6H), 1.23 (d, J = 6.2 Hz, 6H). These NMR data are in agreement with those reported in the scientific literature. MHz, DMSO-d 6 ) δ(in ppm) = 206.57, 153.32, 84.95, 72.30, 24.08, 23.34, 21.86 2-methyl-3-oxobutan-2-yl tert-pentyl carbonate (Product 3D) MHz, DMSO-d 6 ) δ(in ppm) = 206.24, 152.19, 84.91, 84.35, 36.29, 25.38, 23.71, 23.16,8.21 Butyl-(3-methyl-2-oxopentan-3-yl) carbonate (Product 3E)[START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF] H NMR (400 MHz, DMSO-d 6 ) δ(in ppm) = 4.08 (tt, J = 6.9, 3.4 Hz, 2H), 2.10 (s, 3H), 1.87 (dq, J = 15.0, 7.5 Hz, 1H), 1.72 (dq, J = 14.7, 7.5 Hz, 1H), 1.57 (h, J = 6.3, 5.8 Hz, 2H), 1.43 (s, 3H), 1.34 (h, J = 7.3 Hz, 2H), 0.90 (t, J = 7.4 Hz, 3H), 0.81 (t, J = 7.5 Hz, 3H). MHz, DMSO-d 6 ) δ(in ppm) = 206.43 (C=O), 153.77 (OC=OO), 87.94, 68.46, 30.86, 28.89, 24.32, 19.68, 18.70, 14.06, 7.45 Butyl (3,5-dimethyl-2-oxohexan-3-yl) carbonate (Product 3F)[START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF] H NMR (400 MHz, DMSO-d 6 ) δ(in ppm) = 4.08 (td, J = 6.6, 3.1 Hz, 2H), 2.11 (s, 3H), 1.71 (dd, J = 13.2, 6.9 Hz, 2H), 1.58 (dd, J = 8.3, 6.3 Hz, 2H), 1.48 (s, 3H), 1.33 (q, J = 7.5 Hz, 3H), 0.90 (dt, J = 8.0, 4.4 Hz, 9H). 13 C NMR (100.6 MHz, DMSO-d 6 ) δ(in ppm) = 206.24 (C=O), 153.77 (OC=OO), 87.58, 67.83, 44.07, 30.54, 24.60, 23.85, 23.78, 20.79, 18.80, 13.92

	Isopropyl-(2-methyl-3-oxobutan-2-yl) carbonate (Product 3C)
	2-butyn-3-ol (12
	mL, 123.6 mmol), 1-butanol (11.3 mL, 123.6 mmol), [TBA][OPh] (2.0749 g, 6.182 mmol), AgI
	(6.182 mmolButyl-(2-methyl-3-oxobutan-2-yl) carbonate (product 3A)
	Benzyl-(2-methyl-3-oxobutan-2-yl) carbonate (Product 3B)
	1 H NMR (400 MHz, DMSO-d 6 ) δ(in ppm) = 7.39 (s, 4H), 7.45 -7.32 (m, 1H), 5.15 (s, 2H), 2.10
	(s, 3H), 1.45 (s, 6H).

[START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF]

H NMR (400 MHz, DMSO-d 6 ) δ(in ppm) = 4.08 (t, J = 6.6 Hz, 2H), 2.12 (s, 3H), 1.62 -1.52 (m, 2H), 1.43 (s, 6H), 1.42 -1.28 (m, 2H), 0.89 (t, J = 7.4 Hz, 3H). 13 C NMR (100.6 13 C 1 13 C NMR (100.6 1 H NMR (400 MHz, DMSO-d 6 ) δ(in ppm) = 2.10 (s, 3H), 1.75 (q, J = 7.5 Hz, 2H), 1.40 (s, 6H), 1.37 (s, 6H), 0.84 (dt, J = 9.3, 7.5 Hz, 3H). 13 C NMR (100.6 13 C NMR (100.6

, Propargylic Alcohols, and (Mono-and Di-)Alcohols. ACS Sustainable Chemistry & Engineering, 2020, 8 (26), pp.9698-9710. 10.1021/acssuschemeng.0c01787. hal-02990794

Ngassam. C. Detrembleur is FNRS Research Director. Computer time was provided by the Pôle Modélisation HPC facilities of the Institut des Sciences Moléculaires UMR 5255 CNRS -Université de Bordeaux, co-funded by the Nouvelle Aquitaine region.

Funding Sources. This research was partially funded by the Fonds National de la Recherche Scientifique (FNRS) and the Fonds Wetenschappelijk Onderzoek -Vlaanderen (FWO) in the frame of the EOS project n°O019618F (ID EOS: 30902231) and by FNRS in the frame of the FRIA project of C. Ngassam.

Notes.

Any additional relevant notes should be placed here.

ACKNOWLEDGMENT

The authors of Liège thank the Fonds National de la Recherche Scientifique (FNRS) and the Fonds Wetenschappelijk Onderzoek -Vlaanderen (FWO) for funding the EOS project n°O019618F (ID EOS: 30902231) and the FNRS in the frame of the FRIA project of C.

Supporting Information is available free of charge via the Internet at http://pubs.acs.org. It describes the methodology to calculate the reactant conversion by [START_REF] Alves | Organocatalytic Promoted Coupling of Carbon Dioxide with Epoxides: A Rational Investigation of the Cocatalytic Activity of Various Hydrogen Bond Donors[END_REF] H NMR for the model alcoholysis of CC, the monitoring of the carboxylative cyclization of 2-methyl-3-butyn-2-ol and the carbonation of primary alcohol via operando FT-IR, the structural NMR characterizations of the reactant, crude and isolated oxo-alkylcarbonates and oligo(oxocarbonate)s and finally the SEC elugrams of the oligomers synthesized by the domino process and details for the DFT calculations.

AUTHOR INFORMATION

Corresponding Author * christophe.detrembleur@uliege.be Author Contributions. The manuscript was written through contributions of all authors. / All authors have given approval to the final version of the manuscript.

Synopsis

This paper treats on the valorization of carbon dioxide and (bio) sourced diols as carbonyl source for the synthesis of oxoalkylcarbonates and polycarbonates


Arthur Finkelstein
email: arthur.finkelstein@instant-system.com

Jean-Charles Régin
email: jean-charles.regin@univ-cotedazur.fr

Using Goal Directed Techniques for Journey Planning With Multi-criteria Range Queries in Public Transit

Keywords: Public Transit Routing, Shortest Path, Pareto Optimization, Preprocessing

One of the main problems for a realistic journey planning in public transit is the need to give the user multiple qualitative choices. Usually, public transit journeys involve 4 main criteria: the departure time, the arrival time, the number of transfers and the walking distance. The problem of computing Pareto sets with these criteria is called the Pareto range query problem. This problem is complex and difficult to solve within the constraints of the industrial world of smartphone applications, like a response time of the order of a second. In this paper, we present the Goal Directed Connection Scan Algorithm (GDCSA), an algorithm that allows, for the first time, to solve this problem with run times of less than 0.5 seconds on most European city or country-wide networks, like Berlin or Switzerland. In addition, GDCSA satisfies other industrial needs: it is conceptually simple and easy to implement. It partitions the graph in geographically small areas and precomputes some lower bounds on the duration of a trip in order to select for each itinerary a sub-set of these areas to decrease the number of scanned connections. Combining this sub-set and a journey planning using 4 criteria, we scan up to 17 times fewer connections than the best algorithms (CSA and RAPTOR), the number of nodes opened during the search is lowered by a factor of up to 2.9 and the query times are lowered by a factor of up to 9 on metropolitan networks. The integration of GDCSA in a smartphone app backend server led to an improvement in results by a factor of 5.

INTRODUCTION 1.Problem Description

With the advent of smartphones, millions of passengers use computer-based journey planning systems to obtain public transport directions. Those directions need to be given in a reasonable amount of time, usually in less than a second, and a user does not want only the shortest path from A to B but may want a journey with the lowest walking distance, the least transfers, something in between or any number of combinations of criteria. A journey planning system cannot guess what a passenger wants specifically so it has to give directions containing more than one journey. This can be done by computing Pareto sets with multiple criteria (arrival time, departure time, walk distance, number of transfers, accessibility, ...). A lot of work exists on the shortest path problem in public transit but few integrate the real needs of the users: not only the earliest arrival journey but a Pareto optimal set of journeys.

Multiple variants of the public transport routing problem exist: the profile variant solves simultaneously the earliest arrival problem for all source times, the range query variant solves simultaneously the earliest arrival problem for journeys that are at most two times as long as the fastest journey. For each of those variants we can add a Pareto set to solve a multicriteria problem, leading to the Pareto profile variant and the Pareto range query variant.

The Pareto range query variant, mainly the one that involves 4 criteria (departure time, arrival time, number of transfers and walked distance) has a practical relevance because travelers do not want to arrive significantly later than the earliest arrival time and may have specific preferences on the number of transfers or the walk distance. The two main criteria for the range query are the arrival and the departure time. The other criteria provide a wide array of choices for the user, which allows users to find a suitable answer according to their mobility or their aversion to changing vehicles. Note that the price is not used as a criteria because most users have a transit subscription either where the user lives or when visiting another city as a tourist, and therefore do not care about the price.

To solve this kind of problem there are mainly two types of methods. The first one proceeds by pre-processing and pre-calculating many solutions for multiple hours (for example at night) in order to be able to respond quickly to users. The second calculates solutions on demand. We can also imagine combining these two types of methods.

The major drawback of preprocessing methods is that they cannot integrate seamlessly the modifications that may appear on a network and that inevitably occur every day. On the other hand, on-demand calculation methods (called search methods) do not have this problem, but they are too slow at the moment to be used into a modern journey planning system.

In this paper, we propose to speed-up the response time by guiding a search method using goal directed techniques and using a little preprocessing not affected by real-world hazards.

Proposed Solution

Algorithms that yield fast query times for public transit routing in large metropolitan networks are numerous, with extensions of Dijkstra's algorithm [START_REF] Disser | Multi-criteria shortest paths in time-dependent train networks[END_REF][START_REF] Müller-Hannemann | Timetable information: Models and algorithms[END_REF][START_REF] Pyrga | Efficient models for timetable information in public transportation systems[END_REF], graph labeling algorithms (Delling et al., 2015a;[START_REF] Wang | Efficient route planning on public transportation networks: A labelling approach[END_REF], non graph based algorithms like the Connection Scan Algorithm (CSA) [START_REF] Dibbelt | Connection scan algorithm[END_REF] or RAPTOR [START_REF] Delling | Roundbased public transit routing[END_REF], preprocessing heavy approaches with Transfer Patterns [START_REF] Bast | Fast routing in very large public transportation networks using transfer patterns[END_REF][START_REF] Bast | Frequency-based search for public transit[END_REF], or with a lighter preprocessing with Trip-Based Public Transit Routing [START_REF] Witt | Trip-based public transit routing[END_REF]. There are also extensions to these algorithms to allow for shorter response times, Trip Based Routing is made faster with the use of condensed search trees [START_REF] Witt | Trip-based public transit routing using condensed search trees[END_REF], RAPTOR with the use of hyper graphs [START_REF] Delling | Faster transit routing by hyper partitioning[END_REF], CSA with the use of overlaygraphs (CSAccel) [START_REF] Strasser | Connection scan accelerated[END_REF] and Transfer Patterns by reducing the space and time consumption of the preprocessing [START_REF] Bast | Scalable transfer patterns[END_REF].

Among search based methods the two main ones are CSA and RAPTOR. CSA based algorithms are simple, short, easy to implement and have good performances which makes them often used in journey planning systems (e.g. Instant System on the Paris metropolitan network, TrainLine on the European train network, ...). In addition, the PRVCSA, the Pareto range variant of the CSA, seems to be one of the faster algorithms to solve the Pareto range query problem as mentioned in multiple well-known articles (Bast et al., 2016a;[START_REF] Dibbelt | Connection scan algorithm[END_REF]. Therefore, we focus our study on CSA based algorithms.

In CSA, the connections are treated one after the other, without distinguishing if they are useful or not for the journey, CSA trades relevance of information with simplicity and speed. Adding criteria to the CSA leads to a performance degradation because more complex data structures are needed and with each added criterion the size of the Pareto set increases which decreases even more the performance. In practice, for a system to be considered interactive it should respond in less than 1 second. Unfortunately, the PRVCSA does not have this performance when more than three criteria are involved.

One way to achieve such a goal for the PRVCSA is to combine it with goal-directed techniques, that is to "guide" the search toward the target by avoiding the scan of an element (a vertex for Dijkstra, a connection for the CSA) that is not in the direction of the target. Classic algorithms using goal-directed techniques are the A* search [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF]) and the ALT algorithm [START_REF] Goldberg | Computing the shortest path: A search meets graph theory[END_REF] which have been successfully used on road networks. The CSAccel algorithm [START_REF] Strasser | Connection scan accelerated[END_REF] can be seen as the first combination of goal directed technique and CSA. It applies CSA on multi-level overlay graphs to reduce the number of scanned connections and in doing so lower the run time. The main idea behind CSAccel is to avoid looking at rural buses that are neither near the departure city nor the arrival city, and only keep a subset of connections between cities. This reduces the number of scanned connections and the run time as well. CSAccel uses extremely sound principles and has significant gains on country-wide networks. Unfortunately, it does not improve run time for large dense metropolitan networks. It is also a complex algorithm to implement.

In this article, we present GDCSA, a novel approach that combines goal-directed techniques with the PRVCSA to allow the use of more criteria. We reuse the principles behind CSAccel but in an easier and more pragmatic way. We roughly use the same idea of partitioning the graph but we introduce additional lower and upper bounds, and remove the multilevel part of the partitioning. The key idea is to partition the graph in areas and only use the connections of a sub-set of the areas when computing a journey, thanks to lower and upper bounds on the duration of the public transit journey. The lower bounds are computed in a preprocessing step for each pair of areas while the upper bounds are computed during the journey planning. Each area is opened or discarded with a simple evaluation between the upper bound and the sum of two lower bounds (from the start stop to the candidate area and from the candidate area to the arrival stop). Then we merge the connections of the chosen areas and launch the PRVCSA on this restricted set of connections.

Our experiments reveal that on a large and dense metropolitan public transit networks, the GDCSA allows a journey planning using 4 criteria (departure time, arrival time, number of transfers and walked distance) with a run time 2.5 to 9 times faster than the PRVCSA and 4.3 to 16 times faster than the Pareto range query variant of the RAPTOR. Thus, the journey planning can be used in an interactive setting to satisfy the client's needs (i.e. on the passenger's smartphone) with run times of less than 0.5 second on most of the compared networks.

Integrating a Solution in an Industrial Setting

We can identify multiple problems when integrating an algorithm in an industrial setting: the accuracy of the data, the maintainability and adaptability of the algorithm and the integration into an existing system. The problem when using public transport journey planning systems on metropolitan data is that the data is never 100% accurate, we can have multiple problems, e.g. circular lines that are not declared as such, lines that have not been updated with the new stops and departure times and any number of other problems. As such an algorithm that is robust to inaccurate data is essential.

With inaccurate data and real life usage, we have a lot of bug fixing and in a small company like ours with 30 employees, any one of the R&D engineers should be able to debug the core of the journey planning because a debug task is assigned independently of who wrote the code. This means that an algorithm that is easy to code, understand and maintain is vital.

An easily adaptable algorithm is important because each client has different needs, depending on the size of the public transport network, the wish of the community and other factors. This leads to an algorithm that has to be easily modifiable. For example certain clients want specific modes at the top or the bottom, to use gps coordinates instead of stops as departure and arrival, to combine free floating bikes or kick-scooters with public transport which means journeys to or from other modes will have specific constraints.

A complete app containing other components, such as ticketing, next departure times, favorite notification, guiding, transport on demand and more, involves more complex data structures than the ones described in the literature. For example simple identifiers are used for benchmarking whereas they are more complex in an app to be human readable. So access times to the data structures are longer and therefore the run time is slower. We also have the problem of persistence and the need for databases which limit access times, and when connecting to real time providers the correspondence between the line and stop ids is never automatic.

During the development of the GDCSA, we made sure to integrate all those aspects and we will give experimental results as well as results of an integration in an industrial backend server.

This paper is organized as follows: Section 2 will give all the notions necessary to understand the algorithm. Section 3 introduces the GDCSA, the intuition behind it and how the transit network graph is partitioned. Section 4 presents the experimental evaluation of the algorithm on the performance and other metrics. Section 5 concludes with a summary and a discussion of future work.

PRELIMINARIES

In this section we formalize the inputs and algorithms used in this work, we use the same formalization as the CSA [START_REF] Dibbelt | Connection scan algorithm[END_REF] because it is the centerpiece of our algorithm.

Timetable

A timetable represents for one specific day the vehicles that exist (train, bus, tram, ferry, ...), when they travel, where they travel and how passengers can go from one vehicle to another. A timetable is a quadruple (S, T,C, F) of stops S, trips T , connections C and footpaths F:

• A stop is a position outside of a vehicle where a passenger can wait. At a stop (and only at a stop) a vehicle can halt and passengers can leave or get on.

• A trip is defined by a vehicle going through stops at fixed times. Formally a trip is a scheduled vehicle: a journey done by a unique vehicle from a starting stop to a last stop at a fixed time and made of connections. The inequality allows a passenger to be sure the transfer can be done even if one or both of the vehicles have a delay. The variable s change depends on the departure stop, arrival stop and modes for each of these stops. A loop is introduced on each stop to allow a passenger to get off at a stop and take another trip going through this stop.

Example We will use the public transit network of New York City.

Trips can be done by trains, trams, buses, ferry and other modes of transportation that have fixed departure and arrival times. Let t be a trip of the line 1 of the metro going to "South Ferry" with a departure date at 08/16/19 3:14 PM. The trip without a departure date is not a unique identifier because this trip exists each day of the week.

If we take 3 consecutive stops of t "50 Street", "Times Square -42 Street" and "34 Street -Penn Station", then there is a valid connection with "50 Street" as a departure stop, "Times Square -42 Street" as an arrival stop and t as a trip. There is another valid connection with "Times Square -42 Street" as a departure stop, "34 Street -Penn Station" as an arrival stop and t as a trip. A non-valid connection is a connection that has "50 Street" as a departure stop, "34 Street -Penn Station" as an arrival stop and t as a trip because there exists an intermediate stop (i.e. "Times Square -42 street").

Journeys

A journey describes how a passenger can travel through a public transit network. It is made of legs that are pairs of connections (l i enter , l i exit ) from the same trip. l i enter must appear before l i exit in the trip or l i enter = l i exit if the trip has only one connection. Formally a journey is composed of legs and footpaths alternately f 0 , l 0 , f 1 , l 1 , . . . , f k , l k . A journey must start and end with a footpath, which can be a self loop.

Connection Scan Algorithm

Given a source stop s, a target stop t, a minimum departure time τ and a timetable T , the CSA outputs a journey with the minimum arrival time over all journeys that depart after τ from s and arrive at t. This earliest arrival variant assumes that the connections are stored as a sorted array using the departure time of the connections, and that the footpaths are stored in a data structure that allows an iteration over the incoming or outgoing footpaths. A connection is reachable if a passenger can get on the connection. Similarly to Dijkstra's algorithm, tentative arrival times are stored for each stop but a priority queue is not used. Instead, the CSA iterates over all the connections (sorted by departure time) and tests if they are reachable. For each reachable connection, the algorithm updates the tentative arrival time for each stop that can be reached by foot from the arrival stop of the connection. The CSA is significantly faster than Dijsktra's algorithm even though it touches more connections, because the work required per connection does not involve a priority queue operation.

Variants of the Connection Scan Algorithm

The CSA can be extended to account for all of the source times with the profile variant. This is still done by scanning the ordered connections only once, but the journeys are constructed from late to early and the algorithm exploits the fact that an early journey can only have later journeys as sub-journeys. We then can add a Pareto set to solve a multi-criteria problem, the Pareto profile variant. When adding one criterion, the code can be modified in a specific way to avoid decreasing the performances too much but when adding more the code needs to be generic leading to a bigger decrease in performance.

Another way the CSA can be extended is the range query variant, where we only solve the earliest arrival problem for journeys that are at most two times as long as the fastest journey, the solution to this problem is a sub-set of the solution to the profile problem. In the same way as before, we can also then add a Pareto set to solve a multi-criteria problem, the Pareto range query variant. This algorithm is the PRVCSA.

GOAL-DIRECTED TECHNIQUES MEET CSA

From now on we will only consider the Pareto range query variant of the journey planning in public transit with the 4 criteria mentioned in the introduction (departure time, arrival time, walking distance and number of transfers).

CSAccel [START_REF] Dibbelt | Connection scan algorithm[END_REF] uses goal-directed techniques in the form of multi-level overlay graphs. A multi-level (hierarchical) partition of the stop set is done, this approach relies on small balanced graph cuts and while they can easily be found between cities on a country-wide scale, it is significantly more difficult to do so for a particular city. CSAccel works on a hierarchical graph that is organized geographically, large cells at the top and small cells at the bottom. A level corresponds to a geographic abstraction of the reality, the goal is to avoid scanning all the connections of a given cell. This is done with a preprocessing step by keeping a sub-set of the connection in a cell that will allow us to go through it, called transit connections, because a core observation is that connections in a journey where a passenger does not get off or on a bus do not need to be scanned. This allows the CSAccel to scan a lower number of connections by identifying potential relevant cells and only using their transit connections. CSAccel is strongly dependent on its non-obvious hierarchical graph partitioning and has a significant increase in code and algorithmic complexity compared to CSA, as said by its authors.

Our approach is simpler. It partitions the graph in areas, on a single level, and uses lower and upper bounds to open a sub-set of areas needed to compute the journey that will lead to a smaller search space, i.e. the number of connections, and in doing so the run time is lowered as well.

The idea behind the algorithm is that when computing a journey between New York and Washington, it is important to look at trips going between the two cities as well as those that go a little bit off-course, i.e. Atlantic City. On the other hand looking at trips near Boston or Syracuse will only lengthen the journey, thus we can safely remove those trips from the search space.

Partitioning the Graph

Intuitively, we want to geographically partition the timetable to allow a preprocessing step to compute lower bounds to guide the search of the GDCSA.

In order to define the geographical partitioning, we present some notations and define the core concepts of: geographical graph of a timetable, areas, boundaries and geographical partitioning.

Geographical graph

A geographic graph G = (S, E) can be abstracted from a timetable T where S is the set of stops, E is the set of edges and M is the seconds of a day such that

(u, v) ∈ E ⇒ ∃t 1 ,t 2 ∈ M, z ∈ T | (u, v,t 1 ,t 2 , z) ∈ C (1)

Area

An area a is a connected sub-graph of G. The areas partition the graph, i.e. they are pairwise disjoint, such that the union of the parts give you the entire set of stops.

We have a few definitions for an area:

• A connection c belongs to an area a if and only if c dep stop ∈ a.

• For all u ∈ S, A(u) is the area containing u.

• Let connections(a) be the list of connections of the area a.

Boundary of an area

The boundary of an area a is the set of stops B(a) ⊆ a who have at least one edge with an extremity outside of the area a.

The boundary B(a) contains the stops that allow us to leave an area a to reach another and to get to the internal stops of other areas. They are the red stops in the Figure 1.

Management of Candidate Areas

We have two definitions for the duration in public transport:

• An upper bound of the duration in public transit between two stops s and t ∈ S, with a departure time τ s is written d PT (s,t, τ s ).

• A lower bound of the duration in public transit between two stops s and t ∈ S is written d PT (s,t).

Goal directed techniques aim to guide the search toward the target by avoiding the scan of unnecessary stops. We apply the same techniques only to the areas of the graph G to avoid scanning connections that will only take us away from the target. By using upper and lower bounds on the duration between stops and more specifically between the areas.

Opening or not a candidate area will either add the connections of an area to the search space of the current journey computation if it is opened or discard them if the candidate area is not opened.

Given s,t ∈ S. A candidate area a is opened when computing a journey from s to t at time τ s if and only if

d PT (A(s), a) + d PT (a, A(t)) ≤ d PT (s,t, τ s ) (2)
Traversing an area cost 0 in time because the lower bounds are always computed using stops on the boundary. The opening of an area is schematized in Figure 2, let us assume the shortest path between points is the length of a straight line. The green and red arrows represent the lower bounds between the areas and the orange arrow represents the upper bound between and t. Two areas are depicted, the one in green will be opened because the sum of the length of the green arrow from the area containing s to the green area and the length of the green arrow from the green area to the area containing t (traversing an area cost 0) is less than the length of the arrow between s and t. However the red area will not be opened because the sum of the length of the red arrow from the area containing s to the red area and the length of the red arrow from the red area to the area containing t is greater than the length of the arrow between s and t.

Upper Bound on the Duration

Intuitively, the upper bound on the duration is found by quickly computing the size of the search span because a user isn't interested in journeys that arrive significantly later than the earliest arrival time.

We use the maximum arrival time τ t as defined in [START_REF] Dibbelt | Connection scan algorithm[END_REF], which is equal to

τ t = τ s + 2 • (x -τ s ) (3)
Where x is the earliest arrival time. This upper bound is advantageous because it is realistic e.g. consider a traveler departing at 8:00 AM and arriving at the earliest at 9:00 AM, then journeys arriving after 10:00 AM can be discarded because they are not of practical relevance.

The upper bound on the duration we use is

d PT (s,t, τ s ) = τ t -τ s (4)
That is the time span to satisfy a journey request. We can estimate d PT (s,t, τ s ) easily:

d PT (s,t, τ s ) = τ t -τ s = τ s + 2 • (x -τ s ) -τ s = 2 • (x -τ s ) (5)
The only unknown is x which is the earliest arrival time and can be computed with a CSA in an extremely small amount of time.

Lower Bound on the Duration

Intuitively, the lower bound on the duration between two stops s and t is the minimum duration over all the journeys of the day going from the the boundary of the area containing s to the boundary of the area containing t.

The lower bounds associated with an area a s is computed by launching a PCSA, the profile variant of the CSA. The start stops are the boundary of the area, as if we could reach all of them instantly. Then, we iterate over every other area and take the minimum duration to reach the boundary of the area a t from the boundary of the area a s . Algorithm 1 is a possible implementation of these computations.

The lower bounds can be computed once and for all in a preprocessing step, note that this preprocessing step can be parallelized, because each PCSA is independent and we don't access the same variables in memory, meaning the preprocessing time can be reduced. And also because the lower bound is valid for an entire day because public transit vehicle can only be delayed and cannot arrive earlier than the time written in the schedules.

GDCSA

GDCSA works in four phases, the first computes the upper bound, the second iterates over each area to only keep the ones that will be useful to the journey planning, the third will merge all the connections from the chosen areas and the last will launch a PRVCSA using the sub-set of connections.

Algorithm 2 GDCSA algorithm in pseudo-code.

function GDCSA(G, s,t, τ s ) L a ← empty list ub ← d PT (s,t, τ s )

We iterate over all areas of the graph for all a ∈ G.areas()

do if d PT (A(s), a) + d PT (a, A(t)) ≤ ub then L a .insert(a) end if end for L c ← empty list
We iterate over all opened areas of the graph for all a ∈ L a do L c .insertAll(connections(a)) end for

L c ← sort(L c )
We only use the connections of the opened areas return PRVCSA(G, s,t, τ s , L c ) end function

The GDCSA is described in the algorithm 2. We can see 4 phases: the first computes the upper bound (line 3), the second opens areas (from line 5 to line 9), the third retrieves the connections and sorts them (from line 12 to line 15) and the last launches a 4 criteria Pareto range query variant of the CSA using only the sorted connections of the opened areas (line 18). The first two parts (opening the areas and getting their connections) are easy to code and understand leading to an easy code implementation. We only need to precompute the lower bounds but we do so using a profile variant of the CSA which is also fast and easy to code.

Optimizations

Using the earliest arrival CSA instead of the lower bound Instead of using equation 2 to open a candidate area, we can use

d PT (s, r, τ s ) + d PT (r, A(t)) ≤ d PT (s,t, τ s ) (6)
by replacing the lower bound between the start stop and a candidate area with the earliest arrival time already computed by the CSA.

This will let us discard more candidate areas, allowing us to have a more fine-grained management of the candidate areas.

Optimizing the opening time All the connections of an area are not relevant, because the further away we are from the start of the journey s the lower the number of reachable connection there is. Therefore, for an area a the first connection that can be scanned by the PRVCSA has

c dep time ≥ τ s + d PT (A(s), a) (7)
So we only keep connections that have a departure time greater than the first reachable connection. For example, consider a journey from New York to Washington with a departure time at 3:00 PM, then an area near Washington only needs to scan connections with a departure time greater than 5:30 PM because the lower bound between New York and Washington is 2 hours and 30 minutes. This leads to a lower number of scanned connections.

Optimizing the closing time The same optimization can be done but for the last reachable connection.

The last connection of an area a that can be scanned by the PRVCSA must satisfy

c dep time ≤ τ t -d PT (a, A(t)) (8)
So we only keep connections that have a departure time lower than the last reachable connection.

Geographical Partitioning

The areas partition the graph. Thus, by geographically partitioning the graph, a passenger can go through an area using only its connections. We partition the graph using the inertial flow algorithm [START_REF] Schild | On balanced separators in road networks[END_REF], a simple and efficient algorithm that minimizes the boundary between the areas. This is done by sorting the list of stops using either latitude or longitude or both, choosing a certain percentage (lower than 50%) of stops at the start and end of the sorted list, which will be the sources and the sinks respectively. Then a flow algorithm is used, the min-cut gives the smallest boundary that divides the stops into two new areas. These steps are repeated for each new area, until a maximum depth or a minimum size of the area is reached.

For example, when partitioning New York City and New Jersey the algorithm will try to find the smallest boundary which would be the extremities of the bridges connecting New York City to the mainland.

Once the graph is partitioned, we precompute the lower bounds.

EXPERIMENTS

We evaluate the GDCSA and compare it to the 4 criteria Pareto range query variant of the CSA. Apart from measuring the run times, we also report the time needed for the preprocessing as well as other metrics related to the size of the search space (i.e. number of scanned connections, number of stops with at least one label). We also compare the run time of the GD-CSA to the run time of the 4 criteria Pareto range query variant of the RAPTOR.

Our test instance is based on the data of the public transit network of 3 cities (Paris, Berlin and Stockholm) and 2 country wide train networks (Germany and Switzerland), the data is openly available via a GTFS feed (https://transitfeeds.com/) which has been downloaded in October 2019. The details of the size of the instances are in table 1.

We can see that the city wide network range from big with Paris, to smaller with Stockholm, the goal of those metropolitan public transit network is to show the performances of the GDCSA on dense networks. Whereas the goal of the country wide train networks is to show the performances on sparse networks. The footpaths were given in the GTFS feed but the graph was not transitively closed, we then programmatically generated the missing ones.

We implemented all the algorithms in Java 8 and run them with OpenJDK 8. All experiments were conducted on a Intel Core i7-7700HQ processor with 16GiB of RAM.

In our evaluation, we ran for each variant of the algorithm the same set of 1000 queries generated randomly. The source and target stops are chosen uniformly at random. The departure time is picked uniformly at random within the day.

We ran a 4 criteria Pareto range query variant of the CSA (PRVCSA in the table 2), as well as the GDCSA, the 4 criteria are: maximizing the departure time, minimizing the arrival time, minimizing the number of transfers and minimizing the walked distance. We also ran a Pareto range query variant of the RAPTOR (PRVRAPTOR in the table 2) on the same set of queries.

The GDCSA uses an Inertial Flow partitioning with a maximum depth of 12.

The table 2 reports the average for the run time (query), the number of scanned connections, the number of updated stops (stops that have at least one label) and the total number of labels.

We can see that the run time of the GDCSA is 2.5 to 9 times faster than the PRVCSA. The run times for the smaller networks have a greater gain from the GD-CSA, whereas the bigger network the lower the gains are. Across all the networks we see that the number of updated stops (stops with at least one label), the number of scanned connections and the number of labels have considerably decreased when comparing the PRVCSA and the GDCSA.

As for the results of the PRVRAPTOR, we can see that the PRVCSA is 1.42 to 1.99 faster than the PRVRAPTOR, except on the Germany network where the PRVRAPTOR is faster due to the fact that the number of journeys is extremely low. This is in line with the results of (Bast et al., 2016a;[START_REF] Dibbelt | Connection scan algorithm[END_REF] where the same factors between PRVRAPTOR and PRVCSA are shown.

Note that the gains from the GDCSA are really good, one possible alternative would have been to use the same ideas on the PRVRAPTOR. Unfortunately there is no straightforward way to apply the same ideas of partitioning the stops of the graph for the PRVRAPTOR, as said in [START_REF] Delling | Faster transit routing by hyper partitioning[END_REF].

Precomputing the lower bound

Precomputing the lower bound is done by launching a profile variant of the CSA for each area.

We benchmark the partitioning and precomputing on 5 public transit networks, with a maximum depth for the Inertial Flow going from 8 to 14.

As we can see from table 3 and 4, the preprocessing time is quite short. It takes on average 30 minutes except for the biggest city-wide and country-wide network where the preprocessing is close to 3 hours. All those results are sequential, and the longest part of the preprocessing can be easily parallelized (the profile variant of the CSA for each area), meaning that a large gain is possible.

For the query times, we can see that a query with a maximum depth of 12 has the most gain compared to the preprocessing time and that with a maximum depth of 14 the gains are not worth the added preprocessing time.

Integration in an industrial product

The GDCSA is integrated in an industrial backend server for a smartphone app, with less than 1000 lines of code added. We achieve the same results as those found for the European networks, on a large and sparse instance of comparable size to the Germany instance we see that the GDCSA is 5 times faster than the PRVCSA. While also being a more complex problem, the departure and arrival stops can be GPS coordinates, mixing multiple modes of transportation (car, scooter, ...).

With a volume of only 1000 lines, this means that an external engineer could comprehend the code and then be able to modify it in less than a day, in my opinion.

CONCLUSION

In this article we presented an improvement of the CSA to compute Pareto range queries by introducing additional upper and lower bounds that guide the search by safely discarding areas that are not needed during the search. The GDCSA uses preprocessed lower bounds between each areas, and upper bounds that are computed during the journey planning. It also uses the PRVCSA as a center-piece which receives as an input the sorted list of connections from the opened areas. This leads to a simple implementation, with an already working Pareto range query variant of the CSA, the only code needed is the earliest arrival and the profile variants of the CSA. Furthermore the algorithm is easily extensible, because the addition or removal of a criterion is made simple by the fact that the upper and lower bound computation are not affected by the Pareto criteria.

Our experiments on large realistic metropolitan and country-wide public transit network have shown that the GDCSA is up to 9 times faster than the PRVCSA when computing 4 criteria Pareto range queries. An interactive use can be considered for most networks with a response time near or under 0,5 second, even if the Paris network is still too slow some headway has been made.

For future works, we would be interested in using other graph partitioning. One other interesting direction to look in would be the addition of real time information (delays, strikes, major events, ...) in the public transit journey computation. And lastly, we could look at the computation of the lower bounds and try to make them closer to the optimal by adding a temporal aspect with the computation of the lower bound for every 4 hour span of a day.

•

  A connection is a vehicle going from one stop to another with no intermediate stops, it is a sub-part of a trip. It is a quintuple (c dep stop , c arr stop , c dep time , c arr time , c trip ) whose attributes are the departure stop, the arrival stop, the departure time, the arrival time and the trip of c respectively. Each connection must respect two conditions: c dep stop = c arr stop and c dep time < c arr time . All the connections of a trip form a set. This set can be ordered in a sequence c 1 , c 2 , . . . , c k such that c i arr stop = c i+1 dep stop and c i arr time < c i+1 dep time for all i. • The footpaths are used to model transfers, in other words how to get from one vehicle to another. They are neither trips, nor connections. Formally a footpath f is a triple ( f dep stop , f arr stop , f dur ). Going from a connection c to a connection c with c trip = c trip is possible if and only if: -A footpath from c arr stop to c dep stop exists c dep timec arr time > f dur + s change

Figure 1 :

 1 Figure 1: Example of an area.

Figure 2 :

 2 Figure 2: Example of an area opening.

  Algorithm 1 Lower bound algorithm in pseudo-code.

	function LOWER BOUND(G)
	dur ← [G.areas()][G.areas()]
	Creation of a duration matrix
	for all a s ∈ G.areas() do
	r ← PCSA(B(a s ))
	We compute a PCSA using the boundary
	as starting points
	for all a t ∈ G.areas() do
	min dur ← +∞
	Minimum duration to reach a t from a s
	for all b ∈ B(a t ) do
	min dur ← min(min dur, r[b])
	end for
	dur[a s ][a t ] ← min dur
	end for
	end for
	return dur
	end function

Table 1 :

 1 Instance size.

	Network	Stops Connections Lines	Trips Footpaths
	Paris	44534	3209401 1864 150963	502291
	Berlin	28651	1379755 1296	63569	62456
	Stockholm	14258	703326	664	34799	22138
	Germany	74398	3601420 3599 168024	599284
	Switzerland 29844	2599675 5645 248826	27202

Table 2 :

 2 Details of the GDCSA and the variants of the CSA on metropolitan and country wide public transit networks.

	# Scanned # Updated

Table 3 :

 3 Performance of the precomputing on metropolitan public transit networks.

		Paris		Berlin		Stockholm
	Depth Query (ms) Prepro. (min) Query (ms) Prepro. (min) Query (ms) Prepro. (min)
	8	3849	∼ 33	450	∼ 4	103	∼ 2
	9	3686	∼ 39	408	∼ 8	102	∼ 3
	10	3364	∼ 61	379	∼ 13	92	∼ 5
	11	3133	∼ 96	357	∼ 15	91	∼ 8
	12	2981	∼ 172	338	∼ 20	89	∼ 12
	13	2953	∼ 315	323	∼ 30	85	∼ 14
	14	2884	∼ 413	317	∼ 43	88	∼ 16

Table 4 :

 4 Performance of the precomputing on country-sized public transit networks.

		Germany		Switzerland
	Depth Query (ms) Prepro. (min) Query (ms) Prepro. (min))
	8	898	∼ 26	238	∼ 12
	9	843	∼ 43	217	∼ 16
	10	703	∼ 73	195	∼ 27
	11	598	∼ 120	187	∼ 29
	12	529	∼ 178	147	∼ 43
	13	513	∼ 240	132	∼ 58
	14	505	∼ 301	129	∼ 70

ACKNOWLEDGEMENTS

This work has been supported by the 3IA Côte d'Azur, Interdisciplinary Institute for Artificial Intelligence (ANR-19-P3IA-0002) and by ANR project MULTIMOD (ANR-17-CE22-0016).