Jean Philippe Gayon

Jean-Christophe Fauroux

En 2019, je suis venue en M2 de Genie Industrielle sans visa d'étudiant et je pouvais à peine dire «Je m'appelle Mari». Merci beaucoup à Sylvie Norre et Olivier Devise de m'avoir accepté sur cette formation et de m'avoir littéralement donné une nouvelle vie.

Merci à l'équipe de mes encadrants,

ix s'adapter au type de produit (taille/masse) et naviguer en autonomie dans des environnements tels que des entrepôts, des sites de production ou des chantiers. La figure 1 montre deux exemples de poly-robots M3-Cooper transportant des charges. Le monobot de la figure 1a peut transporter une caisse tandis que le quadri-bot de la figure 1b peut transporter une palette. Les robots permettent de décharger les opérateurs des tâches pénibles à faible valeur ajoutée et de les re-déployer sur les tâches complexes : contrôle qualité, préparation de commande. Ils permettent aussi des créations d'emploi dans la supervision et la maintenance robotique.

Problématique

Dans ce travail, nous examinons le transport des charges par des robots reconfigurables, nommés poly-robots, constitués de robots élémentaires. Un robot élémentaire ne peut pas être divisé en plusieurs robots. Un poly-robot est un groupe de robots élémentaires qui sont agrégés afin d'effectuer conjointement une tâche comme un seul robot. Après chaque transport, les poly-robots peuvent être reconfigurés pour s'adapter au type de charge. La capacité du poly-robot dépend de la configuration et du type de charge. On note p-bot une configuration avec p robots élémentaires. Notez qu'un 1-bot est un monobot qui travaille seul. L'objectif, dans un premier temps, est de déterminer le nombre de robots élémentaires nécessaires pour déplacer un ensemble de charges dans un horizon de temps spécifié au coût minimum. Dans un second temps, le but est de minimiser le temps de transport de toutes les charges avec un nombre de robots élémentaires donné.

x This first chapter introduces the reader to the context of the problem and everything that surrounds this thesis. First, we present how warehouses work, then we talk about their automation. Finally, we focus on the core of this thesis: the latest concepts of cooperative reconfigurable robots and the fleet problems. The chapter provides an overview of the current status of the subject of warehouses and the importance of the issue of warehouse automation, which has seen rapid progress recently. Despite the convenience and benefits of automated storage and retrieval systems, they remain expensive and fixed.

Organisation du manuscrit et contributions

Robotic systems can be quickly adapted to customer needs and variable flows of products to transport, and cooperation between them promises great prospects. However, in the context of autonomous vehicles, the fleet sizing problem has not been considered either for cooperative robots or for reconfigurable ones. This dissertation fill this gap.

Warehouses

With the increasing development of e-commerce, the number of warehouses is increasing every year. For example, Figure 2 shows that the number of warehouses in the U.S. increased by 31% between 2007 and 2020, representing 4587 new warehouses.

Definition and functions

According to [START_REF] Van Geest | Design of a reference architecture for developing smart warehouses in industry 4.0[END_REF], a warehouse is a building intended to store goods for commercial purposes. The main functions include receiving, storage, order prepara-1.1. Warehouses 3 tion and dispatching. Each function corresponds to an area in the warehouse (in orange in Figure 3). Loads (such as pallets, boxes, etc.) are transported between the four zones.

Receiving and dispatching are the warehouse's interfaces to the outside world for inbound and outbound material flow, respectively. Incoming goods are unloaded from transporting vehicles (truck, wagons, planes, ships...) and then stored in the storage area.

Different storage strategies can be used such as random storage or storage based on the physical characteristics of the goods (storage on pallets, in boxes, etc.). The warehouses are composed of a storage area which can be made up of two parts: the reserve area, where the products are stored in the most economical way (bulk storage area) and the gripping area where the products are stored for easy retrieval by an order picker. As the stock in the gripping area is depleted, new products are then transferred from reserve storage to the gripping area [START_REF] Cormier | A review of warehouse models[END_REF].

The verification and supply of goods are considered separate functions from reception by the company Mecalux. Mecalux [2016] define the objective of a warehouse as being the regulation of the differences between the input flows (what is received from suppliers, production plants, etc.) and those of output (the products sent in manufacturing centers, at points of sale, etc.). A complete overview of characterization of warehouses along the views processes, resources and organization is provided in [START_REF] Rouwenhorst | Warehouse design and control: Framework and literature review[END_REF].

Storage units

According to [START_REF] Rouwenhorst | Warehouse design and control: Framework and literature review[END_REF], the storage unit is a volume in which products can be stored. Examples of storage units are containers, pallets and boxes (cardboard boxes or plastic boxes).

Boxes or bins are generally made of cardboard or plastic (Figure 4). They preserve the integrity of the product and protect it. The standardization of the storage units allows, on the one hand, to simplify the loading of the pallets in trucks whose dimensions are also standardized, and on the other hand, to put on the pallets a multiple of the number of standard boxes (Figure 5). A container is built for intermodal freight transport, meaning these containers can be used across different modes of transport -from ship to rail to truck -without unloading and reloading their cargo [START_REF] Lewandowski | Growth in the size of unit loads and shipping containers from antique to WWI[END_REF]. The containers of 8 feet (2,44 m) wide, and of either 20 or 40 feet (6,10 or 12,19 m) standard length, are defined by ISO standard [ISO 6346:1995[ISO 6346: , 1995]]. In a 20 feet container, it's possible place up to 11 EPAL pallets (see Figure 7a) on the ground, in a 40 feet -up to 24 EPAL pallets (see Figure 7b). The Table 1 provides a summary of the capacity of containers and pallets described above.

EPAL

Shelving

A distinction is made between single and multiple depth storage systems. For simple storage systems, a shelf depth is a pallet length (Figure 8). Storage capacity can be doubled by using double-depth racks (Figure 9). The double depth saves space by eliminating the aisle that initially separated the racks. On the other hand, only the access to the first pallet is direct. To be able to reach the second pallet, the first one has to be extracted.

Regarding the dimensions of the shelves: the depth of the shelf is generally equal to the The aisles are generally 3,5 m wide to allow a forklift to make a quarter turn in order to position its fork in front of the shelving. Aisles can be one-way or two-way. An aisle of 3,5 m can be two-way (enough for the crossing of two 1, 5m wide vehicles).

Warehouse Automation

Despite the rapid growth of progress, there are still many manual warehouses where all manual tasks are performed by humans: unloading trucks, content checking, horizontal and vertical transfers, unit picking, order preparation, packaging. These are the very laborious and repetitive tasks, so it is not surprising that logistics warehouses are not attractive for human workers and get increasingly robotized.

Roland [START_REF] Berger | Of robots and men -in logistics towards a confident vision of logistics in[END_REF] anticipates that 1,5 million jobs will be replaced by robots between 2016 and 2026 in the Eurozone and that handling costs will be reduced by 20 to 40% in the same time thanks to robotic solutions. Companies decide to buy a robot by com-Chapter 1. Introduction and state of the art paring the cost of its use with that of an operator, knowing that a machine is generally amortized over 3 years. Figure 10 shows the evolution of the hourly cost for robots and human operators. We see that robots are becoming more and more affordable. A recent study [START_REF] Barosz | Efficiency analysis of manufacturing line with industrial robots and human operators[END_REF] confirms the interest of automated systems compared to operators in a certain number of situations as well as the efficiency of the use of automated systems compared to operators.

Automated storage

Automated storage systems have the greatest capacity, storage density and, therefore, require high investments. The principle of operation is as follows: loads arrive, the system chooses the location to store the load, an automated system grips the load and transports it to an empty slot in the storage space.

Existing classifications are rather based on machine elements (carousel, shuttles, etc.) than on mechanical or geometric properties. We distinguish three systems (Figure 11): carousel, VLM (Vertical Lift Module) and AS/RS (Automated Storage and Retrieval System). Automated storage systems could be classified by storage thickness. For example, VLM and carousels belong to the category of single thickness systems whereas AS/RS sometimes allow storage in multiple thicknesses. An automated storage and retrieval system typically consists of racks serviced by cranes traversing the aisles between the racks. An AS/RS is able to handle loads without operator intervention, so the system is fully automated [START_REF] Roodbergen | A survey of literature on automated storage and retrieval systems[END_REF].

AS/RS can use pallets or boxes [ SSI Schaefer, 2023].

There is a wide variety of load recovery instruments. To do this, cranes, shuttles and robots are used, individually and in combination:

•

Cranes

Cranes can move in the same plane, horizontally and vertically, usually simultaneously. Note that two cranes can move on the same horizontal rail to serve different parts of the stock. The vertical movements can be done in parallel without problem. Figure 13a shows the system proposed by RINAC, in which such a crane is represented in orange. The capacity of systems with cranes is limited, as only one crane can move horizontally at a time. This led to a new generation of grips, the shuttles.

• Shuttles

A shuttle is a mobile platform that moves inside the AS/RS. The shuttle system uses elevators to move the shuttles between levels, in turn the shuttles can move on rails along the X and Y axes. In Figure 13b, orange shuttles can be seen over the entire grid used by Vanderlande. A similar method is used in systems with robots that can also, among other things, move on the floor outside the storage system.

Chapter 1. Introduction and state of the art

• Robots

A robot is a machine that senses, decides and acts autonomously. A robot must have sensors necessary to obtain information about its environment [START_REF] Bekey | Autonomous robots: from biological inspiration to implementation and control[END_REF].

We give two examples of the use of robots with gripping systems.

The first example of a system with robots that got a lot of attention is SqUID made by BionicHIVE (Figure 12a). The SqUID consists of a synchronized autonomous robotic fleet. The robots move vertically and horizontally in tracks attached to racks, which can cause traffic jams. The SqUID is only fixed on a single rack, which facilitates the installation but exposes to a mechanical weakness of the guides.

Exotec's Skypod robots (Figure 12b) move horizontally on the ground and hoist themselves vertically by resting on the racks located on either side of the aisle. This double support avoids lifting the cantilever load (robustness) but imposes a good parallelism of the slides, which requires a flat and rigid slab [EXOTEC, 2023].

An integrated control system and intelligent real-time data analysis allow the algorithmic engine to dynamically learn from problems created in a warehouse and apply resolutions to all warehouses in the network. axes, and VTUs allow them to move in height (Figure 13c). Such systems are sometimes referred to as AVS/RS (Autonomous Vehicle Storage and Retrieval System) [START_REF] Lenoble | Optimisation de la préparation de commandes dans les entrepôts de distribution[END_REF]. 13d), is the first implementation of the RCSR system [START_REF] Azadeh | Robotized warehouse systems: Developments and research opportunities[END_REF].

Vertical lift module

The vertical lift modules consist of two columns of trays with a mechanical inserter/extractor positioned in the center (Figure 14). The inserter/removal moves up and down between stored trays, automatically locating and retrieving them as needed, like an elevator with doors that open both front and back [Kardex, 2021a].

VLMs are generally used in groups of several machines to perform entries or exits from a tray of a given VLM during the collection of articles on another VLM [START_REF] Lenoble | Optimisation de la préparation de commandes dans les entrepôts de distribution[END_REF].

Carousel

Carousels are automated storage and retrieval systems in which shelves are linked together and rotate in a closed loop. The rotation is either horizontal or vertical. In this system, the picker has a fixed location in front of the system and the system transports the items to the picker [START_REF] Azadeh | Robotized warehouse systems: Developments and research opportunities[END_REF]. The vertical carousel modules are a series of supports attached to fixed locations to a chain drive (Figure 15a). The movement is powered by a motor, which sends the carriers in a vertical loop around a track in both forward and reverse directions -similar to a Ferris wheel. Goods are stored or retrieved through an ergonomic access opening with a work counter [Kardex, 2021b]. The horizontal carousel modules consist of an oval rail supporting rotating bins with shelves (Figure 15b). A motor located inside the oval track propels the transporters around the track horizontally, stopping at a pre-determined access point for cargo storage or retrieval [Kardex, 2021b].

Carousels are effective in increasing storage density and facilitating access to products, often stored in boxes. On the other hand, the mass of the carousel limits the accelerations. The space between the links of the chain is constant. Care must also be taken to balance the system. VLMs allow varying storage heights and have fewer balancing issues. In both cases, access to the product is at a single point in the system, often on 1.2. Warehouse Automation 13 the ground, and there is a variable waiting time before recovery.

Despite all the advantages of automated systems, they are still expensive to install and once installed they are stationary, which is a major drawback in often reconfigurable warehouses.

Automated transport

For transporting loads in warehouses, different types of automated vehicles are used.

Several terms are used to designate these vehicles: Automated Guided Vehicle (AGV), Autonomous Mobile Vehicle (AMV) and Autonomous Mobile Robot (AMR), Mobile

Robot and Mobile Manipulator Robot. Some of these terms are interchangeable. For clarity, we will divide vehicles into three categories:

Automated Guided Vehicle

AGVs are vehicles guided on a predefined path, often optical or magnetic strips stuck to the ground. These vehicles generally stop when they encounter an obstacle on the road. According to [START_REF] Digani | Traffic Coordination for AGV Systems: an Ensemble Modeling Approach[END_REF], AGVs are used for transporting loads from one warehouse area to another (Figure 16) and consist of the following elements: a localization system (usually laser systems or magnetic systems), a safety system (proximity sensors or bumpers to avoid collisions) and a communication system (most of the type between AGVs and a supervision station, sometimes between AGVs). Chapter 1. Introduction and state of the art

Mobile robots

A mobile robot has a certain degree of autonomy greater than an AGV. The concepts of AMV and AMR therefore fall into this category. A complete overview of the last decade of these technologies can be found in [START_REF] Oyekanlu | A review of recent advances in automated guided vehicle technologies: Integration challenges and research areas for 5g-based smart manufacturing applications[END_REF]. AMVs are similar to AGVs but in addition have the ability to avoid obstacles: in the event of an obstacle in its path, an AMR is able to propose a bypass strategy to finish its task [START_REF] Andersson | AGV & AMR ROBOTS[END_REF].

An AMR is also often considered an advanced AGV. For example, [START_REF] Andersson | AGV & AMR ROBOTS[END_REF] considers that a main function of an AMR is to bring a load (pallet, box, etc.) from a storage area to a picking station, to deposit its load and return to storage. The author considers an AMR only as a basis for transport. At the same time, robots that are able to lift a load (a pallet, a trolley, a roll, a shelf, etc.) and move it, have their name: turtle robots or MRFS (Mobile Robot Fulfillment Systems) which move loads carrying it on their backs. These robots are respectively used in an RMFS (Robotic Mobile Fulfillment System), which according to [START_REF] Azadeh | Robotized warehouse systems: Developments and research opportunities[END_REF], has three main components:

• Robot Drive Units: these robots receive instructions from the central computer to transport inventory shelves to the workstation for restocking or picking. Nowadays, there are also decentralized controlled systems.

• Inventory Shelves: the shelves are mobile industrial shelves that hold stored items.

The small shelves are used for weights up to 450 kg and the large shelves are used for weights up to 1300 kg.

• Workstation: ergonomically designed areas where human workers perform shelf restocking, picking, and packing functions.

RMFS was patented by KIVA Systems Inc. [START_REF] Mountz | Inventory system with mobile drive unit and inventory holder[END_REF], which was later acquired by Amazon in 2012 and renamed AmazonRobotics.

Figure 17 shows a RFMS, where a robot brought products to a worker. This system allows mobility in the plan but is limited in height and mass of shelves.

Another example of a mobile robot, described by [START_REF] Urru | Fleet-sizing of multi-load autonomous robots for material supply[END_REF], is the SOTO manufactured by Magazino (Figure 18a). The SOTO is a mobile robot that performs industrial material supply: the robot enables efficient automated driving supply. In this category of mobile robots, we can also include automated carts. For example, Balyo automates forklifts so that they are able to move without an operator: The TRUCKY robotic pallet truck based on a manual pallet truck (Figure 18b). It is capable of carrying two pallets at a time, and up to 3000 kg, it can perform platform loading and unloading, long-distance transfer and stock line pick-up /drop-off.

Mobile manipulator robot

A mobile manipulator robot consists of a mobile base supporting one or more robotic arms. A fixed base manipulator arm has a certain working space in which its accuracy and speed can be characterized [START_REF] Gifford | Review of selected mobile robot and robotic manipulator technologies[END_REF]. The development timeline of mobile manipulator robots is shown in Figure 19. Robots are increasingly used for Small Load Carriers (SLC) [START_REF] Urru | Fleet-sizing of multi-load autonomous robots for material supply[END_REF]. In this regard, [START_REF] Urru | Fleet-sizing of multi-load autonomous robots for material supply[END_REF] considers these new means of transport highlighting their most important characteristics:

• Navigation in a dynamic environment;

• Transport of a set of SLC;

• SLC handling (full-empty SLC exchange); • High maneuverability

These two technologies are hereafter briefly introduced and analyzed.

1) AMADEUS

Autonomous Manipulator Device for Strengthening Manufacturing in Europe (AMADEUS) was a project started in 2009, funded by the German Federal Ministry of Education and Research (BMBF). The goal of the project was to develop a new robotic solution for intralogistics applications. The demonstrator (Fig. 1), presented at the MOTEK 2011, reproduces exactly the scenario of SLC supply to the point of use in the production plant [START_REF] Multi_Bot Model | [END_REF]. The new platform is a combination of an AGV with an application specific set-up and a robotic manipulator. into an already existing M processes. The point of str approach: all components and already approved for 1, the platform has a small to 8 SLCs with dimensio weight robot-arm equippe 6 kg. For this reason, th transportation of light mat

Multi-robot systems

A system composed of more than one robot is called a Multi-Robot System (MRS) [START_REF] Gautam | A review of research in multi-robot systems[END_REF]. According to [START_REF] Yan | A survey and analysis of multi-robot coordination[END_REF], multi-robot environments can be cooperative or competitive.

We speak of cooperative behavior when robots interact with each other in common interests. For example, search and rescue of people [START_REF] Balakirsky | Towards heterogeneous robot teams for disaster mitigation: Results and performance metrics from robocup rescue[END_REF] or transport of loads [START_REF] Yan | Multi-robot heuristic goods transportation[END_REF]. One of the first papers on cooperation between robots was done by [START_REF] Alami | Multi-robot cooperation in the martha project[END_REF]. The authors considered the autonomous coordination of the robots for transporting goods. The central station only sends high level missions. It is then up to the robots to refine, plan and coordinate route sections and crossings use, as well as trajectories in open areas.

The competitive environment means that the robot only works in its own interest. A typical example is the game of chess. A mixture of cooperative and competitive envi-Chapter 1. Introduction and state of the art ronments can be found in the robot soccer league, where we see cooperation within a team and competition between teams [RoboCup, 2021].

Cooperation

Cooperative robots capable of working in parallel on the same task open wide perspectives [START_REF] Noreils | Cooperation between mobile robots and industrial applications: Some perspectives[END_REF]. Cooperation can be defined as the joint performance of a task [START_REF] Jung | Experiments in realising cooperation between autonomous mobile robots[END_REF]]. For [START_REF] Tuci | Cooperative object transport in multi-robot systems: A review of the state-of-the-art[END_REF], there is cooperation if the task cannot be performed sequentially by a single robot and requires coordination of actions and communication between robots. Communication is explicit when the robots communicate directly with each other, and implicit when they communicate through an object which is, for example, transported.

There is different connection modes, for example, a large load can be transported by several small robots connected to the load (co-manipulation mode) or one robot can transport the load while connecting to another robot to increase stability (connection mode) [START_REF] Chebab | Conception et commande collaborative de manipulateurs mobiles modulaires (C3M3)[END_REF] as illustrated in Figure 21. Whatever the connection mode, there is coordination between robots, that is to say an exchange of information in order to be able to carry out a task together. Coordination is the basic process allowing robots to collaborate with each other [START_REF] Farinelli | Multirobot systems: a classification focused on coordination[END_REF].

Different methods and algorithms are developed so that the robot can take into account the actions of other robots in the system, for example, [START_REF] Majcherczyk | Communication Algorithms for Spatio-Temporal Cooperation in Multi-Robot Systems[END_REF] focus on how to enable the exchange of information for robots to gain better knowledge of the global state by building a collective semantic map from aggregated information. Coordination can also include a teamwork strategy that allows a set of robots to solve the problem of movement between a starting point and an objective through a safe path [START_REF] Chaves | Design of a strategy to obtain safe paths from collaborative robot teamwork[END_REF] or the movement of a load from its arrival location to the unloading point, when 1.3. Multi-robot systems the location of the load is not known at advance [START_REF] Nath | A distributed approach for autonomous cooperative transportation[END_REF].

Concerning the cooperation for the transport of objects, three categories of cooperation can be distinguish [START_REF] Tuci | Cooperative object transport in multi-robot systems: A review of the state-of-the-art[END_REF]]:

• Pushing-only strategy: robots are not physically attached to the object, and transport is achieved by pushing the object. This method can be used when robots cannot pull an object. [START_REF] Kube | Collective robotics: From social insects to robots[END_REF] has done pioneering work in this area, demonstrating the ability to move an object without direct communication between robots. A more complex model with obstacles is presented by [START_REF] Wang | Multi-robot box-pushing: Single-agent q-learning vs. team q-learning[END_REF].

• Grasping strategy: robots are physically attached to the object, and transport can be achieved by pushing or pulling (or both) the object. This strategy assumes that the robots are equipped with a gripping tool. Algorithms have been developed to find the position of the robots to ensure maximum stability of the robots carrying the load [START_REF] Sasaki | Cooperating grasping of a large object by multiple mobile robots[END_REF][START_REF] Hichri | Cooperative mobile robot control architecture for lifting and transportation of any shape payload[END_REF].

• Caging strategy: robots surround the object and block it during transport, unlike the pushing-only strategy. It is essential to position the robots correctly according to the shape and size of the object, so that the object does not escape from the cage [START_REF] Campos | Guilherme as pereira[END_REF].

A complete review of cooperative MRS can be found in [START_REF] Rizk | Cooperative heterogeneous multi-robot systems: A survey[END_REF].

Reconfiguration

A reconfigurable robotic system is an assembly of modules that can attach and detach from each other to modify and adapt to different tasks and environments [START_REF] Bojinov | Emergent structures in modular self-reconfigurable robots[END_REF]. The ability of individual modules or robots to be connected in different ways to perform the required task offers promising potential [START_REF] Arai | Advances in multi-robot systems[END_REF]. [START_REF] Stoy | Self-reconfigurable robots: an introduction[END_REF] define three categories of self-reconfigurable robots based on the number of modules:

pack robots, herd robots and swarm robots. Pack robots are composed of several modules, usually in the range of tens, and require strict coordination due to the fact that the individual modules play a crucial role in the robot's overall performance. Herd robots are composed of a large number of modules, usually in the range of hundreds, and Chapter 1. Introduction and state of the art global coordination of these modules is challenging. They are better managed as a collection of groups since the actions of individual modules are still significant but not as critical to the overall performance of the robot. Eventually, swarm robots are comprised of countless modules. Here, each module is controlled locally since the impact of an individual module on the overall behavior of the robot is minimal.

Several prototypes of reconfigurable robotic systems have been developed. The reader is referred to [START_REF] Jahanshahi | Reconfigurable swarm robots for structural health monitoring: a brief review[END_REF] or Seo et al. [2019] for a survey on this topic.

For instance, systems using multiple modules can create different forms to perform different tasks: it could turn into a snake to reach into narrow places, into a hexapod to carry a load or it may split into many smaller robots to perform a task in parallel [START_REF] Castano | Autonomous and self-sufficient conro modules for reconfigurable robots[END_REF][START_REF] Yim | Polybot: a modular reconfigurable robot[END_REF]. The self-reconfigurable robots can also be used as conveyors. The spherical shape of the ATRON modules enables them to function as wheels, facilitating the construction of surfaces that have the capability to transport items [START_REF] Østergaard | Design of the atron lattice-based self-reconfigurable robot[END_REF][START_REF] Brandt | Atron robots: versatility from selfreconfigurable modules[END_REF]. [START_REF] Shen | Multimode locomotion via superbot reconfigurable robots[END_REF] demonstrate a solution based on SuperBot modules that can perform multimodal locomotions such as snake, caterpillar, insect, spider, rolling track, H-walker, etc. [START_REF] Chebab | Conception et commande collaborative de manipulateurs mobiles modulaires (C3M3)[END_REF] focuses on the design of new architectures of modular mobile manipulators that can cooperate with each other to perform tasks in industrial or service contexts concerning the handling and transport of boxes. Another application of reconfigurable robots can be found in Mars exploration, where tasks such as transportation or building construction have to be performed with limited resources [START_REF] Irawan | A Reconfigurable Modular Swarm Robotic System for ISRU (In-Situ Resource Utilisation) Autonomous 3D Printing in Extreme Environments[END_REF]. A survey of modular system for multifunctional applications in space exploration is presented by [START_REF] Post | Modularity for the future in space robotics: A review[END_REF].

In commercial products, there are several examples of technical solutions for cooperative and reconfigurable robots (Figure 22). JNOVtech robots connect directly to the load (Figure 22a) and MecaBotiX robots (Figure 22b) can connect to each other and /or to the load. Another example of robot cooperation is presented by the Strothmann Round-Track, mobile platforms that cooperatively move big loads on rails (Figure 22c).

Fleet management

A warehouse of a manufacturing company today is characterized by dynamic production processes governed by the demands of a rapidly changing global economy, such as the increasing number of product variants, customization of products and responsiveness to changing market conditions [START_REF] Urru | Fleet-sizing of multi-load autonomous robots for material supply[END_REF]. In order to be competitive, companies are forced to seek the advantageous solutions, specially for vehicle fleet management. Fleets of vehicles require solving several problems related to both the internal management of this fleet and global issues such as determining the required number of vehicles. [START_REF] Rjeb | Dimensionnement d'une flotte de robots dans un entrepôt logistique[END_REF] identifies several of the fleet management problems:

1. Scheduling problem A scheduling problem consists in assigning tasks (e.g. production or transportation) to resources (e.g. machines or vehicles) with the goal to minimize one or more objectives (e.g. makespan that is the time to complete all transportation Chapter 1. Introduction and state of the art tasks) [START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems[END_REF]. Job shop problem is often considered. This problem consists in multiple jobs which are processed on several machines. Each job contains of a sequence of tasks, which must be performed in a given order, and each task must be processed on a specific machine. The job-shop scheduling problem with one mobile robot is investigated by [START_REF] Hurink | Tabu search algorithms for job-shop problems with a single transport robot[END_REF][START_REF] Caumond | An MILP for scheduling problems in an FMS with one vehicle[END_REF] while the problem with several mobile robots has been tackled by [START_REF] Deroussi | A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles[END_REF][START_REF] Lacomme | Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles[END_REF][START_REF] Baruwa | A coloured petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles[END_REF][START_REF] Fontes | Joint production and transportation scheduling in flexible manufacturing systems[END_REF][START_REF] Yao | A novel MILP model for job shop scheduling problem with mobile robots[END_REF]. Most of the job-shop scheduling problems with mobile robots are NP-hard. Hence the exact approaches, such as Mixed Integer Linear Programming (MILP), work only for small instances [START_REF] Caumond | An MILP for scheduling problems in an FMS with one vehicle[END_REF][START_REF] Fontes | Joint production and transportation scheduling in flexible manufacturing systems[END_REF][START_REF] Yao | A novel MILP model for job shop scheduling problem with mobile robots[END_REF]. Approximate solution methods have also been considered to tackle larger instances [START_REF] Deroussi | A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles[END_REF][START_REF] Lacomme | Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles[END_REF][START_REF] Baruwa | A coloured petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles[END_REF]. We refer the reader to [START_REF] Yao | A novel MILP model for job shop scheduling problem with mobile robots[END_REF] for a detailed review of these works.

Vehicle routing problem (VRP)

A VRP consists in determining the optimal route to minimize the cost of transport.

Numerous articles define the limits of the problem formulation in different ways.

According to [START_REF] Golden | The fleet size and mix vehicle routing problem[END_REF], the problem involves a predetermined number of vehicles, with the same capacity. A key assumption is that fixed (or acquisition)

costs have already been incurred and only variable (or routing) costs need to be explicitly considered. The objective is to minimize the total transport cost which is a function of the total distance traveled by the fleet of vehicles. In the article of [START_REF] Bodin | Classification in vehicle routing and scheduling[END_REF], this problem is defined more broadly and, in addition to the above objective, it can have objectives such as: minimizing the sum of fixed and variable costs or minimizing the number of vehicles required. [START_REF] Sitek | Capacitated vehicle routing problem with pick-up and alternative delivery (cvrppad): model and implementation using hybrid approach[END_REF] describe various versions of the problem. A large amount of literature has recently been devoted to the environmentally friendly type of vehicles. A complete review of the literature on this topic can be found in [START_REF] Asghari | Green vehicle routing problem: A state-of-the-art review[END_REF].

Fleet sizing problem (FSP)

Determining the appropriate fleet size, which refers to the number of vehicles to acquire or lease in order to meet demand, often takes precedence and heavily in-1.5. Fleet sizing fluences the routing decision [START_REF] Golden | The fleet size and mix vehicle routing problem[END_REF]. The optimal number of vehicles is considered for various objective functions. Most of the time, the objective is to minimize the number of robots required to achieve a set of transportation jobs in a time interval. Several works consider more elaborate objective functions. [START_REF] Beaujon | A model for fleet sizing and vehicle allocation[END_REF] maximize the total profit (difference between revenues and total transportation costs, including penalty costs for unmet demand). [START_REF] Etezadi | Vehicle fleet composition[END_REF] minimize the cost of a fleet of purchased or leased vehicles. [START_REF] Sinriech | An economic model for determining agv fleet size[END_REF] minimize the cost by applying penalties if performance is not achieved in terms of quality of service. Many articles on the topic of FSP in a road freight transportation are given by Żak et al. [2011].

In what follows, we focus on the fleet sizing problem. This problem is the main one in this dissertation and that is why special attention is paid to it. First of all, we will discuss this problem in the general context of transport systems. Then, the fleet sizing problem for autonomous vehicles is considered. In this area, attention is paid to automated guided vehicles (AGVs) and autonomous mobile robot (AMRs). However, there is a noticeable lack of articles in the literature on the topic of FSP for cooperative and reconfigurable robots. This is a new topic that will be supplemented by this dissertation.

Fleet sizing

One of the most challenging issues in fleet management is a fleet sizing problem. The main focus of the fleet sizing problem (FSP) is to align supply and demand. It involves determining the appropriate number of vehicles in the fleet to achieve two goals: ensuring the complete fulfillment of the incoming transportation orders and preventing high fixed costs associated with fleet underutilization [ Żak et al., 2011].

Transportation systems

The fleet sizing problem in transportation systems consists in determining the optimal number of vehicles for the transport of goods. This is a key logistics problem which concerns all means of transport (air, sea, road, inside warehouses, ...). Baykaso glu et al.

[2019] provides a review of fleet planning problems (including fleet sizing) in transportation systems. In road transportation, the problem involves tanks and rail cars [START_REF] Sha | Fleet sizing in chemical supply chains using agent-based simulation[END_REF][START_REF] Milenković | A fuzzy random model for rail freight car fleet sizing problem[END_REF][START_REF] Cheon | A modeling framework for railcar fleet sizing in the chemical industry[END_REF], trucks [Mohtasham Chapter 1. Introduction and state of the art et al., 2021;[START_REF] Amjath | Fleet sizing of heterogeneous fleet of trucks in a material handling system using anylogic simulation modelling[END_REF], vehicles [START_REF] Rahimi-Vahed | Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm[END_REF][START_REF] Koç | The fleet size and mix pollution-routing problem[END_REF][START_REF] Kumar | Integrated fleet mix and routing decision for hazmat transportation: A developing country perspective[END_REF] and electric buses [START_REF] Manzolli | A review of electric bus vehicles research topics-methods and trends[END_REF]. The issue is not only the composition of the fleet but also the choice of the route [START_REF] Hoff | Industrial aspects and literature survey: Fleet composition and routing[END_REF]. For maritime transport, the question of determining the route can be less relevant due to the fact that the route between the point of departure and destination is connected by a straight line, except when there are areas on the way that need to be bypassed or bad weather condition [START_REF] Romero | An approach for efficient ship routing[END_REF].

The maritime fleet sizing problem considered by [START_REF] Pantuso | A survey on maritime fleet size and mix problems[END_REF] is related to our study. The authors give an example of an objective function and constraints specific to the maritime fleet problem:

min ∑ v C F v y v + ∑ v ∑ r C V vr y v x vr subject to : ∑ r Z vr x vr -Zy v ≤ 0, ∀v ∈ V ∑ v ∑ r Q v A ir x vr ≥ D i ∀t, ∀i ∈ N y v ∈ N, x vr ∈ N ∀i, ∀v, ∀r
• y v represents the number of ships of type v ∈ V

• x vr represents the number of times route r is sailed by ships of type v The objective function includes two terms, the first of which is responsible for the price of the fleet, and the second for the the price of the distance traveled. We can see a similar objective function in Chapter 2, where the type of robot would correspond to the type of ship. The constraint on the demands is also similar. As for the constraint on the time, in our case, a time horizon is given for which it is necessary to transport all loads, in the case of the model described above, an allotted time is given for each type of ship.

• A ir is equal to 1 if route r calls port i,

Autonomous vehicles

A particular development over the last decade has taken place for AGVs and AMRs [START_REF] Oyekanlu | A review of recent advances in automated guided vehicle technologies: Integration challenges and research areas for 5g-based smart manufacturing applications[END_REF], especially in logistics warehouses and industrial production [START_REF] Andersson | AGV & AMR ROBOTS[END_REF]. Different questions arise when operating a fleet of robots, such as the design of the warehouse architecture [START_REF] Van Geest | Design of a reference architecture for developing smart warehouses in industry 4.0[END_REF], trajectory planning with obstacle and collision avoidance [START_REF] Cardarelli | Cooperative cloud robotics architecture for the coordination of multi-agv systems in industrial warehouses[END_REF]Lee et al., 2019], service policy [START_REF] He | Differentiated service policy in smart warehouse automation[END_REF] and battery charging [START_REF] Zou | Evaluating battery charging and swapping strategies in a robotic mobile fulfillment system[END_REF]. Due to the fact that autonomous vehicles are expensive, it is crucial to determine the correct type and number of vehicles,

which is what we focus on in this section.

We begin the study of this issue by a consideration of sizing methods. [START_REF] Ganesharajah | Design and operational issues in AGV-served manufacturing systems[END_REF] identify two sizing methods: simulation and analytical method. Simulation can simulate reality with great accuracy and produce the fewest errors, but at an early stage of work it can be difficult to build a model that accurately characterizes the basic properties and necessary parameters. And then an analytical model can be interesting, which makes it possible to obtain an optimal solution and can quickly run through a large number of parameters. Error in performance estimates using analytical models is generally acceptable for the conceptualization phase. The analytical methods is divided into deterministic and stochastic. [START_REF] Vis | Survey of research in the design and control of automated guided vehicle systems[END_REF] highlights in deterministic approach linear programming models that can be utilized prior to the actual operation to estimate the required number of vehicles, but stochastic models, such as queueing networks, aim to incorporate external influences. On one hand, analytical models tend to underestimate the required number of vehicles compared to simulation results. On the other hand, simulation requires a lot of details and hardly copes with large fleets, that's why the literature on the sizing of a fleet of robots is largely devoted to analytical approaches (with stochastic models [START_REF] Koo | Estimation of part waiting time and fleet sizing in agv systems[END_REF][START_REF] Arifin | Determination of vehicle requirements in automated guided vehicle systems: a statistical approach[END_REF] or with deterministic models [START_REF] Egbelu | The use of non-simulation approaches in estimating vehicle requirements in an automated guided based transport system[END_REF]Rjeb et al., 2021a]).

This dissertation considers an analytical approach, namely deterministic, which is why special attention, in what follows, is paid to deterministic models. The work of [START_REF] Egbelu | The use of non-simulation approaches in estimating vehicle requirements in an automated guided based transport system[END_REF] proposes four analytical approaches to estimate the number of robots, giving examples for each of them. The author proposes to consider adding dispatching rules and then simulate his models with varying incoming material flow. These models are optimistic according to the author. Rjeb et al. [2021b] refine the results of [START_REF] Egbelu | The use of non-simulation approaches in estimating vehicle requirements in an automated guided based transport system[END_REF] in the case of homogeneous loads by providing an analytical formula for the optimal number of robots. In the case of heterogeneous loads, the authors formulate the problem as a bin packing problem. [START_REF] Lee | Robotics in order picking: evaluating warehouse layouts for pick, place, and transport vehicle routing systems[END_REF] investigate a new approach for warehouse order picking. The article focuses on two types of commercially available mobile robots: pickers, capable of grasping items from shelves, and transporters, designed to deliver items from the warehouse to the packing station. The authors determine the optimal combination of picker and transport robots that surpasses the performance of traditional human-based picking operations. [START_REF] Lyu | Approach to integrated scheduling problems considering optimal number of automated guided vehicles and conflict-free routing in flexible manufacturing systems[END_REF] simultaneously consider the optimal number of AGVs, the shortest transportation time, a path planning problem and a conflict-free routing problem. To study these problems simultaneously, they propose a genetic algorithm combined with the Dijkstra algorithm that is based on a time window. Aziez et al.

[2022] focus on the optimization of the number and types of carts and AGVs required to fulfill daily requests in a hospital while optimizing AGVs routes and adhering to time constraints. Each request necessitates specific types of carts, which are transported by the AGVs. The authors present a mathematical formulation and propose a matheuristic approach. This matheuristic leverages a dynamic reoptimization of routes as new requests arrive.

Complete reviews on AGV design/control and on AMR planning/control for intralogistics can be found respectively in reviews in [START_REF] Vis | Survey of research in the design and control of automated guided vehicle systems[END_REF] and [START_REF] Fragapane | Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda[END_REF].

Research questions

The thesis is in the context of intralogistic of an industrial system comprising several robotic entities, which are mobile and cooperative. The goal is to transport loads from 1.6. Research questions 27 one zone of warehouse to another zone by reconfigurable robots. A robot is a machine that has a function and can control itself autonomously to perform its function.

The reconfigurable robots, named poly-robots, consist of elementary robots that are aggregated in order to jointly perform a task as a single robot. An elementary robot is abbreviated as bot and cannot be split into several robots. Each poly-robot configuration has its own transport capacity. The capacity of the poly-robot depends on the configuration and the type of load. We denote by p-bot a configuration with p elementary robots. Note that a 1-bot is a mono-bot that works alone. The time horizon to transport all loads is divided into T periods. At the beginning of each period, the poly-robots are located in the loading area and can be reconfigured. For example, a 3-bot and a 2-bot, i.e. 5 elementary robots, can turn into a 4-bot and a 1-bot. This example is illustrated in Figure 23. The issue is to find out the optimal number of elementary robots and in which configuration, which type of load and in which period of time the loads should be transported to minimize the transportation cost or time.

Organization of the manuscript

The first chapter has presented the context of the thesis and given an overview of existing automated solutions in warehouses, in particular cooperative mobile robots and the state of the art of the fleet problems.

The second chapter treats the transport of identical loads by a fleet of non-cooperative and cooperative robots.

The third chapter deals with the sizing of a fleet of reconfigurable robots for the transport of heterogeneous loads. This chapter also compares the number of elementary robots in the cases with and without reconfiguration.

The fourth chapter studies the complexity of the problem and provides a heuristic algorithm with a numerical experiment.

The fifth chapter gives an extension of the problem, posing the question of makespan minimisation of a given fleet.

At the end we sum up the results and look at further ways of plot development.

Chapter 2

Transport of homogeneous loads In this chapter, we are interested in the sizing of a fleet of non-cooperative and cooperative robots for the transport of standardized loads that are all identical and referred as "homogeneous loads". We consider the problem of determining the number of robots necessary to transport a set of homogeneous loads in a given time interval from a zone

A to a zone B, at minimum cost. The cost is function of the number of robots and of the distance travelled by robots. The operations are divided into several phases: loading, loaded travel forth, unloading, empty travel back and battery charging.

To our knowledge, this chapter is the first scientific work to focus on the sizing of a fleet of cooperative robots. The results obtained in this chapter have been published in [START_REF] Chaikovskaia | Sizing of a fleet of cooperative robots for the transport of homogeneous loads[END_REF].

Non-cooperative robots

In this first part, we consider the sizing of a fleet of non-cooperative robots and extend the results of Rjeb et al. [2021b] by adding the concept of transport capacity.

Assumptions and notations

The following notations are used:

τ = t l + d 2v l + t u + d 2v e (2.1)
Chapter 2. Transport of homogeneous loads Over the time interval [0, T], the robot is immobilized during t b (battery recharge, maintenance, failure, etc.). The remaining available time is then (Tt b ).

The cost per unit of time of a fleet of N > 0 robots traveling a total distance D over [0, T] is

f (N) = αN + βD T + γ (2.2)
where α represents the fixed cost of a robot per unit of time (cost related to maintenance, purchase or rental), β the cost per meter traveled by one robot and γ the cost per unit of time independent of the number of robots (e.g. hardware and software infrastructure).

Note that the total distance traveled D is directly related to the number of loads n to be transported. It takes r = n c round trips to transport the n loads. Then D = dr and the cost function is

f (N, r) = αN + βd T r + γ. (2.
3)

The objective is to determine the number of required robots, N * , to transport the set of n loads over time interval [0, T] at minimum cost, considering A as the starting point of the robots. This simple problem is equivalent to determining the minimum number of round trips and robots allowing all loads to be transported over the time interval. To have feasible solutions, we assume that Tt b ≥ τ.

The following assumptions are also made:

• The robot storage place is located at point A. There is no waiting to load in A or to unload in B (the loads are available immediately to be loaded and the robots do not hinder each other).

• The problem of traffic jams for robots is not taken into account. These different elements could nevertheless be taken into account by introducing an efficiency coefficient, as proposed in [START_REF] Egbelu | The use of non-simulation approaches in estimating vehicle requirements in an automated guided based transport system[END_REF].

Minimal number of robots (finite horizon)

⩾ n c ⌊(T -t b )/τ⌋ .
The number of robots being an integer, the minimum number of robots to transport n loads during the time interval [0, T] is then

N * = n c ⌊(T -t b )/τ⌋ (2.4)
The minimum number of round trips for robots to transport n loads is

r * = n c , (2.5)
where ⌈x⌉ is the least integer greater than or equal to x.

The minimum cost is then

f * = f (N * , r * ) = αN * + βd T r * + γ (2.6) = α n c ⌊(T -t b )/τ⌋ + βd T n c + γ (2.

Minimal number of robots (infinite horizon)

We are also interested in the limit case where the time horizon T tends to infinity. This allows, on the one hand, to avoid side effects (if horizon T is not a multiple of cycle time τ) and, on the other hand, to model a fleet of vehicles operating permanently.

We denote by µ = c/τ the maximum flow rate of loads per robot (maximum number of loads that a robot can carry per unit of time), by λ = n/T the demand flow of loads to transport and by δ = t b /T the immobilization rate.

Theorem 2.1.1. If T tends to infinity, keeping λ and δ constant, then:

N * = λ µ(1 -δ) (2.8) f * = α λ µ(1 -δ) + βd λ c + γ (2.9)
Proof. Using the fact that x -1 < ⌊x⌋ ≤ x, we can limit the optimal number of robots obtained in (2.4):

n c T-t b τ ≤ N * <     n c T-t b τ -1     (2.10) ⇔     n T c τ 1 -t b T     ≤ N * <     n T c τ 1 -t b T -c T     (2.11)
Using the notations λ, µ, δ, this frame is re-written

λ µ(1 -δ) ≤ N * < λ µ 1 -δ -c T (2.12)
If we tend T to infinity, keeping λ and δ constant, we get

N * n T →λ, t b T →δ ---------→ T→+∞ λ µ(1 -δ) (2.13)
Similarly, we have the framing

n cT ≤ 1 T n c < 1 T n c + 1 (2.14) and 1 T n c n T →λ ------→ T→+∞ λ c (2.15) Then f * n T →λ, t b T →δ ---------→ T→+∞ α λ µ(1 -δ) + βd λ c + γ (2.

Cooperative robots

In this section, we assume that robots can cooperate to transport loads. We remind the concepts and terminology developed in Section 1.6:

• bot = An elementary robot, which is cannot be split into several robots.;

• p-bot = A set of p elementary robots, which cooperate on the same task.

Assumptions and notations

The following notations are used:

• p: number of bots constituting one p-bot

• c 1 : 1-bot capacity • c p : p-bot capacity • c ′ 1 = c p /p: virtual capacity of a 1-bot that is part of a p-bot • τ 1 : 1-bot cycle time
• τ p : p-bot cycle time (including possible cooperation time)

• α: fixed cost per unit of time of a bot

• β: cost per meter traveled by a bot

• γ: fixed cost per unit of time, independent of the number of bots

• N 1 : number of 1-bots working alone

• N p : number of p-bots

• n 1 : number of loads transported by 1-bots working alone

• n p : number of loads transported by p-bots

• T: planning horizon

• r 1 : number of round trips for 1-bots

• r p : number of round trips for p-bots

• n: number of loads to be transported from A to B n = n 1 + n p

• N: number of 1-bots in the fleet (including those working in a p-bot)

N = N 1 + pN p
We will make the following additional assumptions:

• τ 1 ≤ τ p as a p-bot may waste time in cooperation.

• There is no additional cost associated to a p-bot. The costs of a p-bot are simply those induced by the bots constituting it.

• There is no possible reconfiguration. A p-bot always remains a p-bot and a 1-bot always remains alone.

Optimal fleet (finite horizon)

The fleet sizing problem can then be modeled by the following mathematical program which aims at minimizing the cost function for cooperative robots f c (r 1 , r p , N 1 , N p ):

f c = α(N 1 + pN p ) + βd T r 1 + pr p + γ (2.17)
subject to:

n 1 ≤ N 1 c 1 T -t b τ 1 (2.18) n p ≤ N p c p T -t b τ p (2.19) n = n 1 + n p (2.20) n 1 c 1 ⩽ r 1 (2.21) n p c p ⩽ r p (2.22) r 1 , r p , n 1 , n p , N 1 , N p ∈ N (2.23)
Constraints interpretation:

• Constraint (2.18): the number of loads carried by 1-bots must be less than or equal to the maximum number of loads that 1-bots can transport on interval [0, T];

• Constraint (2.19): the number of loads carried by p-bots must be less than or equal to the maximum number of loads that p-bots can transport on interval [0, T];

• Constraint (2.20): the sum of the number of loads carried by 1-bots and p-bots must be equal to the total number of loads to be transported;

• Constraint (2.21): the number of round trips for the transport of all the loads designated by 1-bots must be rounded up to allow the transport of all loads;

• Constraint (2.22): the number of round trips for the transport of all loads designated by p-bots must be rounded up to allow the transport of all loads.

When β = 0, the problem comes down to determining the minimum number of robots allowing all loads to be transported. When α = 0, the problem comes down to achieving the optimal number of round trips to transport all the loads (a round trip from a p-bot counts as p round trips):

r * 1 = n * 1 c and r * p = n * p c
, where n * 1 et n * p the optimal number of loads transported by 1-bots and p-bots, respectively, at which the cost is minimal.

We will distinguish three cases linked to the respective capacities of 1-bot and p-bot.

• c 1 = 0 In this first case, we assume that a 1-bot can't carry a load on its own (c 1 = 0). This scenario may appear for a load of great mass, great volume or even great length.

For example, as shown in Figure 27, the robot cannot transport a load much larger than itself for stability reasons. The problem then consists in determining the number of p-bots needed to carry all the loads and the results of Section 2.1 can be re-used. So we have:

Chapter 2. Transport of homogeneous loads

N * p = n c p (T -t b )/τ p , N * 1 = 0. • c 1 ≥ c ′ 1
In this second scenario, a single 1-bot has a greater capacity than a 1 bot in pbot configuration. Let us give a first example where this scenario occurs. If the capacity constraint is related to the transported mass and an additional pallet is needed in p-bot mode, then we lose mass capacity in p-bot mode. Another example would be the case where the load is transported by manipulator arms installed on the mobile platform in p-bot mode. Figure 28 shows the case when the robot loses its mass capacity due to the pallet, and thus the 1-bots transport more than the p-bots.

c 1 ≥ c ′ 1 (or equivalently pc 1 ≥ c p ).
Hence, it is optimal to use exclusively 1-bots.

We can then use again the results from the previous section. So we have

N * p = 0, N * 1 = n c 1 ⌊(T -t b )/τ 1 ⌋ . • 0 < c 1 < c ′ 1
In this 3rd case, a single 1-bot has a lower capacity than a 1 bot in p-bot configuration. This scenario may arise for the transport of long objects (for example tubes)

or even objects of large volumes but of low density. Figure 29 shows an example where a p-bot can have a capacity greater than a 1-bot, when we can not stack loads on top of each other. In this case, unlike previously, the optimal solution can consist of a mix of p-bots and 1-bots. This appears in particular if the cost linked to the traveled distance is significant. Consider the following example:

n = 4, p = 2, c 1 = 1, c p = 3, τ 1 = τ p = T/2, t b = 0, α = 1, βd/T = 10, γ = 0.

Optimal fleet (infinite horizon)

We use the following additional notations:

• µ 1 = c 1 τ 1 : 1-bot flow rate • µ p = c p τ p : p-bot flow rate
• λ: demand flow rate of loads to be transported

• λ 1 = n 1 T : flow rate of loads carried by 1-bots alone

• λ p = n p T : flow rate of loads carried by p-bots

• δ = t b /T immobilization rate
The mathematical program can then be written as a MILP (Mixed-Integer Linear Programming) :

min α(N 1 + pN p ) + βd λ 1 c 1 + p λ p c p + γ (2.24) s.t. λ 1 ≤ N 1 µ 1 (1 -δ) (2.25) λ p ≤ N p µ p (1 -δ) (2.26) λ = λ 1 + λ p (2.27) λ 1 , λ p ∈ R, N 1 , N p ∈ N (2.28)
In two cases, we can re-use the results of Section 2.1.3.

c 1 = 0 N * 1 = 0, N * p = λ µ p (1 -δ)
.

c 1 ≥ c ′ 1 N * 1 = λ µ 1 (1 -δ) , N * p = 0.

Conclusion

The case of non-cooperative robots was considered for which we have derived a closedform expression for the optimal number of robots. Then we have considered the case of cooperative robots where loads can be carried either by a single robot (1-bot) or by several robots that cooperate (p-bot). The fleet sizing problem can be formulated as a mathematical programming. We have distinguished several scenarios, depending on the respective carrying capacity of 1-bots and p-bots. Our mathematical model allows us to determine the most profitable number of robots that should cooperate. If the capacity of p 1-bots is smaller than the capacity of a single p-bot, then using exclusively p-bots or with a mix of 1-bots can lead to a significant cost decrease. Otherwise, it is optimal to use exclusively 1-bots. We have also addressed the infinite horizon problem which models a fleet of vehicles operating permanently and leads to simpler results.

Chapter 3

Transport of heterogeneous loads In this and later chapters, we consider elementary robots that can be connected in different ways in order to transport loads of different types. These robots can be assembled in different ways over time to adapt to the loads to be transported. This connection and disconnection between robots are called reconfiguration. The objective is to determine the optimal number of elementary robots required to transport various loads within a specified time frame. We formulate this problem as an integer linear program. Then, we investigate the special cases with two types of loads, two allowed configurations (1-bot and p-bot with p ≥ 2) and unit capacities.

Some of the results obtained in this chapter have been published in [START_REF] Chaikovskaia | Sizing of a fleet of cooperative and reconfigurable robots for the transport of heterogeneous loads[END_REF].

Assumptions and notations

We consider a fleet of N mobile elementary robots able to cooperate to transport loads of different types. An elementary robot is abbreviated as bot. A p-bot is a configuration where p elementary robots cooperating on the same transportation task. A 1-bot is an elementary robot working alone. A maximum of P elementary robots can cooperate.

Therefore the set of possible configurations is {1, • • • , P}.

There are n k loads of type k to be transported (k = 1, • • • , K). All the loads to be moved are located in the loading area of the warehouse and must be transported by the pbots to the unloading area. A p-bot can only carry one type of load at a time and can simultaneously carry c pk loads of type k. Hence, c pk is called the capacity of the pbot. We assume that for each type of load there is at least one configuration capable of carrying it.

The time horizon is divided into T periods (t = 1, • • • , T). At the beginning of each period, the robots are located in the loading area and can be reconfigured. Note that the time of reconfiguration is not taken into account.

In each period, after the reconfiguration of robots, p-bots have time to complete the following four steps of a delivery, namely: loading, loaded trip, unloading and empty return trip.

We consider three types of costs: a fixed cost per elementary robot linked to its acqui-3.1. Assumptions and notations sition or rental, a variable cost linked to the distance traveled by the robots and a fixed cost independent of the size of the fleet (hardware and software infrastructure). The fixed cost of an elementary robot is denoted α. The cost of a round trip for an elementary robot is denoted β and it follows that the cost of a round trip for a p-bot is pβ.

Finally, the fixed cost of a fleet is denoted γ. Thus, the cost of a fleet of N elementary robots performing M round trips is αN + βM + γ. In the following, we won't consider γ because it is a constant in the optimization problem.

The objective is to determine the number of elementary robots needed to transport all the loads over the time horizon at minimum cost. We consider two variants. In the first variant, reconfiguration is prohibited and the configurations of the robots are fixed over the entire horizon. The optimal number of elementary robots is denoted by N W in this case. In the second variant, reconfiguration is allowed and the configurations can be changed at the start of each period. The optimal number of elementary robots is denoted N R in this case. If we do not consider the cost related to the travelled distance,

i.e. if we take β = 0, then N R and N W represent the minimum number of robots with or without reconfiguration respectively.

We now remind the main notations introduced in this section:

• k: index for load type (k ∈ {1, • • • , K}) • p: index for configuration (p ∈ {1, • • • , P}) • t: index for time period (t ∈ {1, • • • , T})
• n k : number of loads of type k

• c pk : capacity of a p-bot carrying loads of type k

• α: fixed cost of the acquisition of an elementary robot

• β: cost of a round trip for an elementary robot

• N W : optimal number of elementary robots when reconfiguration is prohibited

• N R : optimal number of elementary robots when reconfiguration is allowed

Mathematical formulations

In this part, we propose two ILPs in order to formulate the two variants of the problem of minimizing the number of bots, with or without reconfiguration.

Without reconfiguration

We first assume that reconfiguration is prohibited. We use the following decision variables:

• N p : total number of p-bots

• N t pk : number of p-bots carrying loads of type k in period t

The number of elementary robots is then N W = ∑ P p=1 pN p . The optimization problem can be formulated by the following ILP:

min α P ∑ p=1 p • N p + β T ∑ t=1 K ∑ k=1 P ∑ p=1 p • N t pk (3.1)
subject to :

T ∑ t=1 P ∑ p=1 c pk • N t pk ≥ n k ∀k (3.2) N p ≥ K ∑ k=1 N t pk ∀t, ∀p (3.3) N p ∈ N, N t pk ∈ N ∀k, ∀p, ∀t (3.4)
Constraint (3.2) means that the total capacity of the fleet along the time horizon must be able to transport all loads of each type. Constraint (3.3) means that the number N p of p-bots must be greater than or equal to the number of p-bots used over each period.

With reconfiguration

When the reconfiguration is allowed, we use the same decision variables, with the difference that N R = N because each p-bot can be split into p number of bots, and the problem can be formulated by the following ILP:

min αN + β T ∑ t=1 K ∑ k=1 P ∑ p=1 p • N t pk (3.5)
subject to :

T ∑ t=1 P ∑ p=1 c pk • N t pk ≥ n k ∀k (3.6) N ≥ K ∑ k=1 P ∑ p=1 p • N t pk ∀t (3.7) N ∈ N, N t pk ∈ N ∀k, ∀p, ∀t (3.8) Constraint (3.6
) is similar to that of the problem without reconfiguration. Constraint (3.7) means that the number of elementary robots used, N, must be greater than or equal to the number of elementary robots used over each period.

Minimizing the number of robots

We assume in all this section that β = 0. Therefore N R and N W represent the minimum number of elementary robots needed to carry all the loads over the time horizon with or without reconfiguration respectively. In this section, we derive first closed-form formulas for the optimal number of robots for two types of loads. Then we study the case with unit capacities.

Two types of loads

We suppose that we have a wareshouse that handles only boxes and pallets. We obtain additional results for the special case of two types of loads and two possible configurations (1-bot or p-bot with p ≥ 2). We assume that there are n 1 ≥ 1 loads of type 1 and n 2 ≥ 1 loads of type 2. Capacities of each configuration are summarized in Table 3. We can imagine that loads of type 1 and 2 correspond to respectively small (S) and medium (M) loads. The problem simplifies considerably because there is only one way to transport loads of type 2 and we can obtain analytical formulas for N R and N W . Moreover, when c p1 ≥ p • c 11 , reconfigurability does not allow to reduce the number of robots. Theorem 3.3.1 summarizes these results. In this theorem, x + = max(0, x) denotes the positive part of x.

Type of load Configuration

k = 1 (S) k = 2 (M) 1-bot c 11 0 p-bot c p1 c p2
Theorem 3.3.1 (Two types of loads).

Let n ′ 1 = T • n 2 T•c p2 -n 2 c p2 , n r 1 = (n 1 -n ′ 1 • c p1 ) + and ñr 1 = n r 1 - n r 1 T•c p1 T • c p1 + . If c p1 < p • c 11 , then N W = p • n 2 T • c p2 + n r 1 T • c 11 , (3.9) N R = p • n 2 T • c p2 + (n 1 -n ′ 1 • p • c 11 ) + T • c 11 . (3.10) If c p1 ≥ p • c 11 , then N W = N R = p n 2 T • c p2 + p n r 1 T • c p1 + min ñr 1 T • c 11 , p . (3.11)
Proof. We distinguish two cases. Whatever the case, we assume that the p-bots are fully filled before a new p-bot is loaded so that we have no more than one p-bot with free periods at the outcome of the assignment of loads of type 2.

Case 1 : c p1 < p • c 11 In this case, note that it is always more interesting to use 1-bots to transport loads of type 1. Let's start by determining N W . The general idea is as follows:

1. We first assign loads of type 2 to p-bots;

2. If the last p-bot is not used over all the periods, we assign as many loads of type 1 as possible to the last p-bot assigned for loads of type 2;

3. The remaining loads of type 1 are assigned to 1-bots.

In step (1), the number of p-bots needed to carry loads of type 2 is

n 2 T • c p2 . (3.12)
We assume that the p-bots are fully filled before a new p-bot is loaded, so that there is no more than one p-bot with free periods at the end of the assignment of loads the second type. Let n ′ 1 be the number of periods not used by the last p-bot:

n ′ 1 = n 2 T • c p2 T - n 2 c p2 . (3.13) Indeed, it takes n 2 c p2
periods to transport loads of type 2 with p-bots and the total available number of periods for p-bots is n 2 T•c p2 T.

In step (2), we can therefore assign up to n ′ 1 • c p1 loads of type 1 to the last p-bot.

In step (3), it remains n r 1 = (n 1n ′ 1 • c p1 ) + loads of type 1 that requires n r 1 T•c 11 1-bots.

We conclude that

N W = p • n 2 T • c p2 + n r 1 T • c 11 . (3.14)
We now determine N R . There are three steps as for the calculation of N W .

Step ( 2) is modified as follows: if the last p-bot is not used over all the periods, it is reconfigured into p 1-bots to which we assign as many loads of type 1 as possible (at most n ′ 1 • p • c 11 ). For step (3), then (n 1n ′ 1 • p • c 11 ) + loads of type 1 remain to be transported by 1-bots. We conclude that

N R = p • n 2 T • c p2 + (n 1 -n ′ 1 • p • c 11 ) + T • c 11 . (3.15) Case 2 : c p1 ≥ p • c 11
In step (4), we assign the last ñr 1 loads of type 1 to 1-bots if it requires less than p 1-bot and to a p-bot otherwise. Hence we need the following additional number of elementary robots :

min ñr 1 T • c 11 , p . (3.19)
In the end,

N W = N R = p n 2 T • c p2 + p n r 1 T • c p1 + min ñr 1 T • c 11 , p .
(3.20)

Unit capacities

We now consider K types of loads and P = K configurations with 0-1 capacities. More precisely, the capacity matrix is lower triangular and is such that c kp is equal to 1 if p ≥ k and 0 otherwise. We also assume that there is at least one load of type K (n K ≥ 1), otherwise the problem reduces to a problem with (K -1) types of loads.

Table 4 illustrates the capacity matrix with K = 3 types of loads. We can imagine that loads of type 1, 2, 3 correspond to respectively small (S), medium (M) and large (L) loads. Then small loads can be transported by all configurations, medium loads by 2-bots or 3-bots and large loads only by 3-bots. When considering such capacity structure, we are able to derive simple formulas for the minimum number of elementary robots with or without reconfigurations. In the case without reconfiguration, we obtain a result that holds for an arbitrary number of types of loads K. In the case with reconfiguration, we obtain a result up to 3 types of loads. With 4 types of loads or more, the problem becomes much more complex as the reconfiguration decision is more complex as we can, for instance, reconfigure a 4-bot into a 3-bot plus a 1-bot or into two 2-bots.

Type of load Configuration

k = 1 (S) k = 2 (M) k = 3 (L) 1-bot 1 0 0 2-bot 1 1 0 3-bot 1 1 1

Theorem 3.3.2 (Triangular unit capacities). Let n ′

K = 0 and for k = K, • • • , 2 N k = (n k -n ′ k ) + T (3.21) n ′ k-1 = n ′ k -n k + N k • T (3.22) Then N W = K ∑ k=1 k • N k (3.23)
and, for K ≤ 3,

N R = K ∑ k=2 k • N k + (n 1 -n ′ 1 -∑ K-1 k=1 n ′ k ) + T (3.24)
Note that (3.24) holds for K > 3 if we additionally assume that there are enough loads of type 1 to fill the holes (n 1 ≥ K(T -1)). In this theorem, N k represents the number of required k-bots and n ′ k the number of free periods in the last used configuration after the assignment of loads of type k + 1, • • • , K.

Proof. Assume in all this proof that K = P and that c kp is equal to 1 if p ≥ k and 0 otherwise.

Without reconfiguration

We begin by exploring the case without reconfiguration. Note that, if you have a p-bot, it is optimal to use it as a priority to transport loads with a higher index k. Remind that we denote by N k the minimum number of required k-bots. In what follows, we

determine N k , N k-1 , • • • , N 1 in this order.
We also denote by n ′ k the number of free periods in the last used configuration after the assignment of loads of type k + 1, • • • , K. It is optimal to use these free periods in priority for loads of type k, then of type k -1 and so on. Figure 31 illustrates notation of n ′ k . In this figure, n ′ 3 = 4 means that we have 4 free periods for the transport of the loads of type 3 (L). n ′ 2 = 2 means that we have 2 free periods for the transport of loads of type 2 (M). n ′ 1 = 3 means that we have 3 free periods for the transport the loads of type 1 (S).

T = 5, n 1 = 1, n 2 = 4, n 3 = 2, n 4 = 1)
The number of K-bots necessary to transport loads of type K is

N K = n K T . (3.25)
It then may remain available capacity for the last K-bot. More precisely, the number of free periods for the last K-bot is

n ′ K-1 = N K • T -n K = n K T T -n K . (3.26)
These n ′ K-1 free periods are used to transport in priority loads of type (K -1) and it remains to transport (n K-1n ′ K-1 ) + loads of type K -1. The number of (K -1)-bots necessary to transport these remaining loads of type (K -1) is then

N K-1 = (n K-1 -n ′ K-1 ) + T . (3.27)
Assume now that the number of p-bots, N p , has been determined for p

= k + 1, • • • , K
and that there remains n ′ k free periods on these configurations. These n ′ k free periods are assigned in priority to loads of type k and then (n kn ′ k ) + loads of type k remain to be carried. The number of additional k-bots required is

N k = (n k -n ′ k ) + T . (3.28)
The number of free periods for the last k-bot is

N k • T -(n k -n ′ k ) + .
There remains also (n ′ kn k ) + free periods after the transportation of loads of type j (for j > k). It follows that

n ′ k-1 = N k • T -(n k -n ′ k ) + + (n ′ k -n k ) + (3.29) = N k • T + n ′ k -n k . (3.30)
In the end, we have

N W = K ∑ k=1 k • N k (3.31)
with

N k = (n k -n ′ k ) + T (3.32) n ′ K = 0 (3.33) n ′ k-1 = n ′ k -n k + N k • T (for k = K, • • • , 2) (3.34)
With reconfiguration K = 1: With a single type of load, we have immediately N R = n 1 T and it is easy to check that (3.24) gives the same result. K = 2: When there are two types of loads, we need N 2 2-bots, as in the case without reconfiguration. If there remains free periods on the last 2-bot, it is optimal to reconfigure into two 1-bots. On the n ′ 1 free periods of the last 2-bot, we can transport up to 2n ′ 1 loads of type 1. It remains (n 1 -2n ′ 1 ) + loads of type 2 that require

(n 1 -2n ′ 1 ) + T additional 1-bots. In the end, the optimal number of elementary robots is

N R = 2 • N 2 + (n 1 -2n ′ 1 ) + T (3.35)
and we have shown that (3.24) holds. K = 3: Let's detail now the case with 3 types of loads. We need N 3 3-bots to transport loads of type 3, as in the case without reconfiguration. If there remains free periods on the last 3-bot, it is optimal to reconfigure into a 2-bot plus a 1-bot. On the n ′ 2 free periods of the last 3-bot, we can then transport up to n ′ 2 loads of type 2 and n ′ 2 loads of type 1. It remains (n 2n ′

2 ) + loads of type 2 that require N 2 =

(n 2 -n ′ 2 ) + T additional 2-bots, as in the case without reconfiguration. On the last 2-bots, there are n ′ 1 free periods which can be used to transport up to 2n ′ 1 loads of type 1. It remains (n

1 -n ′ 2 -2n ′ 1 ) loads of type 1 that require (n 1 -n ′ 2 -2n ′ 1 ) + T
additional 1-bots. If ever n 2 = 0, then the 3-bot reconfigures 3.4. Number of robots saved through reconfigurability 55 into three 1-bots and n ′ 2 = n ′ 1 . In the end, we have

N R = 3 • N 3 + 2 • N 2 + (n 1 -n ′ 2 -2n ′ 1 ) + T (3.36)
and we have shown that (3.24) holds.

Number of robots saved through reconfigurability

Again, we assume in all this section that β = 0 and N R and N W represent the minimum number of elementary robots (with or without reconfiguration respectively).

Below we show that we can at best divide the fleet size, by the number of types of loads K, using reconfiguration.

Theorem 3.4.1 (General case). For the problem described in Section 3.1, when β = 0, we have , to note that arg min x f (x) is the set of x for which f (x) attains the function's smallest value (if it exists).

1 ≤ N W N R ≤ K. ( 3
To transport all the loads without reconfiguration, it is necessary

N W = ∑ k p min n k Tc p min k ≤ ∑ k p k n k Tc p k k ≤ ∑ k   p k     T c p k k N R p k Tc p k k       = (3.39) = ∑ k p k N R p k ≤ ∑ k p k N R p k = KN R (3.40)
Chapter 3. Transport of heterogeneous loads

We now present an instance for which N W N R goes to K when P goes to infinity. Assume that c pk equal 1 if p = P -(Kk) and 0 otherwise.

Assume also that P > K and that there is one load of each type. We have N R = P and N W = P + (P -1)

+ • • • + (P -(K -1)) = KP -(1 + 2 + • • • + (K -1)) = KP - K(K -1) 2 . Thus N W N R = K - K(K -1) 2P
which goes to K when P goes to infinity.

Two types of loads

Once we showed that by allowing reconfiguration, the minimum number of robots can be divided by a factor up to K in general case, we now study the case of two types of loads described in Section 3.3.1. We can show that the number of robots saved by reconfigurability is at most p elementary robots.

Theorem 3.4.2 (Two types of loads). With two types of loads, the absolute gain is bounded as follows :

0 ≤ N W -N R ≤ p. (3.41) Proof. When c p1 ≥ p • c 11 , the result is trivial because N W = N R .
In the following, we assume that c p1 < p • c 11 . According to Theorem 3.3.1, we have

N W -N R = (n 1 -n ′ 1 • c p1 ) + T • c 11 - (n 1 -n ′ 1 • p • c 11 ) + T • c 11 (3.42) ≤ (n 1 -n ′ 1 • c p1 ) + T • c 11 + 1 - (n 1 -n ′ 1 • p • c 11 ) + T • c 11 (3.43) = (n 1 -n ′ 1 • c p1 ) + -(n 1 -n ′ 1 • p • c 11 ) + T • c 11 + 1. (3.44)
Three cases are then possible. Assume first that n

1 ≤ n ′ 1 • c p1 . Then (n 1 -n ′ 1 • c p1 ) + = (n 1 -n ′ 1 • p • c 11 ) + = 0. With (3.44), it comes N W -N R ≤ 1 ≤ p. Assume now that n ′ 1 • c p1 < n 1 ≤ n ′ 1 • p • c 11 . Then we have (n 1 -n ′ 1 • c p1 ) + = n 1 -n ′ 1 • c p1 , (n 1 -n ′ 1 • p • c 11 ) + = 0 and N W -N R ≤ n 1 -n ′ 1 • c p1 T • c 11 + 1 (3.45) < n 1 T • c 11 + 1 (3.46) < n 1 n ′ 1 • c 11 + 1 (3.47) ≤ p + 1. ( 3
N W -N R ≤ p. Finally, assume that n 1 ≥ n ′ 1 • p • c 11 .
We can therefore remove the positive parts in (3.44):

N W -N R ≤ n 1 -n ′ 1 • c p1 T • c 11 + 1 - n 1 -n ′ 1 • p • c 11 T • c 11 (3.49) = n ′ 1 (p • c 11 -c p1 ) T • c 11 + 1 (3.50) < p • c 11 -c p1 c 11 + 1 (3.51) ≤ p + 1. (3.52) As n ′ 1 < T, again N W -N R < p + 1 implies that N W -N R ≤ p.
In any case, we have

N W ≤ N R + p.
We now provide a simple example where the upper bounds of theorems 3.4.1 and 3.4.2 are reached. Let's take

T = 3, p = 2, c 11 = c 22 = 1, c 12 = c 21 = 0, n 1 = 4 and n 2 = 1.
Then N R = 2 and N W = 4. Loads of type 1, 2 correspond to respectively small (S) and medium (M) loads. Figure 32 represents the Gantt chart for this example. On the ordinate axis is the reference number of the bots, on the abscissa axis is the reference number of the period. In each rectangle is indicated the type of load that is transported.

In the optimal strategy with reconfiguration, a 2-bot carries one medium load in period 1 and then is reconfigured into two 1-bots that carry the small loads in periods 2 and 3.

In the optimal strategy without reconfiguration, the 2-bot can not be split and we need two additional 1-bots. We have seen that the gain can be important in the previous example with a fleet divided by two. However, the gain in relative value is limited for large robot fleets. Indeed, as a consequence of Theorem 3.4.2, we have

N W N R ≤ 1 + p N R . ( 3

Unit capacities

We now compare the optimal numbers of robots with unit capacities, in the setting described in Section 3.3.2. As formula (3.24) holds only for K ≤ 3, we assume that there are at most 3 types of loads.

Theorem 3.4.3 (Unit capacities). When K ≤ 3, we have

0 ≤ N W -N R ≤ K -1. (3.54)
Proof. From (3.23) and (3.24), we obtain that Note that the number of free periods n ′ k can not exceed T -1 as there is at least one period used to transport some load. Thus n

N W -N R = (n 1 -n ′ 1 ) + T - n 1 -n ′ 1 T - 1 T • K-1 ∑ k=1 n ′ k + . ( 3
′ k ≤ T -1 for k = 1, • • • , K -1. It follows that N W -N R ≤ (n 1 -n ′ 1 ) + T - n 1 -n ′ 1 T -(K -1) + . (3.56)
To conclude we need the following property. Let b a non-negative integer and x a real number. Then ⌈x + ⌉ -⌈(xb) + ⌉ ≤ b. The proof of this property is straightforward.

⌈x + ⌉ -⌈(x -b) + ⌉ =          0 if x < 0 x if 0 ≤ x ≤ b b if x > b ≤ b
Using this property and (3.56) gives

N W -N R ≤ K -1.
This theorem shows that the gain is not substantial in absolute value. When K = 1, the gain is null as expected. When K = 2, we can gain at most one elementary robot by using reconfigurability. When K = 3, the gain is at most of 2 elementary robots. Note that Theorem 3.4.3 holds for K > 3 if we additionally assume that there are enough loads of type 1 to fill the holes (n 1 ≥ K(T -1)).

Theorem 3.4.3 implies that

N W N R ≤ 1 -K-1 N R . As n K ≥ 1, we have N R ≥ K and we get that 1 ≤ N W N R ≤ 2 - 1 K . ( 3

Example with two types of loads

In the following example, loads of type 1, 2 correspond to respectively small (S) and medium (M) loads. Let's take T = 2, n 1 = 2 and n 2 = 2. Then N R = 2 and N W = 3 and N W N R = 3 2 . Figure 33 represents the Gantt chart for this example. On the ordinate axis is the reference number of the bots, on the abscissa axis is the reference number of the period. The type of loads the robot is carrying is indicated in each rectangle. When reconfiguration is allowed, a 2-bot can carry one medium load, then it reconfigures into two 1-bots to carry 2 small loads. If the reconfiguration is not allowed, the 2-bot is not able to split into two independent elementary robots, so it carries a single small load.

Example with three types of loads

In the following example, loads of type 1, 2, 3 correspond to respectively small (S), When reconfiguration is allowed, a 3-bot can carry one load of type L, then it reconfigures into 1-bot and 2-bot and then into three 1-bots to carry 6 small loads. If the reconfiguration is not allowed, the 3-bot is not able to split into two independent robots, so it carries a single large load and then two medium loads and two small loads.

Demand per period

For now, we have shown that the gain in relative value, N W /N R , can be significant while the gain in absolute value, N W -N R , remains limited. We will now propose a variant of the problem where the gain in absolute value can be significant.

We now assume that the demand to transport loads is per period and not over the whole horizon. More precisely, there are n kt loads of type k to be transported in period t (instead of n k loads of type k to be transported over the whole horizon in the original model). This may correspond, for example, to the activity of a warehouse that delivers one type of load on Monday and another type of load on Tuesday. With this new assumption, the ILPs remain unchanged except that constraints (3.2) and (3.6) have to be replaced by the following constraint:

P ∑ p=1 c pk • N t pk ≥ n kt ∀k, ∀t (3.58)
We will now present a simple example where the gain in absolute value can be significant. Consider two types of loads and two periods where n 1 loads have to be transported in period 1 and n 2 loads have to be transported in period 2 (see Table 5b for a summary of demands). Type 1 (S) loads can only be transported by 1-bots while type 2 (M) loads can only be transported by p-bots with p ≥ 2 (see Table 5a for a summary of capacities). For this example, the minimum numbers of elementary robots are easy to derive :

Type of load Configuration

k = 1 (S) k = 2 (M) 1-bot 1 0 p-bot 0 1 (a) Capacities Period Type of load t = 1 t = 2 k = 1 (S) n 1 0 k = 2 (M) 0 n 2 (b) Demands
N W = n 1 + pn 2 , (3.59) N R = (n 1 -pn 2 ) + + pn 2 (3.60) = max(n 1 , pn 2 ).
It follows that

N W -N R = min(n 1 , pn 2 ), (3.61) N W N R =            1 + n 1 pn 2 if n 1 ≤ pn 2 1 + pn 2 n 1 if n 1 > pn 2 .
(3.62)

Figure 35 plots the effect of n 1 on the difference N W -N R and the ratio N W N R .

When

n 1 = pn 2 , the ratio N W /N R is

Conclusion

In this chapter, mathematical programs were obtained in the form of ILP for load transportation with and without the possibility of reconfiguration. This allows us to find out which configuration of the robot in which period and for the transportation of which with unit capacities is also studied. For this case, we have derived closed-form expressions for the minimum number of robots up to three load types with reconfiguration, and for any number of load types without reconfiguration. We have showed that reconfigurability can divide the minimum number of elementary robots up to a factor of K (with K the number of load types). For the two special cases, we show that the gain in number of robots is limited but may be significant for small fleets. Finally, in a variant where the demand is per period of time and not on the whole time horizon, we have showed that the gain in number of robots is not bounded.

Chapter 4. Complexity analysis and heuristic algorithms

In this chapter, we study the complexity of the problem, introduced in Chapter 3, where the transport of loads from one area to another is performed by reconfigurable mobile robots. After studying the complexity of the problem, we focus in this chapter on finding an effective heuristic to solve the problem in polynomial time.

Problem description and model formulation

The Multi_Bot problem

We consider here a fleet of mobile elementary robots which cooperate in order to transport loads of different types. An elementary robot is abbreviated as a bot. A p-bot is a configuration which makes p elementary bots cooperate on the same transportation task. A maximum of P elementary bots may cooperate, which identifies the feasible configuration set with the set P = {1,. . . , P}, P being one of the inputs of our problem.

There are K load types and we denote by K = {1, . . . , K} the set of load types. The transportation demand for every type k is denoted by n k . So K and vector n = (n k , k = 1, . . . , K) is another part of our inputs. Given a load type k, there is at least one value p such that related p-bot is able to transport load type k.

All transportation tasks must be executed within a discrete time horizon T = {1,. . . , T}.

At the beginning of a given period t, the bots are located inside a loading area and may be put together (reconfigured) in order to provide us with the best fitted p-bots for the current period. During a given period t, a p-bot reconfigured this way may only deal with a single type k, and the number of loads of type k that it can transport cannot exceed a threshold c pk . So T, as well as vector C = (c pk , p = 1, . . . , P, k = 1, . . . , K)

becomes also part of our inputs.

Our purpose is to simultaneously minimize the number of bots involved into the process, and the number of transportation transactions (trips) performed throughout the periods 1, . . . , T. We see that if H t denotes the number of bots required to be active during period t, then:

• The number of bots necessary to achieve the whole process is H Max = max t H t ;

• The number of trips necessary to achieve the whole process is H = ∑ t H t .

Problem description and model formulation 67

We consider two scaling coefficients α and β and our objective is to minimize the weighted cost:

Cost = α • H Max + β • H. (4.1)
We call Multi_Bot problem the decisional problem described this way.

A Multi_Bot model

For any period t, configuration p and load type k, we denote by X t pk the number of trips which will take place at period t, and involve the transportation of load type k by a p-bot. Then we see that any H t may be written H t = ∑ k,p p • X t pk , while the demand constraint related to the demand vector n = (n k , k = 1, . . . , K) may be formulated as follows: For any load type k, ∑ t,p c pk • X t pk ≥ n k . It comes that our Multi_Bot problem may be formalized as follows.

Inputs:

• A set P = {1, . . . , P} of configurations;

• A set T = {1, . . . , T} of periods;

• A set K = {1, . . . , K} of load types;

• A non negative integral vector C = (c pk , p = 1, . . . , P, k = 1, . . . , K), which represents capacities (the number of load types k which may be transported by a single p-bot during a period);

• A non negative integral vector n = (n k , t = 1, . . . , K), which represents transportation demands.

• Two scaling non negative rational coefficient α and β.

Objective: Compute a non negative integral vector X = (X t pk , t = 1, . . . , T, p = 1, . . . , P, k = 1, . . . , K) such that:

• For any k, ∑ t,p c pk • X t pk ≥ n k ; • α • (max t ∑ k,p p • X t pk ) + β • (∑ t,p,k p • X t pk ) is the smallest possible.
Observe that the above formulation is not an ILP one. Still, it is easy to turn it into such an ILP model by introducing an additional variable Y that replaces max t ∑ k,p p • X t pk and adding the following constraints: for any t, Y ≥ ∑ k,p p • X t pk .

Structural properties of the Multi_Bot problem

Dealing with the design of algorithms, both for the specific cases when one among the parameters P, T, K is equal to 1 and for the general case, is going to require some better understanding of our Multi_Bot problem. The present section is going to provide us with additional information about Multi_Bot solutions.

Encoding size and decisional reformulation

Given a Multi_Bot instance Multi_Bot. P, T, K being defined as respectively configuration, period and load type sets, the encoding size of a Multi_Bot is:

Size(Multi_Bot) = P + T + K + ∑ k,p (1 + log 2 c pk ) + ∑ k (1 + ⌈log 2 n k ⌉) + (1 + log 2 α) + (1 + log 2 β).
As it is the case when a problem involves both combinatorial inputs and numbers [START_REF] Garey | A guide to the theory of NP-completeness[END_REF], this expression clearly distinguishes between the combinatorial part of the encoding size which is due to the sets P, T, K and the numerical part of this size related to numbers α, β, c p,k and n k , k = 1, . . . , K, p = 1, . . . , P.

We get a feasible Multi_Bot solution by setting X t pk = n k for any t, p, k. Related H value is equal to

K • P • T • n Max

Multi_Bot_dec(S):

Compute non negative integral vector X = (X t pk , k = 1, . . . , K, p = 1, . . . , P, t = 1, . . . , T) such that:

∑ t,p c pk • X t pk ≥ n k ∀k (4.2) α • (max t ∑ k,p p • X t pk ) + ∑ t,p,k p • X t pk ≤ S (4.3) Since log 2 (2n Max • sup(α, β) • K • P • T)

Reinforcement of the Multi_Bot model

We are now going to see that we may impose additional constraints to the Multi_Bot model without deteriorating its optimal value. Those constraints will be the key for our algorithms.

For every k, let us set p 0 (k) = arg sup p (c pk /p). This quantity p 0 (k) is the most efficient configuration for the transportation of k.

Then the following lemma bounds the values X t pk , p ̸ = p 0 (k): does not modify the optimal value of the instance Multi_Bot :

X t pk ≤ p 0 (k) GCD(p 0 (k), p) -1 ∀t, k, p ̸ = p 0 (k) (4.4)
In this lemma, GCD means Greatest Common Divisor.

Proof. Let X a feasible solution of the instance Multi_Bot and let us suppose that, for some (t, k) and for some p 1 ̸ = p 0 (k) we may write:

p 0 (k) = u • GCD(p 0 (k), p 1 ); p 1 = v • GCD(p 0 (k), p 1 ); X t p 1 ,k ≥ u.
Then we increase X t p 0 (k),k by v and decrease X t p 1 ,k by u. Doing this maintains (4.3)

since u • p 1 = v • p 0 . But the inequality p 0 (k) • c p 1 ,k ≤ p 1 • c p 0 (k),k
also keeps the quantity ∑ l,p c pk X l pk from decreasing and so (4.2) keeps holding. We can do this until (4.4) becomes satisfied and so we conclude. A consequence of above result is that we should focus, when dealing with any Multi_Bot instance, on the "critical" variables X t p 0 (k),k . The algorithm that we are going to describe in Section 4.4 for the general case will derive from this interpretation of Lemma 4.2.1 and from the way we are going to characterize the complexity of Multi_Bot. It will also rely on a time polynomial pre-process (Section 4.3.2) which will allow us to store in advance the decisions related to variables X t p(k),k , p ̸ = p 0 (k).

Let us now set:

• For any t, E t = ∑ k p 0 (k) • X t p 0 (k),k and F t = ∑ p̸ =p 0 (k),k p • X t pk ; • For any k, Q(k) = (p 0 (k) -1) • (P • (P + 1)/2 -p 0 (k)) + p 0 (k); • Q = ∑ k Q(k).
Q is bounded by a polynomial function of Size(Multi_Bot). Then the following lemmas 4.2.2 and 4.2.3 allow us to bound differences |E t -E l | and p 0 (k)

• |X t p 0 (k),k -X l p 0 (k),k
| in a way which will open the way to time-polynomial dynamic programming algorithms for the target cases when one among parameters P, T and K is equal to 1. Lemma 4.2.2. Given a Multi_Bot instance Multi_Bot. Then imposing the following constraint (4.5) does not modify the optimal value of the instance Multi_Bot :

|E t -E l | = ∑ k p 0 (k) • X t p 0 (k),k -∑ k p 0 (k)X l p 0 (k),k ≤ Q ∀t, l, t ̸ = l (4.5)
Proof. Let X a feasible solution of the instance Multi_Bot, which satisfies (4.4), and let us suppose that, for some t, l, we have E t -E l > Q. We may choose t 0 and l 0 with this property and such that E t 0 is maximal and E l 0 is minimal. Then must exist k 0 such X t 0 p 0 (k 0 ),k 0 ≥ 1, and so we may try to decrease X t 0 p 0 (k 0 ),k 0 by 1 and to increase X l 0 p 0 (k 0 ),k 0 by 1. Doing this keeps constraints (4.2) and (4.4). Also, we get H t 0 ≥ E t 0 and

H l 0 = E l 0 + F l 0 ≤ E l 0 + ∑ k,p̸ =p 0 (k 0 ) (p 0 (k 0 ) -1) • p ≤ E l 0 + Q -p 0 (k 0 )
. It comes that even after that we increased X l 0 p 0 (k 0 ),k 0 by 1, the new value H l 0 does not exceed the previous value H t 0 and so H Max did not increase. Neither did H = ∑ t H t so αH Max + βH did not increase. But we also see that one of the following properties hold:

• The value max It comes that applying above correction process as many times as necessary leads us to (4.5).

Lemma 4.2.3. Given a Multi_Bot instance Multi_Bot, reinforced by (4.4), (4.5). Then imposing the following constraint (4.6) does not modify the optimal value of the instance Multi_Bot:

p 0 (k) • |X t p 0 (k),k -X l p 0 (k),k | ≤ Q + TP 2 ∀t, l, t ̸ = l (4.6)
Proof. We know that for any t, l, t ̸ = l:

|E k -E l | ≤ Q.
Let us suppose that, for some t, l, t, and for some k, we have:

X t p 0 (k),k -X l p 0 (k),k | ≥ Q + TP 2 + 1. Then (4.5) implies the existence of k ′ ̸ = k such that p 0 (k ′ ) • X l p 0 (k ′ ),k ′ ≥ P 2
, which also implies that X l p 0 (k ′ ),k ′ ≥ P ≥ p 0 (k). By the same way, we clearly have X t p 0 (k),k ≥ P ≥ p 0 (k ′ ). So we modify current vector X as follows:

• Make X t p 0 (k),k decrease by p 0 (k ′ ) and X l p 0 (k),k increase by p 0 (k ′ );

• Make X t p 0 (k ′ ),k ′ increase by p 0 (k) and X l p 0 (k ′ ),k ′ decrease by p 0 (k).

Doing this does not modify values ∑ t,p c pk X t pk and H t and so maintains constraints (4.2), (4.5) as well as the cost value. It also maintains constraints (4.4). Let us now check that we can iteratively perform this procedure until getting (4.6). In order to do it, we choose t, l such that X t p 0 (k),k -X l p 0 (k),k is maximal. Then we choose k ′ such that X l p 0 (k ′ ),k ′ ≥ X t p 0 (k ′ ),k ′ . We can do it because of (4.5). Once above procedure has been applied to X, at least one of the two following conditions holds:

• The value sup k,t,l s.t. t̸ =l X t p 0 (k),k -X l p 0 (k),k have decreased;

• Above value remains the same, but the number of 3-uples (t, l, k) which achieve sup k,t,l s.t. t̸ =l X t p 0 (k),k -X l p 0 (k),k have decreased.

This allows to conclude.

As previously told, the upper bounds Q and Q + TP 2 involved in lemmas 4.2.2 and 4.2.3 are polynomial functions of the encoding size of our Multi_Bot instances. This will provide us in Section 4.3 with the key for the design of the time-polynomial dynamic programming algorithms for the exact resolution of Multi_Bot when K = 1 and T = 1.

Those algorithms will work while controlling the way the sum ∑ k,t X t p 0 (k),k evolves and doing in such a way that even if this quantity may become very large, its difference with some pre-computed lower bound remains bounded by a polynomial function of the size of the instances.

The Multi_Bot problem is strongly NP-Hard

Section 4.2.1 tells us that we only need to prove that Multi_Bot_dec is strongly NP-Complete. We are going to do it in the usual way, by checking that Multi_Bot_dec can be polynomialy reduced to the Bin_Packing problem [START_REF] Garey | A guide to the theory of NP-completeness[END_REF], or, in other words, that Bin_Packing is a particular case of Multi_Bot_dec.

This argument involving the Bin_Packing problem will not only provide us here with a theoretical result, but also with the basis for the design in Section 4.4 of an efficient heuristic algorithm for the general case.

A Bin_Packing instance BP is characterized by: • A set I = {1, . . . , I} of items such that for any item i ∈ I, is provided with a weight w i ;

• A set B = {1, . . . , B} of identical boxes, all with a same capacity ρ.

Then we want to compute an assignment σ from I to B, consistent with the capacities of the boxes, that means such that for any b ∈ B, ∑ i s.t. σ(i)=b w i ≤ ρ.

We know that Bin_Packing is strongly NP-Complete: Strongly means that there exists a polynomial function Q of I and B such that if we restrict ourselves to instances BP such that weights w i and the capacity ρ are bounded by Q(I, B), then resulting problem remains NP-Complete [START_REF] Garey | A guide to the theory of NP-completeness[END_REF]. In order to prove that Multi_Bot_dec Let us start from a Bin_Packing instance BP such that number ρ and coefficients w i are all bounded by Q(I, B), with polynomial function Q as above. We notice that if we add B • ρ -∑ i w i items with weight 1 then we do not modify the feasibility of BP. So we may suppose that BP is such that:

B • ρ = ∑ i w i . ( 4.7)
Let us now derive from the instance BP a Multi_Bot_dec instance Multi_Bot_dec as follows:

• We set t = B: that means that we identify any box b with an index value t of Multi_Bot_dec.

• We set α = 1 and β = 1.

• We set K = Number of distinct values w i involved into vector w. We identify any existing weigth w i with an index value k of Multi_Bot_dec. K may be interpreted as an item type, characterized by its weight w(k). For instance, if we have 5 items with respective weights w 1 = 2, w 2 = 6, w 3 = 3, w 4 = 2 and w 5 = 6, then we get

K = {1, 2, 3}, with w(1) = 2, w(2) = 6, w(3) = 3.
• We set P = sup i w i . We identify any possible weigth w i with an index value p of Multi_Bot_dec.

• According to this, we set: c pk = w(k) if p = w(k) and c pk = 0 else.

• For any k, we set n k = w(k) • R k , where R k denotes the number of items i with weight w i = w(k)).

• Finally we set S = (B + 1)ρ.

According to this, X t pk refers to the number of items with weigth p and item type k which are assigned to box t. Constraints (4.2) means that all items should be assigned to some box t. Since (4.7) implies ∑ t,p,k pX t pk = Bρ, then (4.3) implies that every sum H t = ∑ p,k pX t pk should be equal to ρ.

If σ is a feasible solution of the Bin_Packing instance BP then we see that we get a feasible solution X of the instance Multi_Bot_dec by setting: X t w(k),k = number of items i with weight w(k) assigned to box t, and X t pk = 0 if w(k) ̸ = p. Conversely, if X is a feasible solution of the instance Multi_Bot_dec, then we get a solution σ of the instance BP by assigning X t w(k),k items with weight w(k) to box t.

The Code procedure which computes T, P, K together with coefficients S and n k , k ∈ K, clearly works in polynomial time (as a function of Q(I, B), I and B and thus also as a function of I and B). The Decode procedure which retrieves assignment σ from X works the same way. So we conclude.

Exact polynomial algorithms for special cases

Our purpose here is to prove that, in case one of the 3 main parameters K, T, P of the Multi_Bot problem is neutralized, that means is equal to 1, then Multi_Bot can be solved in polynomial time. Doing it will provide us with tools for the design in Section 4.4 of an efficient heuristic for the Multi_Bot problem. Since dynamic programming will be deeply involved, we are first going to recall a few things about dynamic programming.

A few things about dynamic programming

Dynamic programming [START_REF] Bellman | Dynamic programming[END_REF], abbreviated by DP, can be applied to a problem P if P can be rewritten in such a way it becomes equivalent to the search for a shortest or largest path in an acyclic network G P . Notice that while in most cases, the operator which underlies the notion of length of a path is the standard sum operator +, we may in some case deal with * , max or min operators. In any case Bellman principle is applied, which allows the computation, for any node x of G P , of the optimal value of a shortest (largest) path from origin x 0 to x according to the formula: V(x) = inf arcs e=(y,x) (V(y) +

Cost(e)). The key issue becomes related to the number of nodes in the network G P .

In many cases (the simplest ones), the node set of G P appears as a set of pairs (j, s), j = 0, 1, . . . , N + 1, and s belongs to a set S (j) of states related to time value j. L = Chapter 4. Complexity analysis and heuristic algorithms

The main components of a DP algorithm are:

• The time space L and, for every j, the state space S (j);

• For every (j, s), the decision set D (j, s) and the feasibility procedure O;

• The transition procedure T (j, s, d), which, to any (j, s) and any feasible decision n in D (j, s), makes correspond resulting pair (j + 1, s * ), together with cost C(j, s, d);

• The search strategy (forward, backward, . . . );

• Potential filtering devices, which aim at controlling the number of states in S (j), by killing states s which may be considered as not promising enough.

Pre-processing

This section is dedicated to pre-processing the variables X t pk , p ̸ = p 0 (k) and building the table Table_Bot. As told in Section 4.2, we are going to handle the general Multi_Bot problem while focusing on "critical" variables X t p 0 (k),k . More precisely, we shall neutralize the other variables X t pk , p ̸ = p 0 (k), while using a pre-process relying on Lemma 4.2.1 and the fact that every X t pk , p ̸ = p 0 (k), is bounded by (p 0 (k)/GCD(p 0 (k), p)) -1. The key for this approach is that for any t, k, if we know in advance the value W of ∑ p̸ =p 0 (k) pX t pk , then the best we can do is to compute values X t pk in such a way that ∑ p̸ =p 0 (k) c pk X t pk be the largest possible, that means as an optimal solution of the following Knapsack like problem Aux_Bot(k, W): c pk Y p is the largest possible.

Aux_Bot(k, W): Compute Y = (Y p , p ̸ = p 0 (k)),
We are going to check that solving this problem can be done in polynomial time through a single DP algorithm A_Bot. A_Bot will compute all 3-uples (W, V, Y) such that V and Y define an optimal solution of Aux_Bot(k, W) and which are Pareto optimal. Pareto optimal means here that there does not exist W ′ < W and Y ′ which is a feasible solution of Aux_Bot(k, W ′ ) and which achieves a value V ′ ≥ V. Then, performing A_Bot for any value k and storing resulting 3-uples (W, V, Y) in a list Table_Bot[k] will provide us in polynomial time with the vectors Y = (Y p , p ̸ = p 0 (k)) = (X t pk , p ̸ = p 0 (k)) likely to be involved into an optimal Multi_Bot solution. In other terms, every time we must deal some pair (t, k) and decide about values X t pk , p ̸ = p 0 (k), we shall only decide about value W, next retrieve V and Y from the table Table_Bot and finally set X t pk = Y p for any p ̸ = p 0 (k).

The algorithm A_Bot is a dynamic programming algorithm with the following characteristics:

• The time space L is the set {0} ∪ {p = 1, . . . , P, p ̸ = p 0 (k)); The successor Succ(p) of a time value p is p + 1 in case p + 1 ̸ = p 0 (k) and p + 2 else.

• The state space S is the set of all non negative number w such that w ≤ (p 0 (k) -1) ∑ p̸ =p 0 (k) p. Every state w will be given together its cumulated profit (we seek maximization) v.

• A decision n at time p is a non negative integral number between 0 and p 0 (k)/GCD(p, p 0 (k)) -1, which means at time p the value of Y Succ(p) .

• Related transition increases w by Succ(p) • d and cumulated profit v by c Succ(p),k • d.

• Initial state is 0 with related value 0; Related profit v is 0.

• Final states are all W which could be reached at time P, provided with a final cumulative profit V.

• Bellman principle: for any p, we only keep Pareto pairs (w, v), which means that we forbid two pairs (w, v) and (w ′ , v ′ ) related to a same set S (p) to be such that

w ≤ w ′ and v ≥ v ′ .
The whole algorithmic scheme is a mere adaptation of the general DP scheme of Section

Single type of load

Since K = 1, we may simplify our notations as follows: X t pk becomes X t p , c pk becomes c p , n k becomes n, and p 0 (k) becomes p 0 . Then the problem becomes: The idea for the algorithm is the following. As suggested in the previous sections, we shall rely here on a dynamic programming algorithm, with a time space which follows the values t = 1, . . . , T. The question is clearly about the definition of the state space, since values X t p 0 and c p 0 may not be bounded by any polynomial function of our Multi_Bot inputs. In order to overcome this difficulty, we shall define a state at time t while splitting it into 2 components:

Multi_Bot_K_1: Compute X = (
• A component made of a number W whose meaning will be the value ∑ l≤t,p̸ =p 0 pX l p related at time t to the contribution of the variables X l p , p ̸ = p 0 . We are going to use Lemma 4.2.1 and the table Table_Bot pre-computed in Section 4.3.2 in order to manage those variables X l p , p ̸ = p 0 as a whole according to a single decision.

• A component EX which will refer to the difference between ∑ l≤t p 0 • X l p 0 and some number U Min(t). The key here is that we are going to use lemmas 4.2.2 and 4.2.3 in order to identify (next lemmas 4.3.3, 4.3.4 and 4.3.5) 2 numbers U Min(t) and U Max(t) whose difference is a polynomial function of our Multi_Bot inputs and which are such that ∑ l≤t p 0 • X l p 0 may be maintained between U Min(t) and UMax(t). Related decisions will be designed accordingly.

Let us now enter into the details of this approach, and state:

αp 0 X t * p 0 + β ∑ t p 0 .X t p 0 ≥ S -(α + Tβ) -(α + Tβ)(Q -p 0 ) = S -(α + Tβ)(Q -p 0 + 1).
Let us set ϕ = inf t p 0 X t p 0 as in Lemma 4.3.4. We deduce (α + Tβ)(Q + ϕ) ≥ αp 0 X t * p 0 + β ∑ t p 0 X t p 0 ≥ S -(α + Tβ)(Qp 0 + 1) and so (α + Tβ)ϕ ≥ S -(α + Tβ)(2Qp 0 + 1). So we get that, for any t, p 0 X t p 0 ≥ S/(α + Tβ) -(2Qp 0 + 1) and the result.

For any t, let us set U Min(t) = t 0 S/(α + Tβ)t 0 (2Q + 1p 0 ) and U Max(t) = t 0 S/(α + Tβ) + t 0 Q. The key point is that the number of possible integral values ∑ t≤t 0 p 0 X t p 0 becomes bounded by U Max(t) -U Min(t), which itself bounded by a polynomial function of T and P. By the same way we know that ∑ l≤t ∑ p̸ =p 0 pX l p is also going to be bounded by a polynomial function of T and P (Lemma 4.2.2). So we become able to provide the main components of the DP algorithm Multi_Bot_dec_K_1(S):

• Time Space: The set of all values t = 0, 1, . . . , T.

• State Space: A state at time t is given by: -A number W whose meaning is ∑ l≤t ∑ p̸ =p 0 pX l p induced by the decisions taken until time t; -The value EX whose meaning is the difference (∑ l≤k p 0 .X l p 0 -U Min(t)), whose value is non negative and no larger than U Max(t) because of lemmas 4.3.1, 4.3.3, 4.3.4. -Related Cost value: To any state (W, EX) at time t corresponds some current cost VAL which means current value ∑ l≤t ∑ p pX l p ;

-Initial state at time 0 is (0, 0). Related value VAL is 0.

• Decisions at time t = 0, . . . , T -1:

-We choose a 3-uple (w, v, Y) in the list Table_Bot: for any p ̸ = p 0 we set

X t+1 p = Y p ;
-We decide some number z between 0 and (UMax(t + 1) -U Min(t + 1)); Related value X t+1 p 0 is going to comes as (z + U Min(t + 1) -(EX + U Min(t))/p 0 .

- The fact that this dynamic programming algorithm solves Multi_Bot_dec_K_1(S) derives from Lemma 4.2.2 and lemmas 4.3.3, 4.3.4, 4.3.5 and from the fact that any pair (W, EX) determines the whole values ∑ l≤t ∑ p̸ =p 0 pX l p and ∑ l≤t p 0 X l p 0 . In order to achieve our proof, we only need to check that it works in polynomial time. We first notice that the number of possible state values W is polynomial bounded in T and P. The same holds for values EX, because the difference U Max(t) -U Min(t) = t 0 Q + t 0 (2Q + 1p 0 ) depends on T and P in a polynomial way. The number of possible decisions w contained into the list Table_Bot is also bounded by a polynomial function of T and P, and the same holds for the number of decisions z. We conclude.

Single period

Since T = 1, we simplify our notations as follows: X t pk becomes X pk . By the same way, we set:

H = ∑ kp pX pk ; E = ∑ k p 0 (k)X p 0 (k),k ; F = ∑ k,p̸ =p 0 (k) pX pk .
Then Multi_Bot becomes: Multi_Bot_T_1: Compute X = (X pk , p = 1, ..., P, k = 1, ..., K) such that:

For any k, ∑ p c pk X pk ≥ n k ; ∑ k,p pX pk is the smallest possible.

The idea for the algorithm: as suggested in the previous sections, we shall rely here on dynamic programming, with a time space which follows the values k = 0, . . . , K. Once again, the question is about the definition of the state space, since values X p 0 ,k and c p 0 ,k may take very large values. In order to overcome this difficulty, we are going to define a state at time k while splitting it into 2 components:

• A component made of a number W whose meaning will be the value ∑ u≤k,p̸ =p 0 (u) p • X p,u related at time k to the contribution of the variables X p,u , p ̸ = p 0 (u), u ≤ k.

We are going to use Lemma 4.2.1 and the table Table_Bot pre-computed in Section 4.3.2 in order to manage those variables X p,u , p ̸ = p 0 (u) as a whole according to a single decision.

• A component EX which will refer to the difference between ∑ u≤k p 0 • X p 0 ,u and some number Min1(t). The key here is that we are going to use lemmas 4.2.2 and 4.2.3 in order to identify (next Lemma 4.3.7) 2 numbers Min1(k) and Max1(k) whose difference is a polynomial function of our Multi_Bot inputs and which are such that ∑ u≤k p 0 • X p 0 ,u may be maintained between Min1(k) and Max1(k). Related decisions will be designed accordingly.

Let us now enter into the details of this approach, and state: Table_Bot in order to manage those variables X p,k , p ̸ = p 0 (k) as a whole according to a single decision.

More precisely, it works in two steps as described below:

• First step: We solve the specific Multi_Bot instance involved in the proof of Theorem 4.2.4 in order to get an initial solution. This specific instance, which only involves variables X t p 0 (k),k , t ∈ T, k ∈ K, is a kind of Bin_Packing instance, with item set K and box set T, which we handle by considering the items according to decreasing weights and assigning them to the box with the smallest current load.

• Second step: It involves the table Table_Bot of Section 4.3.2, adapted I such a way that we may control the number of states generated by A_Bot(k)and maintain it below some threshold parameter State_Max. It aims at improving the solution obtained through step 1 while iteratively applying a local procedure which acts by picking up some pair (t 0 , k 0 ), some 3-uple (w 0 , v 0 , Y 0 ) and redistributing part of the value X t 0 p 0 (k 0 ),k 0 among variables X t 0 p,k 0 , p ̸ = p 0 (k 0 ) in order to make the value of the objective function decrease.

The procedure A_Bot is rewritten into a procedure A_Bot(k, State_Max), where State_Max ≤ 3P is a threshold parameter, in such a way that this procedure computes output list Ta-ble_Bot[k] exactly as in Section 4.3.2, with the restriction that a state value w is forbidden from exceeding State_Max. This impose an additional test on the feasibility of decision n, which must be such that n + w must not exceed State_Max. This allows us to better control the running time of the procedure A_Bot, which becomes a heuristic for the problem Aux_Bot.

First step

As previously told, the first step of H_Bot works by focusing on the variables X t p 0 (k),k and making them increase until constraint (4.2) is satisfied in such a way that the values

H t = ∑ k p 0 (k)X t p 0 (k),k , t = 1, . . . ,
= (B k 0 -n k 0 + v)/c p 0 (k 0 ),k 0 ; H Aux = H + w -γ • p 0 (k 0 ); HKAux = H t 0 + w -γ • p 0 (k 0 ); HMax = Max(Max t̸ =t 0 H t , HKAux); H * = β • H Aux + α • HMax;
Choose (w 0 , v 0 , Y 0 ) such that γ ≤ Z t 0 k 0 and which provides us with the smallest value H * ;

(I2) Update:

MARK t 0 k 0 is set to 1; COUNT and N MARK t 0 are decremented by 1;

B k 0 is set to B k 0 -γc p 0 (k 0 ),k 0 + v 0 ;
H t 0 is set to HKAux and H is set to H Aux; Z t 0 k 0 is decremented by γ and ∆ t 0 k 0 becomes (w 0 , v 0 , Y 0 ).

We now provide some details for instructions (I1) and (I2).

Instruction (I1)

• Choice of t 0 : We target t 0 such that N MARK t 0 ̸ = 0 and H t 0 = Max t H t ; In case 4.5. Numerical experiments 91 such a value t does not exist, then we pick up t 0 randomly;

• Choice of k 0 : Once t 0 has been chosen, we target k 0 such that MARK t 0 k 0 = 0 and that p 0 (k 0 ) is the largest possible.

Instruction (I2)

• The 3-uple (w * , v * , Y * ) may be null, which yields no improvement of our current solution (Z, ∆).

We may implement a variant of the algorithm H_Bot_Second_Step by making the main loop depend on a STOP signal, activated when no (t, k) pair exists which induces an improvement of the solution according to above instruction (I2).

Numerical experiments

Recall that the fleet size (= number of robots) is given by H Max = max t ∑ k,p p • X t pk and the number of trips by H = ∑ t,p,k p • X t pk . The objective is to minimize Cost = α • H Max + β • H.

Purpose: We follow here a two-sided purpose. On one side, we want to observe some characteristics of the solutions of our Multi_Bot problem, namely, the size H Max of the robot fleet with regard to Cost. On the other side, we are interested by the performances of the algorithm H_Bot, and more specifically to its ability to compute good solutions (gap to optimality).

Technical Features: Algorithms were implemented in C++, on PC AMD Opteron 2.1GHz, while using gcc 4.1 compiler. On the other hand, to solve the ILP a program was written in Python and solved using PuLP library. PuLP is an application programming interface and it can generate data file created in the Mathematical Programming System (MPS) format or Linear Programming (LP) file and call one of the solvers (GLPK, CBC, CPLEX) to solve linear problems. In the program we use so the default solver is CBC (Coin-or branch and cut).

Instances: We have generated the instances as follows:

• Decide about T, P, K;

• Randomly select α, β in 0; 1000 . If α ≤ T • β 2
, set β = 0. We do this in order to have H Max not negligible compared to H, otherwise the problem becomes trivial.

• For every k:

-Select capacities c pk as follows for every p: -Randomly select a coefficient J ∈ 0; 10000 . Select demand coefficient n k as

n k = P • J • c mean k .
For the purpose of this chapter, we present 20 instances, whose characteristics are summarized in Table 6.

Outputs: For every instance, we compute:

• Characteristics of the solutions:

-H Max = Fleet size -H = Number of trips -Cost = α • H Max + β • H
• Behavior of the Algorithm H_Bot: The results provided by our experiments may be summarized into the flowing Tables 7,8. For 14 of the 20 instances, the H_bot algorithm finds the optimal solution after the first step of the algorithm. For 3 other instances, it does not find the optimal solution and the cost gap does not exceed 3 %. The fleet gap does not exceed 4 % after the first step and 3 % after the second step. For the last 3 instances, the exact method does not find the optimal solution in less than one hour. Note that we can build instances with larger gaps. For instance, take two configurations of robots (p ∈ {2, 3}), two types of loads (k ∈ {1, 2}) and two periods (T = 2). Loads of type 1, 2 correspond to respectively small (S) and medium (M) loads. The capacities are: There are 3 loads of type 1 (n 1 = 3) and 2 loads of type 2 (n 2 = 2). The objective is to minimize the number of robots (α = 1, β = 0). A 2-bot can transport only a small load (c 21 = 1, c 22 = 0) and a 3-bot can transport only a medium load (c 31 = 1, c 32 = 0).

Then H Max (PuLP) = 6, H Max (H_Bot) = 7 and GAP_cost = GAP_fleet ≈ 16.7%. Figure 37 represents the Gantt chart for this example. On the ordinate axis is the reference number of the bots, on the abscissa axis is the reference number of the period. The load type the robot is carrying is indicated in each rectangle.

Conclusion

We have proved that the problem is strongly NP-complete by reducing it to the Bin Packing problem. We have showed that in three special cases (single period, single load type or single configuration), the problem can be solved in polynomial time with appropriate dynamic programming algorithms. We have then derived from our theoretical results an efficient heuristic algorithm for the general case. A numerical study shows that the heuristic algorithm can successfully be applied even for large instances and has good performances on the tested instances.

Chapter 5

Planning problem We propose an integer linear programming formulation for the problems with or without reconfiguration. We show that reconfigurability can reduce significantly the execution time.

Problem description

We consider a fleet of N mobile bots capable of cooperating to transport loads. A p-bot is a set of p bots that are aggregated to carry loads (p = 1, • • • , P). There are n k loads of type k to be transported (k = 1, • • • , K). A p-bot is able to carry c pk loads of type k.

Therefore the poly-robots have a capacity that depends on their configuration and the load type. All loads are to be transported from one point to another in the warehouse.

The time horizon is divided into T periods (t = 1, • • • , T). During a period, a p-bot is able to perform a round trip and carry a maximum of c pk loads of type k. The duration of a round trip is independent of the configuration and load type.

The goal is to minimize the makespan, i.e. the time to transport all loads from one place of the warehouse to another. We examine two scenarios. In the first scenario, reconfiguration is allowed, and the configurations can be modified at the beginning of each period. In the second scenario, reconfiguration is not permitted and the configurations are determined for the whole time horizon. The minimum makespan with allowed reconfiguration is denoted T R . The minimum makespan without any reconfiguration during the process is denoted T W . To have a feasible solution of this problem, T and N must be sufficiently large.

Integer linear programming formulation

In this section, we present ILP formulations for the two scenarios. We first assume that reconfiguration is allowed. We use the following decision variables:

• N t pk : number of p-bots transporting loads of type k in period t;

• α t : binary variable equal to 1 if any load is transported in period t and to 0 otherwise. We now comment each line of the above ILP:

• Objective function (5.1): ∑ T t=1 α t represents the makespan;

• Constraint (5.2): all loads of all types must be transported;

• Constraint (5.3): the number of bots used in each period must not exceed the fleet size;

• Constraint (5.4): if period t is inactive, then period t + 1 is inactive.

When reconfiguration is prohibited, we can simply add the following constraint to the above ILP: (5.6) This constraint ensures that there are less p-bots used in period t + 1 than in period t, which ensures that there is no reconfiguration.

K ∑ k=1 N t pk ≥ K ∑ k=1 N t+1 pk t = 1, • • • , T -1, p = 1, • • • , P

Reconfigurable vs non-reconfigurable fleet

In this section, we compare the makespans of the two scenarios. Consider the following simple example based on the situation described in Figure 1.

• The first load type corresponds to a box and will be referred to as Small (S);

• The second load type corresponds to a pallet and will be referred to as Large (L); 100 Chapter 5. Planning problem

• A 1-bot can carry one box at a time;

• A 4-bot can carry either one pallet at a time or one box at a time (we assume that each box is in a different location and there is no gain to organize a tour);

• There are N = 4 bots;

• There are 1 load of type Large and 4 loads of type Small Table 9 summarizes the capacities of the different configurations.

Type of load Configuration

Small Large 1-bot 1 0 4-bot 1 1 The optimal solutions for both strategies are shown as Gantt charts in Figure 38. When reconfiguration is allowed, a 4-bot transports a load of size L in period 1 and then splits into four 1-bots in period 2 to transport four loads of size S. The makespan is T R = 2.

When reconfiguration is not allowed, the 4-bot transports the load of size L in period 1, then the loads S in periods 2, 3, 4, 5. The makespan is T W = 5. We conclude that the strategy with reconfiguration is 2.5 times faster than the strategy without reconfiguration. we have

1 ≤ T W T R ≤ n 2 .
(5.7)

Proof. We distinguish two cases.

T R ≥ 2

We have T W ≤ n since we transport at least one load per period.

1 ≤ T W T R ≤ n T R ≤ n 2 .
(5.8)

T R = 1

Reconfiguration is not used and T W = T R . Since n ≥ 2, it follows that

T W T R = 1 ≤ n 2 .
By generalizing the example of Figure 38

Conclusion

We have studied the problem of scheduling a fleet of reconfigurable robots with the objective to minimize the makespan. We have proposed a mathematical formulation of the problem which can be solved with a linear optimization solver. We have showed that reconfigurability can reduce drastically the makespan when boxes are located in different locations.

Conclusion and perspectives

The presented work considers the problem of load transportation by poly-robots in the context of intralogistics. The poly-robots in this dissertation are reconfigurables, that is they consist of elementary robots that can be assembled in different ways over time to adapt to the loads to be transported. Each poly-robot configuration has its own transportable load capacity and can be reconfigured after each transportation. The interest of the work is to find out how to determine the optimal number of elementary robots and which configurations is more profitable to use at a given time.

As shown in the study of the literature, over the past decade there has been a significant increase in the use of robots in warehouses, freeing operators from tedious tasks.

While reconfigurable robots offer several advantages for warehouse transport operations. Firstly, the means of transport can be dynamically adapted to the load size or mass, which prevents to use oversized poly-robots and allows to re-affect the available elementary robots. Secondly, poly-robots can fit any warehouse, whatever the rack type, aisle width or door width. The elementary robots are interchangeable, which improves failure tolerance. In addition, a poly-robot has mechanical characteristics that make it more stable and maneuverable than a forklift. However, since this branch of robotics is only at the stage of its development, the question of the size of the fleet of reconfigurable robots has not been considered in the literature, despite its huge potential.

Our contributions on cooperative and reconfigurable models

First of all, in Chapter 2, a comparison of the fleet of robots without cooperation and with cooperation was made for homogeneous loads. In the first case, robots work alone and the minimum number of robots can be found using an analytical formula. In the 104 Conclusion and perspectives second case, the robot fleet consists of 1-bots and p-bots (only one possible configuration). The constructed mathematical model allows us to determine the most profitable configuration (number of robots that should cooperate) for the minimum cost of transportation. If the capacity of p elementary robots is smaller than the capacity of a single p-bot configuration, then using exclusively p-bot configurations or with a mix of 1-bots can lead to a significant cost decrease. Otherwise, it is optimal to use exclusively single robots. With an infinite horizon problem, that is a fleet of vehicles operating indefinitely, the models lead to simpler results.

In Chapter 3 we have added the ability to reconfigure the robots. Mathematical programs were obtained for load transportation with and without the possibility of reconfiguration. This allows us to find out which configuration of the robot in which period and for the transportation of which type of load we will use to minimize the transportation cost. Thanks to the programs, we can compare the cost of the fleet with and without reconfiguration. The reconfigurability can divide the minimum number of elementary robots up to a factor of K (with K the number of load types). For the special case of two types of loads and two configurations of robots, the gain in number of robots is limited by p (with p the number of elementary robots in the p configuration) but may be significant for small fleets. For the second special case, with unit capacities, the gain in number of robots is limited by K -1 (with K the number of load types). In a variant where the demand is per period of time and not on the whole time horizon, the gain in number of robots is not bounded.

Seeing a mathematical problem, the question of complexity is posed and considered in Chapter 4. The described problem of a reconfigurable robot fleet is strongly NP-Hard. In three special cases of single period, single load type or single configuration, the problem can be solved in polynomial time with appropriate dynamic programming algorithms.

An efficient heuristic algorithm for the general case can successfully be applied even for large instances and has good performances on the tested instances.

Eventually, in Chapter 5, we also focused on the issue of minimizing transportation time.

Our mathematical programs of the problem can compare the minimum transport time with and without the possibility of reconfiguration. The reconfigurability can reduce drastically the time to transport all loads from one place of the warehouse to another, when boxes are located in different locations.

Future research directions

This dissertation marked the beginning of a new branch of research in intralogistics by considering a fleet of reconfigurable robots. The models that we considered are naturally simplified compared to real situations. Several lines of research could be thus proposed by tackling more general problems, where some hypotheses of our work are weakened. As an example, an interesting question is the handling of traffic jams in the robot fleet. Another one would consist in examining of options when the same robot configuration can have several different transport capacities and when a p-bot can simultaneously transport several types of loads. Finally, it would be also of interest to consider stochastic processes such as robot breakdowns, demands and transportation.

We terminate this dissertation by focusing on two specific lines of research which sound challenging.

Different transportation times

We focus on a first extension of our initial model: having different locations for unloading areas. Each location could be at a different distance from the loading area, and accordingly has its own transportation time.

Initially, for each type of load, the transportation time lasted one period. We propose a new model where some loads need a larger transportation time, i.e. of several periods.

This new characteristic is justified by at least two reasons. First, some loads might be heavy or voluminous and, hence, make the speed of the robot which carries it decrease.

Second, the unloading area of some loads could be farther from the starting point. As a consequence, the travel time of the robot to transport these loads is increased. In fact, we propose an even more general model: the transportation time of some load can also depend on the configuration which carries it. For instance, some load could be transported in two periods with a 10-bot but in one period with a 4-bot -due to the fact that a 10-bot are heavier and more difficult to guide.

We remind that the initial entries of the model in Chapter 3 were parameters T, K, P, α, β, the number of loads of each type n k and the capacities c pk . We add a new entry τ pk which is the number of periods of time needed to transport loads of type k by a p-bot.

A natural question is whether the techniques employed to tackle the initial problem could fit this more general version. Obviously, some variables have to be modified from the initial model. Indeed, when all transportation time used to be of one period and everything could be reconfigured at each step, variable N t pk denoted the number of pbots carrying loads of type k during period t. It was sufficient to describe entirely the state of the warehouse. Now, we see that these p-bots, when τ pk > 1, can be at different step of their travel: either leaving the loading area at period t, being at the middle of their trip or arriving. For this reason, we fix a new variable Ñt pk which corresponds to the number of p-bots leaving the loading area at period t in order to transport loads of type k. We fix T pk = Tτ pk + 1 as the limit departure time for a p-bot with loads of type k. Hence, the total number of transported loads of type k is ∑ P p=1 ∑

T pk t=1 c pk • Ñt pk . In summary, an ILP formulation of this problem, with variables N (total number of elementary robots) and Ñt pk , can be formulated.

Complexity of the problem with 2 load types

Our last direction of research concerns the complexity of some specific cases of the reconfigurable model. In this dissertation, we showed that the Multi_Bot problem is strongly NP-complete. But, meanwhile, we identified exact polynomial-time algorithms for some cases, in particular when K = 1 (one type of load) but also when T = 1 (only one period) and P = 1 (one configuration). A natural question following our work is to determine where is the frontier between P and NP-hardness on the Multi_Bot problem.

Let us focus on one particular question of this context: what is the complexity of the Multi_Bot problem when K = 2? We thus consider a fleet of poly-robots which must

Figure 1 :

 1 Figure 1: Exemples de poly-robots reconfigurables M3-Cooper [MecaBotiX, 2023]

  Figures Exemples de poly-robots reconfigurables M3-Cooper [MecaBotiX, 2023] . ix Total number of warehouses in the United States 2007-2020 according to Statista [Mazareanu, 2021] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Main functions of a warehouse [VecturaLogistique, 2021] . . . . . . . . . . 3 Cardboards and plastic boxes stored on pallets [Free3D, 2023] . . . . . . . 4 Boxes on pallets [Mecalux, 2016] . . . . . . . . . . . . . . . . . . . . . . . . 4 Dimensions of pallets [Mecalux, 2016] . . . . . . . . . . . . . . . . . . . . . 5 Container loading plan with EURO pallets [MouvBOX, 2023] . . . . . . . 6 Single depth configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Double depth configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 The hourly cost of robots and human operators in France in €/hour [Roland Berger, 2016] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Types of automatic storage . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Examples of AS/RS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 VLM [Lenoble, 2017] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Carousels [Kardex, 2023] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 AGVs used for automated goods transport in a warehouse [Cardarelli et al., 2017] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 RMFS [Amazon Robotics, 2023] . . . . . . . . . . . . . . . . . . . . . . . . . 15 Examples of mobile robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Development timeline of mobile manipulator robots [Oyekanlu et al., 2020] 16 AMADEUS demonstrator in the industrial scenario, by Fraunhofer [Urru et al., 2018] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Different modes of cooperation Chebab [2018] . . . . . . . . . . . . . . . . 18 Robot technical solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 xvi List of Figures Reconfiguration from a 3-bot and a 2-bot into a 4-bot and a 1-bot (R i denotes the i-th elementary robot) . . . . . . . . . . . . . . . . . . . . . . . 27 Examples of reconfigurable poly-robots M3-Cooper [MecaBotiX, 2023] . . 27 Transport of identical loads by a fleet of homogeneous robots . . . . . . . 31 Gantt diagram for optimal transport of 5 loads . . . . . . . . . . . . . . . . 33 Illustration for case c 1 = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Illustration for case c 1 ≥ c ′ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Illustration for case 0 < c 1 < c ′ 1 . . . . . . . . . . . . . . . . . . . . . . . . . 39 Gantt diagram of the optimal solution of 4 loads . . . . . . . . . . . . . . . 39 Illustration of notation n ′ k with four types of loads (T = 5, n 1 = 1, n 2 = 4, n 3 = 2, n 4 = 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Gantt chart for a simple example where the number of robots is halved when reconfiguration is allowed . . . . . . . . . . . . . . . . . . . . . . . . 58 Chapter 1. Introduction and state of the art

Figure 2 :

 2 Figure 2: Total number of warehouses in the United States 2007-2020 according to Statista [Mazareanu, 2021]

Figure 3 : 4 Chapter 1 .

 341 Figure 3: Main functions of a warehouse [VecturaLogistique, 2021]

Figure 4 :

 4 Figure 4: Cardboards and plastic boxes stored on pallets [Free3D, 2023]

Figure 5 :Figure

 5 Figure 5: Boxes on pallets [Mecalux, 2016]

Figure 6 :

 6 Figure 6: Dimensions of pallets [Mecalux, 2016]

Figure 7 :

 7 Figure 7: Container loading plan with EURO pallets [MouvBOX, 2023]

Figure 9 :

 9 Figure 8: Single depth configuration

Figure 10 :

 10 Figure 10: The hourly cost of robots and human operators in France in €/hour [Roland Berger, 2016]

Figure 11 :

 11 Figure 11: Types of automatic storage

  Figure 12: Robots

  Figure 13: Examples of AS/RS

Figure

  Figure 14: VLM [Lenoble, 2017]

  Figure 15: Carousels [Kardex, 2023]

Figure 16 :

 16 Figure 16: AGVs used for automated goods transport in a warehouse [Cardarelli et al., 2017]

Figure 17 :

 17 Figure 17: RMFS [Amazon Robotics, 2023]

  Figure 18: Examples of mobile robots

Figure 19 :

 19 Figure 19: Development timeline of mobile manipulator robots [Oyekanlu et al., 2020]

Figure 20

 20 Figure 20 shows an example of AMADEUS (Autonomous Manipulator Device for Strengthening Manufacturing in Europe) robot. The platform is a combination of an AGV with an application-specific configuration and a robotic manipulator.

Fig. 1 .

 1 Fig. 1. AMADEUS demonstrator in industrial scenario, by Fraunhofer

Figure 20 :

 20 Figure 20: AMADEUS demonstrator in the industrial scenario, by Fraunhofer [Urru et al., 2018]

  Figure 21: Different modes of cooperation Chebab [2018]

  Figure 22: Robot technical solutions

  and is equal to 0 otherwise • C F v represents the cost of including a ship of type v in the fleet • C V vr represents the cost of sailing route r with ships of type v • Z vr is the time consumed every time a ship of type v sails route r • Z represents the total amount of time available for each ship within the planning horizon • Q v is the capacity of a ship of type v • D i is the demand of port i 1.5. Fleet sizing 25

Figure 23 :

 23 Figure 23: Reconfiguration from a 3-bot and a 2-bot into a 4-bot and a 1-bot (R i denotes the i-th elementary robot)

•

  d: round trip distance from A to B to A • τ: cycle time of the round trip, including loading/unloading time • v l : travelling speed of a loaded robot • v e : travelling speed of a empty robot • t l : loading time • t u : unloading time • t b : average immobilization duration for a single robot, due to battery recharge, maintenance, failure • c: robot capacity • D: total distance traveled by all the robots 2.1. Non-cooperative robots 31 • α: fixed cost per unit of time of a robot • β: cost per meter traveled by a robot • γ: fixed cost per unit of time, independent of the number of robots • N: number of robots for loads transportation • n: number of transported loads • r: number of round trips for a robot • T: planning horizon We consider a fleet of N identical mobile robots which must transport a set of n identical loads from zone A to zone B, as shown in Figure 25. Robot capacity is denoted c. The capacity of a robot is related to the size and mass of the loads and the number of loads that a robot can carry simultaneously.

Figure 25 :

 25 Figure 25: Transport of identical loads by a fleet of homogeneous robots

  Figure 26.

Figure 26 :

 26 Figure 26: Gantt diagram for optimal transport of 5 loads

2 Figure 27 :

 227 Figure 27: Illustration for case c 1 = 0

Figure 28 :

 28 Figure 28: Illustration for case c 1 ≥ c ′1

Figure 29 :

 29 Figure 29: Illustration for case 0 < c 1 < c ′1

Figure 30

 30 Figure30shows the Gantt diagram of the optimal solution when both configurations are allowed.

Figure 30 :

 30 Figure 30: Gantt diagram of the optimal solution of 4 loads

Figure 31 :

 31 Figure 31: Illustration of notation n ′ k with four types of loads (T = 5, n 1 = 1, n 2 = 4, n 3 = 2, n 4 = 1)

Figure 32 :

 32 Figure 32: Gantt chart for a simple example where the number of robots is halved when reconfiguration is allowed

  .53) For instance, if N R = 100 and p = 4, then N W /N R ≤ 1.04 and N W ≤ 104. Hence reconfigurability allows to divide the size of the fleet by at most a factor 1.04.

4 .

 4 Number of robots saved through reconfigurability 59

  .57) In what follows, we provide examples where the upper bound in (3.54) and (3.57) are reached for two or three types of loads.

Figure 33 :

 33 Figure 33: Gantt chart for an example with two types of loads

  medium (M) and large (L) loads. Let's take T = 5, n 1 = 8, n 2 = 2 and n 3 = 1. Then N R = 3, N W = 5 and N W N R = 5 3 . Figure34represents the Gantt chart for this example.

Figure 34 :

 34 Figure 34: Gantt chart for an example with three types of loads

  maximum and equal to 2 while the difference is equal to n 1 and thus unbounded.

Figure 35 :

 35 Figure 35: Effect of the number of loads of type 1 on the gains in absolute and relative value

Figure 36 :

 36 Figure 36: Gantt chart when p = 4, n 1 = 8 and n 2 = 2

  , where n Max = sup k n k and so the optimal cost value bounded by 2n Max • sup(α, β) • K • P • T. It comes that we may solve Multi_Bot by successively solving (binary search process) no more than log 2 (2n Max • sup(α, β) • K • P • T) instances of the following decision problem Multi_Bot_dec(S) where S is a threshold parameter bounded by 2n Max • sup(α, β) • K • P • T.

  may be bounded by a polynomial function of Size(Multi_Bot), we see that the time-complexity of Multi_Bot is going to be (in terms of polynomiality or NP-Hardness) the same as the time-complexity (in terms of polynomiality or NP-Completeness) of Multi_Bot_dec(S).

Lemma 4 . 2 . 1 .

 421 Given a Multi_Bot instance Multi_Bot. Imposing the following constraint(4.4)

Theorem 4 . 2 . 4 .

 424 is NP-Complete, we only need to design a time-polynomial algorithm Code which turns any Bin_Packing instance BP into a Multi_Bot_dec instance Multi_Bot_dec = Code(BP) and a time-polynomial algorithm Decode which turns any Multi_Bot_dec output X into a Bin_Packing output σ in such a way that: BP admits a feasible solution σ if and onlyif Code(BP) admits a feasible solution X such that Decode(X) = σ. Multi_Bot_dec is strongly NP-Complete Proof. Its ILP formulation implies that Multi_Bot_dec is in NP. Thus, we only need to prove that it contains Bin_Packing in the sense of the Code/Decode reduction scheme.

  integral and such that:

  p, Y p ≤ (p 0 (k)/GCD(p 0 (k), p)) -1; (*Because of Lemma 4.2.1*) V = ∑ p̸ =p 0 (t)

2 : 4 :

 24 S (0) = a list reduced to one 3-uple (w = 0, v = 0, d = Unde f ined) 3: For any p ≥ 1 and ̸ = p 0 (k), S (p) = Empty list; Main loop: 5: Scan the time space L and, for any p ̸ = P in L (or ̸ = P -1 in case P = p 0 (k)) scan current set S (p):For any (p, (w, v, d 1 )) generated this way, scan the decision set n ≤p 0 (k)/GCD(p, p 0 (k)) -1:For any n generated this way, compare the 3-uple(v + d • Succ(p), w + c Succ(p),k • d, d) with the elements of current list S (Succ(p)):If there exists (w ′ , v ′ , d ′ ) in S (Succ(p)) such that w ′ ≤ w and v ′ ≥ v then drop (w, v, d); Else insert (w, v, d) into S (Succ(p)) while removing from S (Succ(p)) all 3-uples (w ′ , v ′ , d ′ ) such that w ≤ w ′ and v ≥ v ′ ;6: Output: 7: For any (w, v, d) in S (P) (or S (P -1)) if P = p 0 (k), retrieve solution vector Y, and put related 3-uple (w, v, Y) into the list Table_Bot[k]. Lemma 4.3.1. A_Bot(k) solves Aux_Bot(k, W) in polynomial time Proof. A_Bot(k) clearly solves Aux_Bot(k, W). The fact that it does it in polynomial time is a mere consequence of Lemma 4.2.1 and the constraints: For any p, Y p ≤ (p 0 (k)/GCD(p 0 (k), p)) -1. Then the number of states w is bounded by (p 0 (k) -1) ∑ p̸ =p 0 (k) p, which is a polynomial function of P.

Theorem 4 .

 4 3.6. Multi_Bot_T_1 may be solved in polynomial timeProof. It is enough to prove that the decisional version of Multi_Bot_T_1 can be solved in polynomial time. S being a parameter such that S ≤ 2 sup(α, β)PK(sup k n k ), Multi_Bot_dec_T_1 may be written:

*

  Randomly select the mean value c mean k (of coefficients c pk ) in 1; 11 ; * Randomly select coefficient c pk in 0; 2c mean k ← round(c pk ); (rounded to the nearest whole number)

:Chapter 4 .

 4 Gap to optimality with respect to cost -GAP1_cost = Gap to optimality with respect to cost when we restrict ourselves to the first step of H_Bot -GAP_fleet = H Max (H_Bot)-H Max (PuLP) H Max (PuLP) : Gap to optimality with respect to fleet size -GAP1_fleet = Gap to optimality with respect to fleet size when we restrict ourselves to the first step of H_Bot 94 Complexity analysis and heuristic algorithms

Figure 37 :

 37 Figure 37: Gantt chart for simple example with gap 17%.

Figure 38 :

 38 Figure 38: Gantt chart for an example with two types of loads

  , we can easily show that the upper-bound is tight. We consider n loads, n 1 = n -1 loads of type 1, n 2 = 1 load of type 2, two configurations (1-bot and (n -1)-bot), c 11 =1, c 12 = 0, c (n-1),1 = 1, c (n-1),2 = 1 and a fleet of N = n -1 bots. Then we have T R = 2, T W = n. Hence T W = n 2 • T R .

  • • • , T N ∈ N, Ñt pk ∈ N ∀k, ∀p, t = 1, • • • , T

  Le chapitre 1 présente le contexte dans lequel s'inscrit la thèse. Il s'agit tout d'abord de présenter les entrepôts et l'automatisation du stockage et du transport. En outre, une attention est portée aux systèmes multi-robots, plus précisément aux systèmes coopératifs et reconfigurables. Une revue de la littérature est donnée pour le problème de dimensionnement d'une flotte. Dans le cadre des véhicules autonomes, le problème de dimensionnement d'une flotte n'a été considéré ni pour les robots coopératifs ni pour les robots reconfigurables. Les chapitres suivants de cette thèse comblent ce vide. Dans le chapitre 2, nous considérons le transport de charges identiques par des robots coopératifs et non coopératifs ayant une capacité supérieure à un. Un cadre mathé-Dans le chapitre 3, nous considérons la possibilité de reconfigurer les robots pour un transport des charges hétérogènes. Deux PLNEs sont écrits pour comparer le coût d'une flotte de robots avec possibilité de reconfiguration et sans cette possibilité. Ensuite, nous étudions un cas particulier avec deux types de charges et deux configurations autorisées (1-bot et p-bot avec p > 1). Pour ce cas particulier, des expressions de forme analytique sont dérivées pour le nombre minimum de robots élémentaires avec ou sans reconfiguration. Un deuxième cas particulier avec des capacités unitaires est également étudié. Nous montrons que la reconfigurabilité peut diviser le nombre minimum de robots élémentaires jusqu'à un facteur K (avec K le nombre de types de charge). Pour les deux cas particuliers, nous montrons que le gain en nombre de robots est limité mais peut être significatif pour les petites flottes. Enfin, dans une variante où la demande est par période de temps et non sur tout l'horizon temporel, nous montrons que le gain en nombre de robots peut être très important. Dans le chapitre 4, nous montrons que le problème est fortement NP-difficile. Dans trois cas particuliers (une seule période, un seul type de charge ou une seule configuration), le problème peut être résolu en temps polynomial avec des algorithmes de programmation dynamique appropriés. Nous dérivons ensuite de nos résultats théoriques un algorithme heuristique efficace pour le cas général. Une étude numérique montre que l'algorithme heuristique peut être appliqué avec succès même pour de grandes instances et a de bonnes performances sur les instances testées.

	List of Figures	xv
	List of

matique déterministe est développé pour le dimensionnement d'une flotte de robots identiques, nommés 1-bots, qui ont la possibilité de coopérer. Un ensemble de p 1-bots qui coopèrent sur une tâche donnée constitue un p-bot. Lorsque la coopération n'est pas autorisée, nous obtenons une expression sous forme analytique pour le nombre optimal de 1-bots. Lorsque la coopération est autorisée et la reconfiguration interdite, nous formulons le problème de dimensionnement de la flotte par un programme mathématique sous la forme d'un PLNE (programme linéaire en nombres entiers). Notre modèle mathématique permet de déterminer le nombre de robots à coopérer pour un coût de transport minimal. Dans le cas où la capacité de p 1-bots est inférieure à la capacité d'un seul p-bot, nous conclurons que l'utilisation soit exclusive de p-bots, soit d'un mélange de p-bots et de 1-bots, entraîne une diminution des coûts. Dans l'autre cas, il est optimal d'utiliser exclusivement des 1-bots.

Pour ce cas, nous dérivons des expressions de forme analytique pour le nombre minimum de robots jusqu'à trois types de charge avec reconfiguration, et pour n'importe quel nombre de types de charge sans reconfiguration. Enfin, nous comparons les straté-xi gies avec ou sans reconfiguration.

Table 1 : Capacity of containers and pallets

 1

on th International Conference on Service Operations and Logistics, and Inform

	2) SOTO The SOTO by Magaz developed for the task of S facility. It is an autonomo the specific industrial e Moreover, a logistic system integrated while other logi line supply and produc implementation process. ensures high reliability in payload of 15 kg enlarges industrial scenarios. The a handle different kind of S transportation capacity of of the SLC and ranges from
	B. Planning Methods
	During the past years, planning methods and opt established technologies su chapter an overview

  Table 2 presents the optimal solution according to the type of authorized robots.

		N 1 N p n 1 n p total cost
	1-bot only	2	0	4	0	42
	p-bot only	0	1	0	4	42
	Mix of 1-bot and of p-bot 1	1	1	3	33

Table 2 : Optimal solutions according to the types of authorized robots

 2

  Contents 3.1 Assumptions and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Mathematical formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Without reconfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 With reconfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Minimizing the number of robots . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Two types of loads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Unit capacities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Number of robots saved through reconfigurability . . . . . . . . . . . . 3.4.1 Two types of loads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Unit capacities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Demand per period . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 3. Transport of heterogeneous loads

Table 3 : Capacity matrix for 2 types of loads A

 3 1-bot can carry up to c 11 loads of type 1 but no load of type 2. A p-bot can carry up to c p1 loads of type 1 and up to c p2 loads of type 2. In order to always have feasible solutions, we assume that c 11 ≥ 1 and c p2 ≥ 1. When c p1 = 0, it corresponds to a

dedicated transport: loads of type 1 (respectively type 2) can only be transported by 1-bots (respectively p-bots).

Table 4 : Capacity matrix for 3 types of loads

 4

  .48) Strict inequality (3.46) comes from the assumption that n ′ 1 • c p1 < n 1 . Strict inequality (3.47) comes from n ′ 1 < T. Inequality (3.48) comes from the asssumption that n 1 ≤ n ′ 1 • p • c 11 . We have N W -N R < p + 1 and, as N W -N R and p are integers, we conclude that

Table 5 : Example where the gain in absolute value can be significant

 5

	62	Chapter 3. Transport of heterogeneous loads

  t E tmin t E t decreased; 4.2. Structural properties of the Multi_Bot problem 71 • The number of elements t which achieve max t E t or min t E t decreased.

  X t p , p = 1, ..., P, t = 1, ..., T) such that:

	t,p ∑	c p X t p ≥ n;	(4.9)
	α(max t ∑ p	pX t p ) + β( ∑ t,p	pX t p ) is the smallest possible.

  Proof. Let us denote by t * the index value t which achieves sup t H t . (4.12) tells us thatαH t * + β ∑ t H t ≥ S -(α + Kβ). But we may decompose αH t * + β ∑ t H t as αp 0 X t * p 0 + β ∑ t p 0 X t p 0 + αF t * + β ∑ t F t .We know that αF t * + β ∑ t F t ≤ (α + Kβ)(Qp 0 ). We deduce

	Theorem 4.3.2. Multi_Bot_K_1 may be solved in polynomial time
	Proof. It is enough (Section 4.2.1) to prove that the decisional version of Multi_Bot_K_1
	can be solved in polynomial time. S being such that S ≤ 2 sup(α, β)TPn, (see Section
	4.2.1), Multi_Bot_dec_K_1(S) comes as:

  Feasibility criterion: we should have:* α(z + U Min(t + 1) -(EX + U Min(t)) + β(W + w) ≤ S;VAL is incremented by c p 0 (z + U Min(t + 1) -(EX + U Min(t)) + v. There must not exists 2 states (W, EX) and (W ′ , EX ′ ) in L (t + 1) such that W ≤ W ′ , EX ≤ EX ′ and VAL ≥ VAL ′ , VAL and VAL ′ being the cost value related to (W, EX) and (W ′ , EX ′ ) respectively.

	* (z + U Min(t + 1) -(EX + U Min(t)) is an integral multiple of p 0 ;
	* 0 ≤ (z + U Min(t + 1) -(EX + U Min(t)).
	• Transitions:
	W is turned into W + w;
	EX becomes z;

• Bellman Principle:

  T, remain balanced. : Initialize a vector MARK = (MARK t k , t = 1, . . . , T, k = 1, . . . , K) with Boolean values, to the null vector; 3: Initialize a vector N MARK = (NMARK t , t = 1, . . . , T) with integral values all equal to K; 4: For any k, set B k = c p 0 (k),k .(∑ t Z t k ); 5: For any t, set H t = ∑ k p 0 (k)Z t k ; Set H = ∑ t H t ; 6: Initialize counter value COUNT to T • K;

	Algorithm 3 H_Bot_Second_Step
	1: Start from values Z t k = X t p 0 (k),k computed according to H_Bot_First_Step and from a
	null vector ∆;
	7: While COUNT ̸ = 0 do
	Choose t 0 and k 0 ;	(I1)
	For any (w, v, Y) in Table_Bot[k 0 ] compute:
	γ

2

Table 6 : Instances

 6

	Instances	α	β	T	P K	c mean k	a	J
	1		642 21	2	2 2	7;11	8
	2		791 4	4	2 2	7;10	848
	3		465 95	8	2 2	9;2		601
	4		344 0	16	2 2	1;1		945
	5		847 2	32	2 2	2;3		286
	6		161 0	64	2 2	8;9		273
	7		833 0	128 2 2	7;4		816
	8		60	0	256 2 2	5;6		233
	9		428 0	512 2 2	7;8		161
	10		33	0 1024 2 2	7;3		23
	11		872 0 2048 2 2	1;5		411
	12		981 0 4096 2 2	5;9		8544
	13		218 16	2	2 4	4;2;7;3	80
	14		443 12	2	2 6 2;3;6;7;10;11	89
	15		857 96	2	4 4	8;6;7;3	51
	16		90	0	4	4 4	3;7;7;8	41
	17		116 74	2	4 6 5;3;6;7;1;11	42
	18		328 65	4	4 6	9;1;2;7;5;8	9
	19		234 72	6	4 6 4;9;2;9;1;10	6
	20		545 71	2	6 6	1;7;4;1;6;3	22
	a c mean k	are listed by semicolon in order: c mean 1	; c mean

Table 7 : Results cost

 7

	Instances Cost(PuLP) b Cost(H_Bot) Cost(1_Step) GAP_cost GAP1_cost
	1	12975	12975	12975	0%	0%
	2	857022	857022	857026	0%	0.001%
	3	499705	499705	499705	0%	0%
	4	81872	81872	81872	0%	0%
	5	32780	32780	32780	0%	0%
	6	4025	4025	4025	0%	0%
	7	29155	29988	29988	3.0%	3.0%
	8	300	300	300	0%	0%
	9	856	856	856	0%	0%
	10	33	33	33	0%	0%
	11	1744	1744	1744	0%	0%
	12	-	11772	11772	-%	-%
	13	100280	100280	100280	0%	0%
	14	324086	324086	324086	0%	0%
	15	706450	707307	707445	0.121%	0.141%
	16	31320	31320	31320	0%	0%
	17	273768	273884	273884	0.042%	0.042%
	18	54096	54096	55668	0%	3.0%
	19	-	24894	25200	-%	-%
	20	-	671744	671744	-%	-%
	b the dash means that no result has been obtained after one hour of computa-
	tion.

Table 8 : Results fleet

 8

	Instances H Max (PuLP) c H Max (H_Bot) H Max (1_Step) GAP_fleet GAP1_fleet
	1	19	19	19	0%	0%
	2	1062	1062	1062	0%	0%
	3	408	408	408	0%	0%
	4	238	238	238	0%	0%
	5	36	36	36	0%	0%
	6	25	25	25	0%	0%
	7	35	36	36	3.0%	3.0%
	8	5	5	5	0%	0%
	9	2	2	2	0%	0%
	10	1	1	1	0%	0%
	11	2	2	2	0%	0%
	12	-	12	12	-%	-%
	13	436	436	436	0%	0%
	14	694	694	694	0%	0%
	15	710	711	711	0.141%	0.141%
	16	348	348	348	0%	0%
	17	1037	1038	1038	0.096%	0.096%
	18	92	92	96	0%	4.0%
	19	-	39	40	-%	-%
	20	-	978	978	-%	-%

c the dash means that no result has been obtained after one hour of computation.

  Contents 5.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .In this chapter we consider the reconfigurable robots in the context of the problem of scheduling with the objective to minimize the time to execute all transportation tasks.

	98	Chapter 5. Planning problem

5.2 Integer linear programming formulation . . . . . . . . . . . . . . . . . . 5.3 Reconfigurable vs non-reconfigurable fleet . . . . . . . . . . . . . . . .

Table 9 : Capacity matrix for 2 types of loads

 9

Chapter 2. Transport of homogeneous loads

Acknowledgements

This work was financed by the Auvergne Rhône Alpes Regional Council as part of a Pack Ambition Research on the RoMoCo project (Cooperative Modular Robots).

Remerciements

Chapter 3. Transport of heterogeneous loads

We assume that a p-bot has more capacity than p 1-bots to carry loads of type 1. It is then always more interesting to use a p-bot than p 1-bots. Thus, there is no point for reconfiguration and N W = N R .

We now compute N W (= N R ). The general idea is as follows:

1. We first assign loads of type 2 to p-bots;

2. We assign as many loads of type 1 as possible to the last p-bot (assigned for loads of type 2), which may have free periods; 3. We assign the remaining loads of type 1, if any, to p-bots, as long as we can use them at maximum capacity on the whole horizon; 4. We assign the last loads of type 1, if any, to 1-bots if it requires less than p 1-bot and to a p-bot otherwise.

In step (1), the number of p-bots needed to carry loads of type 2 is

We assume that the p-bots are fully filled before a new p-bot is loaded, so that there is no more than one p-bot with free periods at the end of the assignment of loads the second type. Let n ′ 1 be the number of periods not used by the last p-bot:

(3.17) Indeed, it takes n 2 c p2 periods to transport loads of type 2 with p-bots and the total available number of periods for p-bots is n 2 T•c p2 T.

In step [START_REF] Multi_Bot Model | [END_REF], we can assign n ′ 1 • c p 1 loads of type 1 to the last p-bot. There remains then

In step (3), the additional number of p-bots required to transport loads of type 1 (using full capacity on the whole horizon) is

At the end of step (3), it remains ñr

+ loads of type 1 to transport.

Chapter 4

Complexity analysis and heuristic algorithms Contents {0, . . . , N + 1} is then called the time space and S (j) is the state space related to j. In such a case, corresponds to any pair (j, s) a decision set D (j, s), as well as a feasibility procedure O: (j, s, d) → O(j, s, d) ∈ {0, 1}, which checks whether decision n ∈ D (j, s) can be applied to s at time j or not. In case n can be applied, it induces a transition T (j, s, d): (j, s) → d (j + 1, s * ), provided with some cost C(j, s, d), which underlies an arc ((j, s), (j + 1, s * )) d of G P . Therefore, the goal of a DP algorithm is to compute through

Bellman principle [START_REF] Broumi | Shortest path problem using bellman algorithm under neutrosophic environment[END_REF] a sequence of decisions which will allow moving from some initial state s 0 at time 0 to final state s f at time N + 1, with a smallest cumulated cost.

Such an algorithm may be designed according to the following forward driven scheme:

, where s 0 is the initial state;

• For any j ̸ = 0, we set S (j) = Empty list ;

Explanation: For any j, S (j) provides the set of states s which we reached from s 0 , together with their best cumulated cost V and the decision n 1 which allowed us to switch from some former state s ′ in S (j -1) to s.

Main Loop:

Scan time space L , and, for any j, scan the state set S (j): for any 3-uple (s, V, d 1 )

in S (j), generate all feasible decisions n in D (j, s), together with resulting states s* in S (j + 1) and related cost C(j, s, d). At the time when (s, V, d 1 ), n and s * are generated, we are provided with a current set S (j + 1): then we compare s * and the states s ′ currently in S (j + 1). If s * is dominated (Bellman principle) by some We are going to design a polynomial time DP algorithm with time space 0, 1, . . . , T, which solves Multi_Bot_dec_K_1. But in order to control the number of states of this algorithm, we must restrict the search space of Multi_Bot_dec_K_1 , which we are going to do through the following lemmas:

Lemma 4.3.3. Given a Multi_Bot_dec_K_1 instance mb_dec_K_1, reinforced by (4.4), (4.5), (4.6). Then imposing the following constraint (4.12) does not modify the feasibility value of mb_dec_K_1:

Proof. Given a feasible solution X of mb_dec_K_1. We see that if we increase every value X t p 0 by 1, then we do not lose any of the constraints (4.9), (4.4), (4.5), (4.6). So we may impose the following constraint (4.13):

X is maximal in the sense that increasing every X t p 0 by 1 violates (4.11). (4.13) But if X satisfies (4.13) then we must have: α

Lemma 4.3.5. For any t 0 = 1, . . . , T, we must have ∑ t≤t 0 p 0 X t p 0 ≥ t 0 S/(α + Tβ)t 0 (2Q + 1p 0 ). We are going to design a polynomial time DP algorithm with time space 0, 1, . . . , K and decisions related, for any k, to values X pk , p = 1, . . . , P. As a matter of fact, since values X pk , p ̸ = p 0 (k) may be controlled through the table Table_Bot, we focus on the key value

For any k, let us set:

Then we state the following lemma, which is going to help us in controlling the way values Z k = X p 0 (k),k are going to evolve with time value k.

n k for any k, because of (4.4). That means that Z k should be no smaller than n k /c p 0 (k),k -

), and so that p 0 (k)Z k should not be smaller than p 0 (k)

. We conclude.

We may now design our dynamic programming algorithmic scheme, while specifying its main components:

• Time Space: k = 0, . . . , K.

• State Space: A state at time k is a pair (W, EX) with the following meaning:

-W= ∑ p̸ =p 0 (u),u≤k pX pu ;

Explanation: W means the amount of values pX pu ≤ (p 0 (u) -1) which have been decided until k and which are not related to p 0 (u) values. EX provides us with the location, inside the window {Min1(k), . . . , Max1(k)} of the sum of values p 0 (u)X p 0 (u),u decided until k. Defining the states this way will ensure that the number of states remains bounded by a polynomial function of P and K.

• Initial state: (0, 0): no decision has been taken.

• Final State: Any pair (W, EX) related to time value K.

• Decisions: At any k = 0, . . . , K -1, and for any current state (W, EX) we choose:

-A value z which between Min1(k + 1) and Max1(k + 1).

Explanation: Decision w means that we follow Section 4.3.2 and choose values X p,k+1 , p ̸ = p 0 (k + 1) while using the table Table_Bot. Table_Bot[k+1] provides us with the 3-uple (w, v, Y) such that v is the optimal value of the Aux_Bot(k + 1, w) instance of Aux_Bot related to w and k + 1. As for z, it corresponds to the increment of the new difference ∑ u≤k+1 p 0 (u)Z u -Min1(k +

1) when we shift to k + 1, and refers to a quantity p 0 (k + 1)X p 0 (k+1),k+1 = z -Min1(k + 1) + Min1(k) -EX.

• Feasibility of a decision:

z -Min1(k + 1) + Min1(k) -EX must be non negative and a multiple of

• Transitions: Transition from k to k + 1 works as follows:

-W becomes W + w;

-EX becomes z.

Single robot configuration

This last case does not involve dynamic programming. Since P = 1, we simplify our notations as follows: c pk becomes c k and X t pk becomes X t k . Then our Multi_Bot problem becomes:

At this point, Multi_Bot_dec_P_1 is no more than a Transportation problem, i.e. an ILP with a totally unimodular underlying constraint matrix related to a complete bipartite graph. We conclude.

A heuristic algorithm for the general case

We propose now an algorithm H_Bot for the general case, which relies on the arguments used in order to get above theoretical results.

This algorithm starts by capitalizing on the knowledge provided by Lemma 4.

Second step

The second Step of H_Bot relies on the following compact representation of a Multi_Bot solution. We consider here a Multi_Bot solution as given by:

• A vector Z = (Z t k , t = 1, . . . , T, k = 1, . . . , K), which provides the X t p 0 (k),k values;

• A vector ∆ = (∆ t k , t = 1, . . . T, k = 1, . . . , K), where every

Such a pair (Z, ∆), with indexation on T • K, gives rise to a Multi_Bot solution X through the formulas:

• For any t, k, p:

So H_Bot_Second_Step starts from the values Z t k = X t p 0 (k),k computed by H_Bot_First_Step. Then, for every pair (t 0 , k 0 ), it picks up (w 0 , v 0 , Y 0 ) in Table_Bot[k 0 ] in such a way that decreasing Z t 0 k 0 by (c p 0 (k 0 ),k 0 (∑ t Z t 0 k 0 )n k 0 + v 0 )/c p 0 (k 0 ),k 0 and setting X t 0 p,k 0 = (Y t 0 k 0 ) p = (Y 0 ) p for any p ̸ = p 0 (k 0 ) keeps the constraints and yields the best decrease of α • H Max + β • H. carry 2 types of loads. There are two ways to approach such question: trying either to design an exact polynomial-time algorithm for it or to build a reduction from some (strongly) NP-hard problem.

Our first idea is to consider the reduction presented in Theorem 4.2.4, page 73, from Bin_Packing to the general Multi_Bot problem. We wonder whether it could be adapted so that the case K = 2 could be proven strongly NP-hard.

By applying exactly this reduction, we prove in fact that the case K = 2 of the Multi_Bot problem is harder than Bin_Packing_2, which corresponds to Bin_Packing where the items admit only 2 distinct weights. [START_REF] Filippi | An asymptotically exact algorithm for the high-multiplicity bin packing problem[END_REF] showed that Bin_Packing_2 is in P. Therefore, the reduction proposed in Theorem 4.2.4 does not allow us to prove that Multi_Bot with K = 2 is strongly NP-hard. Furthermore, it was proven recently [START_REF] Goemans | Polynomiality for bin packing with a constant number of item types[END_REF] that Bin_Packing with a constant number of items (not only 2 but also 3, 4, 5,. . . ) is in P. As a consequence, there is no hope that this reduction could help us to fix the complexity. On one hand, the observations made above imply that a trickier reduction would be needed if the case K = 2 is strongly NP-hard. On the other hand, they give us some hope to identify an exact polynomial-time algorithm. For the case K = 1, we proposed a dynamic programming algorithm (Section 4.3.3,page 78).

A first approach could be to adapt this algorithm for the case K = 2.

The states of the DP algorithm proposed for K = 1 were made up of two components: value W, which represents the contribution of the p-bots with p ̸ = p 0 (k), and value EX which represents the contribution of the most efficient configurations p 0 (k). Thanks to Lemma 4.2.1, we know that keeping a similar value W in states is certainly a good idea as it will be polynomially bounded. Nevertheless, our analysis of value EX for the case K = 1 does not hold anymore now for K = 2. It seems that there is considerable effort to do in order to adapt this idea to the case K = 2.

In brief, starting from the DP algorithm for case K = 1 and modifying the state space in a suitable way would be our first approach to tackle the case K = 2.