R Meyer

L Froehly

R Giust

J Del Hoyo

L Furfaro

C Billet

F Courvoisier

Extremely high-aspect-ratio ultrafast Bessel beam generation and stealth dicing of multi-millimeter thick glass

We report on the development of an ultrafast beam shaper capable of generating Bessel beams of high cone angle that maintain a high-intensity hot spot with subwavelength diameter over a propagation distance in excess of 8 mm. This generates a high-intensity focal region with extremely high aspect ratio exceeding 10 000:1. The absence of intermediate focusing in the shaper allows for shaping very high energies, up to Joule levels. We demonstrate proof of principle application of the Bessel beam shaper for stealth dicing of thick glass, up to 1 cm. We expect this high energy Bessel beam shaper will have applications in several areas of high intensity laser physics.

Glass and transparent dielectrics are ubiquitous in modern technology. They are used for consumer electronics, microelectronics, automotive, construction. High speed and high quality cutting of thin and thick glass is therefore an important technological problem. Interestingly, the recent development of stealth dicing of glass has enable to cleave glass at speeds in the range of 10 to 100 cm/s using lasers with a high repetition rate of several 100's kHz [1,2]. Stealth dicing is a two-step technique where the first step consists in generating with individual ultrafast laser pulses a series of high aspect ratio nanochannels which define a weakening plane, serving as a fracture initiator. The second step consists in stressing the material, for instance with a small bending, which is generally sufficient to cleave the glass along the pre-defined plane. The process is ablation-free, does not generate debris and is extremely fast.

Infrared ultrafast Bessel beams are ideal tools to process transparent materials with high aspect ratio such as index modifications [3,4] or high aspect ratio nanochannels and voids [5,6]. They are formed by the cylindrically-symmetric interference of plane waves with wavevectors distributed on the generatrix of a cone [7]. In the nonlinear regime at high intensities, Bessel beams are quasi distortion-free, provided the cone angle is sufficiently high [8]. The high stability of the Bessel beams and the confinement of the intense laser-matter interaction makes it possible to create with a single laser pulse a nanochannel with a diameter typically ranging between 200 and 800 nm [5] and has led to a number of advances in terms of materials processing via bulk excitation [9,10]. Stealth dicing using Bessel beams or filaments is now widely used for glass and sapphire separation [11][12][13][14]. Until here, stealth dicing has been limited to thicknesses of typically sub-mm. The limit is the available Bessel beam length.

Bessel beams have also a number of different other applications in the field of nonlinear optics [15,16] where they are expected to provide natural tools for amplification with wideband tunability via Kerr instability [17], high intensity laser physics [18]. Ultrafast Bessel pulses are also emerging in the field of particle acceleration [19,20] because the interference creates along the optical axis a high intensity peak that velocity can be tuned and that can even exceed speed of light [21][22][23][24][25][26]. Therefore, Bessel beam shapers that can sustain high intensities and high energy over several millimeters are desirable. At present, most of Bessel beam shaping techniques for high intensity applications are based on the imaging of an initial Bessel beam formed via an axicon, a spatial light modulator or a diffractive optical element, which is then de-magnified using relay lenses [1,25,27,28]. This approach has several benefits: the Bessel beam is created at a distance from the last optics, enabling a working distance to process thick materials or to realize the generation of the Bessel beam with a smooth injection in the nonlinear medium [29]. In addition, the de-magnification factor of the imaging system effectively increases the cone angle of the Bessel beam. This makes possible generating highly focused beams even if the initial shaping element has relatively low spatial frequencies or even if it is difficult to fabricate high angle axicons [30].

However, this approach has important drawbacks. First, the Bessel beam length after imaging is reduced by the square of the magnification factor, which drastically reduces the length that can be reached when high angles are needed and high magnifications used. Second, and most importantly, the imaging techniques make the first Bessel beam prone to distortions during its propagation in air and increase the risks of laser damage. Indeed, during imaging, the Bessel beam field is Fourier-transformed several times. The Fourier transform of a Bessel beam is an annulus. Its width is proportional to 1/L B , L B being the length of the Bessel zone [31]. Therefore, high intensities can be reached either within the initial Bessel beam, and/or in the relay optics. Kerr effect, thermal lensing, or optical damage occur when high peak power and high average power pulses are used.

Here, we develop a Bessel beam shaper that has no intermediate focus and which is capable of handling extremely high energies. It improves the Bessel beam zone length by two orders of magnitude for a high angle of 23 • similar to state of the art for single shot nanochannel machining [5]. Its working distance is adjustable, and the full system is much more compact than those involving relay lenses. We experimentally characterize the Bessel beam distribution up to 1 mJ in air and show it is constant. We demonstrate a proof of principle application to stealth dicing of thick glass, where we reached cleaving up to 1 cm thick soda-lime glass.

The laser source is a Ti:Sapphire Chirped-Pulse Amplified (CPA), Coherent Legend USP, emitting ∼ 30 fs pulses at a central wavelength of 800 nm, pulse energy of 5 mJ and repetition rate 1 kHz. The pulses can be temporally compressed up to the Fourier-transform limit or stretched using the compressor of the CPA and were characterized just before the beam shaper using an autocorrelator. The concept of the Bessel beam shaper is shown in Figure 1. We use a combination of three high-purity fused silica axicons: the first two are respectively negative and positive with the same wedge angle α. This transforms the input Gaussian beam, with waist w 0 = 4 mm (i.e. radius at 1/e 2 ) from the laser source into a thick annulus of collimated light propagating parallel to the optical axis. In the framework of geometrical optics, the width of the annulus is the waist w 0 of the input Gaussian beam; the diameter is determined by the axicons wedge angle and the distance d between the first two axicons. The cone angle θ is determined only by the wedge angle β and index n ax = 1.45 of the last axicon:

θ = arcsin n ax sin β -arcsin sin β n ax (1)
The typical length of the Bessel zone L B is determined by:

L B = w 0 (1 + tan β tan γ)/ tan θ (2)
Similarly, the working distance d w is evaluated from geometrical optics by:

d w = d tan ϕ (1 + tan β tan γ) -e ax tan γ tan θ (3)
in which e ax stands for the third axicon thickness (tip to plane).

With the experimental values α = 10 , d w = 12.2 mm and L B = 9.7 mm. Our concept is extremely compact because the full length of the beam shaper is ∼15 cm, which is much smaller than the Bessel beam shapers based on relay imaging, which length typically exceeds 1 m [25]. Because of the high angle of the last axicon, it is oriented with the tip to the laser source to prevent total internal reflection. In this configuration, the distance d must be sufficiently large so that the Bessel beam is formed out of the axicon.

We note that a close concept has been developed by another group [32], used in Optical Coherence Tomography (OCT) imaging [33] and recently applied to induce up to 10 mm long modifications in glass [34]. However, the latter concept involves a first axicon in focusing geometry such that non-linearities, thermal lensing and optical damage, that we aim to avoid here, might happen for high average input power. The detrimental disruptions in the modifications that are reported to prevent cleaving, might also arise from a too low cone angle and/or detrimental nonlinearities [8].

We remark that all along the optical path in the beam shaper, the pulse energy is spread over areas that remain on the order of a few cm 2 , such that with a typical damage threshold of optics of several J/cm 2 , the beam shaper is expected to handle extremely high pulse energies close to Joule level. With 1 J illumination at 50 fs pulse duration, the peak intensity reached in the Bessel beam would be on the order of 10 18 W.cm -2 , which is relevant for high-energy physics applications. Similarly, because the pulse energy is quasi uniformly spread over the axicon' surfaces, thermal lensing is largely reduced and its potential focal length would be large, with negligible impact on the Bessel beam structure.

Experimental characterization of the ultrafast beam was performed via an imaging setup made of two lenses (f 1 = 3.6 cm, f 2 = 1 m) in confocal configuration such that the beam is imaged onto a camera. The magnification of this imaging setup is 27.4. The first lens is 2 inches diameter so that the imaging has a high numerical aperture of 0.58, exceeding the Bessel cone angle. The longitudinal position of the imaging setup is controlled by a motorized translation stage. This allows for scanning the beam over a range exceeding 2 cm. Neutral density filters are placed in the optical path of the imaging setup so as to avoid saturation of the CCD sensor. The damage threshold of the imaging setup is limited to an output pulse energy of 1 mJ (because of the intermediate focusing involved in the imaging), but we could operate the Bessel beam shaper up to the maximal pulse energy available, i.e. 5 mJ input pulse energy.

Figure 2 shows experimental characterizations of the beam with different input pulse energies ranging between 12 µJ and 1 mJ with compressed 50 fs pulses. The characterization is shown with a log scale so as to enhance the visualization of the low-intensity parts and show the high quality of the beam even outside the central lobe. We see the high parallelism and roundness of the profiles in the cross-cuts. The quality of the axicon manufacturing is an important parameter. Imperfect axicons generate a non-diffracting intensity pattern with multiple hotspots unusable for applications. The Bessel beam has a homogeneous transverse distribution over its ∼ 8 mm range in air, in agreement with the model described above. This makes the aspect ratio of the beam to be of >10 000:1 because the central spot diameter is 740 nm FWHM. The aspect ratio is two orders of magnitude higher than previously achieved with telescopic arrangements for the same cone angle of 23.3 • .

The beam profile does not vary when the pulse energy is increased, evidencing the absence of distortion in the optical system. In addition, we have experimentally verified that varying d and w 0 respectively changes the working distance d w and the length of the Bessel zone L B , without modifying the beam transverse cross-section. Now, we demonstrate a proof-of-principle application of the high energy Bessel beam shaper to stealth dicing of thick glass. For stealth dicing, high cone angles have been shown essential for high quality cleaving [1], but one of the key limitations for thick glass dicing is to generate material modification on a significant part of the thickness of the material. We demonstrate here that the multi-mm long Bessel beam allows for glass separation up to 10 mm soda-lime glass.

The parameter space is potentially very large and we restricted our study by choosing a fixed translation speed FIG. 3. Images of the cleaved edges of glass for thicknesses varying between 3 to 10 mm and for laser pulse durations of 2.2, 4.2 and 6.2 ps. Chipping occurs at the rear surface of the samples for shorter pulse durations and tends to disappear for the longer pulse durations.

of 5 mm.s -1 with 1 kHz repetition rate, so that individual Bessel pulses create material modifications separated by 5 µm, as found nearly optimal in other studies [12,35]. We used a fixed input pulse energy of 2.5 mJ and varied the input pulse duration in the picosecond regime since pulse duration was evaluated as an important parameter for material excitation. Specifically, material modifications induced by 50 fs pulses were uncleavable. In contrast, picosecond durations have been reported to enhance cleavability in stealth dicing [12,36]. We processed 10 × 10 cm 2 soda-lime samples of thickness varying between 3 and 10 mm for 3 different pulse durations. Our procedure for stealth dicing was the following. The samples were first laser-processed in single pass. The onset of the Bessel beam was positioned at ∼ 0.5 mm before the sample front surface. Then, the samples were mechanically stressed on a 3-lines bending stage. The experiment was repeated 3 times for each set of parameters. Typical results are shown in Figure 3. We show macro-photography images of the cleaved edges of the samples.

For the 2.2 ps pulse duration, the 3 and 5 mm thick samples are cleaved without observable chipping. Excellent results are observed to separate glass with thickness up to 10 mm, but for longer pulse durations of 4.2 ps and 6.2 ps. For the shortest pulse duration, chipping is observed for 6 to 10 mm mainly in the vicinity of the rear surface. The chipping area increases with glass thickness. We interpret this result as originating from the decrease of local fluence in the central lobe of the Bessel beam for increasing propagation distance. We note a slight increase in the quality of the results between 4.2 and 6.2 ps for the 8 mm case where we report the absence of chipping on all our samples. For the 10 mm case, chipping extends over a distance of some 100 µm along the laser beam direction and the deviation from flatness is typically of the same order of magnitude. We note that this could be improved after investigating a wider set of parameters (position of the beam, pulse energy, pulse duration, etc). We determined with optical profilometry that the RMS roughness of the cleaved samples for 6.2 ps pulse duration is quasi-constant among the samples, with values in the range [1.00 -1.25] µm. This is close to the roughness of ground glass (typ. 1.0±0.2 µm). We finally note that the translation speed of 5 mm.s -1 is relatively low in comparison with state of the art stealth dicing, but we believe that high power lasers with high repetition rate will enable improving this parameter.

In conclusion, we have developed a compact Bessel beam shaper producing high energy pulses shaped with 23 • cone angle, over a propagation distance exceeding 8 mm in air. Experimental demonstration has involved energies up to 5 mJ, but we highlight that this Bessel beam shaper has no intermediate focus such that high average power and pulses with extremely high energies, in the range of several 100 mJ to Joules could be shaped. Using such a beam shaper, we manage to upscale stealth dicing technique up to 10 mm millimeters thick glass. With 6 ps pulse duration, the surface roughness of the cleaved glass is similar to the one of ground glass. Therefore, we expect that this technique can save a lot of the energy used at present to post-processed thick glass after mechanical cleaving. Therefore, we anticipate that our results will impact on applications of thick glass processing as well as on more fundamental research for laser plasma physics and high energy laser physics.

The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 682032-PULSAR), European Union 7th Framework Program under grant agreement 619177 (TiSaTD), Région Franche-Comté and the EIPHI Graduate School (ANR-17-EURE-0002).

FIG. 1 .

 1 FIG. 1. Schematic representation of the beam shaper which is formed by a pair of ±10 • axicons and a third axicon with 45 • wedge angle. The Bessel beam of length LB and angle θ is generated at a working distance dw from the last axicon.

FIG. 2 .

 2 FIG.2. Fluence distribution maps of the Bessel beam in air for different energies from 12 µJ to 1 mJ. The maps are displayed in logarithmic scale. The white dashed line on longitudinal sections shows the plane where the maximum intensity is reached, for which we show the beam transverse profiles.


Pierre-Alain Duc
email: pierre-alain.duc@astro.unistra.fr

Matlas Collaboration

MATLAS: a deep exploration of the surroundings of massive early-type galaxies

Keywords: . galaxies, globular-clusters, cirrus

The MATLAS project explores the surroundings of a complete sample of nearby massive early-type galaxies with multi-colour deep optical images obtained at the Canada-France Hawaii Telescope. The observing and data reduction techniques ensured the detection of extended low-surface-brightness (LSB) structures, while the high image quality allowed us to identify associated compact objects such as star clusters. A number of scientific topics are addressed with this data-set that are briefly presented in this review: the study of foreground Galactic cirrus at high spatial resolution, telling us about the ISM structure; the characterisation of collisional debris around the galaxies (streams, tails, shells, stellar halos), giving hints on their past merger history; the distribution of dwarf galaxy satellites, including the ultra-diffuse ones, together with their globular cluster population, which are additional tracers of the formation and mass assembly of galaxies.

Introduction

While the Universe has been scrutinised for decades at all wavelengths, including at exclusive high spatial resolution and depth for some regions, a component of it, ironically located in the vicinity of our Milky-Way, is still largely unexplored. For technical reasons, such as the advent of electronic cameras with initially limited fields of view, luminous but very extended, i.e. diffuse, stellar structures remained for long hidden in the sky background. Opening a window on the Low Surface Brightness (LSB) realm, one of the last Terra incognita in our exploration of the Universe (excluding of course its dark components) appears even more important given that cosmological models predict the presence of a wealth of structures surrounding galaxies, a result of the underlying hierarchical scenario for structure formation.

As a matter of fact, dramatic advances in LSB studies have recently been made. Extended halos and streams were discovered around the Milky Way and the Andromeda galaxy using the stellar counts from ground-based surveys (i.e., SDSS, Pan-STARRs, DES, PandAS/CFHT) or from HST at unprecedented surface brightness limits, confirming the predictions of numerical simulations.

Beyond the Local Group, identifying individual stars becomes challenging, and the detection of LSB structures mainly relies on the possibility to detect their diffuse light. The stunning ultra deep images of nearby galaxies obtained by amateur telescopes have largely contributed to convince professional astronomers to use and adapt already-existing facilities (i.e., Burrell telescope, CFHT, VST, Subaru, etc.) or develop their own concepts (Dragonfly, Huntsman) to perform LSB studies.

A number of either targeted observations or larger surveys are currently being carried 1 2 Pierre-Alain Duc & MATLAS collaboration out by several teams. Their initial results have been presented in a high number of conferences organised during the last few years that were fully dedicated to the LSB exploration, including this IAU symposium. Mentioning only the current vitality of this field of research would however be somehow unfair, regarding all the works made during the 20th century in the 50s to 70s with Schmidt photographic plates, which already had the capability to reveal faint extended light, including that being emanated by the so-called Ultra-Diffuse Galaxies.

Among the various studies done with the modern facilities, the originality of the MAT-LAS survey presented here lies in the high number of galaxies it explores (about 200), the completeness of the observed sample (using complementary data from the NGVS Survey towards the Virgo cluster), and the high image quality (IQ) of the camera (MegaCam on the CFHT) which allowed us to make with the same dataset multiple complementary projects. They are listed in the following sections.

Survey observing strategy and methodology

The targets of the MATLAS survey consists of galaxies from the volume limited complete ATLAS 3D sample (Cappellari, et al. 2011) of nearby (distance below 42 Mpc) massive (absolute K-band magnitude below -21.5) early type galaxies observable from the northern hemisphere (|δ -29 • | < 35 • ) and avoiding low Galactic latitudes. Galaxies too close to bright stars were excluded as well as members of the Virgo Cluster since they were already observed with MegaCam as part of the "Next Generation Virgo Cluster Survey (NGVS)" (Ferrarese, et al. 2012). The MATLAS project 3 Deep optical images were obtained for a total of 177 galaxies. All but one were observed in both the g' and i' bands; 60% have also i' band data, and 7 % have additional u* band observations. Total exposure times ranged between 82 minutes (u) 40 minutes (g,r) and 27 minutes (i). The average seeing ranged between 0.65 arcsec (i) and 0.95 arcsec (g). The observing strategy -a sequence consisting of 7 individual exposures with large relative offsets (between 2 and 14 arcmin) and the data reduction technique using Elixir-LSB (sky subtraction, stacking) are fully detailed in Duc, et al. (2015). The achieved surface brightness limit is 28.5-29 mag.arcsec -2 in the g band.

Images were then explored and analysed by the members of the MATLAS team (see Bílek at al., in prep.) using a dedicated web interface, offering navigation and zoomin/zoom-out facilities through various types of images for a given target (including composite true color images, color index and surface brightness maps). The intensity cuts and contrast could be changed online to enhance LSB features (see Fig. 1). The interface allowed the user to access a questionnaire about the presence and properties of stellar structures in and around the target galaxy, about their small and large scale environments and about the presence of contaminants (bright stellar halos, cirrus, artefacts). A visual identification and classification was indeed used to characterise the fine structures around the ETGs.

Light and colour profiles of the galaxies up to large effective radii (typically 10 Re) were obtained with ellipse fitting techniques, in images that had previously been corrected from PSF effects. A deconvolution technique presented in Karabal, et al. (2017) was used for this correction. Applying it turned out to be fundamental as the outer halos of the bright galaxies on MegaCam images are contaminated by light coming from the central parts of the galaxies because of internal reflections in the camera. The PSF effect which varies from one band to the other, and is most pronounced in the r band for MegaCam, generates an artificial reddening in the g-r colour profiles of some galaxies.

The census of dwarf galaxies in the field-of-view of each target (about 1 square degree) was made with a set of semi-automatic algorithms applied on cleaned images, followed by a visual confirmation and classification by the team members. The technique is described in details in Habas, et al. (2019).

Finally, globular cluster (GC) candidates in all fields were identified using the available colour information, central surface brightness and a proxy of the size obtained comparing magnitudes in two apertures. Further details on this photometric method are given in Lim, et al. (2017). The GC spectroscopic confirmation could be achieved in a few specific fields for which observations with the MUSE integral field spectrograph on the VLT have been obtained, e.g. towards the shell galaxy NGC 474 (Fensch et al., in prep) and a few UDG candidates (Marleau et al., Müller et al. in prep). The catalog of GC candidates in the MATLAS fields contains about 30 000 objects (about 200 per field).

Getting through the foreground emission: cirrus

As illustrated in Fig. 2, at the surface brightness limit of MATLAS, some fields are particularly crowded with the extended reflection halos of bright stars and emission from Galactic cirrus, leaving only small unpolluted regions to study the LSB structures around the target galaxies. Cirrus emission is clearly visible in about 20% of the MATLAS fields. The light that scatters in dust clouds shows up as either very uniform smudges located around bright stars or stripped structures, sharing a common orientation. They do not seem to have specific colors at least in the optical regime. Their filamentary structures actually mimic those of stellar streams and may be confused with them (see an example in Duc, Cuillandre & Renaud 2018). However a comparison to data at other wavelengths, especially in the mid (for instance with the WISE all-sky survey) or far infrared regime, sensitive to the dust thermal emission, leaves little doubts on the nature of the Galactic nature of the emission. Cirrus contamination becomes more important towards the Galactic plane, but it may be present even at high Galactic latitude. Indeed, as discussed in Miville-Deschênes, et al. ( 2016) the culprits may be dust clouds located in the vicinity of the Sun, just a few hundred of parsecs away.

Cirrus emission might be the main limiting issue for the exploration of the LSB Universe, especially if one wishes to reach very low surface brightness limits, for instance from Space observatories. Looking at the maps generated by the Planck mission, one may wonder whether the whole sky has real clean extragalactic windows for LSB studies. This calls for attempting to subtract this foreground component as done for the CMB analysis. Because cirrus does not seem to have a specific color -the g-r color index varies along the structures -, this challenging task will likely require a compilation of the complete spectral energy distribution of the data, from the far UV to the far IR, and advanced techniques of data processing. Meanwhile, the current deep surveys tend to avoid regions of heavy pollution by cirrus.

Instead, one may fully exploit their presence and nearby location, to carry out studies of the interstellar medium at unprecedented spatial resolution. Miville-Deschênes, et al. ( 2016) illustrate some of the scientific questions that may be addressed determining the power spectrum of the cirrus emission from the largest scales given by Planck to the smallest ones probed by the optical images. They involve testing the predictions on the turbulence cascade in the ISM.

Exploring the surrounding of galaxies: fine structures and halos

Determining the fraction of galaxies exhibiting in their surroundings tidal features (also referred as fine structures, FS) was one of the original motivations of the project. FS include narrow streams -tidal features made from stars pulled out from a disrupted low-mass companion, diffuse tails -antennae or plume-like structures from the primary galaxy tracing an on-going or past major merger, or shells -concentric sharp-edge stellar structures, due to specific collisions. Such tracers of the past mass assembly of galaxies may be destroyed by successive collisions or gradually dilute with time scales depending on the FS type, as shown by [START_REF] Mancillas | A&A in press[END_REF] using numerical simulations.

Therefore, as each type of features may tell a different story about the nature of the past merging history of a galaxy (minor vs major merger) and of its progenitors (late or Pierre-Alain Duc & MATLAS collaboration early type galaxies), it was important to not only count the FS, but also to determine their morphology and distribute them in different classes. Currently, this is most easily done with a visual inspection of the images, preferentially by expert eyes -a conclusion from the various tests made by Bílek et al. (in prep.) in order to estimate the reliability of the manual classification. Once the debris have dynamically relaxed or evaporated, extended stellar halo can still bring information about the old merger events.

Therefore members of the MATLAS team were invited to identify in all images the existence of fine structures and classify and count them according to their morphology, and annotate unusual halos. Examples of ETGs classified as a function of their main types of collisional debris are presented in Fig. 3.

With such a statistical database, we could compute the fractions of galaxies having a specific type of features and correlate them with the internal properties of the target galaxies (mass, internal dynamics, presence or kinematical substructures such as KDCs) and with their environment, probed by a tracer of the local density of galaxies. This was possible thanks to the wealth of complementary multi-wavelength data provied by the ATLAS 3D project. The main results, presented in details in Bílek et al. (in prep.), are summarised here. They refer to only ETGs located in the MATLAS fields, thus ignoring the galaxies from the ATLAS 3D sample located in the densest environments, i.e. in the Virgo cluster.

• Globally about 40% of all ETGs in the sample show evidence of tidal features or asymmetric stellar halos.

• The fraction of galaxies showing either likely or secure streams, tails and shells is about the same, around 15%.

• The fraction is mass dependent. For instance, above the mass of 10 11 M , the fraction of fully relaxed objects drops to around 40%. Streams and shells are twice more frequent above that mass.

• Slow rotators have on average 1.3 more tidal features than fast rotators.

• All these statistics seem to only weakly vary with the environment as traced by the galaxy density, but a more detailed analysis is needed to ensure this.

Exploring the surroundings of galaxies: dwarf satellites and globular clusters

Besides, beyond the collisional debris, stellar objects such as dwarf galaxies and globular clusters may be used to probe the large-scale environment of galaxies, and get further clues on their structural properties and formation mechanism.

A total of 2210 dwarf galaxy candidates have been identified in the MATLAS fields, covering together a total area of 142 deg 2 (Habas, et al. 2019). Obviously the absence of a distance indicator for most of them prevents us from ensuring their nature as dwarf objects and physical association with the massive galaxies in the field. This could however successfully be tested for about 10% of them with available velocity measurements from archival data (SDSS or WSRT HI data from the ATLAS 3D survey). About 75% of the dwarf candidates are early-type and may be classified as dEs. They are thus abundant even outside galaxy clusters where they are usually detected. One fourth of them are nucleated with a fraction which increases in denser environments, a trend also found in previous surveys. Assuming that their distances correspond to that of the massive host in the field, the dwarf candidates follow the scaling relations determined previously (effective radius vs absolute magnitude vs surface brightness). This is a further indication about the reliability of the selection process of the dwarf candidates. Among them, about 80 (4% in our sample, or 0.6 per square degree) have an effective radius above 1.5 kpc and central surface brightness below 24 mag/arcsec 2 and would qualify as Ultra Diffuse Galaxies (UDGs). Whether UDGs make or not a genuine class of objects remains highly controversial. Nonetheless it is interesting to note that while the vast majority of UDGs have yet been detected in clusters, we do find some of them in the environments probed by MATLAS, i.e. in the vicinity of ETGs in isolation or groups.

A tiny fraction (1%) of the dwarf candidates -4% considering only those qualifying as UDGs -exhibit an excess of globular cluster candidates (more than 4 GCs, when 1-2 are expected given the mass of the host). Examples are shown in Fig. 4. Understanding how and when these low mass objects managed to form or collect this population of GCs is the focus of on-going spectroscopic follow-up using integral field spectrometers.

Getting further: challenges and prospects

Many of the results presented above rely on visual identifications (fine structures) or classification (dwarf candidates). This could be achieved by a small group of people because of the limited number of fields but will be unpractical for the on-going (e.g. CFIS/Unions on the CFHT) or future (LSST, Euclid) surveys that cover much larger areas (several thousands of square degrees). The use AI techniques, such as deep learning with a training based on visual classifications by large groups of people or data generated by numerical simulations, will soon be unavoidable.

Getting more quantitative results would also be an asset. This implies obtaining a reliable photometry of the faint collisional debris and, before that, delineating them precisely. For this purpose, we have developed a web interface to manually and quickly mark the fine structures (Richards et al.,in prep. and Fig. 5). Alternatively one may Given the tremendous progresses made in AI and advanced data processing techniques, there is little doubt that the next IAU symposium dedicated to the exploration of the LSB Universe will present works fully relying on automatic techniques for the identification and classification of structures.

Figure 1 .

 1 Figure 1. Web interface, navigation tool and questionnaire used for the exploration of the MATLAS images and classification of the detected structures.

Figure 2 .

 2 Figure 2. Examples of fields strongly polluted by Galactic cirrus. The displayed composite (g+r+i) images have a size of 1 square degree. Also note the 7' arcmin diameter reflection halos around the bright stars.

Figure 3 .

 3 Figure 3. Various types of identified and classified fine structures in the MATLAS survey. Top first rows: shells, middle rows: streams, bottom rows: tails. The images consist of co-added g+r frames, with for the stream and tail category the true color images superimposed towards the central region. This helps to identify the primary target galaxy. See more images in Bílek et al. (in prep.).

Figure 4 .

 4 Figure 4. Dwarf satellite candidates in the field of MATLAS galaxies, including UDGs. They show an excess of globular cluster candidates identified by the circles.

Figure 5 .

 5 Figure 5. Annotation interface based on the CDS Aladin lite tool consider using automatic detection of tidal features with algorithms such as NoiseChisel (Akhlaghi & Ichikawa 2015). Further developments are however needed to improve the segmentation process necessary to separate the collisional debris from the host galaxy.Given the tremendous progresses made in AI and advanced data processing techniques, there is little doubt that the next IAU symposium dedicated to the exploration of the LSB Universe will present works fully relying on automatic techniques for the identification and classification of structures.

Acknowledgements

This contribution is given on behalf of the full MATLAS team. Special thanks to Michal Bílek, Jean-Charles Cuillandre, Stephen Gwyn, Rebecca Habas, Sungsoon Lim, Francine Marleau, Marc-Antoine Miville-Deschênes and Mustafa Yildiz who have directly contributed to the results highlighted in this paper. The full list of team members is available at the project web page: http://obas-matlas.u-strasbg.fr

The MATLAS project 9 B. Koribalski: Can you tell us more about features detected by amateurs, but not seen at CFHT ? P.A. Duc: These are the features that are lost behind the prominent reflections halos of the MegaCam camera. Note however that in general the CFHT MATLAS images are deeper that those obtained by amateurs, and exhibit features not seen by them. Thus both approaches are complementary.


Sana Ikli

Catherine Mancel

Marcel Mongeau

Xavier Olive
email: xavier.olive@onera.fr

+ S Ikli

E Rachelson
email: emmanuel.rachelson@isae-supaero.fr

An Optimistic Planning Approach for the Aircraft Landing Problem

Keywords: Aircraft Landing problem, Mixed Integer Programming, Optimistic Planning

published or not. The documents may come

INTRODUCTION

The International Air Transport Association (IATA) expects 7.8 billion passengers to travel in 2036, which represents nearly double the passengers recorded in 2016 [START_REF]The international air transport association[END_REF]; this increasing demand on air transportation exposes the available infrastructure to a risk of saturation. Constructing new infrastructures (runways, airports) is a solution to increase the capacity, however, it may not always be feasible due to the huge cost incurred. The alternative is to optimize the use of current infrastructure, especially the runway which is recognized to be the bottleneck of the whole Air Traffic Management (ATM) system.

Since the runway sequence is one of the key factors that determines runway capacity [START_REF] Odoni | Airport systems: Planning, design, and management[END_REF], several researchers were interested in the optimization of runway sequences, which corresponds in the literature to the following problems:

• The Aircraft Landing Problem (ALP) aims at sequencing arriving aircraft on the available runways and scheduling their landing times taking into consideration several operational constraints. • The Aircraft Take-off Problem (ATP) consists in scheduling take-off slots to departing aircraft

• The Aircraft Scheduling Problem (ASP) consists in sequencing and scheduling simultaneously departing and arriving aircraft. According to the survey [START_REF] Bennell | Airport runway scheduling[END_REF] by Bennell et al., the ALP received much more attention in the literature than the ATP or the ASP. Several approaches are proposed in the literature for the three above-mentioned problems, and can be classified in two main categories:

• Exact approaches, mainly MIP-based approaches ( [4], [START_REF] Furini | Aircraft sequencing problems via a rolling horizon algorithm[END_REF], [START_REF] Briskorn | Aircraft landing problems with aircraft classes[END_REF], [START_REF] Ghoniem | Enhanced models for a mixed arrival-departure aircraft sequencing problem[END_REF], [START_REF] Furini | Improved rolling horizon approaches to the aircraft sequencing problem[END_REF], [START_REF] Faye | Solving the aircraft landing problem with time discretization approach[END_REF]) and Dynamic Programming ( [START_REF] Balakrishnan | Scheduling aircraft landings under constrained position shifting[END_REF], [START_REF] Briskorn | Aircraft landing problems with aircraft classes[END_REF], [START_REF] Lieder | A dynamic programming approach for the aircraft landing problem with aircraft classes[END_REF]) • Heuristic approaches ( [START_REF] Bianco | Scheduling models for air traffic control in terminal areas[END_REF], [4], [START_REF] Faye | Solving the aircraft landing problem with time discretization approach[END_REF]) and Metaheuristics, such as Simulated Annealing ( [START_REF] Salehipour | An efficient hybrid meta-heuristic for aircraft landing problem[END_REF], [START_REF] Hancerliogullari | Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem[END_REF], [START_REF] Rodriguez-Diaz | Minimizing deviation from scheduled times in a single mixed-operation runway[END_REF], [START_REF] Ma | Integrated optimization of terminal maneuvering area and airport at the macroscopic level[END_REF]), Tabu Search ( [START_REF] Furini | Improved rolling horizon approaches to the aircraft sequencing problem[END_REF], [START_REF] Soykan | A tabu search algorithm for the multiple runway aircraft scheduling problem[END_REF]), Genetic Algorithms ( [START_REF] Bencheikh | Hybrid method for aircraft landing scheduling based on a job shop formulation[END_REF], [START_REF] Hu | A ripple-spreading genetic algorithm for the aircraft sequencing problem[END_REF]), Ant Colony Optimization ( [START_REF] Bencheikh | Improved ant colony algorithm to solve the aircraft landing problem[END_REF], [START_REF] Jiang | A schedule optimization model on multirunway based on ant colony algorithm[END_REF]), and Variable Neighborhood Search ( [START_REF] Salehipour | Scheduling aircraft landings by applying a variable neighborhood descent algorithm: Runway-dependent landing time case[END_REF], [START_REF] Salehipour | An efficient hybrid meta-heuristic for aircraft landing problem[END_REF]). Interested readers may refer to [START_REF] Bennell | Airport runway scheduling[END_REF] for a comprehensive review of existing approaches to the ALP.

In this work, we are interested in sequencing and scheduling aircraft landings at the runway threshold. Each aircraft has a target landing time and an authorized landing time window, expressed as an earliest and a latest acceptable landing time based on fuel considerations. Deviations from the target times will cause a cost that depends on each aircraft, and the aim is to minimize the total deviations from target times, which is more general than minimizing only total schedule tardiness. To model the problem, we propose a novel MIP formulation that takes into consideration safety constraints by imposing separation between aircraft at the runway threshold (Table 1). The proposed formulation is adapted to airports that involve multiple independent runways. Due the the NP-hardness of the problem [4], solving directly the MIP model for large realistic instances leads to redhibitory computation times, which is unsuited for the dynamic nature of the problem that requires air-traffic controllers to make quick but good decisions. Therefore, we introduce a novel heuristic search methodology based on Optimistic Planning [START_REF] Munos | From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning[END_REF], that provides good-quality solutions in a negligible time. We then evaluate empirically our approach on realistic instances generated from real-traffic data from Paris-Orly airport.

The remainder of this paper is organized as follows. In Section 2 we describe the ALP and highlight the operational constraints. Next, Section 3 presents our proposed MIP formulation and the constraints taken into account. Then, in Section 4, we explain our proposed solution approach. Section 5 presents computational results that show the benefits of our approach, and finally in Section 6 we summarize the contributions of this work and suggest some perspectives for future research work.

PROBLEM DESCRIPTION

Given a set of aircraft near the terminal area of an airport, the ALP consists in mapping each aircraft to a landing time such that a given criterion is optimized while operational constraints are satisfied. When the airport has more than one runway, a decision with respect to the landing runway has to be made by controllers; the runway assignment depends on several factors such as the airport configuration and the direction of arriving aircraft.

The most common approach used by controllers to sequence aircraft is the First-Come First-Served (FCFS) rule, where aircraft land according to the order of the scheduled times of arrival at the runway, and air-traffic controllers ensure only the minimum separation requirements. This FCFS heuristic is easy to implement and guarantees equity between aircraft. However, it is rarely optimal in terms of runway throughput, especially in congested airports [START_REF] Balakrishnan | Scheduling aircraft landings under constrained position shifting[END_REF], simply consider the large separation requirement in some scenarios where a heavy aircraft is followed by a light aircraft (Figure 1). This motivates the development of efficient methods that compute optimal sequences while satisfying several operational constraints such as minimum separation, authorized time windows and constrained-position shifting. • The minimum separation constraint guarantees that no aircraft is affected by the wake-vortex turbulence generated by a leading aircraft, especially during takeoffs and landings. The International Civil Aviation Organization (ICAO) classifies aircraft in three main categories, namely Heavy (H), Medium (M) and Light (L), and the separation requirements are defined depending on the category of both the leading and the following aircraft. Separation requirements are given in Nautical Miles (NM), but can be converted to seconds as explained in [START_REF] Odoni | Airport systems: Planning, design, and management[END_REF] and summarized in Table 1. • Time-windows constraints are defined by an earliest and a latest possible landing times, based on fuel availability or on possible speed-ups. Indeed, once an aircraft arrives at the boundary of a radar range (about 45-60 minutes from the destination airport), decisionsupport tools compute an Estimated-Time of Arrival (ETA) at the runway threshold. If the aircraft speeds up, the Actual Landing Time (ALT) may be earlier than the ETA. On the other hand, aircraft may by delayed after entering the radar range and, in this case, the ALT will be later that the ETA and the latest possible landing time is limited by the available fuel [START_REF] Lee | A study of tradeoffs scheduling terminal-area operations[END_REF]. • The Constrained-Position Shifting (CPS) constraint limits the deviation from the FCFS sequence for equity reasons. This constraint ensures that an aircraft is not deviated from its initial position in the FCFS sequence by more than a given number of positions called maximum position shifting and denoted m, which is usually small; m = 3 or 4 [START_REF] Balakrishnan | Scheduling aircraft landings under constrained position shifting[END_REF]. This constraint does not only ensure equity between aircraft, but it also reduces the complexity of the problem.

In the following section, we introduce a MIP formulation for the ALP involving one or multiple runways, and we show how we can incorporate different operational constraints in the model.

MATHEMATICAL MODELING

Runway assignment and scheduling aircraft at each runway is formulated as a MIP model which decides the landing dates at each runway threshold, while respecting safety requirements so as to optimize a given objective. We leave the control problem, i.e. how aircraft can be controlled so as to implement the solution of our decision problem, for future research work.

Input data

Consider a set of arriving aircraft A = {1, 2, ..., N }, and a set of available runways K = {1, 2, ..., R}. Without loss of generality, let us assume that each aircraft index i ∈ A represents its position in the FCFS sequence. Then, for each flight i ∈ A, the given input data are presented in Table 2.

Decision variables

Our proposed model involves binary optimization variables for sequencing and runway assignment, and continuous optimization variables for assigning times at the runway threshold. The binary variables are defined as follows:

• a ik = 1 if aircraft i is assigned to runway k, 0 otherwise, • δ ijk =     
1 if aircraft i and j are assigned to runway k, and i lands before j, 0 otherwise,

• y ij = 1 if aircraft i lands beforej, 0 otherwise,
For each aircraft i ∈ A, the continuous variables are:

• t i : landing time • t - i , t + i
: deviations from the target landing time T i (before and after T i , respectively).

MIP model

Our objective minimizes the total deviation cost from target times (T i ) which is more general than minimizing only the total schedule delay. The complete model is given by ( 1)-( 12) min δ,y,a,t i∈A

c - t - i max(0, T i -t i ) +c + t + i max(0, t i -T i ) (1)
t i = T i -t - i + t + i i ∈ A (2) E i ≤ t i ≤ L i i ∈ A (3) y ij + y ji = 1 i, j ∈ A : i < j (4) k∈K a ik = 1 i ∈ A ( 5
) k∈K δ ijk + δ jik ≤ 1 i, j ∈ A : i < j (6) δ ijk + δ jik ≥ a ik + a jk -1 i, j ∈ A : i < j, k ∈ K (7) 2(δ ijk + δ jik ) ≤ a ik + a jk i, j ∈ A : i < j, k ∈ K (8) t j ≥ t i -M 1 (1 -y ij )
i, j ∈ A : i = j (9)

t j ≥ t i + S ij -M 2 (1 -y ij ) i, j ∈ A : i = j (10) i -m ≤ N - j∈A,j =i y ij ≤ i + m i ∈ A (11)
δ ijk , y ij , a ik ∈ {0, 1} i, j ∈ A : i = j, k ∈ K (12)
In the above formulation, constraints (2) are introduced to linearize the objective function; constraints (3) represent the time window restrictions; constraints (4) enforce the order precedence relationship between flights i and j at landing; constraints [START_REF] Furini | Aircraft sequencing problems via a rolling horizon algorithm[END_REF] ensure that an aircraft is assigned to exactly one runway; constraints (6) enforce the order precedence relationship between flights landing on the same runway; constraints [START_REF] Ghoniem | Enhanced models for a mixed arrival-departure aircraft sequencing problem[END_REF] and ( 8) enforce the logical relationship between δ ijk and a ik ; constraints [START_REF] Faye | Solving the aircraft landing problem with time discretization approach[END_REF] relates precedence relationships between landings to landing times; constraints [START_REF] Balakrishnan | Scheduling aircraft landings under constrained position shifting[END_REF] ensure the separation requirements between aircraft landing at the same runway; constraints [START_REF] Lieder | A dynamic programming approach for the aircraft landing problem with aircraft classes[END_REF] impose the CPS constraint, and constraints [START_REF] Bianco | Scheduling models for air traffic control in terminal areas[END_REF] enforce the binary restrictions of our discrete variables.

Before reporting numerical results obtained with this formulation, we shall first present a novel alternate methodology to solve the ALP, since solving directly the MIP leads to redhibitory computation times, as we shall show in Section 5.

OPTIMISTIC PLANNING

The dynamic nature of the ALP requires air-traffic controllers to make quick but good decisions; the computation time of any solution is thereby a critical issue. Given the complexity of the problem, the computation time to find an optimal solution either with our MIP model or with other exact approaches is unsuited for real-time applications. Therefore, we introduce a novel heuristic search approach based on the Optimistic Planning (OP) paradigm [START_REF] Hren | Optimistic planning of deterministic systems[END_REF], [START_REF] Munos | From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning[END_REF], capable of computing solutions that do not deviate too much from the FCFS solution sequence and that are relatively close to optimal solutions, within an acceptable computational time.

Our approach models the ALP as an environment defined by states, transitions, actions, and costs where:

• each state denoted x, is a partition (I, Ī) of the set of aircraft, where Ī is the (ordered) set of aircraft that have already landed, and I is the set of aircraft that have not landed yet.

• each action denoted u is an aircraft index i ∈ I that we decide to land.

• each transition is defined follows. If we execute action u = i ∈ I from a given state x = (I, Ī), then the system generates the unique next state x = (I , Ī ), where I = I \ {i}, and Ī = Ī ∪ {i} (aircraft i landed).

• when the environment transits from the state x to the new state x defined above, the estimated value c (cost) of the the new state is defined by

c = f ( Ī ) + g(I ),
where f ( Ī ) is the delay cost of the (landed) sequence Ī , and g(I ) is a function that estimates the lowest cost among all sequences obtained from I that satisfy the CPS constraints. In our numerical experiments, the FCFS rule is chosen as the estimation heuristic g, i.e. m = 0. Optimistic Planning is the method that incrementally explores this search tree so as to identify an optimal branch as quickly as possible. The algorithm starts from the initial state where the set Ī is empty, and I = A (all aircraft available to land). At each iteration, its main loop seeks to determine which aircraft to land based on the optimistic evaluation c, and it updates Ī by adding this aircraft, until a stopping criteria is met, i.e. all aircraft are landed or a time limit is reached. Only actions that satisfy the operational constraints are available in a given state.

RESULTS AND DISCUSSION

In this section we report the computational results of the MIP formulation ( 1)-( 12) and of our Optimistic Planning approach. Experiments are run on a personal computer under GNU/Linux operating system, processor Intel(R) Core(TM)

Test instances

We use four test instances from a benchmark test-problem set under construction at ENAC, obtained from real traffic in Paris-Orly Airport, that features two runways (06/24 and 08/26 as shown in Figure 2), which are considered independent (runway 02/20 is rarely used for commercial traffic).

These instances are constructed from two traffic days obtained from the OpenSky Network [27]: one in July 2018 containing mostly data about landed aircraft on runway 06/24, and one in April 2019 containing data about landed aircraft on runway 08/26. The four instances come from merging these two traffic days and artificially adding light aircraft to obtain larger and also more congested instances. The four considered instances are available at [START_REF]The Aircraft Landing Problem instances[END_REF]. Table 3 shows an example of such an instance. The fourth and fifth columns, denoted "sta" and "sta_s", indicate the scheduled time of arrival in HH:MM:SS format and in seconds respectively. The sixth column displays the delay cost per time unit of each aircraft, that we computed following a similar approach to that used in [START_REF] Furini | Improved rolling horizon approaches to the aircraft sequencing problem[END_REF].

Computational results

We first report results obtained from implementing our MIP model involving a single runway (|K| = 1), for different values of the maximum position shifting m = 2, ..., 6. Figure 3 illustrates the evolution of the computation time in seconds for each value of m and for a set of 10 test instances of various sizes |A| = 16, 18, ..., 30, obtained by simply considering the first |A| lines of each of the four instances [START_REF]The Aircraft Landing Problem instances[END_REF]. We impose a time limit of 1800 seconds (30 minutes) in CPLEX.

Figure 3 exhibits the expected exponential growth of the computing time with the size of the instance, |A|, and with increasing values of m, (recall that the ALP is an NP-hard problem). The saturation effect of 6-CPS is simply due to our time limit. Table 4 reports the performance of the MIP model on a test instance of size |A| = 28. Throughout Table 4, columns k-CPS represent results for different values of m, and the F-CPS (Free CPS) column reports results without CPS constraints. Results are reported in terms of computing time in seconds with a time limit of 1800 seconds, and the percentage improvements with respect to the FCFS sequence that was computed based on the order given by scheduled time of arrivals. The percentage of improvement is computed as:

%improv = C FCFS -C MIP C FCFS × 100, (13)
where C FCFS and C MIP are the costs of the FCFS sequence and that of the MIP solution calculated via CPLEX, respec-tively. It can be concluded from Table 4 that significant improvements can be obtained starting from m = 3, but this requires large computation times, which make it non-adapted to the dynamic nature of our problem, especially since the complexity scales exponentially with the number of aircraft, and since future ATM systems will have to deal with very large ALP instances.

We report the results of the OP approach on the mediumsized instances used in Figure 3, as well as on large instances of sizes |A| = 30, 32, ..., 40 involving a single runway (Table 5), and imposing each time a limited computational time-budget of {2, 5, 15} seconds. For each instance size, we evaluate the approach on different instances of the same size and report the average, minimum and maximum improvement over the FCFS solution.

Table 5 shows the average percentage improvement of the total cost given by Eq. ( 13) for two values of the maximum position shifting parameter, m = 2 and 3. It can be observed that large instances of sizes greater than 30 can benefit from a significant improvement (on average more than 21%) for a maximum position shifting of m = 3, within only 5 seconds.

Finally, Table 6 reports an example of the solution provided by our OP approach on the instance given in Table 3 with |A| = 22 aircraft, and imposing a computational budget of 2 seconds. The first column displays the aircraft position in the solution sequence. The "index" columns corresponds to the aircraft index from Table 3 occupying each position.

The "landing" columns report the landing times.

For this example, the percentage improvement of the FCFS sequence is 35%, and it can be deduced from Table 6 that our approach does not only improve the FCFS heuristic in terms of total cost, but also optimizes the utilization of the runway in terms of the makespan, i.e. length of the sequence. Indeed, the last landing in the sequence for the FCFS is 7:41:20 while the last landing with our approach is 7:40:45.

Our computational experiments on the MIP formulation and the heuristic search approach show that the latter is more suited and more promising to solve the ALP with large congested instances, since it can provide good solutions in short computation time.

CONCLUSION

Runway sequence optimization is an ongoing challenge for researchers and controllers due to the dynamic nature of the problem and to the various operational constraints that must be taken into consideration. In this work, we proposed an exact approach (MIP) to solve the deterministic case of the ALP as well as a novel method based on Optimistic Planning to solve medium and large challenging instances.

Our computational experiments show that computation times for our MIP model (and other exact approaches) are very high for large congested instances, which make them unsuited to the dynamic nature of ALP. With the constrainedposition shifting restrictions, the complexity of the problem can be reduced, but the problem remains untractable for increasing values of the maximum position shifting parameter and the number of aircraft. On the other hand, our proposed heuristic search approach based on optimistic planning is able to find good solutions that significantly improve the FCFS sequence within a limited time budget, making it a promising method for solving the ALP in real time.

Extending our approach to the multiple runway case and taking into consideration uncertainty on the arrival times are future tracks of research.

Figure 1 :

 1 Figure 1: Comparison of three landing sequences. Case 1 illustrates the FCFS sequence. In case 2, the landing sequence is optimized with respect to wake turbulence separation, and in case 3 the landing sequence is further optimized by runway assignment. Notation Parameter T i Target landing time [E i , L i ] Landing time window ( L i > E i ) S ij minimum separation time (≥ 0) between aircraft i and j, where i lands before j c - i Penalty cost (≥ 0) per time-unit for landing before the target time T i c + i

Figure 2 :

 2 Figure 2: A representation of Orly runways (Source [26])

Figure 3 :

 3 Figure 3: Computational time of the MIP approach for different maximum position shifting values

Table 1 :

 1 Final approach separation matrix (in seconds) according to ICAO's basic wake-turbulence categories (Source[START_REF] Balakrishnan | Scheduling aircraft landings under constrained position shifting[END_REF])

			Following aircraft
		H	M	L
	H	96	157	196
	Leading aircraft M	60	69	131
	L	60	69	82

Table 3 :

 3 Examples of an instance features with |A| = 22 aircraft.

	index	mdl	category	sta	sta_s	delay cost
	1	A332	Heavy	07:00:00 25200	8
	2	-	Light	07:00:00 25200	1
	3	B744	Heavy	07:00:00 25200	22
	4	A333	Heavy	07:00:00 25200	8
	5	B744	Heavy	07:00:00 25200	22
	6	B738	Medium	07:10:00 25800	7
	7	A320	Medium	07:15:00 26100	5
	8	B77W	Heavy	07:15:00 26100	28
	9	A333	Heavy	07:15:00 26100	8
	10	A320	Medium	07:20:00 26400	5
	11	A320	Medium	07:20:00 26400	5
	12	B738	Medium	07:25:00 26700	7
	13	A318	Medium	07:25:00 26700	3
	14	B744	Heavy	07:30:00 27000	22
	15	-	Light	07:30:00 27000	1
	16	A321	Medium	07:30:00 27000	7
	17	A318	Medium	07:30:00 27000	3
	18	A320	Medium	07:35:00 27300	5
	19	A320	Medium	07:35:00 27300	5
	20	A320	Medium	07:35:00 27300	5
	21	A319	Medium	07:35:00 27300	4
	22	A321	Medium	07:40:00 27600	7

Table 4 :

 4 MIP approach performance on a test instance of size |A| = 28 for different maximum position shifting values

		2-CPS 3-CPS 4-CPS 5-CPS 6-CPS F-CPS
	cpu (s)	5	66	154	240	1800	1800
	%improv	25	38	50	57	64	64

Table 5 :

 5 Algorithm performance details (average improvement) for one runway

	|A|	Average improvement (%) k = 2	Average improvement (%) k = 3
		2s	5s	15s	2s	5s	15s
	18	12 12	12	2	15	15
	20	18 18	19	10 23	24
	22	23 22	21	19 32	33
	24	19 25	26	22 26	31
	26	14 19	20	11 24	31
	28	15 16	24	9	23	29
	30	14 18	24	8	21	36
	32	14 18	26	2	22	37
	34	14 12	25	6	23	28
	36	13 13	25	7	24	24
	38	12 13	26	8	23	26
	40	12 13	25	7	22	26
	min	12 12	12	2	15	15
	max	23 25	26	22 32	37
	avg	15 16	20	28 23	29

Table 6 :

 6 Examples of solutions provided by FCFS and our optimistic approach

ACKNOWLEDGMENTS

The authors would like to thank Serge Roux, from ENAC, for his assistance with technical support.