Cyril T Langlois
email: cyril.langlois@paris7.jussieu.fr

T Oikawa

Pascale Bayle-Guillemaud

Christian Ricolleau

Tetsuo Oikawa°

Energy filtered electron microscopy for imaging core-shell nanostructures

Keywords: Energy filtered transmission electron microscopy, nanoparticles, core-shell system, crystal growth

HAL is

Introduction

Core-shell nanostructures have recently attracted much attention, from both experimental and theoretical point of views, since it is possible to enhance or to design new physical and chemical properties that cannot be obtained in the single components nanoparticles. It is also possible, by modifying the thickness of the shell to tailor these properties in a certain range. Coreshell nanoparticles have been used for catalysis applications, optical and magnetic properties. For the catalysis applications, the association of two different metals offers higher catalytic activity, better selectivity of catalytic reactions and stability [START_REF] Sao | Structure and Deformations of Pd-Ni Core-Shell Nanoparticles[END_REF][START_REF] Skarman | Morphology and Structure of CuO x /CeO 2 Nanocomposite Catalysts Produced by Inert Gas Condensation: An HREM, EFTEM, XPS, and High-Energy Diffraction Study[END_REF][START_REF] Toshima | Core/shell-structured bimetallic nanoclusters catalysts for visible-light-induced electron transfer[END_REF][START_REF] Toshima | Catalytic activity and structural analysis of polymer-protected Au-Pd bimetallic clusters prepared by the simultaneous reduction of HAuCl 4 and PdCl 2[END_REF]. In the case of magnetic properties, core-shell nanostructures have been developed to obtain nanoparticles with individual improved magnetic properties by reducing the direct interaction between the nanoparticles [START_REF] Favre | Nanostructured thin films from mixed magnetic Co-Ag clusters[END_REF][START_REF] Zeng | Bimagnetic Core/Shell FePt/Fe 3 O 4 Nanoparticles[END_REF]. In the optical domain, semiconductor core-shell nanostructures have been synthesized to enhance photoluminescence by the passivation of the core material with a shell having a higher band gap energy [START_REF] Chen | Coherency Strain Effects on the Optical Response of Core/Shell Heteronanostructures[END_REF][START_REF] Reiss | Highly Luminescent CdSe/ZnSe Core/Shell Nanocrystals of Low Size Dispersion[END_REF], to improve stability against photochemical oxidation and to perform band structure engineering [START_REF] Correa-Duarte | Stabilization of CdS semiconductor nanoparticles against photodegradation by a silica coating procedure[END_REF][START_REF] Kim | Type-II Quantum Dots: CdTe/CdSe(Core/Shell) and CdSe/ZnTe(Core/Shell) Heterostructures[END_REF].

Metal/oxide and metallic core-shell nanostructures have also been developed in order to modify the surface plasmon resonance energy to a given value by varying the relative composition of the core and the shell as well as their relative size [START_REF] Basu | Optical properties of nanocomposites with iron core-iron oxide shell structure[END_REF][START_REF] Gaudry | Size and composition dependence in the optical properties of mixed (transition metal/noble metal) embedded clusters[END_REF][START_REF] Zhu | Resonance light scattering characters of core-shell structure of Au-Ag nanoparticles[END_REF]. Finally, some recent papers report the use of core-shell nanocomposite materials formed with metal, oxide and/or semiconductor in order to combine magnetic and optical properties in a single nanostructure [START_REF] Kim | Synthesis and Characterization of Co/CdSe Core/Shell Nanocomposites: Bifunctional Magnetic-Optical Nanocrystals[END_REF][START_REF] Lu | Synthesis and Self-Assembly of Au@SiO 2 Core-Shell Colloids[END_REF].

In all such applications, the knowledge of the morphology as well as the precise thickness of the shell are key parameters in order to understand the physico-chemical properties of the nanostructures. Several techniques have been used to study these nano-objects. These techniques can be classified in two categories: the ones that give access to direct imaging of the core-shell nanostructures and the spectroscopic techniques which give indirect information on the nanostructures but in a more statistical way. Transmission Electron Microscopy (TEM) is one of the best tools to image such nanostructures. Among the various TEM techniques, the most common ones to study single objects are the High Resolution Transmission Electron Microscopy (HRTEM) and the Scanning Transmission Electron Microscopy (STEM) imaging techniques. While the first one has several limitations (low sensitivity to chemistry, zone axis orientation, etc.) for the characterization of core/shell nanostructures the second one has given very good results in the AuPt and AuAg systems [START_REF] Garcia-Gutierrez | HAADF study of Au-Pt core-shell bimetallic nanoparticles[END_REF][START_REF] Li | Direct imaging of core-shell structure in silver-gold bimetallic nanoparticles[END_REF].

In the domain of spectroscopy, Raman [START_REF] Hodak | Coherent Excitation of Acoustic Breathing Modes in Bimetallic Core-Shell Nanoparticles[END_REF][START_REF] Sader | Theory of Acoustic Breathing Modes of Core-Shell Nanoparticles[END_REF], EXAFS (Extended X-ray Absorption Fine Structure) [START_REF] Harada | Structure of Polymer-Protected Palladium/Platinum Bimetallic Clusters at the Oxidized State. Extended X-ray Absorption Fine Structure Analysis[END_REF] and optical spectroscopies [START_REF] Lu | Synthesis and Self-Assembly of Au@SiO 2 Core-Shell Colloids[END_REF][START_REF] Huang | Synthesis of Dumbbell-Shaped Au-Ag Core-Shell Nanorods by Seed-Mediated Growth under Alkaline Conditions[END_REF][START_REF] Yang | A Phase-Transfer Identification of Core-Shell Structures in Ag-Pt Nanoparticles[END_REF] have been widely used. Since the interpretations of the data are model dependent, they have to be used in close connection with, at least, one of the imaging techniques cited above [START_REF] Cazayous | Cu-Ag core-shell nanoparticles: A direct correlation between micro-Raman and electron microscopy[END_REF].

In this paper, we have studied by Energy Filtered TEM (EFTEM) the CuAg core-shell nanostructure. A core-shell growth is expected according to thermodynamical arguments: silver and copper being immiscible elements (0.1 % solid solution at 298 K) and a lower surface energy for Ag (1210 mJ/m 2 for Ag compared to 2130 mJ/m 2 for Cu) favor the surface silver segregation. These values are averaged from {111}, {110} and {100} surfaces energies [START_REF] Vitos | The surface energy of metals[END_REF]. The chemical mapping by EFTEM has been widely used for the characterisation of multilayered materials. This is a perfect tool to study core-shell nanostructures since it produces a chemical map of the specimen on sufficiently large area that allows to obtain statistical data on the specimen. To our knowledge, the EFTEM technique is actually not enough popular in the materials science community and needs further attention because of its high performance to image complex nanoobjects at a nanometer resolution. These experiments have been coupled to HRTEM observations in order to study the structural properties of the core-shell configurations at the atomic scale.

Experimental methods

CuAg core-shell synthesis

Core-shell CuAg nanostructures are fabricated by successive deposition of Cu and Ag under ultra-high vacuum conditions directly onto carbon coated grids. The deposition method is thermal evaporation from two crucibles containing respectively Cu and Ag. The substrate is an ultra-thin amorphous carbon film (thickness about 4 nm) transparent to electron beam and supported by a holey carbon microscopy grid. This kind of substrate was chosen because of the importance of substrate thickness in the results presented hereafter and also because it can be used by almost everyone involved in nanoparticles fabrication, including both chemists and physicists.

During the deposition of Cu and Ag, the substrate is heated at a temperature of 400°C. After this operation, the nanoparticles are annealed during half an hour at the same temperature in ultrahigh vacuum. Pressure inside the deposition chamber is below 107 Torr. Typically, evaporation rates for Cu and Ag were around 0.25 nm per minute in nominal thickness. Since the wetting of metallic species on amorphous carbon is low [START_REF] Campbell | Ultrathin metal films and particles on oxide surfaces: structural, electronic and chemisorptive properties[END_REF], nanoparticles are formed instead of a film on the substrate and the nominal thickness indication does not obviously correspond to the size of the particles. For CuAg nanoparticles, two different core-shell nanoparticles were synthesized: (i) sample A obtained by a deposition of 6 nm of Cu followed by a deposition of 3 nm of Ag, and (ii) sample B obtained by a deposition of 2 nm of Cu followed by a deposition of 1 nm of Ag.

Energy filtered TEM technique and application to chemical mapping

The basic principle of the Electron Energy Loss Spectroscopy (EELS) consists in the energy dispersion of the electron beam with a magnetic prism after the specimen in order to obtain a spectrum of the electron energy losses [START_REF] Egerton | Electron energy-loss spectroscopy in the electron microscope[END_REF]. Energy filtered imaging (EFTEM) can be obtained by introducing a slit in the energy dispersive plane along the optical path and hence selecting only electrons having lost a specific part of their energy by inelastic interactions with the different elements of the specimen. By optically forming images with the energy filtered electrons, it is then possible to obtain chemical maps of the region of interest [START_REF] Reimer | Electron Spectroscopic Imaging[END_REF][START_REF] Shindo | Analytical Electron Microscopy for Materials Science[END_REF].

For core-shell nanoparticles, lateral (projected) dimensions of the Ag shell are small, and the thickness is also limited along the optical axis. These limitations result usually in poor signal-tonoise ratio (SNR) for the images and may be the restrictive criterion for applying the EFTEM technique to nanostructured core-shell particles. This is the reason why we used an ultra-thin carbon film as a substrate for the nanoparticles deposition, in order to minimize its contribution to the filtered image. Choosing an commercial amorphous carbon substrate is interesting for characterizing nanoparticles synthesized by chemical routes: several procedures exist to transfer the nanoparticles from the solvent to the surface of the thin carbon film without too much aggregation [START_REF] Zeng | Bimagnetic Core/Shell FePt/Fe 3 O 4 Nanoparticles[END_REF][START_REF] Yang | A Phase-Transfer Identification of Core-Shell Structures in Ag-Pt Nanoparticles[END_REF].

EELS spectra have been first acquired on the B sample, with the thinnest Ag layer, to get insight for the EFTEM parameters, that is, at which edges the selecting slit should be exactly placed for constructing the chemical maps for Ag and Cu, as well as the appropriate energy width of the slit. A large area including many particles has been selected by decondensing the electron beam.

Experimental Cu and Ag electron energy-loss spectra are shown on Figure 1a and 1b respectively.

The shape of the Cu edge corresponds to the reference given by Ahn and Krivanek [START_REF] Ahn | EELS Atlas: A Reference Guide of Electron Energy Loss Spectra Covering all Stable Elements[END_REF], with a smooth edge located at 920eV (L 2,3 edges), followed by a second part slowly decreasing. The L 1 core-loss absorption edge is clearly visible at 1100eV. The shape of the spectrum is typical from non-oxidized copper [START_REF] Shindo | Analytical Electron Microscopy for Materials Science[END_REF]. Due to the small quantity of silver with respect to copper (1:2) together with the formation of shells instead of clusters, the Ag spectrum is far more diluted into the background.

The microscope used for this study was a JEM 2100F working at 200 keV, equipped with a high-resolution pole piece (point-to-point resolution of 0.19 nm) and a post-column GIF 2001 (Gatan Imaging Filter). Chemical maps have been acquired by the three-window technique [START_REF] Reimer | Electron Spectroscopic Imaging[END_REF] using the GATAN Digital Micrograph software. The optimum conditions are realized using a slit width of 30 eV with the three windows centred at 340, 380 and 420 eV for Ag, and 850, 900 and 950 eV for Cu.

Chemical and structural study

Sample A -Chemical mapping

Conventional TEM images in bright field mode are commonly used to determine statistically the shape and the size of the nanoparticles. However, this type of images gives no insight on the chemical nature of the nanoparticles. In this work, chemical maps of Ag and Cu are obtained by performing EFTEM experiments on nanoparticles formed on sample A. Figure 2 shows a set of three EFTEM images revealing the core-shell structure of the considered area. On the Ag map (Figure 2a) and the Cu map (Figure 2b), white pixels correspond to Ag and Cu signals, respectively, on the same area. The complementarity between the Cu and Ag localization is well convincing. Figure 2c shows a color image compiling Ag and Cu maps together, which gives a strong evidence of the formation of core-shell arrangements on sample A.

Criterion for shell thickness measurements

The criterion that will be used to measure the Ag shell thickness on the EFTEM images has to be clearly defined before starting a statistical study of the EFTEM images. To address this point, we consider the intensity profiles drawn on an Ag EFTEM image of sample A across (i) a core-shell nanoparticle (Figure 3a, left) and (ii) a pure Ag nanoparticle (Figure 3a, right). First of all, we can notice that the Ag signal on the core-shell intensity profile is lower near the centre of the nanoparticle than on the edges, where the profile exhibits two intense peaks with different decreasing behavior depending on whether the inner or the outer side of the nanoparticle. These two observations can be explained using a simple geometrical model of the nanoparticle shape: the cores are assumed to be half ellipsoids, truncated by the substrate, and silver consists in an homogeneously thin layer covering the core. The half ellipsoidal morphology is considered here because of (i) the weak interactions between copper and the amorphous substrate, (ii) high diffusion of metallic species on the heated substrate and (iii) coalescence events during the growth, giving rise to elliptic morphologies in the plane of the substrate. Figure 3b shows a cross section of such a modelled core-shell nanoparticles (black lines). The Ag thickness crossed by the electron beam (which is considered perpendicular to the substrate) as a function of the position is also represented on the figure (grey line). A larger Ag thickness crossed by the electron beam will results in a larger number of inelastic interaction events. This is the reason why the intensity profile will be higher on the edges of the core and smaller in the middle of the nanoparticle. As a consequence, the two peaks match the maximum projected Ag thickness visible on the model. The decreasing behaviors on both sides of the peaks also correspond to the variation of the Ag thickness crossed by the electron beam.

It is important to note that the global shape of the intensity profile (double-peaked and non-zero intensity at the centre) is the same if we consider a spherical shape, an ellipsoidal shape with any semi-axes values, with any height of truncature by the substrate.

A question remains: where stops the Ag layer on the edges of the core-shell nanoparticle ? It seems reasonable to consider that when the intensity becomes comparable to the noise level of the image, the limit of the nanoparticle is reached. The error on the measurement then depends on the shape of the silver layer and the SNR of the images.

From these considerations, the criterion chosen to measure with a good approximation the Ag shell thickness was defined as the lateral extension between the maximum intensity of the peak and the limit of the area for which the intensity becomes comparable to the standard deviation of the noise level of the image. An example is shown on the core-shell intensity profile of Figure 3a left (black area).

Profiling also allows differentiating between core-shell nanoparticles and pure Ag nanoparticles on EFTEM images. On the EFTEM image of Figure 3a, a second distribution of very small Ag nanoparticles appears between the large CuAg clusters. For these pure Ag nanoparticles, the contrast variation across the particle (Figure 3a, right) is obviously different from the core-shell profile of Figure 3a, left. The results of the shell thickness measurements using the criterion described here have been confirmed by a more global technique. In a previous work [START_REF] Cazayous | Cu-Ag core-shell nanoparticles: A direct correlation between micro-Raman and electron microscopy[END_REF], we measured by micro-Raman spectroscopy the shell thicknesses in an assembly of CuAg core-shell nanoparticles precisely located on a labelled microscopy grid. The measurements were obtained using the Lamb theory to extract the average Ag layer thickness from acoustic breathing resonance of the core-shell nanoparticles, with an accuracy of 0.3 nm. The results obtained on the very same particle population using a global and a local technique were identical and this gives us a strong confidence in the EFTEM measurement criterion defined in this work.

Core size and shell thickness measurements

The size distribution on CuAg sample A, presented on Figure 4a, exhibits a bimodal size distribution centred on 4.5 nm (FWHM 3.9 nm) for the first peak and 20.5 nm (FWHM 11.6 nm) for the second. This corresponds to the core-shell CuAg population combined with the small pure Ag nanoparticles. Such a polydisperse distribution is common when thermal evaporation is used to synthesize the nanoparticles. The shell thickness distribution (Figure 4b) obtained from EFTEM images is centred on 5 nm (FWHM 2.2 nm), with values ranging between 3 nm and 7 nm.

As it can be seen on Figure 2c, different configurations are formed on the substrate. Perfect CuAg core-shell nanoparticles are visible, together with partially segregated ones and pure Ag nanoparticles. It is interesting to note that segregation occurs for the largest nanoparticles, contrary to the smallest ones which are in a perfect core-shell arrangement. This point will be developed later in this paper.

Moiré effect

The complete capping of the Cu core by the Ag shell is evidenced by a well-known optical effect called 'moirés' (Figure 5). Large dark stripes appear on bright field TEM images when interferences occur between two slightly different spatial frequencies (in orientation and/or spacing) in the reciprocal space. Here, the two sets of fringes are the (111) fringes from Cu and Ag and they are oriented in the same direction because of the epitaxial relationship between the two crystals.

This epitaxial relationship can be seen on the power spectrum on the inset of Figure 5, on which Ag and Cu crystals are oriented along the same [110] nm). This means that the thickness of the Ag layer is greater than the critical thickness below which the accommodation of the core-shell lattice misfit by elastic strain would occur.

Sample B -Chemical mapping and measurements

From Figure 2c, it is worth noting that the core-shell arrangement is found for the smallest nanoparticles (<12 nm) of the distribution. Over this limit, most of the CuAg nanoparticles do not present the core-shell configuration. The size of the pre-existing Cu cores being unambiguously an important parameter in the formation of the core-shell arrangement, we turned to the synthesis of a core-shell system with smaller cores. Controlling the size of the Cu nanoparticles can be done by two different means. The first way would be to lower the substrate temperature during the formation of the Cu core, decreasing the Cu diffusion on the surface. Cu atoms would be then fixed more efficiently on the nucleating sites, resulting in an increased number of particles per unit area, and subsequently smaller particle sizes. The other mean is to decrease the quantity of matter during deposition, keeping constant all the other parameters, especially the substrate temperature. The density of particles per square nanometer remains the same, and the mean nanoparticles size decreases because of the lack of atoms available for the growth.

For the sample B, the same ratio 2:1 between the two elements has been kept but with three times less copper and silver deposited (namely 2 nm of Cu and 1 nm of Ag in nominal thickness).

These growth conditions have resulted in smaller core-shell nanoparticles with a smaller shell thickness.

The same procedure as for the sample A has been used on sample B to obtain the size distribution of the CuAg and Ag nanoparticles as well as the shell thicknesses (Figure 6). First, the observation made on sample A is confirmed: one can note that perfect core-shell nanostructures are more frequently formed on the substrate, compared to sample A (Figure 6a). The size distribution on CuAg sample B presents a bimodal size distribution centred on 5 nm (FWHM 9.5 nm) for the first peak and 17 nm (FWHM 5.0 nm) for the second. The shell thickness distribution obtained from EFTEM images is centred on 2 nm (FWHM 0.5 nm), with values ranging between 1 nm and 3.5 nm. This could be explained by a smaller initial Cu core size, suggesting a critical core size over which silver segregation is promoted. The origin of a critical core size may be linked to the way silver grows on the Cu nanoparticles. From crystal growth theory, it is well known that the growth rate is different depending on the Miller indices of the face exposed to incoming species. On the other hand, Cu nanoparticles exhibits three different morphologies depending on their size: icosahedral below 4.5 nm, decahedral between 4.5 and 7 nm [START_REF] Mottet | [END_REF] and FCC Wulff shape above 7 nm (Henry, 1998). Icosahedral and decahedral shapes present principally (111) faces.

As a consequence, the growth of the Ag shell will tend to be isotropic, and hence the thickness will be homogeneous all around the Cu cores. Further experiments are currently under progress to detail this result.

HRTEM core-shell arrangement characterization

In addition to the EFTEM technique, it is interesting to consider the use of HRTEM to characterize the core-shell configurations on the substrate. Figure 7a shows a HRTEM image acquired on a core-shell nanoparticle. This image has been Bragg-filtered to compute a new image on which the contrast corresponds to the localization of {200} Ag lattice fringes (Figure 7b). The radius of the mask for the filter has been chosen to ensure a resolution of one lattice fringe (i.e. 0.2 nm). The same core-shell nanoparticle has been observed by EFTEM, and the corresponding image is presented on Figure 7c. By comparing the two images (Figure 7b andc), it is clear that trying to localize silver from the Bragg filtered image is totally misleading if we refer to the EFTEM image.

The HRTEM images can give wrong chemical information because of both technical artefacts and limitations due to the sample. From a technical point of view, the best contrast conditions are usually obtained by defocusing the objective lens of the microscope in order to adjust the transfer function of the microscope to the so-called Scherzer conditions. Fringes delocalization occurs in this case. Moreover, Ag and Cu superimposition effects influence dramatically the image contrast. To extract quantitative information from HRTEM images in such case, one has to carry out image contrast simulations by continuously varying the thicknesses of the two materials, together with the focus of the objective lens (through-focus series). Conditions for which the Ag lattice fringes vanish completely can be identified by this way. Concerning sample limitations, the nanoparticles may not be perfectly in zone axis orientation due to the amorphous substrate, which disturbs the formation of lattice interference fringes for both Ag and Cu. It is also assumed that the Ag layer is perfectly relaxed to its own bulk lattice parameter, without any strain effects from the underlying Cu lattice. Finally, if the Ag shell is locally slightly disoriented, the intensity will fall down in the Bragg-filtered image, and will result in misleading chemical information. To summarize, it is worth noting that obtaining chemically interpretable HRTEM images is rather difficult, particularly if statistical analysis is required. In addition, for core-shell systems, in which the lattice parameters are very close, high resolution lattice contrasts appear the same on the images, and this technique is useless to distinguish between the core and the shell.

This pessimistic presentation is tempered by the fact that, among the billion particles accessible to observation on the microscopy grid, a significant number will present good imaging conditions without most of the limitations exposed above. Hence, a good result is a question of time of experiment, but in no case HRTEM can replace EFTEM statistical efficiency for determining the different chemical arrangements.

Discussion

For the core-shell systems, characterizing statistically the segregation of silver by means of HRTEM only would have been a giant task. On the contrary, EFTEM imaging provides an answer on silver localization for each particle in the field of view of the recording camera, in an acquisition time of few tens of seconds. According to the arguments developed in the previous parts, the preeminence of EFTEM over HRTEM is clearly demonstrated in case of chemical core-shell nanoparticles characterisation.

For a large part of research teams working on core-shell nanostructures, either synthesized by chemical or physical route, the EFTEM technique could consist in a highly valuable help for characterizing such nano-objects. Another argument for the EFTEM promotion is the large number of filters available through the world, easily accessible through collaborations.

More generally, even if intense research efforts have been conducted on global optical method to infer the structural nature (core-shell or not) of an assembly of nanoparticles [START_REF] Chen | Coherency Strain Effects on the Optical Response of Core/Shell Heteronanostructures[END_REF][START_REF] Lu | Synthesis and Self-Assembly of Au@SiO 2 Core-Shell Colloids[END_REF], a local characterisation using EFTEM or other TEM techniques must never be ruled out in order to take into account the potential complexity of layered nanoparticles as well as possible segregation of one species into a second population of pure element clusters, together with inhomogeneities within the specimen [START_REF] Cazayous | Cu-Ag core-shell nanoparticles: A direct correlation between micro-Raman and electron microscopy[END_REF].

The successful use of the EFTEM technique to characterize a given system is also dependent on some experimental considerations. The pertinence of the elemental mapping is based on a correct background subtraction to remove from the image the contribution of electrons coming from interactions with other elements and substrate. This correction may be difficult to achieve when another energy-loss edge corresponding to an element present in the specimen is close to the edge of interest. For instance, in our case, the tail of the carbon K edge at 284 eV was disturbing the acquisition of the first reference image necessary to subtract the background for Ag mapping, and we were forced to adapt the thickness of the carbon substrate and the position of the pre-edge windows consequently. Wrong background estimation can generate some artefacts in the final chemical map, misleading conclusions about the specimen. Fortunately, some techniques have been developed to overcome this problem [START_REF] Egerton | Electron energy-loss spectroscopy in the electron microscope[END_REF][START_REF] Reimer | Electron Spectroscopic Imaging[END_REF].

Another concern is the shape of the edge corresponding to a given element, which can be either 'saw tooth-like' (more or less blunted !) for most of the L-shell edges of III th period elements, or 'white line-type' for elements of the IV th period (until copper), according to the vocabulary widely used in the EELS community [START_REF] Egerton | Electron energy-loss spectroscopy in the electron microscope[END_REF]. 'White line' edges are most favorable for EFTEM imaging because of the high number of electrons that can be selected within a narrow energy slit in the dispersion plane of the spectrometer. This is of main importance since the use of a large slit (to collect more electrons in a wider range of energies) hugely decreases the spatial resolution of the chemical map. The choice of the slit width is always a balance between the spatial resolution and the SNR.

As it was pointed out in this paper, it is possible to overcome the above limitations by minimizing the thickness of the substrate and by determining the optimum energy position and energy width of the windows (in the chemical map calculation) during the pre-and post-edge signal acquisition. Practically, the EFTEM technique and the criterion defined in this paper can be used for nanoparticles of any sizes, with shell thicknesses over 1 nm.

Other local techniques using the TEM have been used to characterize core-shell nanoparticles. Li et al. [START_REF] Li | Direct imaging of core-shell structure in silver-gold bimetallic nanoparticles[END_REF] give an excellent example of how High Angle Annular Dark Field (HAADF) imaging can be used to obtain chemical information over an area of interest containing core-shell AuAg nanoparticles. A joined advantage for EFTEM and HAADF technique compared to HRTEM is that a low index zone axis orientation is not necessary, as they point out in their conclusion. [START_REF] Garcia-Gutierrez | HAADF study of Au-Pt core-shell bimetallic nanoparticles[END_REF]) also use HAADF to evidence the core-shell structure in AuPt through the contrast produced by the strain field between the Au core and the Pt shell, but in cases where the nanoparticles are oriented along a zone axis.

Conclusion

In summary, the way a system can be detailed in term of core-shell structure at the nanoscale by the EFTEM technique has been fully demonstrated on the CuAg system, naturally forming nonalloyed nanoparticle configurations. The approach presented in this paper can be very useful to a large community of researchers involved in nanostructured core-shell or alloyed systems characterisation [START_REF] Amalvy | Characterization of the Nanomorphology of Polymer-Silica Colloidal Nanocomposites Using Electron Spectroscopy Imaging[END_REF][START_REF] Horiuchi | Nanoimaging and Spectroscopic Analysis of Rubber/ZnO Interfaces by Energy-Filtering Transmission Electron Microscopy[END_REF]. EFTEM and HRTEM techniques are shown to be complementary since HRTEM can provide invaluable structural information at the atomic level whereas EFTEM can give a straight answer about the chemical features of the specimen. Like the EDX technique, the use of the EFTEM technique can be either in a routine and qualitative way or, at the opposite, very fine and quantitative, with new developments frequently published to improve the technique (deconvolution, spectrum imaging, drift corrections…) [START_REF] Egerton | New techniques in electron energy-loss spectroscopy and energy-filtered imaging[END_REF][START_REF] Grogger | Energy-filtering transmission electron microscopy on the nanometer length scale[END_REF].

Figure Captions Figure 1 .

 Captions1 Figure Captions

Figure 2 .

 2 Figure 2. (a) Ag chemical map of an area on sample A, (b) Cu chemical map of the same area and

Figure 3 .

 3 Figure 3. (a) EFTEM image of sample A, together with intensity profiles corresponding

Figure 4 .

 4 Figure 4. Statistical measurements on sample A -a) Size distribution showing the superimposed

Figure 5 .

 5 Figure 5. High resolution image of a core-shell nanoparticle of sample A, oriented along the [111]

Figure 6 .

 6 Figure 6. (a) Ag chemical map obtained by EFTEM technique on sample B, (b) size distribution

Figure 7 .

 7 Figure 7. (a) HRTEM image, (b) Bragg filtered image and (c) EFTEM image of the same

  zone axis of the Face Centred Cubic (FCC) structure, with the same radial orientation of the four equivalent 111 reflections of the two crystals.

	A set of moiré fringes is then formed, normal to 1 Moiré d d   g g 111 Cu 111 111 111 111  Ag Cu Ag Cu d d d     By taking 111 0.2087 Cu d  nm, the moiré pattern periodicity (d moiré = 1.7 +/-0.15 nm) gives a value of 111 Ag g , with spacing equal to: 0.237 nm for 111 Ag d in the epitaxial layer, which gives an Ag lattice parameter equals to 0.410 0.06 a  nm, showing that the silver layer has recovered the bulk Ag lattice parameter ( 0.4086
	g

bulk a 


C Langlois

Z W Wang

D Pearmain

C Ricolleau

Z Y Li
email: z.li@bham.ac.uk

HAADF-STEM imaging of CuAg core-shell nanoparticles

Scanning transmission electron microscopy (STEM) is used in this study to determine the location of silver in bimetallic CuAg nanoparticles. The Z-contrast effect in STEM is particularly useful in our case because of the large difference in Z number between the two materials. However, the channeling effect that occurs when electrons are transmitted through a crystalline nanoparticle near a zone axis orientation prevents a direct interpretation of the STEM image contrast in terms of silver location. Two simple procedures are presented in this paper to estimate the contribution due to channeling, by varying the detection angle and by tilting the specimen a few degrees from its original orientation.

Introduction

Nanoparticles comprising two different metallic elements offer an additional degree of freedom for altering their physical properties compared to monometallic nanoparticles. This could potentially enable a wide range of new materials and properties. However, as physical properties of nanoparticles depend strongly on their atomic arrangements and structures and because in most cases nanoparticles on a specimen can exhibit size/structure distribution, it is crucial to obtain the localized elemental and structural information of a given bimetallic nanoparticle. For example, for the CuAg core-shell nanoparticles that we have prepared, the location of silver within the particles (core-shell or sidesegregated) is particularly important because the optical properties of such particles are linked to the plasmon resonance frequency of silver, which often depends on its environment.

Scanning transmission electron microscopy (STEM) has been demonstrated possessing capability of exploring the three-dimensional shape and structure of nanoparticles at atomic-scale [1]. It also has potential to correlate structures with electronic and chemical properties of nanomaterials [2,3]. We focus in this paper on the use of STEM with high-angle annular dark field (HAADF) detector for a direct determination of chemical composition within bimetallic CuAg nanoparticles through an incoherent Z-contrast imaging interpretation. Here, we present two simple procedures developed to rule out the possible artifacts from the true chemical information by controlling the so-called channeling effect that occurs when electrons cross a crystal near zone axis orientation. The effects of the detection angle and small sample tilting on the contrast of HAADF-STEM images are considered.

Experimental details

Bimetallic CuAg nanoparticles are prepared under ultra-high vacuum conditions by pulsed laser deposition at MPQ-CNRS laboratory. Copper nanoparticles are first synthesized by condensing Cu atoms onto a thin amorphous carbon film, supported by an electron microscopy grid. Silver is then ablated and deposited on the pre-existing Cu nanoparticles. As neither Cu nor Ag wet easily on the amorphous carbon film, nanoparticles are formed instead of a continuous film. For this study, two samples were prepared. Sample A has been obtained with a deposition of Cu and Ag, with nominal thicknesses of 2 and 1 nm respectively. Sample B is a reference sample with elemental Cu nanoparticles only, obtained simultaneously during the same experiment. For both samples, the substrate temperature was held at 350°C during the deposition. Finally, a 2 nm layer of alumina was deposited to cap the nanoparticles in order to prevent their contamination.

A 200kV FEI Tecnai F20 scanning transmission electron microscope with a field-emission electron source at the University of Birmingham was employed for ex-situ examination. The microscope is fitted with a Fischione model 3000 HAADF detector. The camera length used for this study ranges from 520 to 52 mm, corresponding to the inner collection angle from 12 to 120 mrad.

Results and discussion

3.1. Channeling effect STEM channeling takes place in thin crystals oriented in a zone axis parallel to the electron beam. This effect corresponds to the tendency for the electron beam to stay close to the atomic columns when it crosses the sample [START_REF] Reimer | Scanning Electron Microscopy[END_REF]. This maximizes the scattered intensity of the crystal and would make the crystal appear brighter than a corresponding crystal of same thickness and composition but in an off-axis orientation. Without taking any particular experimental care, the channeling effect would prohibit a direct interpretation of the images in HAADF-STEM mode in terms of chemical localisation by Z-contrast. This is particularly true for the crystalline CuAg nanoparticles prepared for this study. To illustrate this phenomenon, we carried out HAADF-STEM imaging on both CuAg and Cu nanoparticle samples.

Figure 1 shows a comparison between HAADF-STEM images for the two specimens, acquired using the same experimental conditions with a large camera length of 520 mm. This camera length corresponds to an inner angle of 12 mrad and an outer angle of 60 mrad on the HAADF detector. For the CuAg sample (Figure 1a), strong intensity variations between different particles can be noticed, and also variations of the intensity within a single nanoparticle. The latter could be attributed to the segregation of Cu and Ag inside the nanoparticle, because of the large difference in atomic number between Cu (Z=26) and Ag (Z=47). However, similar contrast has been identified on images of sample B that has only elemental Cu nanoparticles on. This comparison demonstrates that these intensity variations are not solely due to the Z-contrast. Indeed, a large proportion of the copper nanoparticles of sample B are not monocrystalline [START_REF] Langlois | [END_REF], and often one of the crystallites composing a copper nanoparticle can be in Bragg orientation relative to the incident electron beam. Channeling effect is then the most probable reason for explaining such a sharp variation of contrast when no chemical contrast presents. The another possible mechanism of intensity variation is strain contrast [6], which is important in this lattice mismatched CuAg bimetallic nanoparticles but does not applys to Cu nanoparticles on the amorphous substrate.

In our present study, we need to avoid channeling effect because here the aim is to get insight on the position of silver atoms over all the area of interest. Because each nanoparticle possesses its own crystallographic orientation, the channeling effect occurs in a different orientation for each of the nanoparticles and it would not be straightforward to deduce useful information about the chemical composition of the bimetallic nanoparticles through simple intensity variation analysis. Care needs to be taken to circumvent the channeling effect.

Scattering angle variation

Figure 2 shows four HAADF-STEM images of the same area of sample A, CuAg nanoparticles, acquired with different collection angles from ADF to HAADF conditions. Whereas a majority of the nanoparticles have kept their internal intensity contrast variation unchanged when the camera length is varied, it is interesting to note that a few particles undergo a contrast inversion (particles arrowed on the figures). This means that, for small collection angles (large camera length), the Bragg-oriented part of the particle gives an intensity by channeling that is larger than the intensity due to the atomic number contrast. This contrast inversion shows that the collection angle used for Figure 2d is large enough to cancel a large part of the diffracted intensity and to restore a contrast linked to the local chemical composition within the nanoparticle. Applying this procedure, it is then possible to discriminate between particles in Bragg orientation giving rise to high intensity through channeling for small collection angles, and off-axis nanoparticles for which the Z-contrast theory can be safely applied for localizing silver because of its big difference in atomic number compared to copper. Clearly, the signal-to-noise ratio of images acquired with such large collector angles is weak. Therefore, optimum conditions need to be carefully assessed and chosen. For bimetallic particles with two metals close in their atomic number, the decreased signal to noise ratio could mask the intensity difference arising from chemical composition.

Specimen Tilting

The channeling effect is very sensitive to the lattice orientation [7]. It is found that one or two degrees tilt of the specimen is enough to decrease the intensity of on-axis nanoparticles and recover a contrast linked to the local chemistry. Figure 3 displays an example of the specimen tilt effects on CuAg nanoparticles, where intensity variation in the arrowed particle is obvious.

This procedure has some advantages compared to the use of a small camera length. By keeping a reasonable scattering angle, the intensity detected does not fall down quickly as the specimen is tilted, thus the signal-to-noise ratio is largely preserved. Small nanoparticles can then be investigated without loosing too much resolution. However, the nanoparticles prepared through the approach we take are oriented randomly along the electron beam, therefore, each particle needs to be examined individually.

Again, among all the particles within the area under consideration, only a few of them may show a contrast that can unambiguously be assigned to silver. It is worth of pointing out that the specimen tilting, whatever the amplitude of the tilt is, can easily result in a loss of the region of interest at such high magnification. The specimen should be at an exact eucentric position, and the backlash of the goniometer should be cancelled by pre-tilting the specimen in the same direction of tilt.

Conclusion

In this paper we detail the use of two different procedures to estimate the channeling effect in STEM observations of CuAg nanoparticles. The first one is to increase the collection angle, in order to decrease any contribution from Bragg diffraction. The second procedure, mostly used for bulk specimen, consists in tilting the specimen out of a zone axis, and relies on the fact that the intensity due to channeling varies rapidly with the tilt angle. Both procedures are applied to the CuAg nanoparticles. It appears that increasing the collection angle by decreasing the camera length can restore a contrast linked to the position of silver atoms but decreases the signal-to-noise ratio of the images. On the contrary, acquiring two (or more) images with a reasonably large detector angle at two slightly different specimen orientations allows one to interpret (with precautions) the contrast in terms of chemical composition qualitatively for each particle. Extra-care is necessary when tilting the sample to keep the area of interest in the field of view. A compromise between the two procedures would be to acquire two images at different tilts with the smallest acceptable detector angle.

Figure 1 .

 1 Figure 1. HAADF-STEM images acquired with a camera length of 520 mm (inner collection angle of 12 mrad). a) Sample A with Cu and Ag deposited. b) Sample B with only Cu. Field of view for both: 101 nm.

Figure 2 .

 2 Figure 2. The effect of the detection angle on HAADF image contrast (a) CL = 520mm. (b) CL = 285mm. (c) CL = 100mm. (d) C L= 52mm.

Figure 3 .

 3 Figure 3. The effect of a small sample tilt on the STEM image contrast (CL = 520mm). (a) 0 degree. (b) 2 degrees.

Acknowledgment

CL and ZYL are grateful to the Egide (France) and British Council (UK) for supporting this study through the Alliance project. Prof. Jun Yuan from University of York (UK) is gratefully acknowledged for helpful discussions about the channeling effects in HAADF-STEM imaging.


Duc-Minh Phan

Laurent Viennot

Fast Public Transit Routing with Unrestricted Walking through Hub Labeling

Keywords: Route planning, Public transportation, Hub labeling

We propose a novel technique for answering routing queries in public transportation networks that allows unrestricted walking. We consider several types of queries: earliest arrival time, Paretooptimal journeys regarding arrival time, number of transfers and walking time, and profile, i.e. finding all Pareto-optimal journeys regarding travel time and arrival time in a given time interval. Our techniques uses hub labeling to represent unlimited foot transfers and can be adapted to both classical algorithms RAPTOR and CSA. We obtain significant speedup compared to the state-ofthe-art approach based on contraction hierarchies.

Introduction

Despite remarkable progress of route planning algorithms in road networks [START_REF] Bast | Route planning in transportation networks[END_REF], public transit routing still requires specific algorithms due to its temporal nature. Various efficient methods were proposed such as CSA [START_REF] Dibbelt | Connection scan algorithm[END_REF], RAPTOR [START_REF] Delling | Round-based public transit routing[END_REF], Transfer Pattern [START_REF] Bast | Fast routing in very large public transportation networks using transfer patterns[END_REF][START_REF] Bast | Scalable transfer patterns[END_REF], PTL [START_REF] Delling | Public transit labeling[END_REF]. They all consider a graph with two types of edges: the connections that correspond to a vehicle traveling from a stop to the next one, and the transfers that correspond to walking from a stop to another nearby stop. While each connection is scanned only once per query, transfer edges from a stop are considered each time an event is detected at the stop. Efficiency of such techniques thus relies on the sparsity of the transfer graph. Additionally, they all share the requirement that the graph resulting from walking transfers is transitively closed and are generally experimented with a sparse transfer graph by restricting transfers to very short distances only. Allowing unrestricted transfers, that is walking from a stop to any other stop, is indeed out of reach with these methods although it would allow to find better answers. Indeed, recent work [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF] shows the benefit of using unrestricted walking over sparse transfers by measuring that it can reduce travel time by hours in Switzerland and Germany networks.

This paper is devoted to enable unrestricted walking in efficient public transit routing. The motivation for considering unrestricted walking goes beyond the gain of quality in the answers. It is indeed a fundamental step towards computing multimodal journeys as it is considered as a main bottleneck in [START_REF] Delling | Computing multimodal journeys in practice[END_REF]. Note that bicycle or taxi transfers can be handled similarly as walking transfers with different speed and cost. Techniques developed for unrestricted walking can thus generalize to other modes of transportation.

A first step towards unrestricted walking was made by MCR [START_REF] Delling | Computing multimodal journeys in practice[END_REF] and UCCH [START_REF] Dibbelt | User-constrained multimodal route planning[END_REF] algorithms that both use a contracted version of the full walking graph, inspired by contraction hierarchies [START_REF] Geisberger | Exact routing in large road networks using contraction hierarchies[END_REF], for representing the full walking graph which is much bigger. However, this contracted graph is not transitively closed and has to be globally scanned several times during a query. Accelerating such computations with unrestricted walking is still challenging as multi-criteria or profile queries require seconds to be performed on practical networks with these methods.

In static graphs such as road networks, hub labeling [START_REF] Abraham | A hubbased labeling algorithm for shortest paths in road networks[END_REF][START_REF] Delling | Hub labeling (2-hop labeling)[END_REF] (also called 2-hop labeling [START_REF] Cohen | Reachability and distance queries via 2-hop labels[END_REF]) is a remarkable technique that achieves state-of-art response-time to shortest path queries. It consists in selecting for each node a small set of access nodes called hubs such that any shortest path can be described as a two hop travel through a common hub of the extremities. Intersecting the two lists of hubs of a source and a destination indeed allows to find efficiently the shortest path between them. Such technique was used in PTL [START_REF] Delling | Public transit labeling[END_REF] on the time expanded graph representation of a network to obtain fast transit routing. A similar approach is followed by TTL [START_REF] Wang | Efficient route planning on public transportation networks: A labelling approach[END_REF] which revisits hierarchical hub labeling [START_REF] Abraham | Hierarchical hub labelings for shortest paths[END_REF] in the context of public transit networks. However, these approaches still assume sparse transfers. Note that the time expanded graph representation duplicates transfer edges from a stop for all events at that stop, and its size can blow up with dense transfer graphs.

In this work, we propose a new approach for handling unrestricted walking in public transit routing based on a different usage of hub labeling. It basically consists in decomposing walking transfers into two consecutive hops. We use hub labeling in the classical setting of a static graph but in a novel manner compared to distance or shortest path queries: we scan hub lists to propagate reachability information. Interestingly, the technique can easily be adapted to both RAPTOR and CSA based algorithms which are the two main classical approaches with restricted transfers. HLRaptor, our variant of RAPTOR obtains significant speedup compared to MCR. HLCSA, our variant of CSA obtains competitive running times for earliest arrival time and profile queries.

The paper is organized as follows. Section 2 defines public transit networks, describes briefly RAP-TOR and CSA algorithms, and introduces hub labeling. Sections 3 and 4 present HLRaptor and HLCSA respectively. We describe in Section 5 public transit data used to evaluate our algorithms. The results of our experiments are presented in Section 6.

Preliminaries

We define a public transit network with a triple (S, T, R) representing trips of vehicles (buses, trains, etc.): S is the set of stops where passengers can enter or disembark from a vehicle, T is the set of trips made by vehicles and are grouped into routes represented by the set R. More precisely, a trip t is given by a sequence of stops served by a vehicle and for each stop u in the sequence, an arrival time τ arr (t, u) of the vehicle at stop u and a departure time τ dep (t, u) of the vehicle from stop u. A route r consists in a set of trips with same stop sequence. This set of trips can be represented by a two-dimensional timetable where each line lists the arrival and departure times τ arr (t, u), τ dep (t, u) of a trip t for all stops u in the sequence. Note that the sequence of times listed in a line is non-decreasing. Similarly to RAPTOR authors [START_REF] Delling | Round-based public transit routing[END_REF], we assume that no trip of a route can overtake another trip of the same route. In other words, the lines of the timetable can be sorted so that each column is non-decreasing. This property can easily be enforced by splitting the set of trips with same stop sequence into smaller subsets of trips if necessary.

The public transit network is complemented by a weighted footpath graph G = (V, E, τ w ) with S ⊆ V , and τ w (u, v) denotes the time needed to walk from a node u to a node v. In the unrestricted walking setting, the graph is not assumed to be transitively closed and we expect that V is much larger than S. Each edge (u, v) ∈ E typically corresponds to a segment of street than can be traversed by walking. We let d G (u, v) denote the length of a shortest path in G from u to v, i.e., the minimum walking time from u to v.

We consider several journey computation problems. Given a source stop s and a target stop t, a journey from s to t is an alternating sequence of trips and footpaths in the public transit network, which starts with s and ends with t. The goal of public transit planning is to compute journeys from s to t optimizing one or several criteria. Given a departure time τ , an earliest arrival time query consists in computing a journey with minimum arrival time at t that departs from s at τ or later. In a multicriteria query, we are additionally interested in the number of transfers and the overall walking time of the journey, and ask for all Pareto-optimal journeys. Recall that a journey is Pareto-optimal if no other journey is better on one criterion and at least as good on all criteria. In a profile (or range) query, we ask for journeys whose departure time falls within a given time interval while optimizing both departure time and arrival time (where later departure time is considered better). The required answer again consists in all Pareto-optimal journeys within the given time interval.

The RAPTOR algorithm and its variants [START_REF] Delling | Computing multimodal journeys in practice[END_REF][START_REF] Delling | Round-based public transit routing[END_REF] compute journeys starting from a given stop at a given time in rounds, where each round extends partial journeys by one trip. More precisely, each round consists of two phases: the first phase explores each route of the public transit network and extends partial journeys arriving at stops served by a route using the first trip arriving at each stop. In the second phase, each partial journey arriving at a stop is extended by walking paths from that stop. In the regular RAPTOR version [START_REF] Delling | Round-based public transit routing[END_REF], single-edge paths only are considered and the footpath graph is assumed to be transitively closed. In the unrestricted walking setting [START_REF] Delling | Computing multimodal journeys in practice[END_REF], a multi-source Dijkstra is performed on a contracted version of the footpath graph in order to find all stops whose arrival times can be improved by walking from the stops that were scanned during the first phase.

The Connection Scan Algorithm (CSA) [START_REF] Dibbelt | Connection scan algorithm[END_REF] breaks each trip into consecutive connections, which represent a vehicle traveling from a stop to the next one in the stop sequence of the trip. All connections are sorted by departure times in a pre-computation step. The algorithm scans all the connections and transfers to update the earliest arrival time at each reachable stops. More precisely, for each connection c in increasing order of departure time, we need to check whether a passenger can travel on c or not: either the trip containing c has been reached earlier, or we can arrive at the departure stop of c before its departure time. Then we update the arrival time at the arrival stop of c if necessary, and scan the footpath transfers from the arrival stop of c. Similarly to RAPTOR, CSA also requires the footpath graph to be transitively closed.

Two-hop labeling [START_REF] Cohen | Reachability and distance queries via 2-hop labels[END_REF], or equivalently, hub labeling [START_REF] Abraham | A hubbased labeling algorithm for shortest paths in road networks[END_REF][START_REF] Delling | Hub labeling (2-hop labeling)[END_REF], for a (weighted, directed) graph G consists in assigning two subsets of nodes H -(u) and H + (v) to each node u. Nodes in H -(u) (resp. H + (u)) are called in-hubs (resp. out-hubs) and serve as intermediate nodes to reach u (resp. to leave u). The following two-hop property is required: for any pair u, v of nodes, there must exist a common hub

h ∈ H + (u) ∩ H -(v) lying on a shortest path from u to v, i.e., satisfying d G (u, h) + d G (h, v) = d G (u, v).
Equivalently, H + (resp. H -) can be seen as a graph with vertex set V and edges (u, v) with weight

d G (u, v) for every pair u, v such that v ∈ H + (u) (resp. u ∈ H -(v)
). The two-hop property can then be stated as H + • H -= G * , where G * denotes the transitive closure of G and • denotes the graph product resulting from the (min, +)-matrix product of adjacency matrices (the weight of an edge (u, w)

in H + • H -is min v∈H+(u)∩H-(w) d G (u, v) + d G (v, w)).
In other words, any shortest path in G corresponds to a two-hop path in H + ∪H -. The interest for such representation comes from the fact that it is possible to compute very small hub sets (less than 100 nodes on average) in large road networks and footpath graphs [START_REF] Delling | Robust distance queries on massive networks[END_REF], and thereby obtain the fastest known practical oracles for computing distances and shortest paths in such networks [START_REF] Bast | Route planning in transportation networks[END_REF].

HLRaptor: RAPTOR with Two-Hop Transfers

Using a hub labeling H -, H + of the footpath graph G, we propose the following modification of RAPTOR that we call HLRaptor. We replace the second phase of a round by two sub-phases: in the first sub-phase we scan every stop u for which arrival time τ u was improved in the regular first phase of the round, and update arrival time at its out-hubs h ∈ H + (u) to min {τ h , τ u + τ w (u, h)}. In the second sub-phase, we scan every hub h whose arrival time was improved in the first sub-phase and update arrival time at nodes

v such that h ∈ H -(v) to min {τ v , τ h + τ w (h, v)}.
The correctness of HLRaptor comes from the two-hop property of the hub labeling that ensures H + • H -= G * . Our two sub-phases using H + and H -are thus equivalent to the second phase of the regular RAPTOR algorithm using the transitive closure G * of G. However, its performance depends on the out-degrees of H + and H -rather than that of G * .

Target pruning optimization.

The lists

H -1 -(h) = {v | h ∈ H -(v)
} and H + (u) can be pre-computed for all u, h ∈ V . Additionally, these lists can be sorted according to walking time from u (resp. h) in non-decreasing order. This enables a target pruning optimization where we stop scanning a list as soon as the arrival time computed for a node in the list exceeds the best arrival time known at the target.

HLprRaptor: profile queries with HLRaptor.

We can follow the same approach as [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF] to compute all Pareto-optimal journeys with respect to departure time and arrival time in a given interval of time. The difference is that we use HLRaptor instead of MCR. The idea is to use HLRaptor to compute the best arrival time τ a when starting at a givent time τ . Then we use a reverse version of HLRaptor (or simply a reversed version of the transit data) to compute the last departure time τ d such that arrival at τ a is still possible. We then repeat this procedure for departure time τ d + ε for sufficiently small ε (we simply use ε = 1 second, which is the time unit in our datasets). We iterate this until all Pareto-optimal journeys in the given time interval have been found.

HLmcRaptor: HLRaptor with multiple criteria.

To deal with more criteria than arrival time and number of transfers, we can keep multiple nondominating labels for each stop u in round k in a bag structure similarly to McRAPTOR [START_REF] Delling | Round-based public transit routing[END_REF]. For each route r with a stop improved in the previous round, we scan the first trip departing after any improved arrival time at a stop u of the route and update bags accordingly at the stops served by the trip after u. In the second phase of the round, each newly inserted label is first propagated along out-hubs links and then newly inserted labels at hubs are propagated along in-hubs links similarly. We can adapt local and target pruning as in McRAPTOR. We can also adapt our target pruning optimization specific to HLRaptor to stop scanning hub lists as soon as the propagated label is dominated by the destination bag.

HLCSA: Connection Scan with Two-Hop Transfers

Given a hub labeling H + , H -of the walking graph G, we propose the following modification of CSA. For an earliest arrival time query from s to t, we first scan out-hubs H + (s) and update arrival time to them by walking from s. Similarly to CSA, we then scan connections by non-decreasing departure time. When considering a connection c, we first scan the in-hubs H -(u) of its departure stop u and update the arrival time at u through walking from a hub. The connection can be boarded if the trip has been marked as boarded or if the arrival time at u plus the minimum transfer time at u is no later than the departure time of c. In that case, we update the arrival time at the arrival stop v of c and scan its out-hubs H + (v) to update their arrival times through walking from v. Finally, we scan the in-hubs H -(t) of the destination t and update the arrival time at t by walking from any of them.

The correctness of the algorithm comes again from the two-hop property of hubs. For any possible transfer from a connection c to another connection d in a journey, c must be considered before d. Let h denote a common hub for the arrival stop u of c and the departure stop v of d such that d G (u, v) = d G (u, h) + d G (h, v) according to the two-hop property. After c is considered, arrival time at h is thus no more than τ + d G (u, h), where τ is the arrival time of c at u and d G (u, h) the walking time from u to h. When d is then considered, arrival time to v is updated to τ

+ d G (u, h) + d G (h, v) = τ + d G (u, v)
as if a transfer from u to v had been considered. A similar reasoning applies for a journey starting with a walk from s or ending with a walk to t. HLCSA thus behaves as in a regular CSA execution where all transitive transfers in G * would be considered.

Optimization.

In addition to all CSA classical optimizations, we can again sort out-hub lists in non-decreasing order of walking time, and apply target pruning similarly as in HLRaptor. In addition, we scan the in-hub list of the departure stop of a connection when the trip is not marked as boarded. Again, this list can be sorted by non-decreasing walking time and we stop scanning the list as soon as the walking time from the hub exceeds the estimated travel time to the departure stop (local pruning). Similarly to the original extension of CSA to solve the profile problem [START_REF] Dibbelt | Connection scan algorithm[END_REF], we store for each stop a bag containing Pareto-optimal pairs of departure time at stop with associated arrival time at destination. We also store such information for hubs. We also consider connections in non-increasing order of departure time. When scanning a connection c, we use the bags of the out-hubs of its arrival stop to obtain the best arrival time through walking after c. If the arrival time of the trip of c is improved, we then update the bags of the in-hubs of the departure stop of c for that arrival time with departure time corresponding to walking from the hub for boarding right in time the connection. We also scan in-hubs of the destination at the beginning of the procedure and out-hubs of the source at end in order to take care of walking from source and to destination. The correctness of the modification follows similar lines as for HLCSA.

Public Transit Data

To evaluate the algorithms, we use datasets from three locations: London, Paris, and Switzerland. The dataset for London was obtained from Transport for London [START_REF]Transport for London Unified API[END_REF]. The dataset for Paris was obtained from Open Data RATP [START_REF]Open Data RATP[END_REF]. And the dataset for Switzerland was provided by Wagner & Zündorf [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF] 1 . The extracted dates are 2015-11-06 for London and 2018-03-30 for Paris.

The public transit data of Paris already has transfers between stops, we simply need to make the transfer graph transitively closed for appropriate use with RAPTOR and CSA. However, the dataset of London does not have transfers, thus we have created transfers by linking any pair of stops separated by 75 meters of walk one from another. This threshold was chosen to obtain a transitively closed transfer graph with similar size as in previous works. The graph obtained by transitive closure of restricted transfers is called transfer graph in the sequel.

The footpath graphs for London and Paris were extracted from Geofabrik's data [15], which is itself extracted from OpenStreetMap's data [START_REF]OpenStreetMap[END_REF]. We call walking graph the union of this unrestricted footpath graph and the transfer graph. The method to merge a stop of the public transit network into the walking graph is the following. For each stop p, we find the closest node v in the walking graph. If the distance between p and v is less than 5 meters, we identify p and v, connecting p with the in-and out-neighbors of v using the same weights. Otherwise, we find the 5 closest nodes of p in the walking graph, and connect p with those at distance 100 meters at most. If there are no nodes in the walking graph within the radius of 100 meters from p, then p is isolated. Walking times are computed according to a walking speed of 4 km/h. Table 1 provides statistics concerning the datasets. The columns stops and transfers provide the number of nodes and edges in the transitively closed restricted walking graph, while the last two columns give the numbers of vertices and edges in the unrestricted walking graphs. We computed hub labelings of the walking graphs using the sampling-based algorithm by Delling et al. [START_REF] Delling | Robust distance queries on massive networks[END_REF] (1-2h of pre-computation per graph). Table 2 provides statistics on the degrees of transfer graphs vs. in-hubs and out-hubs graphs: δ + (T r) and ∆ + (T r) designate the average and maximum out-degree resp. of the transfer graph T r, δ + (H + ) and ∆ + (H + ) designate the average and maximum out-degree resp. of the out-hub graph H + , δ -(H -) and ∆ -(H -) designate the average and maximum in-degree resp. of the in-hub graph H -. We let |H + | and |H -| designate the number of edges in H + and H - resp. while |V (H)| designates the number of hubs (including stops). We note that the size of hub lists is comparable to the number of events and their storage do not increase too much space requirements. We also prepared two sets of roughly 1000 queries for each dataset. In the first one, source and destinations are selected independently uniformly at random among all stops similarly to experiments in [START_REF] Delling | Computing multimodal journeys in practice[END_REF][START_REF] Delling | Round-based public transit routing[END_REF][START_REF] Dibbelt | Connection scan algorithm[END_REF]. In the second one, we select sources and destinations similarly to [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF]: one hundred sources are selected uniformly at random. For each source, we order the destinations by increasing walking distance and select a random one uniformly among those with rank in [2 i , 2 i+1 ] for i = 2 . . . 14. For Switzerland, we use exactly the same pairs as in [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF] where sources are selected with probability proportional the number of trips serving them. In both sets, we additionally selected uniformly at random a departure time in [0, 24 × 3600] for each source-destination pair. We will reference the two sets of queries as "uniform" and "rank" respectively. Note that most of the uniform queries (those in the uniform set) correspond to high rank pairs (2 12 or higher) while the rank set of queries has a strong bias towards low rank pairs.

The datasets are publicly available2 .

Experiments

Our algorithms were implemented in C++ and compiled with GCC version 7.2.0 (with flag -O3). Experiments were conducted on one core of a dual 10-core Intel Xeon E5-2670-v2 with with 25 MiB of L3 cache and 64 GiB of DDR3-1866 RAM. The code is made available3 . Table 3 presents the average running times in milliseconds of HLRaptor and HLCSA variants on the three datasets. We indicate for each algorithm which criteria are optimized: arrival time (Arr.), number of transfers (Nb. tr.), overall walking time (Walk), and whether the query spans a range of departure times (Range).

In the restricted walking setting, our algorithms are equivalent to the corresponding Raptor or CSA based version. On the London instance with restricted walking and uniform queries, we obtain similar results as Raptor [START_REF] Delling | Round-based public transit routing[END_REF] for earliest arrival, multi-criteria and 2h range queries: 5.1ms vs. 7.3ms, 87.3ms vs. 107ms, and 76.5ms vs. 87ms, respectively (we compare times reported in Table 3 to times reported in [START_REF] Delling | Round-based public transit routing[END_REF]). Our running times are 15-30% faster, probably due to the use of more recent hardware. We also obtain similar results as CSA [START_REF] Dibbelt | Connection scan algorithm[END_REF] for earliest arrival and 24h range queries: 2.2ms vs. 1.2ms and 312 vs. 107ms. Our running times are 2-3 times slower than those reported in [START_REF] Dibbelt | Connection scan algorithm[END_REF], probably due to less optimized code.

In the unrestricted walk setting, our algorithms are significantly faster than previous works. On the London instance with uniform queries and unrestricted walking, HLmcRaptor is 3.4 times faster than times reported for MCR in [START_REF] Delling | Computing multimodal journeys in practice[END_REF] (417ms vs. 1438ms) and HLRaptor is 1.7 times faster than the MR-∞ variant of MCR (26.4ms vs. 44.4ms). On the Switzerland instance with ranked based queries and unrestricted walking, HLprRaptor computes profile queries roughly 7 times faster than the profile variant of MCR proposed in [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF]: 751ms vs. 5.5s approximately. Most uniform queries have high rank, and HLprRaptor obtains their profiles in roughly 3.5s compared to 20s approximately as reported in [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF].

Interestingly, our hub-labeling-based versions of CSA obtain rather good performances with respect to Raptor based versions in the unrestricted walk setting: they are nearly as fast or even faster on uniform queries, and at most 2-3 times slower on rank queries. (Note that on low rank queries, Raptor-based solutions benefit from target pruning.) We confirm the results of [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF] showing the benefit of considering unrestricted walking. Table 4 presents the percentage of time gained by using a journey with unrestricted walking compared to the travel time with restricted walking. The average gain ranges from 12% to 47% on uniform queries depending on the dataset. City networks (especially London) seem to benefit less from unrestricted walking than the train network of Switzerland. As observed in [START_REF] Wagner | Public transit routing with unrestricted walking[END_REF], the gain is less important during daytime that is queries with departure time in the range 6h-20h here. We observe a higher gain on low rank queries. The median gain ranges from 13% to 47% for them. More precisely, the gain is at least 13% on half of the low rank queries for London, 21% for Paris and 47% for Switzerland.

Conclusion

We have demonstrated the efficiency of using a two-hop representation of unrestricted walk transfers in conjunction with CSA and RAPTOR algorithm. This shows that is possible to enable unrestricted walking in practical public transit routing engines and opens new perspectives for allowing complex multimodal scenarios. We also want to further investigate how this approach could be integrated in other efficient public transit routing algorithms.

4.0. 2

 2 HLprCSA: Profile queries with HLCSA.

Table 1 :

 1

			Dataset statistics
		routes	trips events stops transfers vertices	edges
	London	1622 122593 4695285 19746	46566 281167 840880
	Paris	1973 78757 1915253 23519 362291 533470 1666386
	Switzerland 13930 369744 4740869 25427	38265 604230 1882551

Table 2 :

 2 Transfers, out-hubs and in-hubs degrees.

		δ + (T r) ∆ + (T r) δ + (H+) ∆ + (H+) δ -(H-) ∆ -(H-) |V (H)|	|H+|	|H-|
	London	2.36	20	70	150	71	142 65059 1393759 1395024
	Paris	15.4	205	118	196	118	210 60519 2770336 2798315
	Switzerland	1.5	26	78	229	79	230 117793 2005312 2005312

Table 3 :

 3 Average running times of HLRaptor and HLCSA.

	Algorithm	R a n g e A r r . N b . t r . W a lk	London Restricted Unrestr. Unif. Rank Unif. Rank Unif. Rank Unif. Rank Paris Restricted Unrestr.
	HLRaptor	• • • •	5.1	1.9	26.4	8.7	3.0	1.3	19.5	5.5
	HLCSA	• • • •	2.2	1.1	33.1	16.8	1.0	0.5	13.8	6.5
	HLmcRaptor	• • • •	87.3	33.0	417	140 60.0	25.9	248	85.4
	HLprRaptor (2h)	• • • •	76.5	31.1	685	237 53.0	23.1	652	205
	HLprCSA (2h)	• • • •	47.1	28.4	1012	539 60.9	35.4	628	330
	HLprRaptor (24h)	• • • •	805	322	7522 2524	567	262 7441 2511
	HLprCSA (24h)	• • • •	312	217 11644 8453	404	298 9523 7902
	Algorithm	R a n g e A r r . N b . t r . W a lk	Switzerland Restricted Unrestr. Unif. Rank Unif. Rank
	HLRaptor	• • • •	13.4	4.0	59.4	7.6
	HLCSA	• • • •	6.6	2.9	54.2	19.4
	HLmcRaptor	• • • •	150	62	854	229
	HLprRaptor (2h)	• • • •	47.7	16.4	402	83.9
	HLprCSA (2h)	• • • •	51.9	32.1	563	240
	HLprRaptor (24h)	• • • •	293	111 3461	751
	HLprCSA (24h)	• • • •	128	96 4173	3076

Table 4 :

 4 Average/median gain of unrestricted walking on travel time compared to restricted walking.

		Unif.	Unif. 6h-20h	Rank	Rank 6h-20h
	London	12% / 5.8% 6.9% / 2.9% 24% / 13%	16% / 5.0%
	Paris	22% / 15%	15% / 13%	31% / 21%	22% / 17%
	Switzerland	47% / 46%	37% / 39%	47% / 47%	35% / 37%
	6.0.1 Gain of unrestricted walking.

https://i11www.iti.kit.edu/PublicTransitData/Switzerland/

https://files.inria.fr/gang/graphs/public transport/

https://github.com/lviennot/hl-csa-raptor

‡ Supported by Irif CNRS laboratory and ANR project MULTIMOD (ANR-17-CE22-0016).