Guix-HPC is a collaborative effort to bring reproducible software deployment to scientific workflows and high-performance computing (HPC). Guix-HPC builds upon the GNU Guix 1 software deployment tool and aims to make it a better tool for HPC practitioners and scientists concerned with reproducible research.

Outline

Guix-HPC aims to tackle the following high-level objectives: • Reproducible scientific workflows. Improve the GNU Guix tool set to better support reproducible scientific workflows and to simplify sharing and publication of software environments.

•

Cluster usage. Streamlining Guix deployment on HPC clusters, and providing interoperability with clusters not running Guix.

•

Outreach & user support. Reaching out to the HPC and scientific research communities and organizing training sessions.

The following sections detail work that has been carried out in each of these areas.

Reproducible Scientific Workflows

Supporting reproducible research in general remains a major goal for Guix-HPC. The ability to reproduce and inspect computational experiments-today's lab notebooks-is key to establishing a rigorous scientific method. We believethat a prerequisitefor thisis the ability to reproduce and inspect the software environments of those experiments.

We have made further progress to ensure Guix addresses this use case. We work not only on deployment issues, but also upstream-ensuring source code is archived at Software Heritage-and downstream-devising tools and workflows for scientists to use.

The Guix Workflow Language

The Guix Workflow Language13 (or GWL) is a scientific computing extension to GNU Guix's declarative language for package management. It allows for the declaration of scientific workflows, which will always run in reproducible environments that GNU Guix automatically prepares. In the past year the GWL has seen further development to refine the language and its integration with the Guix environment management features.

The GWL was always intended to be used as an extension to Guix, but this presented unique problems. Extensions to Guix may use the Guile modules it provides as a library in addition to accessing Guix package definitions. With the exact version of Guix under user control via guix pull this put extension developers between a rock and a hard place: they could either dynamically bind to the version of Guix currently in use and hope that the API of future versions of Guix remains unchanged compared to the version they used during development,or they could restrict the extension to a well-known version of Guix with the unfortunate side effect that any reference to packages would be outdated compared to those available in the variant of Guix currently installed by the user.

Neither of these options appealed to the developers of the Guix Workflow Language, so they implemented a third option based on the Guix API for inferiors14 . The result is that any package requested by users of the Guix Workflow Language will be resolved with the currently installed variant of Guix, including any defined channels or time travel settings 15 . For all other features, the Workflow Language binds to a well-known version of Guix as a library, thereby satisfying the seemingly conflicting expectations and requirements of users and developers.

The requirements of the GWL motivated the implementation of a generic mechanism in Guix to discover extensions, as well as performance improvements in the inferior mechanism.

Version 0.3.0 of the Guix Workflow Language was announced in early February 2021 16 .

Guix-Jupyter

We announced Guix-Jupyter 17 a bit more than a year ago, with two goals: making notebooksself-contained or "deployment-aware"so that they automatically deploy the software (and data!) that they need, and making said deployment bit-reproducible.

In essence, Guix-Jupyter treats software deployment and data as a first-class input to the computation described in the notebook. One can run the notebook on one machine or another, today or two years from now, and be sure it's running in the exact same software environment.

This Jupyter "kernel" builds on Guix support for reproducible builds and for "time travel". That very first version demonstrated what can be achieved, and it addressed what remains a very relevant issue in the Jupyter world, as is clear to anyone who has tried to run a notebook published in one of the many public galleries. 8. Version 0.2.1 was announced in January 202118 . Among the user interface changes and bug fixes it provides, ;;guix describe and ;;guix search "magic" commands have been added, providing the same functionality as the same-named guix commands. Build and download progress is now reported in the cell that triggered it, which improves the user experience. While we still consider it "beta", we believe it already smoothly covers a wide range of use cases.

From Source Code to Research Article

GWL and Guix-Jupyter are both tools designed for a scientific audience, as close as possible to the actual scientific experiments and workflows. In the same vein, we participated in the Ten Years ReproducibilityChallenge19 organized by ReScience C, an open-access, peer-reviewed journal that targets computational research and encourages the replication of already published research.

Participantswere invited to pick a scientific article they had published at least ten years earlier, and to try and reproduce its results. Needless to say, participants encountered many difficulties, most of which boil down to: finding the code, getting it to build, and getting it to run in an environment as close as possible to the original one.

This last challenge-re-deploying software-is of particular interest to Guix, which has to goal of supporting bit-reproducible deployments in time. Of course, the chosen articles were published before Guix even existed, but we thought it was a good opportunity to demonstrate how Guix will allow users to address these challenges from now on. Among the fifty participants, some chose to address deployment issues using Docker or virtual machines (VMs), and several chose Guix. The challenge and its contributions, including a discussion of software deployment issues and Guix, led to an article in Nature 20 (Jeffrey M. Perkel, Challenge to scientists: does your tenyear-old code still run?, August 2020).

9.

The replication work by Ludovic Courtès 21 is an attempt to show the best one could provide: a complete, end-to-end reproducible research article pipeline, from source code to PDF. The articles shows how to bridge together code that deploys the software evaluated in the paper, scripts that run the evaluation and produce plots, and scripts that produce the final PDF file from LaTeX source and plots. The end result is approximately 400 lines of code that allow Guix to rebuild the whole article and the experiment it depends on with a well-specified, reproducible software environment.

The article concludes on our vision:

We hope our work could serve as the basis of a template for reproducible papers in the spirit of Maneage 22 . We are aware that, in its current form, our reproducible pipeline requires a relatively high level of Guix expertise-although, to be fair, it should be compared with the wide variety of programming languages and tools conventionally used for similar purposes. We think that, with more experience, common build processes and idioms could be factorized as libraries and high-level programming constructs, making it more approachable.

[…] We look forward to a future where reproducible scientific pipelines become commonplace. This is just the beginning. We plan to keep working closely with scientists and journals such as ReScience C to investigate ways to make this approach more widely applicable.

Soon after the challenge, we organized a one-day on-line hackathon to collectively work on providing missing bits so more scientific experiments can be reproduced. This led to improved coverage of historic pack-

Ensuring Source Code Availability

Guix, for instance with guix time-machine, allows you to travel back in time and to re-deploy software reproducibly. It is a great step forward in support of reproducible research. But there is still an important piece to make this viable: a stable source code archive. The collaboration with Software Heritage (SWH) initiated in 2019 24 is continued.

Since March 2019 25 , Guix eases the request submission to SWH for long-term archiving via guix lint -c archival. Once the package is ready, linting ensures the source code is saved on SWH. Later, if original upstream source code vanishes, Guix falls back to SWH. This aforementioned article read:

Our plan is to extend Software Heritage26 such that it would periodically archive the source code of software packaged by Guix. This is now the case: Guix serves the file sources.json27 , which contains references to all the source code packages refer to; this is periodically ingested by Software Heritage via the SWH nixguix 28 "loader". As a result, more packages are continuously archived. This work was done by Tweag for the benefit of the Nix and Guix projects; the Guix team helped review it. The primary issue that remains before SWH covers all the needs of Guix is the availability of source code "tarballs" (archives such as tar.gz files). SWH archives the contents of version control repositories and tarballs-not tarballs themselves. This makes sense from an engineering viewpoint, but it means that tools such as Guix that depend on those tarballs cannot simply fetch them by hash. However, most Guix packages currently refer to tarballs rather than version-control system (VCS) repositories. For these, the automatic SWH fallback in Guix will be of little help.

Guix developer Timothy Sample started working on a solution to address this issue. Sample developed a tool called Disarchive that aims to create a link between tarballs and their contents29 . Concretely, Guix would maintain a Disarchive database mapping source code tarball hashes to their content hash along with tarball metadata. This would allow Guix to fetch content from SWH while still being able to reconstruct the expected tarball and check that it corresponds to the hash contained in the package definition. This work is still in a prototyping phase but is already promising.

Package Transformations

HPC practitioners are often demanding when it comes to customizing software they deploy: choosing dependencies, versions, build flags, and so on. Guix caters to these needs through its programming interfaces but also via its easy-to-use package transformation options 30 .

Over the past year, several of them were added. The --with-c- toolchain option allows users to build a package and all its dependents with a given C toolchain; this is useful for those willing to benefit from the latest improvements in optimizing compilers. The --with-patch option applies a patch to a package and rebuilds it along with its dependent. The --with-debug-info rebuilds a package in a way that preserves its debugging info (if it wasn't already available) and without requiring a rebuild of its dependents.

12.

Furthermore,packagetransformationoptionspassed toguix install and similar commands are now recorded in profiles and replayed when running guix upgrade, thereby ensuring user customization is preserved. Another novelty is that package transformations now apply to "implicit inputs" (package dependencies provided by the build system), giving users even more flexibility.

The Guix reference manual now includes a section discussing the various ways to define package variants31 .

13. run-time support softwaresuch as implementationsof the MessagePassing Interface (MPI), to linear algebra software, to statistics and bioinformatics modules for R. In addition to packages in Guix proper, we have been maintaining channels, which provide additional packages, usually specialized in one application domain.

As part of the aforementioned Ten Years Reproducibility Challenge and subsequent reproducible research hackathon, we created the Guix-Past channel 32 , with the goal of collecting versions of software older than Guix itself, for use in reproducible research experiments. It now contains sixty packages, including Python 2.4 (from 2008), Perl 5.14 (from 2011), and 2006-era versions of the GNU "Autotools". As an example, Guix-Past allowed Genenetwork administrators to migrate a 20-year old web service 33 from a 12-year old CentOS and it is now running in a modern Guix container. We expect Guix-Past will serve as the basis for future reproducible research endeavors.

A new Guix Science channel 34 has been established to collaborate on packaging and maintaining recent scientific software that currently cannot be included into Guix proper. JASP, RStudio and JupyterLab are available. A substitute server continuously builds these packages and serves binary substitutes for them.

Since Guix is trivially extensible,users do not need to wait for the community to prepare missing packages they may need right now. Tools like the new package importer and installer for R 35 let users of the R programming language install any R package-from CRAN, Bioconductor, or any Mercurial or Git repository-by leveraging the recursive package importing facilities that Guix provides from within a running R session. This replaces the need for installers like devtools and exposes reproducible package management features through a familiar interface within R.

Cluster Usage and Deployment

Over the last few years, we have been developing guix pack to support userswhotarget supercomputerswhereGuix isunavailable. guix pack creates "application bundles" as Docker or Singularity images, or as plain selfcontained tarballs. We previously implemented relocatable packs: archives that can be extracted anywhere on the file system while still allowing users to run the software therein. The appeal of this option is that it allows users to run packaged software on machines that provide neither Guix nor a container run-time.

Relocatable packs were initially implemented by using the Linux "unprivileged user namespace" feature, with a fallback to PRoot when unprivileged user namespaces are unavailable. In the latter case though, the overhead can be prohibitively high for some applications. To address that, guix pack can now build faster relocatablepacks36 that rely on a customization of the run-time linker (ld.so) along with the use of Fakechroot. It provides the flexibility of packs with negligible overhead.

Guix deployment on scientific clusters continues. A notable example is work-in-progress to support Guix out-of-the-box on Grid'500037 , a major French grid and HPC environment. Installing Guix on Grid'5000 is quite different from installing it on a "regular" HPC cluster due to the unusual nature of this environment: Grid'5000 usershave the option to deploy their own operating system images on compute nodes and have administration privileges on them. This has required adjustmentscompared to our cluster installation guide38 . This should be in production in the coming weeks.

This fall at UTHSC, Memphis TN, we have installed an 11-node HPC Octopuscluster (264 cores) 39 for pangenomeand geneticsresearch. Notable about this HPC is that it is administered by the users, thanks to GNU Guix: 15.

we install, run and manage the cluster as researchers. UTHSC IT manages the infrastructure, i.e., physical placement, routers and firewalls, but beyond that there are no demands on IT. Thanks to out-of-band access we can completely (re)install machines remotely. Octopus runs GNU Guix on top of a minimal Debian install and we are experimenting with pure GNU Guix nodes that can be run on demand. Lizardfs is used for distributed network storage. Almost all deployed software has been packaged in GNU Guix and can be installed by regular users on the cluster without root access.

Guix is also the foundation for the data analysis platform PsychNotebook40 , which assists researchers and students in the preparation, analysis, and transparent documentation of psychological data. While a modern web interface hides most aspects of Guix from the user, under the hood channel files and manifests are used to create shareable and reproducible environments, which then can be shared with other users of the platform or exported and run on local hardware. After a testing period in the previous semester with about 15 students the system is now live and currently used to teach about 20 students the basics of R using RStudio Web.

  23 https://gitlab.inria.fr/guix-hpc/guix-past 24 https://www.softwareheritage.org/2019/04/18/software-heritage-and-gnu-guix-join-forces-toenable-long-term-reproducibility/ 25 https://hpc.guix.info/blog/2019/03/connecting-reproducible-deployment-to-a-long-term-sourcecode-archive/ 11.

  versions in the new Guix-Past channel 23 , which was created for the challenge.

20 https://www.nature.com/articles/d41586-020-02462-7 21 https://doi.org/10.5281/zenodo.3886739 22 http://maneage.org/ 10. age

https://workflows.guix.info

https://guix.gnu.org/manual/en/html_node/Inferiors. html

https://guix.gnu.org/manual/en/html_node/Invoking-guix-time_002dmachine. html

https://lists.gnu.org/archive/html/gwl-devel/2021-02/msg00000.html

https://hpc.guix.info/blog/2021/01/guix-jupyter-0.2.1-released/

https://rescience.github.io/ten-years/

https://forge.softwareheritage.org/T1352

http://guix.gnu.org/sources.json

https://issues.guix.gnu.org/42162#15

https://guix.gnu.org/manual/en/html_node/Defining-Package-Variants.html

https://hpc.guix.info/blog/2020/05/faster-relocatable-packs-with-fakechroot/

https://www.grid5000.fr/

https://hpc.guix.info/blog/2017/11/installing-guix-on-a-cluster/

https://www.psychnotebook.org

Guix-HPC was the Max Delbrück Center for Molecular Medicine (MDCThis year was marked by 1 https://guix

Declarative Deployment with Manifests

In addition to the "imperative" management style where one runs guix install and related commands, Guix supports a declarative style where the user provides a code snippet, called a manifest, that describes the packages to deploy. The declarative approach has the advantage of being explicit and stateless: the manifest file can be put under version control and shared with others. It is also flexible because users have access to the whole programming environment of Guix from within the manifest.

To reduce the learning curve and make it easier to switch to the declarativestyle,we madetwo improvements. First,userscan now export a manifest from an existing profile by running guix package --export-manifest. The output can be stored in a file and users can switch to running guix package --manifest with that file right away.

Second, there is now a high-level programming interface giving access to package transformations, with a one-to-one mapping to their command-line syntax. This interface can be used in manifests. In fact, the manifest produced by --export-manifest uses it when needed.

Packaging

The package collection that comes with Guix keeps growing. It now contains 16,000 packages, including many scientific packages ranging from

Outreach and User Support

Guix-HPC is in part about "spreading the word" about our approach to reproducible software environments and how it can help further the goals of reproducible research and high-performance computing development. This section summarizes articles, talks, and training sessions given this year.

Articles

The following articles were published in the Ten Years Reproducibility Challenge special issue of the ReScience C journal 41 (volume 6, issue 1); they present different ways of using Guix to reproduce the software environment associated with a past computational experiment:

Training Sessions

JDEV, the annual conference gather research engineers from all the French research institutes and universities, took place on-line in July 2020 56 . It included an presentation of Guix along with an introductory workshop.

The User Tools for HPC (UST4HPC) 57 workshop took place in January 2021. It is organized as part of the training sessions program of the French national scientific research center (CNRS). It included talks and hands-on session about Guix and Guix-Jupyter.

56 http://devlog.cnrs.fr/jdev2020/t4 57 https://calcul. math.cnrs.fr/2021-01-anf-ust4hpc-2021.html 19.

Personnel

GNU Guix is a collaborative effort, receiving contributions from more than 60 people every month-a 50% increase compared to last year. As part of Guix-HPC, participating institutions have dedicated work hours to the project, which we summarize here.

Perspectives

Guix availability on scientific computing clusters remains a top priority. We have seen increased adoption and interest among cluster system administrators. The latest guix pack improvements should be welcomed by those targeting clusters not running Guix. We expect to continue work on these two complementary fronts: reaching out to system administrators, notably through training sessions, and streamlining the use of packs and non-root deployment in general.

Upstream, we will continue to work with Software Heritage with the goal of achieving complete archive coverage of the source code Guix refers to. We have identified challenges related to source code "tarball" availability; this will probably be one of the main efforts in this area for the coming year. Downstream, a lot of work has happened in the area of reproducible research tools. First, our package collections have grown to include more and more scientific tools; the new Guix Science and Guix-Past channels cater to additional use cases. Second, the Guix Workflow Language, Guix-Jupyter, have matured; along with the PsychNotebook service, they bridge thegapbetweenreproduciblesoftwaredeploymentand reproduciblescientific tools and workflows. Likewise, our participation in the "Ten Years Reproducibility Challenge" demonstrated very concretely what Guix brings to scientific workflows. It showed that fully reproducible research article workflows are indeed a possibility.

Working on the tools and workflows directly in the hands of scientists will be a major focus of the coming year. We want to contribute to raising the bar of what scientists come to expect in terms of reproducible workflows.

There's a lot we can do and we'd love to hear your ideas 58 ! 58 https://hpc.guix.info/about 21.

22.

23.


A mathematical construction of n-dimensional quasicrystals starting from G-clusters

Nicolae Cotfas, J.-L.

A mathematical construction of n-dimensional quasicrystals starting from G-clusters Abstract. We present a mathematical construction of n-dimensional quasicrystals by starting from its symmetry group, an arbitrary finite group, and from its local structure described by using a finite union of orbits of G, called a G-cluster: namely, we construct the periodization space, the G-invariant lattice, the decomposition into the physical and internal space in a canonical way. Using a strip-and-projection method we obtain quasiperiodic patterns corresponding to various generic local structures.


On a generalization of the Hermite constant

Jean-Louis Verger-Gaugry

To cite this version:

Jean-Louis Verger-Gaugry. On a generalization of the Hermite constant. Periodica Mathematica Hungarica, 1997, 34 (1-2), pp.153-164. 10.1023/A:1004288927330. hal-03136653

On a Generalization of the Hermite Constant Abstract. We report some results on the theory of quasiperiodic sphere packings controlled by a finite group G in the n-dimensional Euclidean space, constructed by means of an higher dimensional Euclidean space which contains G-invariant lattices. A generalization of the Hermite constant is used to find upper bounds of the density.


Manuel Trotta
email: manuel.trotta@emse.fr

Claudia Archetti
email: archetti@essec.edu

Dominique Feillet
email: dominique.feillet@mines-stetienne.fr

Alain Quilliot
email: alain.quilliot@isima.fr

CMP -CAMPUS GEORGES CHARPAK PROVENCE

Keywords: Routing, pickup and delivery problems, ring, computational complexity

In this paper we introduce a new class of Pickup and Delivery problems on circles (or rings).

We consider m stations arranged in a circle and n transportation requests. Each request i asks for the transportation of a certain quantity qi from a pickup station si to a delivery station ti.

A fleet of capacitated vehicles is available at the depot. In the first part of the paper we propose a classification scheme for these problems. In the second part, we address the variants in which the vehicles are allowed to move in a single direction of the circle (either clockwise or counterclockwise) and the objective is to minimize the number of tours on the ring while serving all the requests. We provide a complexity analysis for this class of problems. We develop polynomial time algorithms for the variants that are polynomially solvable and proofs of NPhardness for the variants that are NP-hard. In addition, for the latter, we provide mathematical formulations and perform computational tests that show the effectiveness of these formulations.

Finally, we compare optimal solutions with those obtained using a straightforward greedy algorithm.

Introduction

It is a matter of fact that urban mobility, by means of public transport or personal cars, has become a key factor in people's everyday life, making it easier. Nowadays, working activities are more and more concentrated in urban areas. Thus, more and more people commute on urban areas on a daily basis. This clearly causes a number of issues, and public entities are struggling to find ways and policies that help in facing the ever growing demand of service. Among the different solutions proposed in the recent years, the one in which we are interested in this paper is the use of autonomous vehicles, like cars, minibuses and shuttles. The use of these vehicles raises legal, ethical, economic and safety issues. Due to these problems it is not likely that autonomous vehicles will totally replace normal vehicles soon. However, they will probably first be authorized for collective transportation.

There already exist few cases where fully autonomous vehicles are used in public transportation. In May 2019 Groupe Renault, the Transdev Group, IRT SystemX, Institut VEDECOM and the University of Paris-Saclay initiated a new project called Paris-Saclay Autonomous Lab (par (2019)). Its purpose was to develop new autonomous (i.e. driverless) mobility services using dedicated lane and public streets to supplement the existing Saclay Plateau transportation system. An overnight public transportation service using an autonomous Transdev-Lohr i-Cristal shuttle was designed to serve the Saclay Plateau neighborhoods from the Massy station. On December 2018, Keolis and the European Metropolis of Lille launched an electric autonomous shuttle service at the University of Lille in Villeneuve d'Ascq, with a student population of 20,000 and 1,600 researchers (lil (2018)). The service at Lille university had employed two NAVYA electric autonomous shuttles for a period of one year with four dedicated stops on a 1.4 km circle route, and had provided connections to two metro stations. More recently, in Lyon a project has been launched to study the use of electric autonomous shuttles for urban mobility (lyo (2020)).

In [START_REF] Antonialli | International benchmark on experimentations with autonomous shuttles for collective transport[END_REF] a worldwide benchmark on the use of Autonomous Shuttles for Collective Transport (ASCT) has been performed. By the time this research was carried out, a total of 92 experiments were identified, spread over 32 countries around the world and enabled by 20 different autonomous shuttle manufacturers. Results showed a European lead on both the number of experiments and manufacturers, with highlights to the French startups Navya and EasyMile. Regarding the road environment, two distinct scenarios were observed.

In the first, shuttles circulate in closed/controlled areas (such as university campuses, parks, hospitals, resorts, airports, and other designated roads); this kind of deployment comprised 52.17% of the projects. In the second scenario (47.83%), shuttles were able to circulate among mixed traffic -for these cases the routes were mainly predetermined in city-centers or areas with a slow-speed circulation for regular vehicles. By analyzing the prevailing business models, the author observed that the vast majority of experiments tackled public transport schemes (96.55%) with daily commuters as the main revenue source for the transport operator. Systems with regular lines comprised the vast majority of models among the sampled projects (91.21%) while demand-responsive transport answered to only 4.40% and a mixed approach comprising both operation models was present in the other 4.40%. Notwithstand-ing, as more countries and cities begin to allow testing and circulation of AVs, the percentage of on-demand autonomous mobility is likely to increase.

In this work, we investigate on-demand services carried out using autonomous vehicles on circular networks. Circular networks are typical in the closed/controlled areas mentioned above. These problems belong to the class of Vehicle Routing Problems with Pickups and Deliveries (VRPPD). For an overview on the VRPPD the reader is referred to [START_REF] Desaulniers | Vrp with pickup and delivery[END_REF]. For a survey on pickup and delivery problems the reader is referred to [START_REF] Parragh | A survey on pickup and delivery models part i: Transportation between customers and depot[END_REF][START_REF] Parragh | A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations, to appear[END_REF], where the problems are classified as Pickup and Delivery Vehicle Routing Problem (PDVRP), where pickup and delivery points are unpaired, the Pickup and Delivery Problem (PDP), where pickup and delivery points are paired, and the Dial-A-Ride Problem (DARP) which deals with passenger transportation between paired pickup and delivery points. The research on Pickup and Delivery problems is still very active (see [START_REF] Wu | An improved hybrid heuristic algorithm for pickup and delivery problem with three-dimensional loading constraints[END_REF], [START_REF] Rüther | A grouping genetic algorithm for multi depot pickup and delivery problems with time windows and heterogeneous vehicle fleets[END_REF]). The reader is referred to [START_REF] Berbeglia | Static pickup and delivery problems: a classification scheme and survey[END_REF][START_REF] Berbeglia | Dynamic pickup and delivery problems[END_REF] for surveys on static and dynamic Pickup and Delivery problems. [START_REF] Toth | Vehicle routing: problems, methods, and applications[END_REF] contains two chapters on the PDP, respectively the PDP for goods transportation [START_REF] Battarra | Chapter 6: pickup-and-delivery problems for goods transportation[END_REF]) and for people transportation [START_REF] Doerner | Chapter 7: Pickup-and-delivery problems for people transportation[END_REF]). For a review article on the DARP the reader is referred to Cordeau & Laporte (2007). For more recent surveys on dial-a-ride problems, see [START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF] and [START_REF] Molenbruch | Typology and literature review for dial-aride problems[END_REF]. For a high-level classification of dial-a-ride problems, the reader is referred to [START_REF] Gökay | A high-level category survey of dial-a-ride problems[END_REF].

Concerning problems defined on circles, the exisiting literature is limited. [START_REF] Gendreau | Heuristics for the traveling salesman problem with pickup and delivery[END_REF] developed a linear time exact algorithm for the Single-Vehicle Pickup and Delivery Problem defined on a cycle graph. [START_REF] Tzoreff | The vehicle routing problem with pickups and deliveries on some special graphs[END_REF] studied the Vehicle Routing Problem with Pickup and Delivery on some special graphs. They developed an optimal algorithm that runs in polynomial time for cycle graphs. [START_REF] Ilani | A fixed route dial-a-ride problem[END_REF] presented some optimal polynomial-time algorithms for two variants of the Fixed Route DARP with a circular route.

The first one considers a fleet of infinite capacity vehicles, while the second one considers the more general case of vehicles with heterogeneous capacities. Dial-a-Ride problems with autonomous vehicles have also been studied in [START_REF] Pimenta | Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles[END_REF] and [START_REF] Baïou | The stop number minimization problem: Complexity and polyhedral analysis[END_REF].

A number of related problems arise in the field of industrial automation. [START_REF] Atallah | Efficient solutions to some transportation problems with applications to minimizing robot arm travel[END_REF] were probably the first to study the problem of efficiently rearranging parts in the plane with a centrally placed gripper that can rotate. This problem is known as the Stacker Crane Problem (SCP), and they proposed a polynomial time algorithm for the SCP on a circle. [START_REF] Anily | The uncapacitated swapping problem on a line and on a circle[END_REF] studied a similar problem, the Uncapacitated Swapping Problem, on a line and on a circle, where the objective is to rearrange objects of different types on a circular graph using an uncapacitated vehicle. It can be seen as a generalization of the SCP. They proposed a polynomial time algorithm for both cases of a line and a circle.

The contributions of this paper can be summarized as follows. We introduce a new class of problems, the Pickup and Delivery Problems on Rings (PDP-R). We propose a classification scheme for these problems which resembles the classification used for scheduling problems.

In this class, we investigate a subclass where vehicles all travel in the same direction along the circle and the objective is to minimize the time at which the last vehicle returns to the depot. The peculiarity of these problems is that they do not involve any routing decision: the vehicles repeatedly turn around the circle until all pickup and delivery services have been carried out. The optimization comes from the efficient assignment of operations to vehicles and the scheduling of these operations. We determine the computational complexity for all variants of this subclass. We develop polynomial time algorithms for the problems that are polynomially solvable and proofs of NP-hardness for the others. In addition, for the latter, we provide efficient mathematical formulations that allow solving large-size instances quickly. Finally, we compare optimal solutions with those obtained using a straightforward greedy algorithm, that could be easily implemented by practitioners.

The rest of the paper is organized as follows. In Section 2, we introduce notation and some basic definitions, and we present the classification scheme. Section 3 is dedicated to problems with unitary requests and no release/due dates. Section 4 is devoted to problems with unitary requests and release/due dates. Section 5 deals with problems having non-unitary requests.

Computational experiments and the greedy algorithm are presented in Section 6. In Section 7, we summarize the results and present the perspectives of this work.

Problem description, classification and scope of the paper

In this section, we first provide a general description of the PDP-R. Then, we introduce a classification scheme. Finally, we present the variants addressed in this paper.

General problem description

The setting of the PDP-R is the following. The ring is represented by a directed graph whose set of nodes includes m stations numbered from 0 to m -1. To simplify further notation, station 0 is indifferently denoted as 0 or m. The set of arcs consists of 2 × m links (j, j + 1) and (j + 1, j) between consecutive stations (0 ≤ j ≤ m -1) (see Figure 1). Travel times δ j,j+1 and δ j+1,j are defined between two consecutive stations (j = 0, ..., m -1). These travel times are not necessarily symmetric. We consider a multiset R of n transportation requests. In the more general case, each request i ∈ R is defined by: a pickup station s i and a target station t i (s i , t i = 0, ..., m-1, s i = t i ), a quantity q i to be transported, a release date r i and a due date d i . The release date indicates the earliest time for the pickup operation, the due date is the latest time for the delivery. R is defined as a multiset instead of a set because it can contain identical requests.

The requests are served by a fleet of vehicles that can travel along the ring in either one or both directions. The vehicles are capacitated, so the load they can transport at the same time cannot exceed their capacity. Station 0 is the depot, i.e., a station where the vehicles are located before starting the service and have to return after having served all the requests. Without loss of generality, we assume that travel times are equal to distances, and therefore the words time and distance are interchangeable.

A classification scheme

One of the objectives of this work is to propose a classification scheme for PDP-R problems. It has been inspired by the three-field classification introduced in [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF] for scheduling problems . It is composed of three fields -α, β and γ -separated by a vertical bar. Each field may be a comma separated list of words that describes one or more features of the problem.

The α field contains information on the vehicles, separated by a comma:

• number of available vehicles: 1 or V (with V > 1);

• capacity of the vehicles:

1 or Q (with Q > 1) or Q v (if vehicles have different capacities).
The β field reports optional constraints, i.e., the field is empty in case of default settings.

The optional constraints, separated by a comma, are:

• sd (single direction): vehicles all follow the same direction, fixed from the beginning (clockwise or counterclockwise);

• md (mixed single-direction): each vehicle follows a single direction, fixed from the beginning, that can be either clockwise or counterclockwise;

• r i : pickups are subject to release dates;

• d i : deliveries are subject to due dates;

• u: demands are unitary.

The default settings are: bi-directional, meaning that vehicles travel in both directions; no release and due dates; demands corresponding to generic quantities q i . Finally, field γ indicates the objective function:

• C max : makespan, i.e., the completion time of the last request scheduled among all the vehicles;

• C i : total completion time, i.e., the sum of completion times over all vehicles;

• CLT : closing time, i.e., time at which the last vehicle comes back to the depot when all requests are served.

For example, the PDP-R with one vehicle of unit capacity rotating clockwise with no release dates and due dates whose objective is the minimization of the maximum completion time is denoted by 1, 1|sd, u|C max .

Scope of the paper and related definitions

In this paper, we present theoretical results and computational experiments concerning all the problem variants where the vehicles are allowed to move on the ring in a single direction (sd ) and the objective function is the minimization of the closing time (CLT ). Without loss of generality, we assume that all vehicles go clockwise.

Due to the circular layout, to go from j 1 to j 2 , vehicles must pass through all intermediate stations between j 1 and j 2 , that is: stations j 1 +1, . . . , j 2 -1 if j 1 < j 2 , stations j 1 +1, . . . , m-1, 0, . . . , j 2 -1 otherwise. This allows us to define the distance between two stations from distances between consecutive stations:

δ j 1 ,j 2 =      j 2 -1 k=j 1 δ k,k+1 if j 1 < j 2 m-1 k=j 1 δ k,k+1 + j 2 -1 k=0 δ k,k+1 otherwise (1)
Note that distances δ j 1 ,j 2 satisfy the triangle inequality. We call L the length of a complete tour, starting from the depot and returning back to the depot.

To ease the readability in the remainder of the paper, we introduce a few definitions.

Definition 1. We say that a request i ∈ R covers a segment [j, j + 1] if stations j and j + 1 are within stations s i and t i when going clockwise. Equivalently, it means that a vehicle needs to traverse arc (j, j + 1) in order to serve i.

Definition 2. We say that a request i ∈ R covers a station j if it covers both segments [j -1, j] and [j, j + 1].

In particular, a request i covers the depot when 0 < t i < s i .

Definition 3. We say that two requests i 1 , i 2 ∈ R overlap if at least one segment [j, j + 1] of the ring is covered by both requests (j = 0, ..., m -1).

Definition 4. If two requests do not overlap they are said to be compatible. Otherwise, they are said to be in conflict (or conflicting).

Figure 2 shows an example with four stations and three requests identified by their pair (s i , t i ): (3, 1), (1, 2), (1, 0). Requests (3, 1) and (1, 2) are compatible, while requests {(1, 2), (1, 0)} or {(1, 0), (3, 1)} are in conflict (requests overlap in both pairs). Definition 5. A tour is a complete rotation of a vehicle around the ring, starting from station 0, passing through all stations j (j = 1, ..., m -1) and getting back to 0. Definition 6. A schedule is an assignment of the requests to the vehicles that specifies, for each vehicle, the tour in which the requests are executed. A schedule is also a solution for the problem.

Definition 7. A request is said active at a given time when the service of this request is started but not finished, i.e., the request has been picked up at station s i but not yet delivered to station t i .

Problems with unitary requests and no release/due dates

In this section, we first prove that problem 1, 1|sd, u|CLT is polynomially solvable. In this case, the fleet is limited to a single vehicle of unit capacity and requests have unitary demands. No release dates nor due dates are considered.

We then investigate other classes of problems with unitary demands and no release/due dates. Remember that, as all other problems addressed in this paper, we consider that vehicles are subject to the sd constraint (single-direction) and that the objective is CLT (closing time). We show that these problems are NP-hard (Section 3.2) and propose a mixed integer linear programming formulation (Section 3.3).

Problem 1, 1|sd, u|CLT

A single vehicle of capacity one has to serve the multiset R of n unitary requests. It is constrained to travel clockwise. The objective is to serve all requests and return to the depot as early as possible. Equivalently, it consists in minimizing the number of tours traveled by the vehicle to serve all requests.

We propose a polynomial-time algorithm that solves the problem. The basic idea is to construct a graph whose vertices represent the stations and whose arcs represent the requests, and then find an Eulerian tour in this graph.

We introduce the following notation. T OP T is the optimal number of tours. We denote z(R) the optimal closing time. We express z as a function of R because we introduce dummy requests in the algorithm, as explained later. Note that z(R) = L × T OP T . Requests are defined by their origin and their destination; we represent them by pair (s i , t i ). Then,

R = ((s i , t i ) : 1 ≤ i ≤ n).
We define for all stations j (j = 0, ..., m -1):

• N (j, j + 1) : the number of requests that cover segment [j, j + 1];

• N * (j) : the number of requests that cover station j;

• N sup = max(N (j, j + 1) : 0 ≤ j ≤ m -1). N sup is the maximum number of pairwise overlapping requests.

Note that N * (j) ≤ N (j, j + 1) and, thus, also, N * (j) ≤ N sup for j = 0, ..., m -1.

The pseudo-code of the algorithm for solving problem 1, 1|sd, u|CLT is provided in Algorithm 1.

Algorithm 1 Solution algorithm for problem 1, 1|sd, u|CLT

1: for all j ∈ {0, . . . , m -1} do 2:

compute N (j, j + 1) and N * (j)

3: end for 4: compute N sup 5: R (1) ← R

6: for all j ∈ {0, . . . , m -1} do 7:

add N sup -N (j, j + 1) copies of (j, j + 1) to R (1) 8: end for

9: R (2) ← R (1) 10: if N * (0) = N sup then 11:
for all j ∈ {0, . . . , m -1} do 12:

add (j, j + 1) to R (2) 13:

end for In Lines 1 to 4, we first compute values N (j, j + 1) and N * (j) for j = 0, . . . , m -1. Then, we compute N sup .

Lines 5 to 8 complete the multiset of requests so that the number of requests covering every segment [j, j + 1] is exactly N sup . To this end, artifical requests (j, j + 1) are added.

We denote R (1) the new multiset. We will see in Lemma 2 that adding these requests does not change the optimal solution value: z(R (1) ) = z(R).

If the number of requests covering station 0 is equal to N sup , we modify again the request multiset in Lines 9 to 14. The new multiset is called R (2) . In addition to R (1) , it contains a request (j, j + 1) for every segment [j, j + 1]. Again, we will see in Lemma 4 that z(R (2) ) = z(R (1) ).

The next step consists in introducing a directed multigraph G (Line 15). In this graph, the vertex set is the set of stations. An arc is added between two stations j 1 and j 2 for each request (j 1 , j 2 ) in the extended multiset of requests. A cost δ j 1 ,j 2 is defined for each arc (j 1 , j 2 ). We will prove in Lemma 5 that graph G is semi-Eulerian.

Semi-Eulerian graphs can be exhaustively decomposed into a set of Eulerian circuits with disjoint vertices (see [START_REF] Wahlström | Euler digraphs[END_REF], in which these kinds of graphs are called balanced ).

Procedure decomposeEulerian(G) at Line 16 executes this decomposition. It results in a set of P circuits C 1 to C P . In addition, it computes station n inf p of minimal index in every circuit

C p . Without loss of generality, we assume n inf 1 < • • • < n inf P . If P = 1, that is, if graph G is
Eulerian, the procedure returns the schedule defined by circuit C 1 (Lines 17 and 25). Note that the schedule corresponds to the sequence in which requests are served which, in turn, is the sequence in which the corresponding arcs are traversed in the Eulerian graph. Otherwise, in Lines 17 to 24, the algorithm connects the P circuits using arcs (n inf p , n inf p+1 ) to obtain a single circuit Λ. Then, it returns the schedule obtained from this circuit (Line 25). We prove in Theorem 1 that in both cases the schedules are optimal.

We now prove the various lemmas that are needed to prove the main result in Theorem Proof. Since we consider a vehicle of capacity one, conflicting requests must be served in different tours. The N sup requests that cover the same segment must then be active on N sup different tours. It follows that the number of tour in any feasible solution is at least

N sup . Lemma 2. Multiset R (1) is such that z(R (1) ) = z(R).
Proof. We call Λ * (R) the optimal schedule when the request set is R. From Lemma 1, we know that the vehicle performs at least N sup tours in Λ * (R). Furthermore, we know that every segment [j, j + 1] is covered exactly N (j, j + 1) times in request multiset R. It means that the vehicle is not active on at least N sup -N (j, j + 1) tours in schedule Λ * (R) when it traverses segment [j, j + 1]. A feasible schedule for request multiset R (1) can be constructed from Λ * (R) by serving the new requests (j, j +1) when the vehicle is not active. This schedule has the same cost than Λ * (R), that is, z(R). It follows that z(R (1) ) ≤ z(R). Trivially, as

R ⊆ R (1) , we have that z(R (1) ) ≥ z(R). Thus, z(R (1) ) = z(R). Lemma 3. If N * (0) = N sup , T OP T ≥ N sup + 1.
Proof. If N * (0) = N sup , N sup requests cover the depot and have to be active at the depot on different tours. Given a feasible solution, the first active request at the depot cannot be finished before tour number 2, the second before tour number 3, and, by a simple induction, active request number N sup before tour number 1) . Otherwise, we can follow exactly the same proof as in Lemma 2. With request multiset R (2) , we know, thanks to Lemma 3, that the vehicle performs at least N sup + 1 tours. So, compared to R (1) , an additional request can be added for each segment [j, j + 1] without increasing the solution cost.

N sup + 1. It implies T OP T ≥ N sup + 1. Lemma 4. Multisets R (1) and R (2) are such that z(R (2) ) = z(R (1) ). Proof. If N * (0) < N sup , R (2) = R (
Lemma 5. Graph G is semi-Eulerian.

Proof. For each node j of graph G, let d + G (j) be the number of outgoing arcs and d - G (j) be the number of ingoing arcs. To show that the graph is semi-Eulerian, we prove d + G (j) = d - G (j) for j = 0, . . . , m -1. We know that every segment [j, j + 1] is covered by the same number 2) contains at least once each request (j, j +1) for j = 0, . . . , m-1.

N of requests from R (2) (N = N sup or N sup + 1, depending on condition N * (0) < N sup ). Let us consider j ∈ {0, . . . , m -1}, d + G (j) + N * (j) = N = d - G (j) + N * (j), which proves the lemma. Lemma 6. If N * (0) = N sup , graph G is Eulerian. Proof. If N * (0) = N sup , R (
These requests create a directed circuit in G containing all the nodes. Graph G is then strongly connected. As Lemma 5 states that G is semi-Eulerian, then G is Eulerian.

Theorem 1. Schedule Λ is optimal. Three cases can be distinguished:

1. If N * (0) = N sup , T OP T = N sup + 1 2. If N * (0) < N sup and graph G is Eulerian (algorithm decomposeEulerian(G) returns a single circuit), T OP T = N sup 3. If N * (0) < N sup and graph G is not Eulerian (algorithm decomposeEulerian(G) returns several circuits), T OP T = N sup + 1
Proof. We prove the three cases separately:

1. If N * (0) = N sup , G is Eulerian. Every segment [j, j + 1] is covered exactly N sup + 1 times in R (2)
, so the sum of request lengths is (N sup + 1) × L. Circuit Λ contains an arc for each request in R (2) . Its total length is also (N sup + 1) × L. Thus, T OP T ≤ N sup + 1.

From Lemma 1, we have T OP T ≥ N sup + 1. This demonstrates that T OP T = N sup + 1 and that schedule Λ is optimal.

2. If N * (0) < N sup and graph G is Eulerian, we can apply exactly the same proof, except that every segment is now covered N sup times. We obtain T OP T = N sup and schedule Λ is optimal.

3. If N * (0) < N sup and graph G is not Eulerian, we first show that T OP T ≥ N sup + 1.

Assume T OP T ≤ N sup . From Lemma 1 it means T OP T = N sup , that is, the optimal schedule exactly covers the arcs in G. However, this contradicts the fact that G is not connected. Thus, T OP T ≥ N sup +1. We now show that schedule Λ is optimal. The total length of this schedule is

N sup × L + 1≤p≤P -1 δ n inf p ,n inf p+1 + δ n inf P ,n inf 1 = N sup × L + L = (N sup + 1) × L.
Thus, the number of tours is N sup + 1 and it is optimal. Using Hierholzer's algorithm , procedure decomposeEulerian(G) can be implemented with a complexity O(N sup × m) (see, for example, Jungnickel ( 2013)). The different loops of the algorithm (to compute values N (j, j +1) and N * (j), to construct R (1) and R (2) , to obtain Λ) all have either the same complexity or a lower complexity. The overall complexity of the algorithm is thus O(N sup × m). Seeing that N sup ≤ n, it proves that problem 1, 1|sd, u|CLT is polyniomally solvable.

We illustrate the algorithm with two simple examples.

Example 1

Let us consider a ring with m = 5 equidistant stations (numbered from 0 to 4) and four requests: R = {(4, 2), (2, 3), (1, 3), (3, 1)} (see Figure 3). On this example: 2, 3), (3, 4), (4, 0)} (see Figure 4) Based on multiset R (2) , we obtain graph G represented on Figure 5. Applying Hierholzer's algorithm provides a single optimal circuit (the graph is Eulerian), e.g.:

• N (0, 1) = N (1, 2) = N (2, 3) = N (4, 0) = 2, N (3, 4) = 1, N sup = 2 and N * (0) = 2 • R (1) = R ∪ {(3, 4)} (see Figure 4) • R (2) = R (1) ∪ {(0, 1), (1, 2), (
0 → 1 → 2 → 3 → 1 → 3 → 4 → 2 → 3 → 4 → 0.
This circuit gives the schedule (2, 3), (3, 1), (1, 3), (4, 2) which is completed in three tours on the ring. We consider the same ring and a new request set: R = {(0, 4), (4, 0)(1, 3), (3, 1)} (see Figure 6):

• N (0, 1) = N (1, 2) = N (2, 3) = N (3, 4) = N (4, 0) = 2, N sup = 2 and N * (0) = 1 • no new requests are added: R (2) = R (1) = R
Graph G is depicted on Figure A.13. Applying Hierholzer's algorithm provides two Eulerian circuits C 1 = 0 → 4 → 0 and C 2 = 1 → 3 → 1. These two circuits are reconnected with arcs (0, 1) and (1, 0) to form Λ = 0 → 4 → 0 → 1 → 3 → 1 → 0. The vehicle performs 3 tours and the schedule is (0, 4), (4, 0), (1, 3), (3, 1).

= V, 1 or 1, Q or V, Q or V, Q v
In this section we demonstrate that different generalizations of problem 1, 1|sd, u|CLT are NP-hard.

We first show that the problem with multiple vehicles of capacity 1 is NP-hard (problem V, 1|sd, u|CLT ). Because of the length of the proof, the proof is omitted here and can be found in the Appendix. We then show that this problem is equivalent to the problem faced when the fleet is composed of a single vehicle of non-unitary capacity (problem 1, Q|sd, u|CLT ), which demonstrates that 1, Q|sd, u|CLT is also NP-hard. These results show that V, Q|sd, u|CLT and V, Q v |sd, u|CLT , that generalize the two others, are NP-hard.

Theorem 2. Problem V, 1|sd, u|CLT is NP-hard.

Proof. See proof in Appendix.

Theorem 3. Problem 1, Q|sd, u|CLT is NP-hard.

Proof. We consider an instance of 1, Q|sd, u|CLT and the equivalent instance of V, 1|sd, u|CLT where the vehicle of capacity Q is replaced by V vehicles of capacity 1, with V = Q. To prove that 1, Q|sd, u|CLT is NP-hard, we show that any feasible solution Λ 1,Q of the former problem can be transformed to a same-cost feasible solution Λ V,1 of the latter, and vice-versa.

Considering a feasible schedule Λ 1,Q , we assign a number v i between 1 and Q to all requests i ∈ R, so that two requests active at the same time have different numbers. This numbering always exists as, when a request starts, at most Q -1 other requests are active and so, a number between 1 and Q is available. Then, we build schedule Λ V,1 by starting all requests as in Λ 1,Q and by assigning every request to vehicle number v i . The schedule is feasible because two requests with the same number are not active at the same time and because v i ≤ V for all requests. Both schedules Λ 1,Q and Λ V,1 are feasible for their respective problem and have the same closing time. Starting with a feasible schedule Λ V,1 , the reverse transformation can be applied exactly the same, with the same conclusion. The two problems having the same set of feasible solutions with equivalent costs, they have the same complexity.

It permits to conclude that problem 1, Q|sd, u|CLT is NP-hard.

An integer linear programming formulation for problem V, Q|sd, u|CLT

As problem V, Q|sd, u|CLT is NP-hard, we propose a mathematical formulation that could allow solving it. The formulation makes use of the following notation, in addition to the one introduced in previous sections.

• K: maximum tour number at which a request should be started

• R[j, j + 1]: set of requests in R that cover segment [j, j + 1]. • c ik : cost of inserting request i ∈ R if it is started in tour number k c ik =      k if s i < t i k + 1 otherwise
To calculate K, finding a feasible solution is enough. Requests can be ordered in the increasing order of their pickup station, and started in consecutive tours. Then, the last request would start at tour n. We set K = n.

We introduce the following decision variables:

x ik =      1 if request i is started in tour k 0 otherwise (1 ≤ i ≤ n, 1 ≤ k ≤ K) CLT = closing time.
Note that that the closing time corresponds to the maximum number of tours traversed by each vehicle multiplied by the length of the ring L. As L is a constant, then minimizing CLT corresponds to minimizing the the maximum number of tours traversed by each vehicle.

Thus, in the following we refer to CLT as the latter number.

The mixed integer linear program is then:

min CLT (2) s.t.: {i∈R[j,j+1],s i ≤j} x ik + {i∈R[j,j+1],s i ≥j+1} x ik-1 ≤ V × Q (0 ≤ j ≤ m -1, 1 ≤ k ≤ K) (3) k∈K x ik = 1 (1 ≤ i ≤ n) (4) CLT ≥ k∈K c ik x ik (1 ≤ i ≤ n) (5) x ik ∈ {0, 1} (1 ≤ i ≤ n, 1 ≤ k ≤ K) (6) CLT ≥ 0 (7)
The objective function minimizes the closing time, expressed in number of tours. Constraints (3) make sure that the number of active requests never exceeds the total capacity of the V vehicles. For each segment [j, j + 1] and each tour k, this number is evaluated by counting the active requests that started in the tour before station j and those that started in the preceding tour after station j + 1. Constraints (4) make sure that every request is served. Constraints (5) compute the maximal tour number CLT . Constraints ( 6)-( 7) define decision variables.

Problems with unitary requests and release/due dates

In this section, we analyze the class of problems where each request i ∈ R is unitary and is subject to a release date r i and a due date d i . Note that in the context of the single-direction (sd) constraint, release dates and due dates can be expressed as the smallest and the highest tour number in which the request can be served.

4.1. Problem 1, 1|sd, u, r i , d i |CLT
This section is devoted to the problem where a single vehicle of capacity one has to serve the requests. The problem is the same as in Section 3.1 with the addition of release dates and due dates. We show that, when having release dates and due dates, the problems becomes NP-hard. We proceed by reduction from a variant of the list coloring problem, called (γ, µ)-coloring problem, introduced Bonomo et al. ( 2009) and shown to be NP-hard.

Definition 8. Given a graph G = (V, E) and functions γ, µ :

V → N such that γ(v) ≤ µ(v)
for every v ∈ V, we say that G is (γ, µ)-colorable if there exists a function f :

V → N of G such that γ(v) ≤ f (v) ≤ µ(v) for every v ∈ V, and f (v) = f (v ) for every (v, v ) ∈ E.
In [START_REF] Bonomo | Exploring the complexity boundary between coloring and list-coloring[END_REF] it is shown that this problem generalizes the graph coloring problem and is NP-hard, also in the case where the underlying graph is an interval graph.

Theorem 4. Problem 1, 1|sd, u, r i , d i |CLT is NP-hard.
Proof. The main argument in the proof is that the constraints implied by release dates and due dates can be equivalently expressed as constraints on the lowest and largest tour number on which a request can be started. The starting tour of a request can then be interpreted as a color, bounded by these two limits. Given that fact, we first show how to transform an instance of the (γ, µ)-coloring problem on an interval graph into an instance of 1, 1|sd, u, r i , d i |CLT .

We for each v ∈ V. Instance I c consists in deciding if there exists a coloring function f :

V → N such that γ(v) ≤ f (v) ≤ µ(v) for each v ∈ V and f (v) = f (v ) for (v, v ) ∈ E.
We build an instance I s of 1, 1|sd, u, r i , d i |CLT as follows. Let D denote the set of interval extremities: D = {a i , b i : i = 1, ..., n}. We sort D in increasing order and introduce a station in the ring for every element in D, in this order. We complete the ring with station 0. This way, the number m of stations is at most two times the number n of intervals plus the depot (m ≤ 2n + 1). We define unitary distances between successive stations, which gives a tour length L = |D| + 1. We introduce a request in R for every interval in A. Given interval (a i , b i ), request i is defined as follows: s i is the station obtained from extremity a i , t i is the station obtained from extremity b i , r i is set to L × γ(v i ) and

d i = L × (µ(v i ) + 1)). Basically,
this means that request i has to be active between the beginning of tour number γ(v i ) and the end of tour number µ(v i ). We note that no request covers the depot, so two requests will be scheduled in the same tour if and only if they do not overlap. Note also that this construction is polynomial.

We claim that H is (γ, µ) colorable if and only if I s admits a feasible schedule. A feasible schedule for I s is a function f : R → N that assigns each request i ∈ R to a tour (that is the tour in which the request is served) so that requests do not overlap and that the tour number of request i lies between the lowest possible tour number and highest possible tour number given by the release and due dates, that is, γ(v i ) and µ(v i ). More formally, function f has to be such that:

• f (i 1 ) = f (i 2 ) =⇒ i 1 and i 2 do not overlap ∀i 1 , i 2 ∈ R • γ(v i ) ≤ f (i) ≤ µ(v i ) ∀i ∈ R Assume first that H is (γ, µ)-colorable. This means that a function g : V → N is a coloring for H. Let f : R → N be a function such that f (i) = g(v i ), v i ∈ V .
It is easy to see that f is a feasible schedule for I s .

On the other hand, assume that I s admits a feasible schedule f . Let g : V → R be a

function such that g(v i ) = f (i), (a i , b i ) ∈ A.
It is easy to see that g is a coloring function for H. In fact, g(v i 1 ) = g(v i 2 ) means that requests i 1 and i 2 do not overlap, i.e., edge

(v i 1 , v i 2 ) / ∈ E.
In addition, from the definition of r i and

d i , γ(v i ) ≤ g(v i ) ≤ µ(v i ).
It shows that solving the (γ, µ)-coloring problem on an interval graph amounts to finding a feasible solution to an instance of problem 1, 1|sd, u, r i , d i |CLT . This proves that problem 1, 1|sd, u, r i , d i |CLT is NP-hard.

Given the result of Theorem 4, it follows that all problems with release and due dates, monodirectional and where the objective function is the minimization of CLT are NP-Hard.

In the following section, we present a mathematical formulation for problem V, Q|sd, u, r i , d i |CLT which can be used to solve also problems α|sd, u, r i , d i |CLT , with α = 1, 1 or 1, Q or V, 1, and that could be easily adapted to solve problems with heterogeneous fleet of vehicles.

4.2. Integer linear programming formulation for problem V, Q|sd, u, r i , d i |CLT

In addition to notation defined in previous sections, we define K i as the set of tour numbers in which request i can be started

K i = {k ∈ N : (k -1)L + δ 0,s i ≥ r i and (k -1)L + δ 0,s i + δ s i ,t i ≤ d i }
Also, we tighten K, that is, the tour number upper bound for the last started request, by taking account of due dates:

K = max 1≤i≤n ( d i L )
Decision variables are the same as in model ( 2)-( 7). The formulation is given by ( 2)-( 3), ( 5)-( 7) and the following modification of constraints (4):

k∈K i x ik = 1 (1 ≤ i ≤ n) (8)
Constraints ( 8) make sure that every request is served and that release and due dates are respected.

Problems with non-unitary requests

In this section, we consider the extension of previous problems to non-unitary requests.

Note that in this context, the case Q = 1 does not make sense. Remembering that 1, Q|sd, u|CLT is NP-hard (see Section 3.2), we can conclude that all problems investigated in this section are NP-hard.

Alternative complexity proof for problem 1, Q|sd|CLT

Though theorems 2 and 3 show that problem 1, Q|sd|CLT is NP-hard, the proof appears overly complex when requests are not necessarily unitary. In this section, we propose a simpler proof based on a reduction from the Bin Packing Problem (BPP).

The BPP is defined as follows. We are given a finite set O of n objects and K bins. Let Let us consider an instance I B for the BPP, with a set O of objects and K bins. We construct an instance I S for 1, Q|sd|CLT as follows. We define a ring with two stations S = {0, 1}. For each object o ∈ O, we introduce a request i in R, with s i = 0, t i = 1 and

q i = w o .
The capacity Q of the vehicle is set to bin capacity W . We finally set C = K. In instance I S , all requests overlap, hence, a schedule Λ is feasible if and only if:

• in each tour, the sum of the demands of the requests started in the tour is not greater than Q,

• the schedule contains at most C tours.

We show that I B is feasible if and only if I S is. Assume first I B feasible. We build a schedule Λ for I S by executing the requests of the K bins in K separate tours. Conversely, let us assume I S feasible. We consider a feasible schedule Λ. We build a solution for I B by assigning all requests starting in the same tour to the same bin. This shows that solving the BPP can be reduced to solving the decision version of 1, Q|sd|CLT , with a polynomial reduction, which proves that 1, Q|sd|CLT is NP-hard.

An integer linear programming model

In this section, we present a mathematical formulation for problem V, Q|sd, r i , d i |CLT .

This formulation can also be used to solve problems 1, 1|sd,

r i , d i |CLT , 1, Q|sd, r i , d i |CLT and V, 1|sd, r i , d i |CLT .
This formulation extends the formulations presented in Section 3.3 and 4.2. We use the notation introduced in these sections. Tour assignment variables takes a third index to take into account the vehicle that serves a request:

x ikv =      1 if request i is started in tour k by vehicle v 0 otherwise
The mixed integer linear program is then:

min CLT (9) s.t.: {i∈R[j,j+1],s i ≤j} q i x ikv + {i∈R[j,j+1],s i ≥j+1} q i x ik-1v ≤ Q (0 ≤ j ≤ m -1, 1 ≤ k ≤ K, 1 ≤ v ≤ V ) (10) v∈{1,...,V } k∈K i x ikv = 1 (1 ≤ i ≤ n) (11) CLT ≥ v∈{1,...,V } k∈K i c ik x ikv (1 ≤ i ≤ n) (12) x ikv ∈ {0, 1} (1 ≤ i ≤ n, 1 ≤ k ≤ K, 1 ≤ v ≤ V ) (13) CLT ≥ 0 (14)
The objective function minimizes the closing time, expressed as number of tours, over all vehicles. Constraints (10) ensure that vehicle capacities are satisfied. They disaggregate constraints (3) for each vehicle. Constraints (11) make sure that every requests is served, at an acceptable time. Constraints (12) compute CLT . Constraints ( 13)-( 14) define variables domain.

We propose the following symmetry breaking constraints to strengthen formulation ( 9)-( 14). The first set of constraints ranks vehicles according to the number of satisfied requests:

the smallest the vehicle index, the largest the number of satisfied requests

n i=1 k∈K i x ikv ≥ n i=1 k∈K i x ikv+1 (1 ≤ v ≤ V -1). ( 15
)
The second set imposes that the first requests are served by the first vehicles: the i first requests have to be assigned to vehicles in set {1, . . . , i}: u∈{1,...,j} v∈{1,...,j} k∈K i

x ukv = j (1 ≤ j ≤ min(V, n)). (16)
Note that ( 15) and ( 16) cannot be used simultaneously.

We evaluated computationally the impact of these constraints and noticed a slight improvement, in terms of computing times, over the formulation without symmetry breaking constraints. In particular, the most effective constraints are the ones given by inequalities ( 16). Thus, the computational results presented in the following include these constraints.

Computational tests

We now present the set of experiments we made in order to evaluate the efficacy of the formulations presented above. The formulations are solved through CPLEX 12.9.0 on a computer equipped with an Intel Core i7-9700 processor and 32GB of RAM. For all instances a time limit of 30 minutes was set. As shown in the results, all instances were solved (either to optimality or by proving infeasibility) within this time limit.

Instance sets

As far as we know, the problems investigated in this paper are new and no benchmark instances exist. We propose to generate random instances as follows. All random numbers are chosen from uniform distributions.

We consider a ring with m = 10 stations. The number of requests is chosen in the set {20, 40, 80, 160}, and we generated 5 instances for each number of requests. The pickup station of a request is randomly taken in {0, . . . , m -1} and the target station in {0, . . . , m -1} \ {s i }. For each instance, distances between consecutive stations are randomly drawn in [1,10]. This gives a total of 20 combinations of the parameters mentioned above.

Every instance is replicated several times with different fleet of vehicles and demand values. We consider the following values for V and 2QV otherwise. We denote as C this value. Then:

Q: V ∈ {1, 2, 3}, Q ∈ {1,
• Release dates are randomly generated in intervals [0, 1.5C] (tight) or [0, 2C] (wide)

• Due dates are generated in intervals [r i + L, r i + L + C] (tight) or [r i + L, r i + L + 1.5C] (wide)
For the 20 × 24 combinations above, this gives four alternatives for release and due dates: t-t, t-w, w-t, w-w, where t and w stand for tight and wide, respectively.

For each instance constructed this way, two variants are finally considered: the original instance and the instance where due dates are relaxed. The reason behind the latter is to investigate the impact of due dates on the problem tractability. Also, it might correspond to a realistic situation where, for example, goods have to be moved between stations to prepare the planning for the next day. In this case, goods are ready at a given time at the pickup station (the release date) but there is no restriction on the time at which they should be available at the delivery station.

To calculate value K in the case with release dates and no due date, it suffices to notice that at the beginning of tour 2C

L + 1 all requests are ready to be processed (release dates are passed). Then, the reasoning of Section 3.3 can be applied to set K = 2C L + n.

Greedy algorithm

In order to evaluate the benefits of solving the problems to optimality, we designed the following simple greedy algorithm that is easy to implement and that would be easy to understand for practitioners. We then compared the solutions provided by the greedy algorithm with the optimal solutions. The greedy algorithm works as follows.

When a vehicle reaches a station that is the pickup station of at least one request and this request can be started, it is started. If several requests can be started at the same time, ties are broken by giving priority to requests according to the following criteria, taken hierarchically:

• earliest due date first (due date is considered infinite if no due date is defined);

• largest demand first;

• longest distance to reach the delivery node first.

Note that, in case of instances with unit demands and no release/due dates, only the third criterion is used.

Computational results for V, Q|sd, u|CLT

In Table 1 we report results for problem V, Q|sd, u|CLT . All results are averaged over the We can observe that the formulation in Section 3.3 is extremely effective. In fact, the computational time is always smaller than 40 seconds. The computational time increases with the number of requests, as expected, and decreases with the vehicle capacity. Also, the solution value decreases as the capacity increases, as expected. The performance of the greedy algorithm highly depends on vehicle capacity: the larger the capacity, the worse is the performance. This might be due to the fact that, when increasing the capacity, the chances of making a bad choice of assignment of requests to vehicles increases. On the other side, we see that the gap decreases with solution values. This was expected: in fact, the relative impact of bad choices made by the greedy algorithm decreases.

6.4. Computational results for V, Q|sd, u, r i , d i |CLT

Tables 2 and3 report results for problem V, Q|sd, u, r i , d i |CLT . The meaning of the column headings is the same as above. "-" indicates that either the instance is infeasible or the greedy algorithm failed in finding a solution. In Table 2, three cases are considered for release and due dates: tight-tight (t-t), tight-wide (t-w) and tight release dates without due dates (t). The three remaining cases are reported in Table 3. The main observation from these tables is that the model remains extremely efficient, even when release dates and due dates are considered. Even more, solution times are much smaller than those reported in Table 1, with almost all instances solved in less than one second. This might be due to the fact that release and due dates reduce the solution space.

Still, the instances are not trivial to solve, as witnessed by the results related to the greedy algorithm. Indeed, while almost all instances admit feasible solutions, the greedy algorithm fails in finding the optimal solution for most of them. In addition, the greedy algorithm has difficulties even in finding a feasible solution, especially for the case in which release and due dates are tight. This shows that a solution approach smarter than the simple greedy algorithm can provide large advantages.

6.5. Computational results for V, Q|sd, r i , d i |CLT

Tables 5 and6 report results for problem V, Q|sd, r i , d i |CLT . Contrary to previous results, demands are not forced to be unitary. optimal solutions are the ones obtained from solving the formulation in Section 5.2. Columns are the same as in the former section. In addition, the case with no release dates and due dates is considered in table 4. These tables confirm the good-quality of the formulation but also exhibit larger computing times. Largest instances regularly require a few minutes for getting the optimal solution, with or without release dates and due dates. The reason is related to the larger number of variables due to the disaggregated capacity constraints. These instances are also specially difficult for the greedy algorithm. In fact, it fails in finding a feasible solution for most of the instances and shows larger gaps compared to instances with unitary demands, when feasible solution are found. The additional complexity implied by the packing of non-unitary requests makes the greedy algorithm not effective.

n V Q CPU(s)

Conclusions and perspectives

In this paper we introduced a new class of Pickup and Delivery problems where the stations are located on rings. We first proposed a classification scheme. Then, we investigated the complexity of the variants in which the vehicles are allowed to move in a single direction and the objective is the minimization of the maximum number of tours. We described a polynomial time algorithm for some variants and we proved the NP-hardness of the remaining variants.

For the NP-hard variants, we proposed MILP formulations and computational tests to evaluate these formulations. Experiments on a large number of instance show the impressive efficiency of our formulations. All instances, with up to 160 requests, could be solved in a few minutes. Comparisons with a simple and practically relevant greedy algorithm also confirmed the intrinsic difficulty of the problems/instances and the usefulness of applying exact solution schemes. (1, 1)

(2, 1) Clause-related arcs are defined in

(3, 1) c 2 (1, 1, 1) (1, 1, 0) (2, 1, 1) (2, 1, 0) (3, 1, 1) (3, 1, 0) (1, 1, 1) * (1, 1, 0) * (2, 1, 1) * (2, 1, 0) * (3, 1, 1) * (3, 1, 0) * Q (1, 1) * (2 ,
= (z 1 ∨ ¬z 2 ∨ z 3 ) are lit(c 1 , 1) = (1, 1, 1), lit(c 1 , 2) = (2, 1, 0),
and lit(c 1 , 3) = (3, 1, 1). Consequently, the three c-variable arcs for the clause are arcs (c 1 , (1, 1, 1)), (c 1 , (2, 1, 0)) and (c 1 , (3, 1, 1)). Note that first middle nodes have exactly one in-going clause-related arc each. Note also that the notation introduced in the table does not always enable to distinguish between parallel arcs (c-default arcs, good bottleneck arcs, bad bottleneck arcs are not distinguished). We keep this notation to ease readability. Clauserelated arcs represent exactly 3S arcs between every successive layers except between layers 3 and 4 where no clause-related arcs are introduced (remembering that 3S = 2U ). and c 2 , and considering assignment z = {1, 1, 1}. The partition is as follows:

Layers Category

Symbol Length Number (1, 2) c-id arcs (s, c k ) Id (k ∈ {1, . . . , S}) 5 S first c-def arcs (s, c k ) Def (k ∈ {1, . . . , S}) 1 S second c-def arcs (s, c k ) Def (k ∈ {1, . . . , S}) 1 S (2, 3) first c-variable arcs (c k , (j, u, )) (k ∈ {1, . . . , S}, (j, u, ) = lit(c k , 1)) 1 S second c-variable arcs (c k , (j, u, )) (k ∈ {1, . . . , S}, (j, u, ) = lit(c k , 2
• We first generate a path for every occurrence u of literal z j and a path for every occurrence u of literal ¬z j in the clauses, for a total of 2 × U paths:

-(j,u)-identifier path: s These paths cover all variable-related arcs, except middle-id arcs ((j, u, j ), (j, u, j ) * ) Id and middle-def arcs ((j, u, ¬ j ), (j, u, ¬ j ) * ) Def . They all have a length equal to 11. • We then generate three paths for every clause c k , for a total of 3 × S paths. A clause involves three literals that can be matched to a variable z j and an occurrence u. Each path visits, in sequence, nodes s, c k , (j, u, ), (j, u, ) * , Q and p, where = 1 if the literal is z j and = 0 if the literal is ¬z j (see definition of clause-variables arcs). The arcs traversed depend on the type of path as follows.

correspondence with the vertices in X as follows. We first sort the nodes in X in a topological order (we can do that because G is a directed acyclic graph) and reverse this order. Node p is then the first node and node s the last. We then associate one station with each node following this order, thus having station 1 representing node p and station |X| representing node s. We denote stat(x) the station associated with node x ∈ X. We define unitary distances between successive stations, which gives a tour length L = |X| + 1. For every arc (x, y) ∈ E, we introduce a request in R defined by s i = stat(x), t i = stat(y). This request is denoted r(x, y). Since we considered nodes in a reversed topological order, all requests cover the depot. We complete R by adding K requests (0, stat(s)) and K requests (stat(p), 0). This way, |R| = KT + 2K. We finally set V = K and CLT = L × (T + 1). Note that this construction is polynomial.

We illustrate this construction on a simple example. We consider the graph G of figure A.13. Assume first that I EP P is positive. This means that set E can be partitioned into K arc-disjoint paths P k , each of length T . We build a feasible schedule for I in the following way. Every vehicle k (1 ≤ k ≤ V ) starts from the depot by serving request (0, stat(s)). Then, it serves all requests r(x, y) for (x, y) ∈ P k , in the order defined by this path. It finally serves request (stat(p), 0). This sequence starts from the depot, finishes at the depot and is such that the ending station of every request is the starting station of the next request. It thus defines a feasible schedule without any intermediate empty traveling between requests. The schedule traverses exactly T times the depot, once for every request r(x, y) with (x, y) ∈ P k .

So, the number of tours is T + 1. All KT + 2K requests are covered by the V vehicles, which proves that I is positive.

Assume now that I is feasible. This means that there exists a schedule with the K(T + 2) requests assigned to the K vehicles, each vehicle making T + 1 tours. We first show that vehicles never travel empty in this schedule.

Segment [0, 1] of the ring is covered by the KT requests r(x, y) with (x, y) ∈ E and K requests (0, stat(s)), that is, K(T + 1) requests. We show that all other segments are covered by the same number of requests. We can easily check that at every station stat(x) exactly K requests stop, either because d -(x) = K or because x = s and the K requests (0, stat(s))

stop (remember that d -(s) = 0 so no other request stops). Similarly, exactly K requests start from every station stat(x), either because d + (x) = K or because x = p and the K requests (stat(p), 0) start. This shows that every segment is covered by exactly K(T + 1) requests which, in turn, means that none of these segments is traveled empty in a schedule composed of K(T + 1) tours.

We now consider the schedule of a given vehicle k. It executes T + 1 tours so it covers at most T requests r(x, y) with (x, y) ∈ E. As the KT requests r(x, y) with (x, y) ∈ E are shared by the K vehicles, every vehicle exactly fulfills T of these requests. Also, every vehicle starts and ends at the depot, and given that the vehicle never travels empty, this means that it starts with a request (0, stat(s)) and ends with a request (stat(p), 0). Given the total number K of (0, stat(s)) requests and (stat(p), 0) requests, each vehicle exactly fulfills one request (0, stat(s)) and one request (stat(p), 0).

One can conclude that every vehicle starts from the depot with a request (0, stat(s)), continues with T requests r(x, y) with (x, y) ∈ E and finishes with request (stat(p), 0), without any segment traveled empty in between. It also means that the arcs (x, y) ∈ E associated with the requests in the vehicle schedule form a path in G, starting from s, ending at p and composed of T arcs. It proves that I EP P is positive.

Figure 1 :

 1 Figure 1: PDP-R with four stations (station 0 is the depot)

Figure 2 :

 2 Figure 2: An example of compatible and overlapping requests

1.

  In what follows, multisets R (1) and R(2) , graph G and circuit Λ are those obtained from Algorithm 1. Two illustrative examples follow.Lemma 1. T OP T ≥ N sup .

Figure 3 :

 3 Figure 3: Example 1: Ring and initial requests (R)

Figure 4 :Figure 5 :

 45 Figure 4: Addition of new requests. The dashed arc denotes the request added in lines 6-8, while the dashdotted arcs denote the requests added in lines 9-14 of Algorithm 1.

Figure 6 :Figure 7 :

 67 Figure 6: Example 2: Ring and initial requests (R)

  consider an instance I c of the (γ, µ)-coloring problem on an interval graph. A = {(a 1 , b 1 ), ..., (a n , b n )} is a set of n intervals on a real line with a < b for each (a, b) ∈ A. An interval graph H = (V, E) is constructed from A by introducing a vertex v i for each interval (a i , b i ) ∈ A and by adding an edge (v i , v j ) each time intervals (a i , b i ) and (a j , b j ) overlap. Let γ and µ be two functions that map vertices in V into natural numbers, such that γ(v) ≤ µ(v)

W

  ∈ Z + be the bin capacity and w o be the weight of each object o ∈ O, with w o ≤ W . The problem consists in determining whether a partition of O in K disjoint subsets O 1 , . . . , O K exists such that the sum of item weights in each subset O k is at most W . This problem is NP-complete. Theorem 5. 1, Q|sd|CLT is NP-hard Proof. We consider the decision version of problem 1, Q|sd|CLT , i.e., the problem of determining, given an integer C, whether a feasible schedule exists with CLT ≤ C.

5

  instances with the same value of n, V and Q, considering feasible instances only. Column CPU(s) reports the solution time of the formulation in Section 3.3, in seconds. Column feas reports the number of feasible instances. Column grSuccess reports the number of instances for which the greedy algorithm found a feasible solution. Column T OP T reports the value of the optimal solution (closing time expressed in number of tours). Column gapGr gives the average percentage gap of the solutions found with the greedy algorithm with respect to the optimal solution.

  CPU(s) feas grSuccess CLT gapGr(%)

  feas grSuccess CLT gapGr CPU(s) feas grSuccess CLT gapGr CPU(s) feas grSuccess CLT

p

  Figure A.8: A Graph H = (V, F ), with 2 clauses c1, c2 and 3 variables z1, z2, z3

  variable arcs (c k , (j, u, )) (k ∈ {1, . . . , S}, (j, u, ) = lit(c k , u, ) * , Q) (j ∈ {1, . . . , N }, u ∈ {1, . . . , u(j)}, good bottleneck arcs (Q, p) good S copies 3 S bad bottleneck arcs (Q, p) bad,Id U -S copies 7 U -S bad bottleneck arcs (Q, p) bad,Def 3S -U copies 6 3S -U

Id-→

  (j, u) -→ (j, u, ¬ j ) Id -→ (j, u, ¬ j ) * -→ (j, u+(¬ j )) * Id -→ p; (the red paths in fig. A.11) -(j,u)-default path: s Def --→ (j, u) -→ (j, u, j ) Def --→ (j, u, j ) * -→ (j, u + j ) * Def --→ p;(the green paths in fig.A.11)

Figure

  Figure A.11 shows these paths.

  Figure A.13: Graph G

Figure A. 14 :

 14 Figure A.14: Ring and requests constructed from G

  For each of the 20 combinations mentioned above, this gives 12 fleet/demand compositions for unitary and non-unitary demands, respectively.When needed, release dates and due dates are defined based on the following observations. × n, respectively. The fleet brings a total capacity CLT × V × Q in the same unit. With a capacity fully exploited, CLT should thus approach nL 4V when demands are not unitary, nL

	The expected length of a request is approximately L 2 . The expected demand is approximately
	Q 2 when demands are non-unitary or exactly 1 when they are. So, every request approximately
	generates an expected workload L 2 × Q 2 in unit-of-distance × unit-of-demand for non-unitary
	demands and an expected workload L 2 otherwise. The total expected workload is thus L 2 ×
	Q 2 × n or L 2

2, 4, 8}. When demands are not unitary, they are generated in interval [1, Q].

Table 1 :

 1 Problem V, Q|sd, u|CLT

	80 1 1	2.5	5	5	46.4	1.3
	80 1 2	1.2	5	5	23.4	1.6
	80 1 4	0.6	5	5	12.0	1.7
	80 1 8	0.2	5	5	6.4	12.9
	80 2 1	2.5	5	5	23.4	1.6
	80 2 2	1.3	5	5	12.0	5.0
	80 2 4	0.6	5	5	6.4	6.2
	80 2 8	0.4	5	5	3.4	25.0
	80 3 1	3.8	5	5	15.8	3.8
	80 3 2	1.7	5	5	8.2	9.7
	80 3 4	0.8	5	5	4.4	19.0
	80 3 8	0.3	5	5	3.0	6.7
	160 1 1 17.6	5	5	87.4	0.2
	160 1 2	8.2	5	5	44.2	0.9
	160 1 4	5.3	5	5	22.2	2.8
	160 1 8	2.0	5	5	11.4	5.5
	160 2 1 30.9	5	5	44.2	0.5
	160 2 2 19.9	5	5	22.2	1.9
	160 2 4	6.6	5	5	11.4	5.5
	160 2 8	3.3	5	5	6.0	16.7
	160 3 1 39.9	5	5	29.4	2.1
	160 3 2 18.8	5	5	15.0	5.4
	160 3 4	9.9	5	5	7.8	10.4
	160 3 8	4.3	5	5	4.0	25.0

Table 5 :

 5 Problem V, Q|sd, ri, di|CLT (part 1) OP T gapGr CPU(s) feas grSuccess T OP T gapGr CPU(s) feas grSuccess T OP T gapGr

			feas grSuccess CLT gapGr(%)	n V Q CPU(s) feas grSuccess CLT gapGr(%)
	20 1 1	0.1	5	5	13.0	1.5	80 1 1	2.5	5	5	46.4	1.7
	20 1 2	0.1	5	5	9.8	8.2	80 1 2	2.9	5	5	35.6	2.8
	20 1 4	0.1	5	5	8.8	11.6	80 1 4 15.9	5	5	30.4	9.9
	20 1 8	0.1	5	5	8.2	16.9	80 1 8 22.9	5	5	27.6	11.9
	20 2 1	0.1	5	5	6.8	2.9	80 2 1	2.5	5	5	23.4	1.6
	20 2 2	0.1	5	5	5.4	10.9	80 2 2	3.9	5	5	18.2	5.6
	20 2 4	0.1	5	5	5.2	13.0	80 2 4	5.4	5	5	15.6	9.0
	20 2 8	0.1	5	5	4.8	13.0	80 2 8 24.4	5	5	14.2	12.8
	20 3 1	0.1	5	5	4.8	9.0	80 3 1	3.9	5	5	15.8	3.8
	20 3 2	0.1	5	5	3.8	23.3	80 3 2	5.8	5	5	11.8	7.0
	20 3 4	0.1	5	5	3.6	26.7	80 3 4	6.0	5	5	10.4	13.5
	20 3 8	0.1	5	5	3.2	26.7	80 3 8 20.2	5	5	9.8	16.6
	40 1 1	0.3	5	5	25.4	1.6	160 1 1 17.6	5	5	87.4	0.7
	40 1 2	0.2	5	5	19.0	3.2	160 1 2 102.9	5	5	65.4	1.2
	40 1 4	1.2	5	5	17.0	12.9	160 1 4 227.7	5	5	54.8	10.6
	40 1 8	0.5	5	5	14.6	11.0	160 1 8 292.3	5	5	51.6	12.5
	40 2 1	0.4	5	5	13.2	1.5	160 2 1 30.8	5	5	44.2	1.8
	40 2 2	0.3	5	5	9.8	10.4	160 2 2 29.7	5	5	33.2	3.0
	40 2 4	0.4	5	5	8.6	6.9	160 2 4 213.1	5	5	27.4	11.8
	40 2 8	0.7	5	5	8.8	11.4	160 2 8 453.7	5	5	25.4	11.0
	40 3 1	0.4	5	5	9.0	4.2	160 3 1 39.9	5	5	29.4	2.0
	40 3 2	0.4	5	5	7.2	14.0	160 3 2 50.3	5	5	22.2	3.6
	40 3 4	0.4	5	5	6.0	14.7	160 3 4 86.4	5	5	19.8	10.1
	40 3 8	0.3	5	5	5.0	20.3	160 3 8 162.7	5	5	18.4	12.1
					Table 4: Problem V, Q|sd|CLT

Table 6: Problem V, Q|sd, ri, di|CLT (part 2)

  Different future research directions are possible. In parallel to this work, we started addressing other variants of these problems, e.g., problems where vehicles are allowed to move in different directions or problems with alternative objective functions. Another interesting direction would be to consider different network topologies such as lines or other geometric shapes that can be encountered in practice. Also, autonomous vehicles are bound to use electric engines. A future step of our research should be to investigate the issues implied by the limited autonomy of electric vehicles (range anxiety, recharging policies. . . ).both a name and a notation for the nodes of the category. The total number of nodes in each category is reported in the last column. All nodes are visible in Figure A.8. One can notice that layers 3 and 4 contain exactly 2U nodes, that is, the number of literals in the clauses.

	Layer Category	Symbol		Number
	1 Source node	s		1
	2 Clause nodes	c 1 , ..., c S		S
	Low layer variable nodes (j, u)	(j ∈ {1, . . . , N }, u ∈ {1, . . . , u(j)})	U
	3 First middle nodes	(j, u, )	(j ∈ {1, . . . , N }, u ∈ {1, . . . , u(j)}, ∈	2U
			{0, 1})
	4 Second middle nodes	(j, u, ) *	(j ∈ {1, . . . , N }, u ∈ {1, . . . , u(j)}, ∈	2U
			{0, 1})
	5 Bottleneck node	Q		1
	Top layer variable nodes (j, u)*	(j ∈ {1, . . . , N }, u ∈ {1, . . . , u(j)})	U
	6 Sink node	p		1

Table A.7: Node set V Arc set F includes clause-related and variable-related arcs. Figure A.8 reports all these arcs for our illustrative example. s c 1

  in this clause, notation lit(c k , i) in the table indicates a triplet composed of: the index of the associated variable, the occurrence number of the literal, 0 or 1 if the variable is in its negative or positive form in the literal, respectively. For example, the three literals associated with clause c 1

Table A.8 and are shown in figures A.8 and A.9, with information on arc lengths on the latter. The structure of the table is similar to that of Table A.7, with an additional column for arc lengths. Given a clause c k and a literal y i

  Table A.8: Clause-related arcs in Set FProof. Let us first assume that our 3-SAT instance is positive, that is, it admits a feasible solution z = ( 1 , . . . , N ). Then we show how we can partition the arcs of H * into 3S + 2U paths with 11 arcs or equivalently the arcs of H into 3S + 2U paths with length 11. The construction is illustrated in Figures A.11 and A.12, pursuing with the same two clauses c 1

This work was sponsored by a public grant overseen by the French National Research Agency as part of the "Investissements d'Avenir" through the IMobS3 Laboratory of Excellence (ANR-10-LABX-0016) and the IDEX-ISITE initiative CAP 20-25 (ANR-16-IDEX-0001).

Appendix A. Complexity of problem V, 1|sd, u|CLT

In this Appendix, we prove that problem V, 1|sd, u|CLT is NP-hard. We consider the decision version of the problem and prove that it is NP-complete. In the decision version of V, 1|sd, u|CLT , one searches for a feasible solution with route lengths not longer than a given threshold CLT .

The proof is in two steps:

1. We introduce the Eulerian Path Partition Problem (EPP) and prove that it is NPcomplete. This is done through a polynomial-time reduction from the well-known 3-SAT problem, which is NP-complete.

2. We then propose a polynomial-time reduction from EPP to the decision version of

The EPP is defined as follows.

Definition 9. Let us consider a directed acyclic graph G = (X, E), together with 2 nodes s ∈ X and p ∈ X and 2 integer numbers K and T . We suppose that, for any node x ∈ X, a path from s to x and a path from x to p exist in G. The EPP consists in determining if a partition of E into K arc-disjoint paths can be found, with exactly T arcs in each path. In this case, we say that G is (K, T ) -EP P .

Appendix A.1. Reduction of 3-SAT to EPP

We will follow an approach very similar to the construction procedure which was proposed in [START_REF] Itai | The complexity of finding maximum disjoint paths with length constraints[END_REF]. We consider a 3-SAT instance Z = {z 1 , ..., z N } (variable set) and C = {c 1 , ..., c S } (3-clause set), with N variables and S clauses. We suppose that for any j = 1, ..., N , the number of occurrences of z j in C is equal to the number of occurrences of ¬z j and we denote it by u(j). We call this assumption the Well-Balanced Hypothesis.

We know from Lemma 3.1 [START_REF] Itai | The complexity of finding maximum disjoint paths with length constraints[END_REF] that the resulting restriction of 3-SAT remains NP-Complete. We set U = N j=1 u(j) and see that the total number of literals in the clauses is 3S = 2U . In what follows, we assume that each occurrence of any literal y i in a clause (variable z j or its negation) is associated with a number in {1, . . . , u(j)}.

We build a graph H = (V, F ) such that the 3-SAT instance is feasible if and only if a graph which is slightly modified with respect to H is (3S + 2U, 11)-EP P . H is acyclic and is composed of six layers. The construction is illustrated on Figures A.8 and A.9 for an instance with 3 variables and 2 clauses

Each line defines a given category of nodes, at a given layer, and introduces Variable-related arcs are defined in Table A.9. This table reads as Table A.8 (that is, 3S) between every successive layers except between layers 3 and 4, with 4U arcs.

Considering the two sets of arcs, the graph contains exactly 4U arcs between every successive layers.

Layers Category

Symbol

Length Number

(1, 2) low-first-id arcs (s, (j, u))

(3, 4) middle-id arcs ((j, u, ), (j, u, From graph H = (V, F ), we define a second graph H * = (V * , F * ) by replacing every arc of length h > 1 with a chain of h arcs of length 1. This new graph is useful to meet the definition of EPP in which the length of a path is given by its number of arcs. Then, finding a partition of F * in K arc-disjoint paths with T arcs in each path is equivalent to finding a partition of F in K arc-disjoint paths with length T .

-c-identifier path: among the three literals, at least one confirms the validity of the clause, i.e., its assignment is such that the clause is satisfied; we arbitrarily choose one such literal (in case there is more than one literal that satisfies the clause) and we generate path s

two c-default paths: a path is generated for every of the two remaining literals;

the literals can satisfy the clause or not; the path is s (1, 1)

(2, 1)

(3, 1) All paths have a length equal to 11. They cover all remaining middle-id and middle-def arcs. Indeed, an arc ((j, u, ), (j, u, ) * ) Id is traversed when the literal is true in the clause, that is, when = j . They also cover all clause-related arcs. Especially, for every clause, the c-id and the two c-def arcs are covered, as well as one good bottleneck arc and two bad bottleneck arcs. Furthermore, thanks to the well-balanced assumption, exactly U literals satisfy their clause and U literals do not. So, U literals cover the U bad bottlenecks arcs with cost 6, the other bottleneck arcs being covered by the other literals (S for the good bottleneck arcs, U -S for the remaining bad bottleneck arcs).

All together, the 3S + 2U paths partition F in paths of length 11, which proves that H * is (3S + 2U, 11)-EP P .

Conversely, let us now assume that H * is (3S + 2U, 11)-EP P . We will show that 3-SAT is positive. Indeed, if H * is (3S + 2U, 11)-EP P , it means that there exists a partition of the arcs of H into M = 3S + 2U paths with length 11, which we denote by Γ 1 , ..., Γ M . Then we see that those paths, which all contain one first middle node (j, u, ), can be split into 4 categories:

1. Those who reach node (j, u, ) with a sub-path s Id -→ (j, u) -→ (j, u, ) of length 8. To have a length 11, they must have the form of (j,u)-identifier paths. Every such path contains arc ((j, u, ), (j, u, ) * ) Id .

2. Those who reach node (j, u, ) with a sub-path s Def --→ (j, u) -→ (j, u, ) of length 4. They must be (j,u)-default paths. Every such path contains arc ((j, u, ), (j, u, ) * ) Def .

3. Those who reach node (j, u, ) with a sub-path s

Id

-→ c k -→ (j, u, ) of length 6. They must finish with good bottleneck arcs and be c-identifier paths.

4. Those who reach node (j, u, ) with a sub-path s Def --→ c k -→ (j, u, ) of length 2. They should finish with bad bottleneck arcs. They are c-default paths. Furthermore, U -S of them contain bad bottleneck arcs of size 7, and, so, also contain an arc ((j, u, ), (j, u, ) * ) Id .

Every node (j, u, ) is traversed by two paths:

• One path Γ m which is either a (j,u)-identifier path or a (j,u)-default path. We call this path the representative path of (j, u, ). We see that if the representative path of (j, u, ) is a (j,u)-default path then the representative path of (j, u, ¬ ) is a (j,u)-identifier path and vice-versa. Indeed, one path starts with sequence s Id -→ (j, u), the other with sequence s Def --→ (j, u).

• One path Γ m * which is either a c-default or a c-identifier path for some clause c k .

We now derive from paths Γ 1 , ..., Γ M , an assignment of {0, 1} values to variables z j . For every clause c k , we consider the node (j, u, ) traversed by the c-identifier path. We give value to variable z j . After this first step, it is possible that not all variables are assigned. We complete with random values for other variables. We prove that these values are consistent, i.e., the resulting assignment makes 3-SAT positive.

We use the following property of the Saw Pattern that we call the Saw Pattern Property.

Given a variable z j , we know that paths Γ 1 , ..., Γ M contain u(j) (j, u)-default paths and that each of these (j, u)-default paths reaches one of the u(j) nodes (j, u) * . The Saw Pattern imposes that the latter are reached from nodes (j, u, u ) with all u equal (using the arcs of one of the two perfect-matchings that compose the Saw Pattern). This also implies that, if variable z j gets value , then all arcs ((j, u, ¬ ), (j, u, ¬ ) * ) Id have to be in (j, u)-identifier paths and all arcs ((j, u, ), (j, u, ) * ) Def have to be in (j, u)-default paths. For example, in Figure A.10, the first occurrence of variable z j is negative (i.e. takes value 0), if and only if node (j, 1, 1) is reached with a (j, u)-identifier path, that must therefore finish with arc ((j, 2) * , p) of length 1. It means that arc ((j, 2) * , p) of length 4 must be in a (j, u)-default path together with arc ((j, 2, 0), (j, 2, 0) * ) Def , forcing also arc ((j, 2, 1), (j, 2, 1) * ) Id to be in a (j, u)-identifier path and thus forcing the second occurrence of variable j to get value 0. The same happens for the third occurrence.

Assume now that a variable z j receives two values and from two clauses c and c .

It means that arcs ((j, u, ), (j, u, ) * ) Id and ((j, u , ), (j, u , ) * ) Id are in the c-identifier path and the c -identifier path, respectively. It implies that arcs ((j, u, ), (j, u, ) * ) Def and ((j, u , ), (j, u , ) * ) Def are in the (j, u)-default path and (j, u )-default paths, respectively. Equality = follows from the Saw Pattern Property.

By construction, we also know that all clauses are satisfied for these values, which concludes the proof.

Appendix A.2. Reduction of EPP to V, 1|sd, u|CLT

In this section we prove that EPP can be reduced to V, 1|sd, u|CLT .

Theorem 7. EPP can be reduced to V, 1|sd, u|CLT .

Proof. Let I EP P = (G(X, E), s, p, K, T ) be a non trivial instance of EPP, i.e., the problem of determining whether there exists K disjoint paths of length T from s to t in G. Non trivial means that G has the following properties: It is easy to see that any instance that does not meet these requirements is trivially not (K, T ) -EP P . Note that it is enough to consider non-trivial instances in the reduction because if non-trivial instances could be solved with the reduction then all instances would be solved.

We build an instance I of V, 1|sd, u|CLT as follows. We introduce a ring with m = |X| + 1 stations. We first define station 0, the depot. The other stations have a one-to-one