Kader Sanogo
email: ksanogo@cesi.fr

Abdelkader Mekhalef Benhafssa A , M'hammed Sahnoun

Belgacem Bettayeb
email: bbettayeb@cesi.fr

Moussa Abderrahim
email: abderrahim.moussa@univ-relizane.dz

Abdelghani Bekrar
email: abdelghani.bekrar@uphf.fr

A multi-agent system simulation based approach for collision avoidance in integrated Job-Shop Scheduling Problem with transportation tasks

Keywords: JSSP, Transportation tasks, AGV, Simulation, Multi-agent system, Collision avoidance

At the operational level of Flexible Manufacturing Systems (FMS), several research works have developed solutions not fully realizable considering the operational constraints, which can be difficult to model. One of the well-known problems in FMS is the Job-Shop Scheduling Problem (JSSP) with transportation tasks. Indeed, this problem is addressed by many researchers, but most of their studies do not consider operational constraints such as collision avoidance between transporters. Moreover, optimized scheduling may contain deadlock situations due to often neglected geometric constraints. Therefore, in this paper, we propose a simulation approach based on a multi-agent system to test the optimized results known in the literature in more realistic conditions, where collision avoidance between transporters is considered. We propose as well a sim-optimization approach to explore suitable solutions considering collision avoidance constraints. In addition, an algorithm is proposed to solve deadlocks. The obtained results highlight the impact of collision avoidance on the performance of the literature solutions while being more realistic. Furthermore, these results demonstrate the efficiency of the proposed algorithms, since all identified collisions are avoided and all deadlocks are also solved. The proposed approach is expected to be more attractive to the industries as it ensures a small gap between the theoretical and actual results.

Introduction

For several decades, the fierce competitiveness of industrial companies leaves no room for inefficiency and wasting of time and resources. Companies are constantly looking for new processes, new technologies, and new paradigms to optimize their industrial productions and increase customer satisfaction. This involves solving several operational optimization problems within the production system of the company.

The planning and scheduling of production tasks represent one of the most difficult and challenging optimization problems usually encountered by operations managers in all industrial sectors. Thus, several research works have studied these types of problems for different configurations and environments of production systems using different approaches. The proposed solutions have found many real-world applications, although sometimes assumptions might be more or less realistic, which creates a gap between the actual and the theoretical performances of the solutions. This is why some classic problems in the literature are perpetually revisited to include new assumptions, to take into account new technologies, new organizational paradigms, new external and internal constraints, or to use new methods and tools of resolution.

In Flexible Manufacturing Systems (FMS) environment, a great interest is noted on several variants of the wellknown Job-Shop Scheduling Problem (JSSP) [START_REF] Chen | A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem[END_REF]. The JSSP is a problem in which products processing must be sequenced on several workstations [START_REF] Ahmadian | A meta-heuristic to solve the just-in-time job-shop scheduling problem[END_REF]. Each product must undergo several operations one after the other, and each of these operations must be carried out by a particular machine defined in a predetermined order. Each machine can only perform a specific operation per product (job) and cannot be substituted by any other one. The main objective of the JSSP is to optimize the scheduling resulting from the sequencing of the operations of the jobs (products) to be processed on each machine, while respecting the precedence constraints between the operations constituting each job.

The laborious and repetitive tasks of transporting products between the different machines and stocks on the shop floor are at the heart of the job-shop activities, as they have a direct impact on the efficiency of industrial activities. Thanks to the progress of industrial automation, these transportation tasks are now performed by mobile robotic systems called Autonomous Guided Vehicles (AGV). It is therefore becoming essential to optimize the scheduling of the transportation tasks as well as the production tasks.

Although several researchers have tried to solve the JSSP with transportation tasks, most of these works did not consider operational constraints such as shared pathways and collision avoidance between transporters. Consequently, the optimized scheduling can, in practice, generate some deadlocks due to the often neglected spacial and geometric constraints.

Thus, we propose in this paper, a simulation approach based on a multi-agent system in order to simulate some JSSP optimized results from the literature ( [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF]), and to put in evidence the possible collisions and deadlocks. As a consequence, algorithms for implementing collision avoidance and for fixing deadlocks (or blocking situations) are suggested. The simulations are carried out on the well-known benchmark instances proposed by Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF] while using the scheduling extracted from the Variable Neighborhood Search (VNS) algorithm developed by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF].

This paper is organized as follows: Section 2 presents a literature review related to JSSP with transportation tasks, and collisions and deadlocks avoidance issues. Section 3 is dedicated to the problem description, where we describe the model of the considered JSSP, the transportation tasks, and the problem of collision avoidance and deadlocks. Section 4 contains the main contribution of this work, which are the proposed approach and the suggested algorithmic solutions. In Section 5, experiments are conducted, and the results are highlighted and discussed. Finally, a conclusion ends this paper.

Related work

The issue of job-shop scheduling is at the crossroads with algorithmics, mathematics, operations research, and industrial engineering [START_REF] Zhang | Review of job shop scheduling research and its new perspectives under industry 4.0[END_REF][START_REF] Mohan | A review of dynamic job shop scheduling techniques[END_REF]. Thereby, researchers have handled it by focusing on one or many aspects according to their specialties. Several researchers have considered transportation tasks in their works, such as [START_REF] Moussa | Modular mobile manipulators coalition formation through distributed transportation tasks allocation[END_REF][START_REF] Mokhtari | A multi-objective model for cleaner production-transportation planning in manufacturing plants via fuzzy goal programming[END_REF][START_REF] Erik | Integration of material handling devices assignment and facility layout problems[END_REF]. The resulting problem is considered as a simultaneous scheduling of production and transportation tasks. Their main objective is the minimization of both costs of production and completion time of the whole scheduling (Cmax, a.k.a. makespan).

Many studies dealing with the problem of transportation in job-shop problems are based on Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF] benchmark instances. They propose four different layouts, which are well-known in the literature, composed of four machines and one load/unload station (stock) while transportation tasks are done by two AGVs. They solve the problem as a nonlinear mixed integer programming model with the minimization of the makespan as the objective.

Taking it from there, Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF] address the JSSP in a vehicle-based manufacturing facility that is mainly related to the job assignment and resources. They consider the processing resources that accomplish fabrication tasks for specific products and the transportation resources as the two types of resources belonging to the job-shop production cell. They use a Variable Neighborhood Search (VNS) algorithm to schedule both product manufacturing and transportation tasks in the aim to minimize the makespan. They also improve the lower bounds found by Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF] with a new calculation method.

Fontes and Homayouni [START_REF] Fontes | Joint production and transportation scheduling in flexible manufacturing systems[END_REF] consider integrated production and transportation scheduling problem as two interrelated problems that need to be addressed simultaneously. They formulate the joint production and transportation scheduling as a novel mixed integer linear programming model and show the efficiency of their model in finding optimal solutions by using a commercial software (Gurobi) for computational experiments on benchmark problem instances.

Ham [START_REF] Ham | Transfer-robot task scheduling in job shop[END_REF] on his side consider machines and autonomous mobile robots (transporters) both as constraining resources. Then, he proposes a novel application of constraint programming for the JSSP with AGVs. This application proves its efficiency on well-known benchmark instances. He also proposes a medium-scale benchmark instance.

Saad et al. [START_REF] Saad | Scheduling for job shop problems with transportation and blocking no-wait constraints[END_REF] studies the transportation in the job-shop problem with blocking and no waiting constraints, which is an extension of the classical job-shop problem that takes into account transport operations and the absence of storage space between machines. They formulate the problem by means of a new disjunctive graph, model blocking situations, and describe properties of partial schedule that lead to deadlock situations. They solve the problem with both a greedy heuristic approach based on priority and avoiding blocking cycle rules and an exact method based on a Mixed Integer Linear Program (MILP).

Simulation has been used to solve several problems faced in FMS, such as workshop energy consumption [START_REF] Benhafssa | Optimizing energy-conscious dynamic flexible job shop scheduling: Multi-agent simulation approach[END_REF] and AGVs fleet size management [START_REF] Sahnoun | Optimization of transportation collaborative robots fleet size in flexible manufacturing systems[END_REF]. However, few works deal with the validation of optimized scheduling by simulation. Zaidi et al. [START_REF] Zaidi | Optimisation and simulation of transportation tasks in flexible job shop with muti-robot systems[END_REF] used simulation to demonstrate the difference between the simulated and the theoretical schedule in a simple example. This difference should be more pronounced with cases using defined paths of the robots.

Xu et al. [START_REF] Xu | A simulated multi-objective model for flexible job shop transportation scheduling[END_REF] are among the first ones to introduce a simulation approach to tackle the Flexible Job-Shop Scheduling Problem (FJSSP). Like Jianfeng et al. [START_REF] Jianfeng | A two-stage optimization algorithm for multi-objective job-shop scheduling problem considering job transport[END_REF], they develop a multi-objective scheduling algorithm that considers the following objectives: makespan, robot travel distance, time difference with due date, and critical waiting time. To do so, they develop a multi-agent-based simulator to test the proposed solution and implement a sim-optimization (simulation-optimization) based genetic multi-objective algorithm. The simulation model is featured to be interactive and allows getting all the real-time information such as remaining jobs, robot positions and machine conditions.

In this regard, sim-optimization has been an active field of research for the last decade to deal with FMS issues with operational constraints' consideration [START_REF] Klanke | Scheduling and batching with evolutionary algorithms in simulation-optimization of an industrial formulation plant[END_REF][START_REF] Piana | Hybrid evolutionary optimization of the operation of pipeless plants[END_REF]. This approach consists in combining optimization and simulation to solve complex problems that could not (or hardly) be solved by optimization alone [START_REF] Zambrano Rey | Reducing myopic behavior in fms control: A semi-heterarchical simulation-optimization approach[END_REF][START_REF] Amaran | Simulation optimization: a review of algorithms and applications. 4OR-Q[END_REF]. For example, A. Allal et al. [START_REF] Allal | Multi-agent based simulation-optimization of maintenance routing in offshore wind farms[END_REF] used a sim-optimization approach to deal with the routing and the scheduling of maintenance for offshore wind farms, which is actually a complex problem.

The implementation of concurrent processes in discrete event systems can lead to deadlocks, which can be defined as resource conflicts that prevent concurrent processes from completing their tasks [START_REF] Zajac | Structural on-line control policy for collision and deadlock resolution in multi-agv systems[END_REF]. A deadlock occurs when the four following conditions are met: (i) mutual exclusion, (ii) hold and wait, (iii) no pre-emption, and (iv) circular wait [START_REF] Coffman | System deadlocks[END_REF]. The first three conditions are always present in transportation systems based on AGVs [START_REF] Zajac | Structural on-line control policy for collision and deadlock resolution in multi-agv systems[END_REF]. Thus, avoiding the fourth condition to arise is an issue that is addressed in the literature. Researchers have proposed solutions that are suitable for centralized control systems [START_REF] Chen | Deadlock-solving traffic control methods for automated guided vehicle systems[END_REF], distributed control systems [START_REF] Zhou | Collision and deadlock avoidance in multirobot systems: A distributed approach[END_REF], or for both systems [START_REF] Zajac | A deadlock handling method for automated manufacturing systems[END_REF].

AGVs handling transportation tasks in a workshop is a fairly well documented issue in the literature. The research works can be divided into two categories according to the assumptions made. The first category limits the role of transporters to the simple execution of transportation tasks along a predefined path. This category neglects collision risks [START_REF] Xu | A simulated multi-objective model for flexible job shop transportation scheduling[END_REF][START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF], fleet management and/or disruptions due to breakdowns [START_REF] Fontes | Joint production and transportation scheduling in flexible manufacturing systems[END_REF][START_REF] Ham | Transfer-robot task scheduling in job shop[END_REF], battery capacity [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF][START_REF] Xiaohui | Metaheuristic for solving multi-objective job shop scheduling problem in a robotic cell[END_REF], etc. It should also be noted that this category mainly concerns works relating to JSSP with transportation tasks. The second category takes into account collision risks [START_REF] Sharad | Development of an intelligent agent-based agv controller for a flexible manufacturing system[END_REF][START_REF] Elena | Cooperative cloud robotics architecture for the coordination of multi-agv systems in industrial warehouses[END_REF], traffic routing [START_REF] Parham | Alleviating the collision states and fleet optimization by introducing a new generation of automated guided vehicle systems[END_REF][START_REF] Murakami | Time-space network model and milp formulation of the conflict-free routing problem of a capacitated agv system[END_REF], path planning [START_REF] Perez-Grau | Introducing autonomous aerial robots in industrial manufacturing[END_REF][START_REF] Zhong | Multi-agv scheduling for conflict-free path planning in automated container terminals[END_REF], deadlocks resolution [START_REF] Zajac | Structural on-line control policy for collision and deadlock resolution in multi-agv systems[END_REF], etc. The objective is to find a collision-free and time-optimized path [START_REF] Drótos | Suboptimal and conflict-free control of a fleet of agvs to serve online requests[END_REF][START_REF] Reith | Conflict-minimal routing for free-ranging transportation vehicles in in-house logistics based on an a-priori lane design[END_REF] for the transporters.

Through this literature review, we can see that the JSSP with transportation tasks is addressed in several studies, but these works mainly focus on the development of solutions based on optimization methods. Additionally, in optimization-based approaches, real operational constraints are usually neglected for simplification purposes. Therefore, the real implementation of these solutions might be difficult, as they do not match the real industrial environment, especially the spatial constraints. Furthermore, simulation, which can be considered as an intermediate step before the real implementation, allows considering more temporal and spatial constraints (e.g. space and shape constraints). Hence, in order to reduce the gap between theoretical study and real implementation, the following contributions are presented in this paper: (i) Verify the feasibility of optimized scheduling by simulation since, to the best of our knowledge, no study focuses on verification by simulation of the proposed optimized solutions for well-known benchmark instances, such as those of Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF]; (ii) Consider collision avoidance as an operational constraint during simulation, since collision avoidance in JSSPs with transport tasks is not a well-covered issue. To this end, algorithms for collision avoidance and pathways negotiation are proposed. We also introduce a sim-optimization approach to find optimized and more suitable schedules.; (iii) Show the impacts of collision avoidance on optimized schedule results and propose a heuristic, based on collaboration between transporters, to solve deadlocks during simulations; (iv) Test the sensitivity of our approach by varying the processing times and verify its ability to adapt the optimized scheduling.

Problem description

This section will be devoted to the description of JSSP, transportation tasks within the workshop, collision avoidance, and deadlocks.

JSSP

The JSSP is the problem of sequencing a set of jobs J = {J 1 , J 2 , ..., J I } to be processed on a set of machines M = {M 1 , M 2 , ..., M M } in a job-shop organization. Each job J i is composed of a sequence (O i1 , O i2 , ..., O in ) of operations to be performed consecutively. The operation O i j , which means operation j of job i, can be performed only on the machine M k ∈ M with the processing time τ k . Furthermore, a machine can only perform one operation at a time, and preemption of operations is not allowed.

Transportation task

During the manufacturing process, a job J i may move from one machine to another to perform its next operation. This transportation task is carried out by one of the single-load AGVs available V p ∈ V. A transportation task is denoted by T i, j , which means the transportation of the job J i to the machine selected to perform the operation O i, j .

In this paper, our objective is not to find a collision-free path but to avoid collisions and deadlocks while transporters follow a static predetermined path (also called motion planning [START_REF] Kunchev | Path planning and obstacle avoidance for autonomous mobile robots: A review[END_REF]). In fact, to the best of our knowledge, this work is the first to consider collision avoidance between transporters when they are carrying out transportation tasks while following a predefined path within JSSP. Besides, this work proposes algorithms to deal with deadlocks or blocking situations that could happen in this context.

Collision avoidance & Deadlocks

Collisions and deadlocks need to be prevented for the safety of the workshop [START_REF] Moorthy | Deadlock prediction and avoidance in an agv system[END_REF]. Collision avoidance is defined as the simple act of preventing AGVs from colliding. Besides, a deadlock (or blocking situation) is a problem that prevents the execution from proceeding well to completion. It is a situation in which an AGV is blocked and cannot perform any operations [START_REF] De Ryck | Automated guided vehicle systems, state-of-the-art control algorithms and techniques[END_REF][START_REF] Silitonga | Application of simulation of dining philosophers problem in concurrent process[END_REF].

Two methods are mentioned in [START_REF] De Ryck | Automated guided vehicle systems, state-of-the-art control algorithms and techniques[END_REF] to avoid collisions and deadlocks in a static predetermined path: (i) Centralized motion planning, which is currently used in most industrial AGV systems. It aims to plan a collision-free and deadlock-free path for the entire fleet of AGVs by a central controller, (ii) Decentralized motion planning, which allows AGVs to react individually to avoid collisions and/or deadlocks according to their awareness of the local environment [START_REF] De Ryck | Decentral task allocation for industrial agv-systems with routing constraints[END_REF][START_REF] De Ryck | Resource management in decentralized industrial automated guided vehicle systems[END_REF]. Recently, hybrid approaches were developed to take advantage of the centralized and decentralized methods to control the robot fleet and define a strategy of collision avoidance [START_REF] Moussa | Modular mobile manipulators coalition formation through distributed transportation tasks allocation[END_REF]. For this study, we decided to adopt hybrid motion planning based on optimization and simulation methods. As it is based on the local reaction of AGVs, this method is, therefore, more appropriate in a multi-agent system rather than the heavy computational demands of a central controller.

To implement collision avoidance, a safety area is defined around each AGV. When two AGVs are too close to entering each other's safety area, the one behind must stop to avoid hitting the one ahead. If the AGV ahead is waiting for a job before handling a transportation task, the AGV behind has to stay motionless until the AGV ahead moves. Taking from there, the following deadlock situation is identified and could happen: V p is waiting for the job J i before handling T i, j . But, before completing the operation O i, j , J i has to be transported by V q for operation O i, j-1 . Thus, while V p is still waiting for T i, j , V q is coming behind V p for T O i, j-1 . Therefore, due to collision avoidance, V q will stay motionless behind V p until it moves. Consequently, O i, j will never happen because O i, j-1 can not be performed either.

Methods

This section will address the description of the experimental method and the proposed solutions, the benchmark instances and the simulation framework used for this work.

Experimental protocol

In order to achieve the goals of this study and to experiment the proposed solutions, we first define our experimental procedure, which is illustrated in Figure 1. The experimental method aims to: check the feasibility of known-optimized scheduling proposed in the literature, consider collision avoidance between AGVs and exhibit its effects on the makespan, and then implement a heuristic to solve deadlocks. The method is composed of the following steps:

1. Find a JSSP benchmark instance with a known optimized solution of the literature: The instance should take into account transportation tasks performed by AGVs as well as processing tasks performed by production machines. 2. Simulate the schedule as it is: In this step, the simulation of both schedules of AGVs and machines is executed to detect potential collision situations without considering their effect. The simulation must remain faithful to the information collected in the previous step. 3. Simulate the schedules with collision avoidance: It consists of considering collision avoidance between AGVs during the simulation. It means that all collision situations observed in the previous step are prevented. 4. Fix deadlocks: at this stage, it is a matter of applying the proposed algorithm to fix deadlocks. 5. Keep the makespan: once the execution is completed, we retain the makespan value (also called Cmax). 6. Sim-optimization process: If a gap is observed between the makespans of Type 1 and Type 2 simulations, we run the whole process (VNS optimization and type 2 simulation) until an equivalent makespan is reached or the sim-optimization process is completed.

Proposed solutions

In this work, two heuristics are proposed: an algorithm for collision avoidance and another for fixing deadlocks. These algorithms are inspired by traffic regulations and bird flocking.

Collision avoidance

The collision avoidance algorithm is inspired by bird flight. Birds fly in tight rows when they are in colonies while keeping a minimum distance to avoid colliding. Based on the same principle, the collision avoidance rule allows AGVs to be far enough separated to avoid colliding. To do so, a safety area is defined around each AGV. If another AGV is about to penetrate this safety area, it has to stop. This is presented on Figure 2. It is also assumed that each AGV has a field of view centered on its steering. The pseudocode of the proposed algorithm for implementing the collision avoidance is shown on Algorithm 1, which ensures that frontal, rear, and side impacts are all prevented. It is a scalable and low-computational algorithm that is executed by each AGV within the fleet. Hence, collisions are avoided in a decentralized way, whatever the fleet size. In [START_REF] Sanogo | Multi-agent simulation for flexible job-shop scheduling problem with traffic-aware routing[END_REF], a study with a fleet size ranging from 2 to 10 AGVs was conducted.

Algorithm 1 Pseudocode of collision avoidance algorithm

Input: any AGV within the fleet Output: the AGV motion planning 1: procedure AVOID COLLISIONS(current agv)

2:
if any other transporter in the safety area then 3:

if any other transporter the field of view then end if 9: end procedure In a more complex topology of the environment, the local perceptions of each AGV are not enough to avoid blocking situations. For that, more global perceptions, based on information exchange between AGVs and external sensors installed in the workshop, are necessary to avoid such situations. When an intersection or a turn is present on the AGV path, it can create blocking situations if the corridors are not wide enough for two AGVs. In this case, we assume that each robot reserves a part of the path to follow from its current position until the next intersection, as shown in Figure 4. Checkpoints are defined as the threshold before the intersection (see Figure 3), where the AGV (called checker) verifies the state of the next portion of the path that will be used for its travel. Algorithm 2 is proposed for implementing this path verification. The following situations can be distinguished:

1. Another AGV moves towards the checker's position along the path. Then, the checker must wait until the path is free because it is already reserved by the other one. 2. Another AGV moves in the opposite direction to the checker along the path. Then, the checker can reserve a portion of the path and go on. Frontal impacts are prevented. 3. The path is free. Then, the AGV reserves a path portion and continues. let mypath: the bi-directional path the checker is about to take end if 11: end procedure

Fixing deadlocks

The proposed solution for fixing deadlocks (or blocking situations) is based on collaboration between AGVs. In fact, when an AGV meets another AGV which is waiting for a job to perform an operation that should be preceded by another operation, both AGVs exchange their remaining transportation tasks. The relevance of this collaboration lies in the fact that the number of operations of each job is known by AGVs. Therefore, they know whether a job J i is ready for a particular operation O i, j according to the σ (σ < j) previous performed operations

(O i,1 , ..., O i,σ-2 , O i,σ-1 , O i,σ )
of J i and the rank of O i, j in J i operation-list. This collaboration prevents any deadlocks and enables the successful completion of the execution. Algorithm 3 shows the pseudocode of the algorithm for implementing this collaboration. It should be noted that Algorithm 3 is appropriate for decentralized deadlocks resolution since it does not involve a central controller to redefine the pathways and/or reschedule the AGVs. Moreover, in the current study, deadlocks occur when AGVs share pathways as a common resource. Algorithm 3 ensures that no robot can monopolize the pathway for its own use. It also represents a fast algorithm that can be used in the real-time decision process for a fleet of two or more transporters. if another agv is idle in front of current agv then 3:

get another agv current transportation task 4:

if another agv is waiting for J i to handle T i, j and J i is not ready for O i, j then 5:

EXCHANGE REMAINING TRANSPORTATION TASKS(current agv, another agv) end if 10: end procedure It may happen that AGV2 waits for the job it has just delivered to take it over during the next transportation task. In that case, AGV2 will wait until the completion of the job processing before moving on with it. If AGV1 comes while it is waiting, AGV1 must wait to avoid collisions. This is what the fifth line of Algorithm 3 means. In addition, it may also happen that exchanging the remaining transportation tasks between the two AGVs leads to another deadlock similar to the previous one. Thus, AGV2 will make an empty trip (also called "deadheading" [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF]) to allow AGV1 to complete its current transportation task. However, this scenario is quite rare.

Variable Neighborhood Search (VNS) algorithm

The VNS algorithm was first introduced by N. Mladenovic and P. Hansen in 1997 [START_REF] Mladenović | Variable neighborhood search[END_REF]. The VNS implementation proposed by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF] is used during our study. It is based on neighborhood switching and works to find the local optimum through the vertical local search as well as horizontal search to avoid the current valley. To do so, schedules are represented by two strings: the first one represents machines' production tasks and the second one represents vehicles' transportation tasks (see figure 5.(a)). From this two-string-based representation, A local search is initiated to explore the solution set for a better makespan. The algorithm uses two asynchronous local search stages: a local search is done to find a transportation string within the current transportation neighborhood, and then, a second local search is used on the production neighborhood to find the production string that gives the best Cmax with the current transportation string. This is repeated with all the elements from the current transportation neighborhood until the local search stop condition is met or a better production-transportation combination is found. Thereafter, the whole process is repeated with a new transportation neighborhood until reaching the stop condition. A detailed flowchart is sketched in Figure 5.(b). For more details, please refer to [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF].

Sim-optimization approach

As highlighted by Barton [START_REF] Barton | Simulation optimization using metamodels[END_REF], when a model has a large number of parameters or when one or more parameters have too many values, it becomes very difficult to evaluate all possible alternatives, requiring the use of optimization via simulation (OvS) techniques [START_REF] Soares Do Amaral | Metamodel-based simulation optimization: A systematic literature review[END_REF], which is a specific type of sim-optimization approaches. Indeed, integrating collision and deadlock avoidance constraints in the modeling of advanced schedules is not easy. We must consider and forecast any collision on each common portion of the pathway within the working environment. To alleviate this problem, the sim-optimization approach schematized in Figure 6 is used to find optimized and suitable schedules by considering collision avoidance. In fact, after running the VNS algorithm, the obtained schedule is simulated considering the collision avoidance constraint. If the simulated makespan is delayed, we look for another optimized schedule from VNS. To limit the computational effort, the process is stopped after 5 attempts since the VNS algorithm is configured to return a schedule after 50 runs. This approach aims to find feasible advanced schedules in simulation or, at least, find advanced schedules with the smallest delay.

Layouts & Instances

Experiments are carried out through simulations using the well-known benchmark instances proposed by Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF]. They proposed 4 different layouts of the job-shop, composed each of an L/U (load/unload) station and 4 machines. The L/U station is used as a storage place for all jobs before the beginning of processing (row material) and after the end of operations completion (finished products). Transportation tasks are carried out by two identical uni-charge AGVs. All transportation tasks start and end at the L/U station. Each layout has a particular trip orientation, travel times, and L/U station and machine location. They also proposed 10 different job sets, where each job set is composed of 5 to 8 jobs. Jobs are made up of several operations with the corresponding machines and the associated processing times. The proposed test instances are noted "EXαβ" where α and β represent respectively the job set and the layout. Notice that travel times and processing times are in seconds.

Table 1 shows the travel times between all elements of the workshop for each layout. In order to simulate the system, travel times are turned into travel distances. It is assumed that the distance unit is a meter and the speed of AGVs is 1 m/s (meter/second). When two elements can be connected by several paths, the shortest one is privileged. Therefore, the presented distances in Table 1 are the shortest. Figure 7

Simulation model

The simulation model is based on multi-agent system that allows an ease representation of complex systems. The proposed model involves 4 main agents that are: AGVs, machines, jobs, and stocks. Each machine is equipped with two buffers: an input-buffer for storing jobs before processing and an output-buffer for storing processed jobs before transportation. These buffers and the L/U station are considered as stocks. The interactions between agents are described as follows:

• AGVs pick up jobs from output-buffers (resp. the load station), and deliver them to input-buffers (resp. the unload station).

• Stocks store jobs before (resp. after) their processing by machines.

• Machines retrieve jobs from input-buffers, process them and store them in output-buffers.

• Jobs are transported by AGVs to the stocks.

For each agent, we consider the following assumptions: • AGV:

-AGVs are independent of each other.

-Each AGV can transfer one and only one job at a time.

-Time required to load and unload jobs from buffers is included in transportation time.

-AGVs have an orders list in which all the transportation tasks to be carried out are recorded with the jobs involved, the operations to be performed and the associated machines according to the scheduling.

-It is possible to know the current transportation task of AGVs thanks to the current-order list, which is the i th element of the orders-list.

-AGVs have to move through the direction imposed by the layout.

-AGVs have to respect exactly the defined scheduling, i.e. take the right job, follow the right path and go to the right machine as it is described in the scheduling.

-AGVs may collaborate, but should avoid collisions.

-Issues such as: failure, battery recharging, fleet management, etc. are not considered and left for future works.

• Machine:

-Machines completely independent.

-Each machine can perform one and only one operation at a time.

-Machine setup times and breakdowns are ignored.

-Machines process jobs according to the scheduling.

-All the machines are available at the beginning of the simulation.

• Job:

-Jobs are independent.

-Each job can be processed on one and only one machine at a time.

-Each job can be transported by one and only one AGV at a time.

-Job operations must be performed according to the define sequence.

-Preemption of operation is not allowed.

• Stock:

-Machine buffers have an identical limited capacity.

-L/U station capacity is unlimited.

-Stocks can store products as long as possible.

Framework

The whole simulation model, composed of the MAS, the layout and the instances, is implemented on NetLogo 6.2. NetLogo is both a programming language and a simulator that is used to model and simulate systems making several agent's interactions. It works as a desktop application and makes the modeled system able to be used directly and easily by any other user. Each agent is called turtle and each turtle belongs to a breed. It is possible to define global parameters for the whole model, and parameters can be restricted to a breed. Characteristics or parameters defined for a particular breed can not be called by another breed. In our case for example, AGVs, machines, jobs and stocks are considered as 4 different breeds. Figure 8 shows a screenshot of layout 2 simulation interface.

Simulation begins with the setup button. It initializes (or reinitializes) the model and the simulation environment. Once the environment is set up, the simulation is launched with the button go. The latter can be used either in one time or forever mode. In the first mode, it triggers an action and then stops. The second mode, on its side, ensures a continuous execution of the simulation. It will stop only if a stop condition is specified in the code or if the go button is pressed again.

The simulation time is counted in ticks, which is a simulation step. In order to be able to simulate the production and transportation tasks, we assume that 20 ticks represent 1 second. Therefore, if an operation should be performed in 8 seconds in the benchmark instances, this operation will be performed in 8 × 20 = 160 ticks during the simulation.

Likewise, an AGV moves a patch forward in one tick. Thus, travel that should be completed in 2 seconds, for example, will be completed in 2 × 20 = 40 ticks.

The simulator presented in Figure 8 allows real-time visualization of the evolution of agents, and it is able to perform a dynamic scheduling simulation optimization process [START_REF] Sanogo | Multi-agent simulation for flexible job-shop scheduling problem with traffic-aware routing[END_REF] as well as the possibility to provide advanced schedules. In this latter case, the simulator takes the advanced scheduling matrix as input. Table 2 presents the matrix of the instance EX11 advanced scheduling (taken as an example), generated after optimization using VNS algorithm [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF]. The first row of Table 2 reports jobs (J i ). The second line gives the locations where jobs must be sent. The location can be a machine (M k ) or the L/U station. The third line identifies the transporter (T p ) in charge of the transportation. And finally, the fourth line refers to the operations (O i j ) that jobs must undergo. "R" is the job return to the L/U station after being processed. The matrix is read by column. For example, the first column means that the transporter T 2 must transport the job J 3 to the machine M 3 to undergo the operation O 31 . By doing so, all the transportation tasks can be extracted for each transporter, and put in their orders-list. Similarly, production tasks can be extracted for each machine.

Once production and transportation tasks are extracted, the model is simulated. At the end of each simulation, the simulator reports the makespan, the number of collisions encountered and the number of deadlocks solved. This process is schematized on Figure 9.

J 3 J 4 J 1 J 1 J 2 J 1 J 5 J 3 J 3 J 4 J 5 J 2 J 2 J 1 J 5 J 4 J 3 J 2 M 3 M 4 M 1 M 2 M 1 M 4 M 3 M 4 M 1 M 2 M 1 M 3 M 2 L/U L/U L/U L/U L/U T 2 T 2 T 1 T 1 T 2 T 2 T 1 T 1 T 2 T 1 T 1 T 2 T 2 T 1 T 1 T 2 T 2 T 1 O 31 O 41 O 11 O 12 O 21 O 13 O 51 O 32 O 33 O 42 O 52 O 22 O 23 R R R R R

Sensitivity analysis

In order to go further in our study, simulations with a probabilistic consideration were conducted. It was assumed that machine processing times follow a normal distribution N(µ, σ 2 ): µ, the mean value is the machine processing time as presented in the job set instance, and σ is the standard deviation that represents the margin of error from the mean. σ is written as σ = λ × µ, where λ is the relative standard deviation (RSD) divided by 100 (RS D = σ µ × 100), considered as the margin of error. For example, in job set 1 in Appendix A, the processing time of the first operation of job 1 is 8s. However, with probabilistic consideration, this processing time will be given by the normal distribution N(8, (8λ) 2 ). The same approach will be used for all other operations. Three different cases were tested according to the value of λ: 0.1 (RSD = 10%), 0.2 (RSD = 20%), and 0.3 (RSD = 30%). For each value of λ, all the benchmark instances (10 job sets for 4 layouts) were simulated 50 times in both situations (with and without collision avoidance consideration). At the end of each run, the makespan, the number of collisions, and the number of deadlocks were reported. Once the 50 runs are completed, we calculate the average and standard deviation of the reported values. Finally, these results are compared with the optimization results.

Experiments

This section is dedicated to the presentation of the experiments conducted on the simulator developed using Netlogo 6.2. The hardware used is an Intel(R) Core(TM) i7-8565U CPU with 1.99 GHz and 16.0 Go RAM. As announced previously, the aims of these experiments are:

• check the feasibility of a known optimized schedule by simulation;

• consider collision avoidance and exhibit its effects;

• identify the deadlocks and blocking situations;

• implement the proposed algorithms to fix the troubles encountered.

Experimental protocol

The experiments consist of simulating the scheduling proposed by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF], which are, to the best of our knowledge, among the best results in the literature that optimize the job-shop scheduling problem using the benchmark instances of Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF]. They proposed a solution based on the Variable Neighborhood Search (VNS) algorithm to schedule the production of a set of jobs with consideration of transportation tasks. The aim of their work is to minimize the maximum completion time of the job sets (Cmax) and to improve the lower bound proposed in the literature with a new calculation method. The results of Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF] do not consider products' return time to the L/U station because they focus only on the minimization of the maximum completion time of production tasks. In our case, transportation tasks are as important as production tasks. Therefore, we consider the makespan as the maximum completion time of both production and transportation tasks. Consequently, the results of Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF] are presented in both situations: with and without products' return time consideration. On one hand, the experiments prove the efficiency of their approach compared to the results of [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF], and on the other hand, they are used to generate the schedules that will be simulated.

Our experimentation process is described as follows:

1. We run each instance with the algorithm proposed by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF] 50 times. Each instance is launched with and without products' return times, and then, the best-optimized scheduling is selected for each case. 2. The best-optimized scheduling with products' return to the L/U station is simulated for each instance. 3. The best-optimized scheduling with products' return to the L/U station is simulated again with collision avoidance consideration between AGVs. If a deadlock is encountered, Algorithm 3 presented in section 4.2.2 is implemented. 4. If the simulation with collision avoidance consideration is delayed, the sim-optimization approach is applied to find a suitable scheduling. As mentioned in Section 4.4, this approach is limited to 5 attempts.

Instance Cmax [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF] The number of deadlocks solved → their new number after the sim-optimization.)

Numerical results

Optimization and simulation results of the benchmark instances are presented in Table 3. The benchmark instances are indicated in "Instance" column. Instances with an asterisk are those concerned by the sim-optimization approach. "Cmax" column represents the optimized results of the original benchmark instances proposed by Bilge et al. [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF]. "LB" column represents the lower bounds obtained by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF] with their new calculation method. The column "BFS" represents the Best Found Solution obtained with the VNS algorithm proposed by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF]. This column, like "Cmax" column, does not take into account the return of products to the L/U station after processing. This is done in order to compare these two columns and to highlight the efficiency of the latter, which is giving better results in most cases.

"BFS-L/U" column represents the Best-Found Solution with products' return to the L/U station using the VNS algorithm proposed by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF] among all the run of the algorithm. This will, firstly, allow including products' return time in the makespan and, secondly, to better highlight AGVs' collision risks. "Type 1 simulation" column represents the makespan obtained by the simulation of BFS-L/U scheduling, and "Type 2 simulation" column represents the makespan obtained by the simulation with collision avoidance consideration of the BFS-L/U scheduling. "Type 3 simulation" column relates the values of the sim-optimization approach. Values in brackets are the corresponding makespan obtained by the VNS algorithm during the sim-optimization process. The column "#Collisions" represents the number of collisions encountered during Type 1 simulation and finally, the column "#Deadlocks" represents the number of deadlocks fixed thanks to Algorithm 3 during Type 2 simulation. In these last two columns, the arrow (→) indicates the new values found after sim-optimization process.

Discussion

"BFS-L/U", "Type 1 simulation" and "Type 2 simulation" columns of Table 3 are used to make a comparison between the three scenarios. "BFS-L/U" is considered as the reference of comparison, which is the theoretical solution. It can be observed that the values of "BFS-L/U" and "Type 1 simulation" columns are globally identical, with a very small difference of less than 0.15s in the worst case (for example EX31 and EX82). This difference is due to the computation approximation of C++ for VNS and NetLogo for simulation. This first result validates the simulator and demonstrates the feasibility by simulation of the schedules obtained from VNS algorithm without collision consideration. The simulation satisfies exactly all the characteristics of the generated scheduling: the sequence of transportation tasks of each AGV, the sequence of processing tasks of each machine, and the travel time of the layout were the same in both cases.

Regarding the different results presented in Table 3, we can make the following conclusions:

• Collision avoidance consideration increases the makespan: This phenomenon is more noticeable when looking at Figure 10. The different charts are used to compare the obtained Cmax for both types of simulation. There are 50% of significant makespan increases (more than 1s) for layouts 1 and 2, 70% for layout 3, and 30% for layout 4. This can be explained by the fact that AGVs delay each other due to collision avoidance. Indeed, when an AGV is waiting for a task to be processed, the one following it is obliged to wait until the former finishes its task, which creates a delay in its scheduling. This can be illustrated in Figure 11 which represents the Gantt diagrams of the instance EX12 using simulation types 1 and 2. The schedules resulting from type 2 simulations contain an asterisk ("*"). On AGV2 scheduling after type 2 simulation, it can be noted a longer delay between T O 4,2 and T O 5,2 compared to the scheduling of type 1 simulation. This is because AGV2 must stop behind AGV1 while the latter was waiting for J 2 before continuing. It should also be noted that this waiting time delayed AGV2 scheduling. However, there is an exception when the processing time of the job to be loaded is greater than the sum of travel time and motionless time. Indeed, if an AGV comes to load a job that is still being processed on the machine, it will have to wait until the operation is completed, regardless of what has happened on its way. Therefore, its scheduling will not be delayed. This phenomenon can be observed on EX32 Gantt diagrams, where the makespan is still 95s despite the recorded collision. In Figure 12, there is no difference between the two schedules, while the collision encountered took place at 77.3s. Figure 13 is a zoom on AGVs Gantt diagrams at the moment of collision. During type 1 simulation, AGV1 meets AGV2 at 77.3s, arrives to its destination at 81.4s, and waits until J 1 processing completion at 82.6s. In type 2 simulation, AGV1 waits behind AGV2 from 77.3 to 78.65s, and finally arrives at 82.6s to load J 1 .

• Known-optimized scheduling can be disturbed: An AGV delaying another due to collision avoidance and/or job waiting can disturb optimized scheduling. For example, if an operation O xy was initially scheduled to be processed before another operation O x ′ y ′ and if the operation O xy is delayed, the initial sequence may no longer be respected. Sometimes, this can lead to resource conflicts, and therefore deadlocks. We observe that some collisions avoided lead to deadlocks. That is why, in Table 3, the number of deadlocks is always less than or equal to the number of collisions, except for EX82, which is presenting another phenomenon explained in the next paragraph.

• A deadlock resolution can lead to new ones: This phenomenon was observed with EX82. We counted 5 deadlocks and 3 collisions, but this only accounts for the situations where the AGVs encountered issues after exchanging the remaining transportation tasks. Subsequently, the AGVs encountered new deadlocks due to job waiting and/or collision avoidance. On Figure 14, the three collisions identified took place at the 45th, 60th, and 145th seconds. But, the transportation task exchanges took place at the 45th, 60th, 75th, 91st, and 124th • An AGV scheduling with long waiting times increases deadlock risks: There are optimized schedules that force the AGV to wait a long time for a job. During this time, the AGV blocks the path and can interfere with the activities of other AGVs. This is the case, for example, for EX82, EX63, and EX83.

• Routing flexibility avoids deadlocks: The more flexible the layout is in terms of routing, the less risk of AGVs meeting in the corridors. Therefore, this avoids situations leading to deadlocks [START_REF] Mohammadi | Toward high degree flexible routing in collision-free fmss through automated guided vehicles' dynamic strategy: A simulation metamodel[END_REF] and explains why no deadlocks were recorded for layouts 1 and 4, which offer more possibilities to reach a destination. However, • Schedules with same Cmax could be different: This phenomenon, highlighted thanks to simulation, has been observed during the sim-optimization phase. We have indeed found schedules with the same Cmax after optimization but with different behaviors on simulation. For example, the former BFS-L/U of EX62 is 102s, its type 2 simulation presents two collisions and one deadlock and provides a Cmax of 108.5s. However, after sim-optimization, the new schedule gives a Cmax of 102s with only one collision and zero deadlocks for a Cmax of optimisation of 102. Figure 15 and Figure 16 show the before and after sim-optimisation schedules with their type 1 and Type 2 simulations. This phenomenon shows simulation relevance in exhibiting theoretical schedules' behaviors before their real potential implementation.

• Best optimized schedules are not always the most suitable: This phenomenon is highlighted by Type 3 simulation column in Table 3. Actually, it can happen that schedules with degraded Cmax give much better results in type 2 simulation than the BFS-L/U. For instance, in EX12, the BFS-L/U is 92s and its type 2 simulation reports 102.8s. However, after the sim-optimization process, the VNS algorithm gave a scheduling with 99s as Cmax, which is worse than the BFS-L/U, but whose type 2 simulation result is also 99s, so better than 102.8s. Several instances such as EX12, EX94, EX61, and EX71 are also affected by this phenomenon.

Furthermore, it can be noted that the algorithm for fixing deadlocks (Algorithm 3) avoids getting stuck in deadlocks. Its efficiency is proven given that all the deadlocks identified during the simulations have been overcome. However, as it is based on the local perception of AGVs, this algorithm can generate other deadlocks in the future, as is the case of EX82.

In addition, the makespan increase observed with type 2 simulations is the consequence of real operational constraints' consideration, particularly collision avoidance between AGVs. This makes the results more realistic and questions the optimized solutions proposed in the literature. Indeed, many of the proposed schedules would not be feasible as it stands without the deadlocks fixing algorithm. Hence, these literature results will be hardly exploitable by companies if they are not close to the reality in industries. The process of sim-optimization is a safe way to explore the space of optimized solutions and test their feasibility. Through these experiments, it was found that an instance can admit several equivalent solutions (i.e. same Cmax) but whose results in the simulation are different, so a priori, they will be different in the real implementation. Moreover, notice that loading and unloading times of jobs [START_REF] Sanogo | Multi-agent simulation for flexible job-shop scheduling problem with traffic-aware routing[END_REF] are not considered in this study to be able to compare with the literature results. The consideration of these aspects will also confirm our hypothesis, which states that realistic considerations degrade theoretical solutions, but reduce the gap between theoretical studies and real production systems (avg, sd) (120.6, 1.2) (122.7, 0.8) (132.9, 1.3) (147.1, 0.9) (116.0, 0.1) (139.9, 1.7) (159.3, 0.8) (169.3, 2.8) (131.4, 1.2) (171.2, 3.4) Type 2 simulation (avg, sd) (120.3, 0.8) (125.9, 1.5) (133.3, 1.7) (147.2, 0.9) (116.2, 0.2) (144.9, 1.7) (162.6, 0.1) (174.6, 3.1) (131.9, 1.3) (174.6, 2.7) #Collisions (min, avg, max) (0, 0.0, 1) (3, 3.0, 4) (0, 0.0, 1)

(3, 3, 3) (1, 1, 1)
(1, 1.9, 2)

(1, 1, 1) (0, 2.8, 6) (1, 2.3, 3) (0, 3.2, 5) #Deadlocks (min, avg, max) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) 20% of RSD (λ = 0. (min, avg, max) (0, 0.0, 1) (3, 3.0, 4) (0, 0.1, 1) (3, 3.9, 5) (0, 0.9, 1) (0, 2, 4)

(1, 1, 1) (1, 2.9, 6) (0, 1.9, 2) (0, 2.7, 5) #Deadlocks (min, avg, max) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) 30% of RSD (λ = 0. (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) Table 4: Sensitivity analysis of layout 1

Results of Sensitivity Analysis

The simulation results of the sensitivity analysis carried out on layout 1 of benchmark instances are presented in Table 4. The other results of layouts 2, 3, and 4 are presented in Appendix B.

Table 4 presents the obtained results in 4 main blocks of RSD value. Each block has 4 rows, which are: Type 1 simulation, Type 2 simulation, #Collisions, and #Deadlocks. For each type of simulation, the average (avg) and the standard deviation (sd) of the results of 50 runs are shown. Likewise, the minimum (min), the average (avg), and the maximum (max) number of collisions and deadlocks are shown. Moreover, the " 0% of RSD" block represents the results of simulations with deterministic processing times. The "BFS-L/U" row reports the best optimization results. The results of layouts 2, 3, and 4 are reported similarly in Appendix B.

The results show that:

• the more processing times are disturbed, the more the resulting makespan is also disturbed. Indeed, when the standard deviation of processing times increases, the standard deviation of the makespan also increases, with a slight increase in the average makespan.

• including uncertainties in the processing times leads to variability in the number of collisions. Whether a job processing is longer or shorter, this could lead to collision situations that didn't appear in the deterministic case. For example, both EX11 (see Table 4) and EX23 (see Appendix B2) instances have zero collision in the deterministic case. But uncertainties in processing times make their collisions number go up to 1 for EX11, and to 3 for EX23.

• the number of deadlocks can also vary due to uncertainties. In EX83, for example, the number of deadlocks increases to 6 whereas it was 2 in the deterministic case.

• layouts play an important role in the avoidance of deadlock situations, both in deterministic and probabilistic cases. Indeed, layouts 1 and 4 don't present any deadlocks and remain flexible even though the processing time is variable. Moreover, Algorithm 2 also helps because the path reservation avoids having two robots face-to-face on the same path section.

Overall, these results show the importance of Algorithm 1 and Algorithm 3, respectively, for collision avoidance and deadlock resolution. Indeed, even advanced schedules without any collisions or deadlocks can be disturbed due to uncertainties. Therefore, these schedules could be dead on arrival if there are no solutions to deal with the collisions and deadlocks that occur due to uncertainties. Furthermore, the proposed algorithms have proved their efficiency in a more realistic simulation environment. Even though we notice a makespan increase during type 2 simulations compared to type 1 simulations or optimization results, they ensure a reliable workflow. It should be underlined that these algorithms are robust and work well whatever the fleet size and the environmental behavior (deterministic or not).

Conclusion

The JSSP with transportation tasks has been widely addressed in the literature. However, almost all of this work ignores operational, temporal, and spatial, constraints such as collision avoidance between Autonomous Guided Vehicles (AGVs). Thus, in this paper, a multi-agent system-based simulation is proposed to evaluate the efficiency of a known-optimized result of the literature with the consideration of collision avoidance. The contributions of this paper are as follows: (1) verify the feasibility by simulation of the theoretical schedules proposed in the literature with realistic constraints' consideration such as collisions between AGVs and uncertainties in processing times, [START_REF] Ahmadian | A meta-heuristic to solve the just-in-time job-shop scheduling problem[END_REF] highlight and avoid collisions between AGVs, (3) propose a heuristic to solve deadlocks, and (4) test the sensitivity of the proposed approach according to processing times variation.

To achieve these objectives, the simulations have been carried out on the well-known benchmark instances proposed by Bilge and Ulusoy [START_REF] Bilge | A time window approach to simultaneous scheduling of machines and material handling system in an fms[END_REF] using the results extracted from the VNS algorithm proposed by Abderrahim et al. [START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF]. Each schedule has been simulated twice: "Type 1 Simulation" to validate the theoretical scheduling generated by the VNS algorithm and "Type 2 Simulation" to introduce the collision avoidance behavior. Regarding the latter, some avoided collisions led to deadlocks. Thus, a heuristic has been proposed to solve these problems. In addition, a "Type 3 simulation" based on a sim-optimization approach has been presented to find more suitable schedules with collision avoidance consideration.

Experiments have shown that, in general, the makespan increases when collision avoidance is considered. They have shown as well that solving one deadlock can lead to new ones, and AGVs delaying cannot impact the makespan if the job processing time is longer than the AGV travel time. We observed also that the layout plays an important role in the behavior of AGV, where layouts 1 and 4 provide more flexibility and avoid situations leading to deadlocks. The sim-optimization step has revealed that the optimal solution obtained through optimization alone is not always the best one to implement. Moreover, a scheduling problem can admit several equivalent optimized solutions that can have different outcomes after real implementation. Furthermore, results obtained under uncertainties in processing times indicate that collisions can result from delays/advances in processing times, and increasing processing times variability increases makespan variability.

These observations bring us closer to the reality in industries and prove that the consideration of real operational constraints will degrade theoretical results. Finally, the efficiency of the proposed algorithms is proved as all identified collisions have been avoided, and all deadlocks have been fixed.

From a short-term perspective, future work will be carried out assuming that transporters move freely in the workshop rather than on dedicated paths. It will consider more intelligent robots called AIVs (Autonomous Intelligent Vehicles), which are able to make more complex decisions such as optimal path selection, dynamic obstacle avoidance, and collaborative tasks. It will also take into account issues such as energy consumption, charging of transporter batteries, unforeseen obstacle avoidance, etc. These issues will be addressed in a multi-objective optimization approach. From a long and medium-term perspective, we will investigate the presence of human operators in the workshop to include the human aspect in the context of Industry 5.0. A stochastic model of the human operators in the workshop depending on the period of the day (morning, peak period, evening) will be established. This model will be integrated into a job-shop scheduling optimization algorithm with transportation tasks in order to propose optimized scheduling taking into account human activities. A sim-optimization method can be used to define a dynamic scheduling strategy in an uncertain environment. (min, avg, max) (0, 0.4, 3) (0, 0.0, 1) (0, 0.7, 1) (1, 1, 1) (2, 2.2, 4) (2, 3.1, 6) (0, 0, 0) (1, 2.4, 5) (0, 0.5, 2) (1, 2.5, 7) #Deadlocks (min, avg, max) (0, 0, 0) (0, 0, 0) (0, 0, 0) (1, 1, 1) (0, 0, 0) (1, 1, 1) (0, 0, 0) (5, 5, 5) (0, 0. (min, avg, max) (0, 0.0, 0) (0, 0.0, 0) (0, 0.9, 1) (0, 0.0, 0) (0, 0.0, 0) (0, 0.1, 1) (0, 0.0, 1) (0, 0.7, 2) (0, 1.0, 2) (0, 0.0, 0) #Deadlocks (min, avg, max) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) 20% of RSD (λ = 0. (min, avg, max) (0, 0.0, 0) (0, 0.0, 0) (1, 1.4, 3) (0, 0.1, 1) (0, 0.1, 1) (0, 0.4, 2) (0, 0.0, 1) (0, 0.9, 2) (0, 1.0, 2) (0, 0.3, 1) #Deadlocks (min, avg, max) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) 30% of RSD (λ = 0. (min, avg, max) (0, 0.0, 1) (0, 0.0, 1) (1, 1.5, 3) (0, 0.1, 1) (0, 0.2, 1) (0, 0.5, 3) (0, 0.2, 1) (0, 1.0, 3) (0, 1.2, 4) (0, 0.6, 2) #Deadlocks (min, avg, max) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0) (0, 0.0, 0)

Figure 1 :

 1 Figure 1: Diagram of the experimental protocol

Figure 2 :

 2 Figure 2: Collision avoidance

Figure 3 :

 3 Figure 3: Check point illustration Figure 4: Path portion reservation

Algorithm 3

 3 Pseudocode of Deadlocks Resolution Algorithm (DRA) Input: any AGV within the fleet Output: exchange the remaining transportation tasks with another AGV 1: procedure DEADLOCKS RESOLUTION(current agv) 2:

Figure 5 :

 5 Figure 5: VNS neighborhoods (a) and its implementation (b) proposed by[START_REF] Abderrahim | Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[END_REF]

Figure 6 :

 6 Figure 6: Sim-optimization approach

Figure 7 :

 7 Figure 7: The 4 layouts proposed by Bilge and Ulusoy

Figure 8 :

 8 Figure 8: Layout 2 simulation interface on Netlogo

Figure 9 :

 9 Figure 9: Simulation framework diagram

[ 1 ]

 1 without return to the L/U station; BFS-L/U: Makespan of the Best Found Solution among all the experiments with products' return times consideration; Type 1 simulation: Results of simulation without collision avoidance to validate the simulator; Type 2 simulation: Results of simulation with collision avoidance and the algorithm for fixing deadlocks for the BFS-L/U scheduling; Type 3 simulation: Results of the sim-optimization process (values in brackets are the VNS results); #Collisions: The number of collisions during the Type 1 simulation → their new number after the sim-optimization; #Deadlocks:

Figure 10 :Figure 11 :

 1011 Figure 10: Comparison of the obtained values after simulations

82. 6 Figure 11

 611 Figure 11

Figure 12 :

 12 Figure 12: Gantt diagram of EX32 after simulations

Figure 13 :

 13 Figure 13: Zoom on AGVs schedules in EX32

Figure 14 :

 14 Figure 14: Gantt diagram of EX82 after both types of simulations with collisions and DRA execution

Figure 15 :Figure 16 :

 1516 Figure 15: Former EX62 scheduling combined Gantt diagrams

  . The obtained results and the proposed methodology can play an important role in resolving other problems faced by companies, such as the definition of the AGVs fleet size, AGVs' battery charging management, and FJSSP with transportation tasks.

  4) (86.7, 1.9) (113.7, 4.5) (101.5, 1.3) (159.8, 9.2) (111.4, 4.4) (159.3, 9.5) #Collisions (min, avg, max) (0, 0.4, 3) (0, 0.2, 1) (0, 0.4, 1) (1, 1.1, 3) (0, 2.5, 4) (0, 4.1, 8) (0, 0.0, 1) (1, 3.36, 3.7) (84.9, 3.5) (101, 5.3) (111.5, 3.7) (88.2, 4.2) (113.9, 8) (102.7, 2.5) (167.2, 10.5) (114.4, 7.2) (155.4, 10) Type 2 simulation (avg, sd) (107.5, 5.7) (84.4, 3.7) (102.3, 6.8) (118.2, 3.9) (88.3, 3.5) (117.2, 6.1) (103.7, 3.1) (161.5, 10.9) (114.2, 6.2) (163.4, 11.1) #Collisions (min, avg, max) (0, 0.8, 3) (0, 0.4, 2) (0, 0.3, 3) (1, 1.3, 3) (0, 2.4, 4) (0, 4.8, 8) (0, 0.4, 2) (1, 4.17, 1.7) (93.8, 1.7) (103.1, 2.4) (112.4, 1.4) (94, 1.5) (112.6, 2.6) (112.4, 0.7) (155.9, 4.8) (113.2, 4.3) (150.8, 3.5) Type 2 simulation (avg, sd) (100.3, 1.7) (93.9, 2.3) (107.6, 2.6) (112.4, 1.7) (96.1, 1.2) (119.3, 3) (114.9, 1.5) (166.4, 9.6) (117.8, 2.4) (174, 11.2, 3.3) (96.9, 4.1) (107.2, 4.2) (113.4, 3.1) (94.9, 2.7) (114.9, 4.5) (113, 1.8) (159.4, 8.5) (116.4, 4.7) (153.81, 5.5) (100.6, 6.9) (110.5, 6.1) (116.6, 6.4) (96.1, 4.6) (121.2, 6.5) (115.6, 3.9) (163.9, 10.8) (119, 6.1) (158.2, 9.2) Type 2 simulation (avg, sd) (105, 4.7) (98.9, 5.3) (113.6, 6.3) (115.6, 3.9) (97.7, 4) (123.5, 7.1) (117.1, 3.7) (172.3, 11.5) (122.8, 6.6) (174.8, 11.1) #Collisions (min, avg, max) (0, 1.1, 3) (0, 1.4, 3) (1, 2.2, 5) (0, 0.7, 3) (1, 2, 3) (1, 3.4, 6) (1, 1.6, 3) (3, 4.11.7) (156, 1.9) (160.3, 1.0) (180.7, 1.2) (140, 0) (169, 2.2) (191.6, 0.8) (191.5, 3.1) (157.2, 1.8) (201.9, 0.8) Type 2 simulation (avg, sd) (144.9, 1.4) (156.6, 2.3) (162.8, 0.5) (180.6, 0.8) (140.2, 0) (168.1, 1.7) (191.3, 0.6) (191.7, 2.4) (160.3, 2.5) (204.8, 2.1) #Collisions

Table 1 :

 1 shows the 4 layouts used for the experiments with the travel distances. Travel times

		L/U M1 M2 M3 M4		L/U M1 M2 M3 M4
	L/U	0	6	8	10	12	L/U	0	4	6	8	6
	M1	12	0	6	8	10	M1	6	0	2	4	2
	M2	10	6	0	6	8	M2	8	12	0	2	4
	M3	8	8	6	0	6	M3	6	10	12	0	2
	M4	6	10	8	6	0	M4	4	8	10	12	0
			(a) Layout 1					(b) Layout 2
		L/U M1 M2 M3 M4		L/U M1 M2 M3 M4
	L/U	0	2	4	10	12	L/U	0	4	8	10	14
	M1	12	0	2	8	10	M1	18	0	4	6	10
	M2	10	12	0	6	8	M2	20	14	0	8	6
	M3	4	6	8	0	2	M3	12	8	6	0	6
	M4	2	4	6	12	0	M4	14	14	12	6	0
			(c) Layout 3					(d) Layout 4

Table 2 :

 2 Matrix of EX11 advanced scheduling

Table 3 :

 3 Comparison of the obtained results: (Cmax: Results obtained by Bilge and Ulusoy [7]; LB: Lower Bound of the makespan computed by Abderrahim et al. [1]; BFS: Makespan of the Best Found Solution obtained by Abderrahim et al.

			LB[1] BFS[1] BFS-L/U	Type 1	Type 2	Type 3	# Collisions # Deadlocks
						simulation	simulation	simulation
	EX11	96.0	76.0	96.0	120.0	120.0	120.0	-	0	0
	EX21*	105.0	86.0	100.0	122.0	122.0	125.65	125.65 (122.0)	1 → 3	0
	EX31*	105.0	88.0	102.0	132.0	132.15	132.2	132.2 (132.0)	2 → 0	0
	EX41	118.0	78.0	116.0	147.0	147.0	147.05	-	3	0
	EX51	89.0	65.0	87.0	116.0	116.0	116.15	-	1	0
	EX61*	120.0	108.0	120.0	138.0	138.0	143.2	142.9 (139.0)	2	0
	EX71*	119.0	77.0	121.0	159.0	159.0	162.6	160.15 (160)	1 → 1	0
	EX81*	161.0	161.0	161.0	167.0	167.1	171.45	171.45 (167.0)	5 → 3	0
	EX91*	120.0	105.0	117.0	130.0	130.1	130.1	130.1 (130.0)	1 → 2	0
	EX101*	153.0	133.0	152.0	169.0	169.0	173.45	173.30 (169.0)	4 → 3	0
	EX12*	82.0	76.0	82.0	92.0	92.0	102.8	99.0 (99.0)	1 → 0	0
	EX22*	80.0	76.0	76.0	82.0	82.0	82.2	82.2 (82.0)	1 → 0	0
	EX32	88.0	80.0	85.0	95.0	95.0	95.0	-	1	0
	EX42*	93.0	70.0	92.0	109.0	109.1	116.8	109.0 (109.0)	1 → 0	1 → 0
	EX52*	69.0	64.0	69.0	84.0	84.0	85.05	84.0 (84.0)	1 → 0	0
	EX62*	100.0	98.0	98.0	102.0	102.15	108.5	102.35 (102.0)	2 → 1	1 → 0
	EX72*	90.0	74.0	84.0	101.0	101.0	101.0	101.0 (101.0)	0	0
	EX82	151.0	151.0	151.0	155.0	155.15	155.3	-	3	5
	EX92	104.0	98.0	102.0	106.0	106	106.1	-	1	0
	EX102*	139.0	128.0	139.0	142.0	142.0	156.15	145.0 (145.0)	3 → 1	2 → 0
	EX13	84.0	74.0	84.0	99.0	99.0	99.4	-	1	0
	EX23	86.0	82.0	86.0	92.0	92.0	92.0	-	0	0
	EX33*	86.0	82.0	86.0	101.0	101.0	107.0	104.1 (104.0)	1 → 0	1 → 0
	EX43	95.0	71.0	92.0	112.0	112.0	112.0	-	0	0
	EX53*	76.0	63.0	74.0	93.0	93.0	96.05	93.1 (93.0)	2 → 1	0
	EX63*	104.0	100.0	104.0	110.0	110.05	117.75	117.75 (110.0)	2	2
	EX73*	91.0	76.0	87.0	112.0	112.0	114.75	112.0 (112.0)	2 → 1	1 → 0
	EX83*	153.0	153.0	153.0	155.0	155.0	161.9	155.15 (155.0)	2	2 → 3
	EX93*	110.0	100.0	105.0	108.0	108.0	116.65	109.15 (109.0)	2 → 0	0
	EX103*	143.0	133.0	143.0	148.0	148.0	181.15	148.05 (148.0)	4 → 2	1 → 0
	EX14	108.0	76.0	103.0	144.0	144.0	144.0	-	0	0
	EX24	116.0	84.0	113.0	156.0	156.0	156.15	-	0	0
	EX34*	116.0	87.0	113.0	160.0	160.0	162.4	162.4 (160.0)	1	0
	EX44	126.0	81.0	131.0	180.0	180.0	180.0	-	0	0
	EX54	99.0	62.0	97.0	140.0	140.0	140.15	-	0	0
	EX64	120.0	103.0	129.0	168.0	168.0	168.15	-	0	0
	EX74	136.0	78.0	134.0	191.0	191.0	191.0	-	0	0
	EX84	163.0	163.0	163.0	190.0	190.0	190.25	-	1	0
	EX94*	125.0	102.0	123.0	156.0	156.0	160.2	158.0 (158.0)	1 → 0	0
	EX104*	171.0	136.0	169.0	202.0	202.0	202.0	203.3 (202)	1	0

  2) Type 1 simulation (avg, sd) (146.4, 2.7) (156.4, 4.2) (161.7, 2.3) (181.8, 1.9) (140.3, 0.7) (170.8, 4) (191.7, 1.3) (193, 3.6) (159.5, 2.9) (203.3, 2.2) , 3.1) (156.1, 4.2) (164.5, 2.9) (181.6, 1.6) (140.2, 0) (169.2, 3.2) (191.7, 1.3) (193.6, 3.6) (162.9, 4.8) (205.1, 3.4)

	Type 2 simulation (146.3#Collisions (avg, sd)

  3) Type 1 simulation (avg, sd) (148.2, 4.6) (158.9, 5.8) (162.3, 4.5) (183.1, 3) (141.2, 1.9) (173.4, 5.2) (192.8, 2) (196.3, 7.4) (163.8, 6) (207.5, 6.8) , 4.6) (158.1, 5.8) (167.3, 6.5) (182.7, 2.6) (140.6, 1.2) (169.7, 3.6) (193.3, 2.3) (195.6, 5.4) (165, 5.1) (211.5, 7.3)

	Type 2 simulation (147.5#Collisions (avg, sd)

Table Appendix B3

 Appendix : Sensitivity analysis of layout 4

Appendix A. Job sets proposed by Bilge and Ulusoy Job set 1 Job 1: M1(8); M2(16); M4(12) Job 2: M1(20); M3(10); M2(18) Job 3: M3(12); M4(8); M1(15) Job 4: M4(14); M2(18) Job 5: M3(10); M1(15) Job set 2 Job 1: M1(10); M4(18) Job 2: M2(10); M4(18) Job 3: M1(10); M3(20) Job 4: M2(10); M3(15); M4(12) Job 5: MI(10); M2(15); M4(12) Job 6: M1(10); M2(15); M3(12) Job set 3 Job 1: M1(16); M3(15) Job 2: M2(18); M4(15) Job 3: M1(20); M2(10) Job 4: M3(15); M4(10) Job 5: M1(8); M2(10); M3(15); M4(17) Job 6: M2(10); M3(15); M4(8); M1(15) Job set Job 1: M4(11); M1(10); M2(7) Job 2: M3(12); M2(10); M4(8) Job 3: M2(7); M3(10); M1(9); M3(8) Job 4: M2(7); M4(8); M1(12); M2(6) Job 5: M1(9); M2(7); M4(8); M2(10); M3(8) Job set 5 Job 1: M1(6); M2(12); M4(9) Job 2: M1(18); M3(6); M2(15) Job 3: M3(9); M4(3); M1(12) Job 4: M4(6); M2(15) Job 5: M3(3); M1(9) Job set 6 Job 1: M1(9); M2(11); M4(7) Job 2: M1(19); M2(20); M4(13) Job 3: M2(14); M3(20); M4(9) Job 4: M2(14); M3(20); M4(9) Job 5: M1(11); M3(16); M4(8) Job 6: M1(10); M3(12); M4(10) Job set 7 Job 1: M1(6); M4(6) Job 2: M2(11); M4(9) Job 3: M2(9); M4(7) Job 4: M3(16); M4(7) Job 5: M1(9); M3(18) Job 6: M2(13); M3(19); M4(6) Job 7: M1(10); M2(9); M3(13) Job 8: M1(11); M2(9); M4(8) Job set 8 Job 1: M2(12); M3(21); M4(11) Job 2: M2(12); M3(21); M4(11) Job 3: M2(12); M3(21); M4(11) Job 4: M2(12); M3(21); M4(11) Job 5: M1(10); M2(14); M3(18); M4(9) Job 6: MI(10); M2(14); M3(18); M4(9) Job set 9 Job 1: M3(9); M1(12); M2(9); M4(6) Job 2: M3(16); M2(11); M4(9) Job 3: M1(21); M2(18); M4(7) Job 4: M2(20); M3(22); M4(11) Job 5: M3(14); M1(16); M2(13); M4(9) Job set 10 Job 1: M1(11); M3(19); M2(16); M4(13) Job 2: M2(21); M3(16); M4(14) Job 3: M3(8); M2(10); M1(14); M4(9) Job 4: M2(13); M3(20); M4(10) Job 5: M1(9); M3(16); M4(18) Job 6: M2(19); M1(21); M3(11); M4(15) Appendix B. Sensitivity analysis


Christian Wolff
email: christian.wolff@hs-mainz.de

Markus Schaffert
email: markus.schaffert@hs-mainz.de

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Hocine Cherifi
email: hocine.cherifi@u-bourgogne.fr

Analysis of the German Commuter Network Period 2013 -2021

Keywords: Commuter, Complex Network Analysis, Spatial Data

Understanding the behavior of commuters is crucial as the number of commuters steadily rises, causing significant traffic congestion in many cities. Indeed, commuter behavior is vital in city and transport planning and policy-making. Previous studies have investigated various factors that may impact commuting decisions. Still, these studies are often limited by the scale of data examined, including time duration, space, and the number of commuters. To address this gap, we gathered large-scale inter-city commuting data in Germany and analyzed the weighted commuting network from 2013 to 2021. This work relies on publicly available data so that the results can be reproduced.

Introduction

The ongoing work presented here aims to analyze the Commuter flows in Germany from 2013 to 2021 from a network science perspective [1][2][3][4][5][START_REF] Kumar | Companion Proceedings of the The Web Conference 2018[END_REF][START_REF] Chakraborty | Computational Social Networks: 5th International Conference, CSoNet 2016[END_REF][START_REF] Rajeh | [END_REF]. Using all years of the period makes it possible to consider the short-term effects due to the COVID-19 pandemic. The network consists of the German districts (nodes) and the commuter flows (Einpendler) (edges) and incorporates weights based on the overall number of commuters. We exclude Commuter flows from outside German districts. The Federal Employment Agency, BA (Bundesagentur für Arbeit) (Dataset "Arbeitsmarkt in Zahlen, Sozialversicherungspflichtig Beschäftigte -Pendlernach Kreisen") provided us with the data representing the Commuter flows. One may notice different annotations in the dataset regarding the data quality of the years 2013/14, 2016/2017, and 2019 due to technical issues or local government reorganization. Coordinates were added to the dataset using the dataset Geographische Namen 1:250 000 (GN250), State geometries are added using the dataset Verwaltungsgebiete 1 : 250 000 (VG250-EW) (© GeoBasis-DE / BKG 2021) provided by the Federal Agency for Cartography and Geodesy (BKG).

Results

Preliminary results of the analysis confirm the findings of the BBSR regarding the increase in commuting activity. Indeed, the number of commuters in Germany has continuously increased in recent years. According to the Federal Office for Building and Regional Planning -BBSR, commuters rose by 6.6 percent in five years, from 18.4 million employees in 2016 to 19.6 million in 2021. This corresponds to 59.5% of all those subject to social security contributions. The group of commuters with a one-way commute of more than 50 kilometers experienced a sharp increase of 7.4%. It rose from 3.3 million in 2016 to 3.6 million in 2021. Among the major cities, Munich continues to lead the list with the most commuters [9].

The analysis of the minimum Degree through time show that commuting increases. For example, the min degree increases from 30 in 2013 to over 40 in 2021. The median Degree rose from 115 in 2013 to more than 130 in 2021. The degree distribution shows that most districts have a low degree while a few districts have a high Degree.

Figure 1 shows the evolution throughout the global topological properties of the network. The diameter decreased from 3 in 2013 to 2 in 2014. Since then, it did not change. So, in terms of commuter routes, the German districts are pretty close. Taking into account the overall commuter counts as the weight adds a bit more dynamics to the diameter development as it decreases from 39 (2013) to 36 (2017/18) and increases again to 40 (2021). The density increases throughout the period (from 0.33 in 2013 to 0.37 in 2021) except for one drop from 2019 to 2020. It shows that commuting in Germany is increasing in numbers and connections between the districts. Although far from a complete graph, 0.37 seems pretty dense concerning the topic and the geographical extent of Germany. The development of transitivity follows the same trend, with the same drop between 2019 and 2020. It suggests that the increase also occurs between transitively connected nodes, for example, districts related to the same urban district. The Degree Correlation Coefficient shows a negative increase from -0.179 in 2013 to -0.188 in 2021. So, the network becomes more disassortative over time. It suggests that the rural-urban commuter relationships increased in the given period. The Federal Institute for Population Research (Bundesinstitut für Bevölkerungsforschung) reports that migration to urban municipalities has been steadily decreasing since 2012 and since 2014. They have even recorded migration losses. In contrast, rural districts have gained population for some years, indicating a renewed suburbanization phase in Germany [START_REF] Rosenbaum-Feldbrügge | Aktuelle Trends der Binnenwanderung in Deutschland[END_REF]. One can assume that these people don't migrate to the rural areas because of a new job offer in these districts but due to other reasons, e.g., lower housing prices. Considering the weights, we observe the same trend but on a less disassortative level. The analysis of the community structure of the network also reveals interesting insights. Figure 2 shows the evolution of the community structure over the period uncovered by the Louvain Community Detection Algorithm. The communities fit the geographical areas quite well except for some large cities such as Berlin and Hamburg, which are in the southeastern cluster. We can also see that the community in central Germany disappeared in 2014, 2019, and 2021. The modularity exhibits low values around 0.2, characteristic of a weak community structure with many links between the communities. We observe a slightly decreasing trend except for a short increase between 2018 and 2020.

Using the overall commuter flows as weight. We can see that the community structure of the weighted network divides into smaller communities. The high modularity (0.7) shows that the communities are more cohesive. Their evolution in time follows the same trend as the unweighted community structure. The weighted community structure does not fit the state's borders well, except for some communities surrounding more prominent cities such as the Karlsruhe or the Mainz region. Furthermore, the number of communities varies between 10 and 13 (Fig. 3). Some clusters disappear, e.g., in Lower Saxony / Eastern North Rhine-Westphalia, where the number of communities evolves between 1 and 3. It could be a result of the structure of the area consisting of rural areas and a few urban areas like Bremen, Hannover, Braunschweig, and Bielefeld.

We plan to extend the current analysis of static networks to include temporal networks, which can capture how the network structure and dynamics change over time [START_REF] Mboup | [END_REF]. It could involve investigating how different types of temporal dependencies affect the behavior of the network and the properties of its microscopic and mesoscopic structure. Additionally, incorporating information about the timing and duration of interactions between nodes could provide a more nuanced understanding of commuting patterns and dynamics.

Fig. 1

 1 Fig. 1 Global topological properties evolution from 2013 to 2021

Fig. 2

 2 Fig. 2 Community structure evolution of the unweigthed network uncovered by Louvain from 2013 to 202

Acknowledgements This work is part of the project Spatial Intelligence for the Integrated Care of Senior Citizens in Rural Neighbourhoods (Raumintelligenz für die integrierte Versorgung von Seniorinnen und Senioren in ländlichen Quartieren (RAFVINIERT) ). It is funded by the Carl Zeiss Foundation in the program SocietyTransfer -Intelligent Solutions for an Ageing Society ("Transfer -Intelligente Lösungen für eine älter werdende").


Benjamin Perrette

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Hocine Cherifi

A local Agent-Based Model of COVID-19 spreading and interventions

This research presents a simulation model that combines metapopulation geospatial data with the SEIR epidemiological model to simulate a city of up to 250,000 residents while considering various factors such as virus transmission rate, disease severity, and prevention and control measures. This model can assist decision-makers in exploring different pandemic response strategies, including lockdowns, social distancing, mass testing, contact tracing, and vaccination. This simulation aims to provide decision-makers with a better understanding of the implications of their choices and enable them to make informed real-time decisions to manage a health crisis.

Introduction

The COVID-19 pandemic is a global challenge that significantly impacts health and the economy. Compartmental and metapopulation models [1,2] are crucial in evaluating the effects of containment policies like facility closures [START_REF] Wang | Statistical physics of vaccination[END_REF][START_REF] Gupta | 2015 7th international conference on communication systems and networks (COMSNETS)[END_REF][START_REF] Chakraborty | Computational Social Networks: 5th International Conference, CSoNet 2016[END_REF][START_REF] Kumar | Companion Proceedings of the The Web Conference 2018[END_REF][START_REF] Messadi | [END_REF][START_REF] Ghalmane | [END_REF]. More sophisticated models consider the spatial and social structure and the people's evolving awareness. However, they are unsuitable for analyzing the transmission dynamics in small populations with complex behavior. Agentbased modeling offers the advantage of observing global behavioral patterns by modeling the interactions between individuals with distinct characteristics [9]. This study presents an agent-based model to evaluate the transmission process of COVID-19. The model relies on collected meta-population geospatial data and the SEIR epidemiological model. The framework enables simulations of various scenarios, such as different levels of virulence, confinement consideration, and the number of available intensive care units. Initially limited to the city center of Dijon, the study considers a greater Dijon area allowing simulations of up to 250,000 residents [START_REF] Prudhomme | MARAMI 2020-Modèles & Analyse des Réseaux: Approches Mathématiques & Informatiques-The 11th Conference on Network Modeling and Analysis[END_REF].

In the SEIR (Susceptible-Exposed-Infectious-Recovered) compartmental model, any individual can be in one of the following states: S: Susceptible: The individual is healthy; E: Exposed: The individual is incubating the virus and is characterized by the incubation period; I: Infectious: The individual is contagious and in the period of infection; R: Recovered: The individual has recovered or has been removed (dead). The infectious state period includes three cases: the classic Us, the asymptomatic A, and the rarer Ua. Patients in the Us class present symptoms of the virus and are contagious. Patients in the A category are contagious but have no symptoms. Ua is an intermediate case in which the patient begins to be infectious before the end of the incubation period but does not present any symptoms yet. One can integrate individual conditions, such as age, gender, and co-morbidity, into the model by defining the transition rates at the personal level. The simulations reported in the experiments use generic parametrization from [START_REF] Dong | [END_REF]9]. However, one can use parameters obtained by an epidemiologist from on-site experimentation. In this study, we use the vaccination strategies applied in France for the vaccine model. According to data on vaccine efficacy, the vaccine reduces severity by 90%, infectivity by 30%, and susceptibility by 90%. The vaccination is initially disabled, and these data are modifiable during the simulation.

Experimentation

This section presents our experimentation using the GAMA platform [12]. It combines explicit multi-agent simulations with GIS data management, multilevel modeling, and the capacity to implement Belief-Desire-Intention (BDI) and reactive agents. Thus, GAMA is powerful for prototyping and automatic simulation through its agent-oriented language GAML.

We collected data from the Dijon metropolitan area from OpenStreetMap. We extracted a Shapefile containing all of the buildings throughout Burgundy and a file containing all the roads. The simulation starts when the agents go to work between 6 and 8 am. In the evening, they stop between 4 and 8 pm and can then go to a place of leisure. The principle is the same for those under 18, but they go to school rather than work. One can change all these parameters. As shown below, one can tune many parameters on the agents to adapt the model to its needs. One of the agents is infected at the beginning of the simulation. Depending on their state of health, the agents have a different color. The healthy agents are yellow, those in the incubation period are orange. The symptomatic infected are red, the asymptomatic infected are red with purple borders. The hospitalized infected are red dots with green contours, the agents in specific states are orange with red contours, the recovered are green. The dead are black with red contours. It is possible to change the virus settings, as reported in (fig. 1). One can close schools so that young people stay at home. The suspension of leisure activities prevents agents from going to public places such as large shopping centers, restaurants, or places of worship.

In the case of a complete lockdown, the agents stay at home and no longer move. All of these parameters are aimed at reducing the spread of the virus. It is also possible to implement preventive measures to decrease virus transmission. Hospitalization of infected individuals can be activated to decrease the likelihood of dying from the virus. One can change the Parameters linked to the hospitals, such as the number of beds. It is also possible to change the entire vaccination model by deciding when the vaccinations should be carried out and how many vaccine doses are available in the city. One can deal with many variants in the simulation. It can also save information about agents and their environments to a CSV file to create a dataset. Afterward, it is possible to search for information on a particular agent (for example, patient 0) and save it to another CSV file. The simulation can be manually paused at any time or automatically. All these parameters are tunable during the simulation.

The different figures illustrate the infection development in the population. It shows the main places where infections occur and the evolution of available hospital beds. They also report the growth of the variant compared to the strain, the variation of the vaccinated population of the first and the second dose, and the distribution of deaths related to the virus according to agents' age. In the first curve (fig. 2a), we can observe the evolution of the number of infections over time in different locations. The gray line represents infections at home. It continues to rise throughout the simulation, even during a lockdown. The dark blue line represents workplace infections, which remain stable during the lockdown but experience a sharp spike after its lifting. The light blue line represents infections at leisure venues, which stay stable when these places are closed. Finally, the purple line represents infections in schools, which remain stable as long as they are closed but increase upon reopening. In the second graph (fig. 2b), we can observe the evolution of the agent states during the simulation. The number of individuals in the incubation period (state E) is orange. It varies according to the restrictions, decreasing during confinement and increasing afterward. The number of infected agents (state I) is shown in red. It falls with improved regulations. The number of agents who have recovered from the disease is shown in green, while the number of agents who died is black (state R). Finally, the number of agents in the specific state (state Ua) is violet. This model could be a valuable tool for decision-makers in the field of public health to determine when it is the right time to impose restrictions, predict the rise of an epidemic, and act accordingly to stop it. It can be significantly improved, particularly regarding computational speed, to facilitate larger-scale simulations and use knowledge graphs to refine agent behavior.

Fig. 1 :

 1 Fig. 1: Dijon metropolitan area with 250,000 inhabitants

Fig. 2 :

 2 Fig. 2: Evolution of variables during the simulation