<figure><img src="image_1.png" /></figure>

ALAA DAOUD, FLAVIEN BALBO, PAOLO GIANESSI, GAUTHIER PICARD

AV-OLRA : Une modélisation générique pour le problème de l’allocation des ressources dans le domaine du transport à la demande

Volume 4, n° 2 (2023), p. 169-192.

https://doi.org/10.5802/roia.61

© Les auteurs, 2023.

<figure><img src="image_2.png" /></figure>

Cet article est diffusé sous la licence

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_3.png" /></figure>
# AV-OLRA : Une modélisation générique pour le problème de l'allocation des ressources dans le domaine du transport à la demande

Alaa Daoud<sup>a</sup>, Flavien Balbo<sup>a</sup>, Paolo Gianessi<sup>a</sup>, Gauthier Picard<sup>b</sup>

**RÉSUMÉ.** — Le développement de véhicules autonomes, capables de communiquer de pair à pair, ainsi que l’intérêt pour les solutions à la demande (par exemple, Uber, Lyft, Heetch), sont les principales motivations de cette étude. Le problème d’allocation des véhicules aux clients est d’une importance majeure dans la gestion des systèmes de transport à la demande (ODT). Il est étudié depuis des décennies, et diverses solutions ont été proposées. Les différentes familles de solutions peuvent être classées en deux catégories, centralisées et décentralisées avec dans la pratique, pour chacune ses avantages et ses inconvénients. Dans ce travail, nous visons à fournir un modèle générique pour le problème du transport à la demande en ligne avec des véhicules autonomes. Indépendant des solutions, ce modèle permet une description synthétique du problème et propose des indicateurs de qualité. Nous proposons également un modèle multi-agents dédié à l’allocation des ressources et à la planification de la flotte. Ce dernier considère des véhicules autonomes comme des agents qui communiquent dans un réseau inter-véhiculaire pour satisfaire les demandes de transport dans un système de transport à la demande selon la stratégie de résolution que l’utilisateur souhaite évaluer. Nous montrons la généricité de ce modèle en appliquant plusieurs approches d’allocation (optimisation linéaire en nombres entiers, approche gloutonne, enchères et optimisation sous contraintes distribuée) et comparons en détail leurs performances en termes de qualité de solution et d’indicateurs techniques sur des scénarios générés à partir de données réelles.

**MOTS-CLÉS.** — Systèmes multi-agents, Coordination, Transport à la demande, Allocation des ressources, Véhicules Autonomes Connectés, Simulation.

## 1. INTRODUCTION

Parmi les questions importantes dans la gestion des systèmes de transport à la demande (ODT) nous retrouvons les problèmes d’allocation de demandes de courses aux

<footnote><sup>a</sup> Mines Saint-Étienne, Univ Clermont Auvergne, INP Clermont Auvergne, CNRS, UMR 6158 LIMOS Saint-Étienne, France</footnote>

<footnote>E-mail: alaa.daoud@insa-rouen.fr</footnote>

<footnote>URL: https://territoire.emse.fr/, flavien.balbo@emse.fr, paolo.gianessi@emse.fr</footnote>

<footnote><sup>b</sup> ONERA/DTIS, Université de Toulouse, Toulouse, France</footnote>

<footnote>E-mail: gauthier.picard@onera.fr.</footnote>
véhicules qui soient réalisables et efficaces. Les taxis autonomes sont une catégorie de véhicule sans conducteur qui en plus de leur autonomie de déplacement dans le trafic ont l'autonomie du choix des clients à servir. Cela signifie qu'ils sont responsables de leur choix d'affectation aux demandes (en prenant des décisions décentralisées) ou d'exécuter les plannings qui sont décidés de manière centralisée par un répartiteur. En pratique, la faisabilité et l'efficacité du choix de centraliser/décentraliser la solution dépendent de la complexité du problème, de ses contraintes (e.g. la topologie du réseau et la structure de la demande) et de la dynamique de l'environnement (e.g. le trafic routier, les aléas de conduite). Notre intérêt se porte sur la version en ligne du problème d'allocation des ressources au sein des flottes de véhicules. Dans cette version, les demandes apparaissent aléatoirement dans le temps et l'espace, et les véhicules n'ont aucune information sur la demande à l'avance. Cependant, ils doivent réagir efficacement et de façon dynamique en temps réel. Dans cet article, (i) nous proposons AV-OLRA, un modèle générique pour le problème d'allocation des ressources en ligne avec des véhicules autonomes. Ce modèle est générique, car il est indépendant des solutions mises en œuvre. Ainsi, nous modélisons les données du problème (composantes, contraintes) et les indicateurs permettant d'évaluer les différentes stratégies d'allocation; (ii) nous proposons un modèle multi-agents générique support de solutions au problème des systèmes ODT, où les véhicules autonomes (agents) communiquent avec leurs voisins via une communication pair-à-pair au sein d'ensembles connectés; Ce modèle est générique, car il supporte la réalisation des solutions en limitant les nouveaux développements aux particularités de la méthode d'allocation. (iii) nous classons les différentes méthodes d'allocation en fonction du comportement de coordination des agents; (iv) nous évaluons et comparons expérimentalement différentes méthodes de résolution (optimisation linéaire en nombres entiers, enchères et optimisation sous contraintes distribuée).

Le papier est structuré comme suit. La section 2 présente quelques travaux relatifs à l'allocation de ressources multi-agents avec un focus sur les travaux concernant les systèmes ODT. Sur la base de cette analyse de l'état de l'art, nous exposons le problème AV-OLRA dans la section 3, et un modèle multi-agents générique pour le résoudre dans la section 4. La section 5 examine plus en détail les différents mécanismes de coordination investigués dans cette étude, qui sont ensuite évalués expérimentalement dans la section 6. Enfin, le document se termine par quelques perspectives dans la section 7.

## 2. ALLOCATION DE RESSOURCES MULTI-AGENTS ET SYSTÈME ODT

Ces dernières années, le nombre d'articles consacrés à l'application des technologies fondées sur les agents dans le domaine des transports a considérablement augmenté, attestant les bénéfices de cette approche pour ce domaine d'application. [14] propose une synthèse des publications concernant des simulations et modèles pour systèmes ODT. Dans ce domaine, mieux répondre à la demande est considéré comme un défi et doit prendre en compte les personnes avec leur comportement et leur interaction avec un environnement de transport complexe. La vision MARA (*Multi-Agent*
*Resource Allocation)* est pertinente pour la résolution des problèmes ODT et a été mise en œuvre selon différentes approches. Ainsi, la centralisation du processus d'allocation avec un répartiteur automatique est encore assez courante dans les approches multi-agents [3, 12, 17]. D'autre part, et pour réaliser une planification en temps réel des services ODT, plusieurs modèles décentralisés ont été proposés [6, 16]. Un modèle théorique de système de transport est développé dans [8] pour étudier le comportement de coopération des véhicules, avec une perspective globale ; la stratégie permettant d'obtenir la meilleure efficacité est de partager les informations entre véhicules coopérants dans un réseau de transport flexible (i.e les horaires et itinéraires sont variables). Dans le cas contraire (absence de communication entre les agents), [11] a proposé d'utiliser la programmation génétique pour développer des systèmes multi-agents décentralisés qui résolvent les problèmes dynamiques des systèmes ODT. Les auteurs ont conclu que la planification à long terme n'est pas bénéfique dans de tels contextes en raison de la très forte dynamique ; ainsi, les agents ne devraient examiner qu'une seule demande à l'avance.

L'un des principaux défis que pose l'utilisation des approches MARA et plus généralement multi-agents, pour résoudre les problèmes liés à l'ODT est le goulot d'étran glement en matière de communication. Une solution est une organisation spatiale des agents, *e.g.* une zone de planification limitée par agent et pas de communication [7]. Un second défi concerne la dynamique du système. Les solutions aux problèmes d'allocation de ressources pour un système ODT dans des environnements dynamiques doivent remettre en question les plannings des véhicules en temps réel. Cette remise en cause rend dans la pratique l'objectif de proposer une solution optimale inaccessible. Cependant, la conception d'approches itératives pour obtenir des solutions réalisables en temps raisonnable est une alternative appropriée pour aborder l'aspect dynamique ; cela nécessite de considérer le besoin de communication (pour mettre à jour les infor mations) et donc de fournir des schémas de communication et de coordination solides et efficaces.

De même, un cadre de modélisation générique, c'est-à-dire indépendant de la solu tion/stratégie, du problème d'allocation de ressources localisées en ligne (OLRA), et un système multi-agents pour résoudre le problème de la gestion du stationnement urbain ont été proposés dans [21]. La solution repose sur une communauté de conducteurs qui partagent leurs connaissances locales sur la disponibilité des places de stationnement. Notre travail s'appuie sur ce dernier modèle pour proposer un modèle spécifique au problème de l'allocation des ressources à la demande dans les flottes de véhicules autonomes.

### 3. MODÈLE DE PROBLÈME AV-OLRA

Dans cet article, nous définissons le problème AV-OLRA comme une spécialisation du modèle OLRA pour l'allocation de ressources en ligne avec des véhicules auto nomes, et une extension pour la prise en compte de la communication et la modélisation de contraintes temporelles supplémentaires.
Nous formulons donc le problème AV-OLRA comme suit :

$$
\text{AV-OLRA} := (\mathcal{R}, \mathcal{V}, \mathcal{G}, \mathcal{T}) \qquad (3.1)
$$

$$
\mathcal{R} = \{r_i \mid i \in \mathbb{N}\} \qquad (3.2)
$$

$$
\mathcal{V} = \{v_i \mid i \in \mathbb{N}\} \qquad (3.3)
$$

$$
\mathcal{G} = (\mathcal{N}, \mathcal{E}, \omega) \qquad (3.4)
$$

$$
\mathcal{T} := \{t_0, t_1, \dots, t_{end}\} \qquad (3.5)
$$

où $\mathcal{R}$ définit un ensemble dynamique de demande des passagers (les ressources dans le
modèle OLRA) qui sont disponibles sur une fenêtre temporelle spécifique au moment
de l'exécution, l'ensemble des véhicules $\mathcal{V}$ (ensemble des consommateurs $\mathcal{C}$ dans le
modèle OLRA) représente une flotte de $m$ véhicules autonomes qui sont mobiles et
ne peuvent communiquer qu'à une portée limitée; $\mathcal{G}$ est un graphe dirigé, avec $\mathcal{N}$
l'ensemble des nœuds (carrefours), et $\mathcal{E}$ l'ensemble des arcs (routes), $e_{ij} \in \mathcal{E}$ est l'arc
entre les nœuds $i$ et $j$, $\omega$ est une fonction d'évaluation qui associe à chaque arc $e \in \mathcal{E}$
une valeur $\omega_e$ sur la base d'une mesure de distance temporelle (par exemple, le temps
de conduite moyen en minutes), qui sera utilisée pour calculer les coûts opérationnels
des déplacements des véhicules. Enfin $\mathcal{T}$ est l'horizon temporel du problème.

DÉFinition 3.1. — Un véhicule autonome $v \in \mathcal{V}$ est caractérisé par sa capacité (nombre maximum de passagers) $c$, son coût de trajet par distance parcourue cpd et une portée de communication limitée rng

$v := (c, cpd, rng)$

ainsi qu’un ensemble de propriétés dépendantes du temps qui sont

• loc : $\mathcal{V} \times \mathcal{T} \to \mathcal{N} \cup \mathcal{E}$ sa localisation actuelle,

• dest : $\mathcal{V} \times \mathcal{T} \to \mathcal{N}$ sa destination actuelle,

• seats : $\mathcal{V} \times \mathcal{T} \to \mathbb{N}^+$ le nombre de sièges actuellement disponibles,

• dist : $\mathcal{V} \times \mathcal{T} \to \mathbb{N}^+$, la distance parcourue depuis $t_0$,

• distR : $\mathcal{V} \times \mathcal{T} \to \mathbb{N}^+$, la distance parcourue avec un client depuis $t_0$,

• $r_k : \mathcal{V} \times \mathcal{T} \to \mathbb{N}^+$, le nombre de demandes connues depuis $t_0$,

• $r_s : \mathcal{V} \times \mathcal{T} \to \mathbb{N}^+$ le nombre de demandes satisfaites depuis $t_0$,

• messageC : $\mathcal{V} \times \mathcal{T} \to \mathbb{N}^+ \times \mathbb{N}^+$ le nombre de messages envoyés depuis $t_0$,

• messageS : $\mathcal{V} \times \mathcal{T} \to \mathbb{N}^+ \times \mathbb{N}^+$ le volume de messages envoyés depuis $t_0$.

La communication entre deux composants du système est réalisée si la distance
qui les sépare est inférieure ou égale à leur portée de communication. Cependant,
comme la portée de communication des véhicules est limitée, et pour maximiser leur
connectivité, deux véhicules peuvent être connectés par transitivité. Cela conduit à la
définition suivante d'un ensemble connecté :

DÉFinition 3.2. — Un ensemble connecté (noté CS pour connected set) est un ensemble d’entités connectées directement ou par transitivité.
Les CSs sont des entités dynamiques; ils sont créés, divisés, fusionnés en cours d'exécution en fonction du mouvement des véhicules. Ainsi, selon la définition précédente, un véhicule ne peut communiquer au temps t qu'avec les membres de son CS par des messages directs ou diffusés. De même, il ne peut recevoir que les demandes accessibles au sein de l'ensemble connecté selon les mêmes règles de communication. La portée de communication limitée divise implicitement la flotte en plusieurs ensembles connectés.

**DÉFINITION 3.3.** — Une solution à un problème AV-OLRA est définie pour chaque ensemble connecté comme une agrégation des allocations de tous les consommateurs de cet ensemble qui évite tous les conflits.

Cette définition implique qu'une solution à un problème AV-OLRA défini pour des véhicules et des demandes peut être sous-optimale parce que la solution optimale n'est pas l'union des sous-solutions optimales de chaque CS. En outre, toute solution dépend du temps à cause de l'aspect en ligne du problème.

La portée de communication dépend de la technologie de communication utilisée (formalisée par la propriété *rng* de véhicule) et de la densité du réseau (propriété de transitivité de formation des ensembles connectés). Considérer cette dimension dans notre modélisation du problème contribue à sa généricité en permettant de considérer son impact sur différents types de solution. Ainsi, plus la portée de communication est faible, plus il existe d'ensembles connectés ; cela signifie que pour une communication à courte portée, même avec des approches centralisées, le calcul de la solution est décentralisé vers plusieurs répartiteurs. Une flotte ayant une portée de communication suffisamment longue pourrait revenir à un seul ensemble connecté à l'échelle d'une ville avec un partage global des connaissances. Une approche centralisée conduit alors à un répartiteur central pour déterminer la solution globale.

La qualité d'une allocation est caractérisée par des indicateurs fonctionnels et techniques dont le calcul est indépendant des approches de résolution, mais qui permet de comparer leur faisabilité et leur qualité. Les indicateurs fonctionnels sont des mesures de l'optimalité du processus d'allocation défini par sa fonction objectif, tandis que les indicateurs techniques sont utilisés pour évaluer la faisabilité et l'applicabilité du processus d'allocation et pour prévoir ses coûts opérationnels dans différents contextes.

Dans ce papier, nous caractérisons la qualité d'une solution AV-OLRA dans les scénarios ODT par les indicateurs suivants calculés à partir de la définition des véhicules autonomes :

Quality est le pourcentage de demandes satisfaites (consommées) sur toutes les demandes annoncées. Par conséquent, cet indicateur indique le niveau de qualité de service (QoS). Son calcul repose sur l'utilisation des propriétés $r_k$ et $r_s$. Individuellement, il peut être calculé au niveau du véhicule v comme suit :

$$QoS_v = \frac{r_s^v}{r_k^v}$$
La QoS est formulée au niveau de la flotte :

$$QoS = \frac{\sum_{v \in V} r_s^v}{|R|}$$

Utility est l'utilité totale des plannings des véhicules, dérivée des distances des voyages réalisés (effectués avec un passager à bord, de la source à la destination *distR*), qui définit le **gain** pour l'entreprise.

Cost est le coût opérationnel, dérivé des distances totales parcourues par les véhicules *dist*. La relation entre les indicateurs **Utility** et **Cost** définissent la qualité des affaires (QoB).

$$QoS = \sum_{v \in V} P * r_s^v + p * distR^v - cpd^v * dist^v$$

P est un prix fixe (frais de service) par demande, p est un facteur de tarification par unité de distance parcourue.

MsgCount est le nombre total de messages échangés au cours du processus d'allocation dérivé de *messageC*.

MsgSize est la taille moyenne des messages échangés pendant l'allocation dérivée de *messageS*.

Ces deux derniers indicateurs de communication estiment le coût technique de la solution et permettent de prédire si elle est applicable en termes de charge de communication, c'est-à-dire si elle pourrait provoquer des goulets d'étranglement critiques. Ces indicateurs sont génériques, car fondée sur l'utilisation de données issues des activités élémentaires des véhicules.

## 4. APPROCHE MULTI-AGENTS POUR AV-OLRA

Dans cette section, nous décrivons notre modèle multi-agents support aux solutions au problème AV-OLRA. L'environnement du problème AV-OLRA représente la topologie de l'infrastructure urbaine $G$ et le modèle de communication des agents tel que décrit par la définition 3.2.

Il n'y a qu'un seul type d'agents dans notre modèle. Un agent véhicule autonome (AV) est associé à chaque véhicule du système. Nous pouvons distinguer trois sous-comportements différents (*acting*, *communicating* et *planning*). Comme nous modélisons AV-OLRA dans un espace de temps discret, l'horizon temporel est défini comme un ensemble de pas d'exécution. À chaque pas, chaque agent effectue les actions suivantes, comme le montre la figure 4.1 :

(1) lire les messages reçus et mettre à jour le contexte (sous-comportement de communication, *communicating*);

(2) choisir les lieux à visiter (sous-comportement de planification, *planning*);

(3) agir en effectuant une action de conduite (sous-comportement d'action, *acting*);

(4) diffuser ses informations contextuelles (sous-comportement de communication, *communicating*).
Le sous-comportement de planification, planning et ses relations aux autres sont à
spécialiser pour chaque solution (représentation en pointillé figure 4.1) alors que les
autres seront identiques pour chaque solution.

<figure><img src="image_4.png" /><figcaption>FIGURE 4.1 – Comportement générique d’un véhicule</figcaption></figure>

4.1. SOUS-COMPORTEMENT D’ACTION

En fonction de la présence de passagers à bord, de la localisation du véhicule et de
sa connaissance des demandes à venir, un agent AV peut se trouver dans l'un des états
suivants (figure 4.2) :

**Marauding:** le véhicule n'a pas de passager à bord et cherche sa prochaine
destination;

**Moving:** le véhicule a une destination et s'y rend selon la topologie urbaine;

**Picking up:** le véhicule est à l'emplacement d'origine de la demande du passager $p$ afin d'effectuer l'action `pick_up(p)` avant de reprendre son déplacement;

**Dropping off:** le véhicule est à l'emplacement de destination de la demande du passager $p$ afin d'effectuer l'action `drop_off(p)` avant de rechercher une nouvelle destination.

Les transitions entre ces états sont illustrées dans la figure 4.2.

<figure><img src="image_5.png" /><figcaption>FIGURE 4.2 – Sous-comportement d’action</figcaption></figure>
## 4.2. SOUS-COMPORTEMENT DE COMMUNICATION

En tant qu'agents communicants, les AVs ont un comportement de communication avec les autres entités environnantes; ils peuvent rejoindre/quitter des ensembles connectés (CS), diffuser, envoyer et recevoir des messages.

* join cs : l'agent rejoint le CS cs du fait qu'il se trouve dans le rayon de communication d'au moins un de ses membres;

* leave cs : l'agent quitte le CS cs car il n'est plus dans le rayon de communication d'au moins un membre;

* send(m, a) : l'agent envoie un message m à un autre agent a à condition qu'ils soient dans le même CS;

* receive(m) : l'agent reçoit un message m d'un autre agent de son CS (une fois reçu et lu, le message est stocké dans la base de croyances de l'agent);

* broadcast(m) : similaire à send(m, a) mais ici l'agent ne spécifie pas l'agent récepteur, il diffuse plutôt le message à l'ensemble des membres de son CS.

## 4.3. SOUS-COMPORTEMENT DE PLANIFICATION

Le comportement des AVs en matière de planification dépend du mécanisme d'allocation choisie (centralisée/décentralisée, coopérative/compétitive, avec/sans modèle de coordination). La figure 4.3 illustre le comportement de planification abstrait et générique des AVs. Pour mettre à jour son planning, un AV recherche en permanence des options de planification. Si une option est trouvée, l'AV en sélectionne une et communique (ou pas selon le modèle de coordination) sa décision à ses voisins (les autres agents de son CS). Le voisinage parvient à un accord ou à un désaccord, selon le mécanisme de coordination et l'option choisie. En cas d'accord, l'AV met à jour son planning et recherche l'option suivante et ce, jusqu'à ce qu'aucune option ne soit disponible. La nature des options de planification dépend également du mécanisme de coordination.

<figure><img src="image_6.png" /><figcaption>FIGURE 4.3 – Sous-comportement de planification</figcaption></figure>

Bien que nous soutenions plusieurs modèles de coordination, nous souhaitons étudier chacun et non les conséquences de leurs interactions. Par conséquent, nous considérons que l'ensemble des agents de la flotte est homogène. Dans la section 5, nous présentons en détail différents mécanismes de coordination que nous utilisons pour valider notre modèle, y compris certaines approches coopératives avancées comme
l'usage d'algorithmes DCOP et un mécanisme d'enchères pour le comportement de coordination des agents. Ce dernier répond aux exigences du problème AV-OLRA en fournissant une solution utilisant des calculs légers, dynamiques et continuellement sujets à amélioration.

## 4.4. UTILITÉ, CONTRAINTE ET OBJECTIF

Dans tout problème MARA, la fonction d'utilité représente le degré de satisfaction d'un agent pour une allocation donnée [1]. Chaque agent a une valeur d'utilité exprimée sous la forme d'une valeur explicite ou d'une relation qui révèle la solution la plus satisfaisante (optimale). Une procédure d'allocation tente de fournir aux agents des ressources qui correspondent autant que possible à leur exigence. Dans notre modèle, nous définissons la fonction d'utilité des agents AV sur la base des indicateurs de la qualité de solution décrits dans la section 3. Nous considérons que plus un agent satisfait de demandes, plus il doit gagner en valeur d'utilité. Ainsi, l'indicateur **Quality**, s'il est considéré individuellement pour chaque agent $a \in V$, définit son utilité :

$$u_a = \frac{r_s(a, t_{end})}{r_k(a, t_{end})} \qquad (4.1)$$

Bien entendu, l'attribution de la demande $r$ à l'agent $a$ est contrainte par la disponibilité spatiale et temporelle de $a$ et de $r$. Nous considérons que l'origine et la destination de chaque demande sont des constantes, et qu'une demande n'est disponible pour être prise en charge qu'à son origine pendant sa fenêtre temporelle définie $w_r[l_r, u_r]$. Ainsi, l'affectation de $r$ à $a$ exige que $a$ puisse arriver au point d'origine de $r$ à un moment $t$ situé entre la limite inférieure $l_r$ et la limite supérieure $u_r$ de la validité temporelle de $r$.

Dans ce document, nous n'envisageons pas de scénarios de partage de véhicules. Nous supposons qu'un trajet en véhicule est consacré à une seule demande, mais nous devons tout de même tenir compte de la taille de la demande (nombre de sièges requis) et de la capacité du véhicule. Cela implique que la définition de la disponibilité doit également inclure la contrainte de capacité :

$$\exists t \in w_r[l_r, u_r] : \text{seats}(a,t) \ge s_r \quad \& \quad \text{loc}(a,t) = o_r \qquad (4.2)$$

Le fait d'être membre d'une flotte impose aux AV d'être coopératifs et de suivre le mécanisme de coordination prédéfini pour atteindre leur objectif global. Dans une perspective globale d'ODT en tant que modèle commercial, l'objectif principal des prestataires de services ODT est de gagner la satisfaction des utilisateurs. Cela signifie que leur objectif est de réduire les coûts et d'augmenter les gains. De ce point de vue, nous pouvons définir la fonction objectif $\mathcal{F}$ à maximiser par le processus d'allocation fondé sur la relation entre les indicateurs **Utility** et **Cost** :

$$\mathcal{F} = \sum_{v \in V} (P + p * \text{dist}(v, t_{end})) - \sum_{v \in V} cpd_v * \text{distR}(v, t_{end}) \qquad (4.3)$$

$P$ est un prix fixe (frais de service) par demande, $p$ est un facteur de tarification par unité de distance parcourue.
# 5. MÉCANISMES DE COORDINATION

Cette section illustre certains comportements de coordination que les flottes de véhicules peuvent suivre pour atteindre un objectif global d'allocation. Pour chacun, nous présentons le modèle de coordination correspondant. Un mécanisme de coordination est défini par trois composantes $\langle DA, AC, AM \rangle$, où $DA$ indique le niveau d'autonomie de décision qui est soit centralisé (C) soit décentralisé (D); $AC$ indique s'il y a coopération des agents en notant $S$ s'ils coopèrent et partagent des informations sur les plannings et $N$ s'il n'y a pas de coopération. $AM$ est le nom du processus d'allocation.

## 5.1. COMPORTEMENT ÉGOÏSTE

Le mécanisme de coordination noté $\langle D, N, Greedy \rangle$ est fondé sur un processus d'allocation décentralisé avec des agents compétitifs et sans coordination explicite. Dans ce mécanisme, les agents ne s'appuient pas sur les décisions des autres et n'échangent jamais leurs plans. Dans les scénarios du monde réel, une stratégie de ce modèle est fondée sur l'avidité, dans laquelle le véhicule ne considère qu'une seule demande à l'avance (par exemple, la plus proche, afin de raccourcir la distance de conduite à vide) [11]. Lorsqu'un véhicule ne transporte pas déjà des clients, il doit décider quelle demande il traitera en premier, en fonction des informations dont il dispose sur les demandes disponibles. Une heuristique calcule une valeur de priorité pour chaque demande. Ensuite, l'agent traite en premier la demande ayant la valeur de priorité la plus élevée. Des conflits peuvent survenir, mais ils sont résolus simplement en appliquant la politique du « premier arrivé, premier servi ». Alors, si l'agent n'a pas de passager à bord ses options sont ses demandes connues et réalisables, sinon aucune option n'est prise en compte. L'état *coordinating* est ignoré (comme s'il parvenait à un accord pour toute option choisie), de sorte que la qualité de la solution dépend de la stratégie de l'agent pour choisir la demande suivante.

## 5.2. COMPORTEMENT AVEC RÉPARTITEUR

Ici, le mécanisme de coordination est centralisé, le rôle de l'agent est de mettre à jour son planning en fonction de ce qu'il reçoit du répartiteur. $\langle C, S, ILP \rangle$ est un exemple de ce type de mécanisme avec la résolution ILP (Integer Linear Problem) comme processus d'allocation. Dans notre modèle, nous avons besoin d'un répartiteur par ensemble connecté (CS). Ainsi, lors de la création (ou de la mise à jour), un membre d'un CS (par exemple, celui qui a l'indice le plus bas dans l'ensemble) devient le répartiteur qui sera responsable de collecter les informations des autres agents et sur demande. Il doit aussi faire le calcul d'allocation par lui-même, ou en appelant un service externe pour obtenir une allocation optimale (résolvant un ILP), puis envoyer à chaque autre véhicule son planning potentiel, comme dans [4, 10, 20]. Dans ce modèle centralisé, le rôle du comportement de planification des AVs est de demander à l'agent responsable (sur un portail ou un véhicule) de mettre à jour leur planning en permanence. Dans ce cas, la seule option disponible est de requêter le
portail, et l'état *coordinating* consiste en un protocole de demande/réponse qui enverra
le nouveau planning sous forme d'accord.

5.3. COMPORTEMENTS RÉELLEMENT COORDONNÉS

Dans ce cas, de type ⟨D, S, PC⟩, le mécanisme de décision est décentralisé, les agents sont coopératifs et un protocole de coordination (PC) est appliqué pour l'allocation. Dans cette catégorie de mécanismes de coordination, les agents échangent des informations et coopèrent pour atteindre un objectif commun, en évitant les conflits et en optimisant la qualité de la solution. Il existe plusieurs approches pour atteindre ce comportement, comme l'optimisation sous contraintes distribuées (DCOP) [5], les protocoles de négociation [3, 16] et les enchères [15, 19]. Nous instancions ici des solutions par enchères et par DCOP.

Coordination par enchères

Les enchères sont très courantes dans les situations quotidiennes et fournissent une
base conceptuelle générale pour comprendre les problèmes d'allocation des ressources
au sein d'ensembles d'agents [18]. Nous présentons ici un exemple de mécanisme col-
laboratif de construction de plannings de véhicules, dont notre proposition ORNInA
(voir [2]), notée ⟨D, S, Auction⟩, fondée sur des enchères pour coordonner de ma-
nière pair-à-pair les décisions de planification de flottes de véhicules autonomes. Ce
mécanisme est proposé pour fonctionner dans un cadre dynamique, entre des agents
véhicules qui appartiennent à un ensemble connecté dans lequel ils peuvent recevoir
et envoyer des messages directs ou diffusés. Les agents intéressés par une demande
donnée lancent des enchères au premier prix pour cette demande, et le gagnant l'ajoute
à son planning. La détermination du gagnant est un processus complètement décentra-
lisé. Afin d'améliorer l'efficacité de la planification dans des contextes dynamiques, les
agents sont autorisés à échanger leurs demandes planifiées au moment de l'exécution,
avec des tours d'enchères supplémentaires pour décider si cet échange augmente la
valeur de la fonction objectif au sein du CS. Les agents communiquent entre eux par
des messages directs ou indirects pour partager des informations ou coordonner leurs
décisions.

Coordination par DCOP

Dans ⟨D, S, DCOP⟩, les agents décident seuls mais se coordonnent avec les agents
du même ensemble connecté en utilisant un algorithme d'optimisation sous contraintes
distribuée afin d'éviter les conflits au sein du CS. À chaque fois qu'un ensemble
connecté change, un DCOP P = ⟨A, X, D, C⟩ est généré à partir de l'instance AV-
OLRA pour maximiser la fonction objectif dans l'équation 4.3, comme suit. A définit
l'ensemble des agents dans l'ensemble connecté. X définit l'ensemble des variables
de décision dans trois sous-ensembles (des xᵢⱼ, des yᵢⱼ et des zᵢⱼ) : xᵢⱼ ∈ X est une
variable binaire égale à 1 si le véhicule vᵢ sert la requête rⱼ ; yᵢⱼ est une variable binaire
égale à 1 seulement si la requête rⱼ est la première requête à être servie par vᵢ. Enfin,
$z_{ij}$ est une variable entière qui définit à quel moment une requête $r_j$ est visitée par $v_i$. D définit les domaines des variables : {0, 1} pour les $x_{ij}$ et les $y_{ij}$, et un ensemble de domaines de plages de temps définissant la fenêtre $[l_j, u_j]$ pour chaque $z_{ij}$. C définit l'ensemble des contraintes, qui se compose de contraintes dures (capacité, disponibilité spatio-temporelle et fenêtres temporelles) et de contraintes souples définissant le coût et l'utilité de la décision d'allocation (utilisées pour calculer la valeur de la fonction objectif).

Les algorithmes DCOP sont variés, et le choix dépend de l'objectif de la solution et du contexte du problème. Les caractéristiques d'exécution de l'algorithme (temps d'exécution, nombre/taille des messages et besoin en mémoire par agent) sont des facteurs essentiels pour traiter les problèmes dynamiques en ligne.

# 6. ÉVALUATION EXPÉRIMENTALE

Dans cette section, nous présentons les résultats expérimentaux de l'instanciation du modèle AV-OLRA avec le modèle multi-agents décrit dans la section 4, en prenant en charge les différents types de mécanismes de coordination de la section 5. Le modèle est mis en œuvre en tant que système multi-agents avec un simulateur de transport en temps discret.

## 6.1. CADRE EXPÉRIMENTAL

Nous explorons deux types de scénarios pour nos expérimentations. Le premier, sur données synthétiques, est fondé sur le réseau routier de la ville de Saint-Étienne. Plus de 1 400 arcs ont été extraits de Open Street Map (OSM)⁽¹⁾ et post-traités pour un quartier situé entre les coordonnées GPS (45.4325,4.3782) et (45.437800,4.387877) pour produire un graphe formé de 71 arcs. Les demandes des passagers sont générées aléatoirement avec des lieux de ramassage et de dépôt appartenant à un ensemble spécifique de lieux appelé *sources*. 40 lieux répartis uniformément sur la carte ont été sélectionnés comme *sources* pour l'émission de la demande.

Le second scénario est fondé sur le réseau urbain en forme de grille de l'arrondissement de Manhattan dans la ville de New-York. Pour ce scénario, les demandes des passagers ont été extraites de l'ensemble de données de NYC-TLC⁽²⁾.

L'idée principale qui motive l'utilisation de deux types de scénarios est d'expérimenter notre modèle SMA et la performance des approches de solution dans une variété de situations. Les scénarios de données synthétiques permettent de contrôler la taille du problème et la distribution de la demande lors de la création des instances du problème. Ils sont donc idéaux pour diagnostiquer les paramètres symptomatiques

<footnote>⁽¹⁾https://www.openstreetmap.org.</footnote>

<footnote>⁽²⁾The New York City Taxi and Limousine Commission (NYC-TLC) collecte des données, telles que les enregistrements des trajets, le nombre de véhicules et les tarifs dans la ville de New York sous forme de fichiers CSV par mois et par type de véhicule (taxis jaunes, taxis verts, véhicules de location et véhicules de location à gros volume).</footnote>
et pour régler les paramètres des algorithmes. D'autre part, l'extraction d'instances à partir de jeux de données tels que NYC-TLC permet d'expérimenter la performance des solutions sur des instances plus grandes (avec des tailles de flotte plus importantes et une plus grande densité de demandes) sur la base d'une distribution similaire au déploiement dans le monde réel.

Lorsque les véhicules doivent échanger directement des messages, nous considé-
rons qu'ils communiquent via DSRC<sup>(3)</sup> avec une portée de communication réaliste de
250 mètres. Le nombre de demandes générées et le nombre de véhicules sont des pa-
ramètres de la simulation. Tous les scénarios ont une durée de 1000 cycles et, à chaque
cycle, 0 ou 1 demande est générée. Nous évaluons la performance des 5 mécanismes
de coordination vus en section 5 dont celui fondé sur un DCOP avec l'algorithme
DSA, variante A, $p = 0,5$ [22] $\langle D, S, DCOP(dsa) \rangle$, et celui fondé sur un DCOP avec
l'algorithme MGM-2 [13] $\langle D, S, DCOP(mgm-2) \rangle$.

Le système multi-agents et le simulateur hébergé par la plateforme Territoire<sup>(4)</sup>, implémentés en Java, ont été exécutés sur un processeur Intel® Xeon® E-2146G CPU @ 3,50GHz, avec 32 Go de RAM DDR4. Les algorithmes DCOPs ont été mis en œuvre en utilisant la bibliothèque FRODO [9].

## 6.2. LE CHOIX ET LE PARAMÉTRAGE DES ALGORITHMES DE DCOP

Compte tenu des caractéristiques de notre problème, une comparaison (sur données synthétiques) des algorithmes DCOP en termes de charge de communication et de temps d'exécution en fonction de la taille du problème est présentée dans la figure 6.1. Cette comparaison a permis d'éliminer ceux qui nécessitent un temps d'exécution trop important et/ou une charge de communication trop élevée.

ADOPT, DPOP, ASO-DPOP, SynchBB et AFB sont connus pour être des al-
gorithmes complets qui trouvent des solutions optimales mais ont une complexité
algorithmique exponentielle. D'autre part, Max-Sum est un algorithme incomplet avec
un temps d'exécution raisonnable, mais qui nécessite une taille de mémoire exponen-
tielle par rapport au nombre moyen de voisins de l'agent dans le graphe de contraintes,
c'est-à-dire une mémoire exponentielle par rapport à l'arité des contraintes.

Max-Sum opère sur un graphe de facteurs qui est un graphe biparti dans lequel les variables et les contraintes sont représentées par des nœuds. Chaque nœud représentant une variable dans le DCOP est connecté à tous les nœuds de fonction qui représentent les contraintes (ou facteur) dans lesquelles elle est impliquée. De même, un nœud de facteur est connecté à tous les nœuds de variable qui représentent les variables dans le DCOP original qui sont incluses dans la contrainte qu'il représente. Chaque agent adopte le rôle du nœud représentant sa propre variable et le rôle d'un des nœuds de fonction représentant une contrainte dans laquelle il est impliqué. Ainsi, dans notre cas avec les instances fortement contraintes, Max-Sum nécessite une grande quantité

<footnote><sup>(3)</sup>La communication de véhicule à véhicule via la communication dédiée à courte portée (DSRC) offre une connectivité réseau rapide et à faible latence dans un rayon de communication allant jusqu'à 300 mètres.</footnote>

<footnote><sup>(4)</sup>https://territoire.emse.fr.</footnote>
<figure><img src="image_7.png" /><figcaption>FIGURE 6.1 – Comparaison des algorithmes DCOP au cours de l'exécution</figcaption></figure>

de mémoire pour la charge de communication et peut ne pas converger car le graphe factoriel comprend des cycles de tailles différentes.

Les autres sont les algorithmes DCOP de recherche locale dont la structure générale est synchrone. À chaque étape de l'algorithme, un agent envoie son affectation à tous ses voisins dans le réseau de contraintes et reçoit l'affectation de tous ses voisins. Ils diffèrent par la méthode que les agents utilisent pour décider s'ils doivent changer leurs affectations de valeurs actuelles à leurs variables. Par exemple, dans l'algorithme MGM (Maximum Gain Message), l'agent qui peut améliorer le plus son état dans son voisinage remplace son affectation. Dans MGM-2, la première étape consiste à décider quel sous-ensemble d'agents est autorisé à faire des offres. Chaque agent génère un nombre aléatoire de manière uniforme parmi [0, 1] et se considère comme un offrant si le nombre aléatoire est inférieur à un seuil $q$. Si un agent fait une offre, il ne peut pas accepter les offres des autres agents. Tous les agents qui ne font pas d'offre sont considérés comme des récepteurs. Chaque récepteur choisit aléatoirement (uniformément) un voisin et lui envoie un message d'offre, qui consiste en tous les mouvements coordonnés entre l'offreur et le récepteur qui apporteront un gain d'utilité locale au récepteur dans le contexte actuel. La décision stochastique de remplacer une affectation est inspirée de l'algorithme stochastique distribué DSA. Dans DSA un agent génère un nombre aléatoire à partir d'une distribution uniforme sur [0, 1] et agit si ce nombre est inférieur à un certain seuil $p$. Une valeur seuil plus faible réduit le nombre d'agents qui peuvent agir à chaque cycle, ce qui signifie une charge de messages plus faible et une qualité de solution légèrement inférieure, tandis qu'un seuil plus élevé signifie que chaque agent a plus de chances d'agir à chaque itération, ce qui signifie plus de cycles d'amélioration de la solution avec leurs dépenses en termes de communication.

Une comparaison (sur données synthétiques) de la qualité des solutions des algorithmes de recherche locale DCOP est présentée dans la figure 6.2. Cette comparaison montre que les différentes variantes de DSA ont des performances presque identiques sur nos instances lorsqu'elles ont la même valeur $p$. Pour les variantes DSA et MGM, la qualité des solutions augmente avec le temps d'exécution de chaque cycle jusqu'à
<figure><img src="image_8.png" /><figcaption>AV-OLRA</figcaption></figure>

FIGURE 6.2 – Qualité de solution des algorithmes DCOP à recherche locale

atteindre un point de stabilisation après lequel l'amélioration devient très faible. En fixant $p = 0,5$, $q = 0,5$, les algorithmes DSA et MGM-2 atteignent ce point de stabilisation après environ les cycles 30 à 50 itérations. Plus précisément, avec la variante A de DSA, le point de stabilisation de 80 % est atteint en 45 itérations lorsque $p = 0,5$, et MGM-2 atteint ses 82 % en 40 itérations lorsque $q = 0,5$. Sur la base de ces résultats, nous limitons nos expérimentations aux seuls algorithmes DCOP MGM-2 ($q = 0,5$) et DSA (variante A, $p = 0,5$).

## 6.3. EXTRACTION D'INSTANCES AV-OLRA À PARTIR DE JEUX DE DONNÉES
### NYC-TLC

À New York, il y a plus de 13 000 taxis pour satisfaire l'énorme densité de demandes. Ainsi, si nous voulons obtenir une qualité de service élevée dans nos expériences avec n'importe quel mécanisme d'allocation, nous avons besoin d'une flotte de taille similaire. Cependant, faire une simulation microscopique sur des flottes de cette taille demande beaucoup de ressources. Par conséquent, nous devons produire des instances de taille inférieure qui restent toutefois représentatives de ces données. Pour ce faire, nous avons étudié le modèle statistique des données et, dans ce qui suit, nous présentons quelques analyses de données sur un fichier CSV provenant de l'ensemble des données d'enregistrement des trajets de NYC-TLC pour le mois de janvier 2018.
Sur la base du modèle statistique de jeux de données NYC-TLC, nous avons produit des instances de taille inférieure d'enregistrements de trajets qui contiennent une distribution spatiale et temporelle similaire des demandes, mais avec une densité inférieure. Pour chaque instance, nous avons choisi un nombre limité de zones, bien distribuées géographiquement dans Manhattan, et dont la densité de demandes varie. Puis nous avons sélectionné dans les fichiers CSV originaux un sous-ensemble de demandes courtes entre ces zones ayant des heures de prise en charge et de dépose correspondant à la distribution temporelle des données originales. Les figures 6.4 et 6.3 illustrent une comparaison de la distribution spatiale et temporelle des demandes dans l'une des instances réduites et les données originales. Si nous ne considérons que Manhattan, les exemples réduits sont bien représentatifs des données originales sur les trajets courts, malgré le fait que le nombre de zones de prise en charge et de dépôt soit limité. Nous avons dans ces exemples des zones qui varient (de la même manière que les données originales) de zones très encombrées comme Times Square à des zones très peu encombrées en périphérie. Nous avons également le même schéma d'heures de pointe.

<figure><img src="image_9.png" /><figcaption>FIGURE 6.3 – Comparaison de la distribution temporelle des demandes à Manhattan pour les jeux de données originaux et réduits</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>FIGURE 6.4 – Comparaison de la distribution spatiale des demandes à Manhattan pour les jeux de données originaux et réduits</figcaption></figure>

## 6.4. QUALITÉ DES SOLUTIONS

Les figures 6.5 et 6.6 illustrent les performances des cinq approches en termes d'indicateurs de qualité de service (QoS) et de qualité des affaires (QoB) avec une analyse comparative des deux jeux de données. Chaque point de ce diagramme représente la valeur de l'indicateur agrégée sur 1 000 cycles de simulation. Ces deux figures montrent comment la qualité des solutions évolue avec l'augmentation de la taille de la flotte. Nous pouvons remarquer l'augmentation de la QoS et de la QoB avec l'augmentation du nombre de véhicules dans la flotte jusqu'à atteindre un point de bascule, après lequel il n'est plus possible d'améliorer la QoB en ajoutant des véhicules supplémentaires et la QoS n'est amélioré qu'à la marge.

<figure><img src="image_11.png" /><figcaption>FIGURE 6.5 – Évolution de la QoB en fonction de la taille de la flotte de véhicules</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>FIGURE 6.6 – Évolution de la QoS en fonction de la taille de la flotte de véhicules</figcaption></figure>

Les valeurs obtenues par le comportement *avec répartiteur* représentent une limite supérieure pour la QoB car le répartiteur central calcule pour chaque cas la solution localement optimale compte tenu du contexte de l'ensemble connecté. Les performances des quatre autres approches varient selon les indicateurs. Ainsi, si Enchères domine DCOP DSA-A (QoS et QoB), sa domination sur DCOP MGM dépend du nombre de véhicules selon les indicateurs.

Étant basée sur un algorithme glouton, dont le temps d'exécution est linéaire par rapport à la taille du problème, l'approche égoïste est très efficace en termes de temps de prise de décision. La raison en est qu'elle ne nécessite pas beaucoup de calculs pour sélectionner la demande la plus proche. L'inconvénient est ici l'ignorance de ce qui précède les décisions prises et le fait que les conflits de décisions entre différents véhicules (par exemple, deux véhicules vont vouloir prendre le même passager) ne sont résolus que tardivement, ce qui réduit la QoS. Avec un faible nombre de véhicules, les ensembles connectés sont peu nombreux et, par conséquent, la quantité d'informations partagées est réduite.

Les performances des approches coopératives et de l'approche avec répartiteur dépendent fortement de la quantité d'informations. Ayant des quantités similaires d'informations partagées, la qualité des quatre approches ne semble pas être très différente.

Avec des flottes de taille plus importante, davantage d'informations sont partagées dans les ensembles connectés. En outre, les véhicules passent plus fréquemment d'un ensemble connecté à un autre. Les trois approches coopératives ont des performances presque similaires. Pour atteindre les mêmes valeurs de QoS avec une approche égoïste, il faut davantage de véhicules dans la flotte.

Si l'on considère les algorithmes DCOP (DSA et MGM-2), au temps *t*, et en partant d'une solution réalisable $s_{t-1}$ obtenue au temps $t-1$, chacune de ces approches tente d'obtenir une nouvelle solution $s_t$ dans laquelle la valeur de la fonction objectif est améliorée. Les algorithmes DCOP se concentrent sur la maximisation de l'utilité individuelle des agents pour maximiser l'objectif global, ce qui signifie attribuer aux
agents des demandes qui augmentent son gain. Plus les demandes de voyage (potentiellement réussies) assignées à un agent sont nombreuses, plus l'utilité individuelle est élevée. Bien sûr, cela augmentera la QoB, mais l'effet principal sera sur la valeur de la QoS. D'autre part, chaque agent dans ORNInA, à chaque pas de temps, essaie d'ajouter à son planning au maximum une demande qui peut améliorer son utilité et donc les valeurs de QoS et QoB, puis la phase d'amélioration du planning, définie par le protocole pull-demand, essaie de réallouer les demandes de manière à maximiser le gain global même si cette réallocation diminue le gain de l'agent qui abandonne la demande. Le protocole pull-demand n'affecte que la valeur de la QoB car le nombre de demandes programmées (à servir) ne change pas, elles sont seulement réaffectées à d'autres agents. Ainsi, alors que la coordination basée sur les enchères d'ORNInA est plus performante que les algorithmes de recherche DCOP en termes de QoB, elle est surpassée par les deux en termes de QoS.

Pour atteindre un certain niveau de QoS, il faut un nombre minimum de véhicules, ce nombre varie selon les différentes approches, par exemple servir 90 % des demandes(5) (illustré par la ligne noire pointillée sur la figure 6.6(b)) nécessite de manière optimale 240 véhicules avec l'approche Répartiteur, tandis que ce nombre augmente à plus de 350 pour l'approche Egoïste. Les figures 6.7 comparent les cinq approches en termes de taille de flotte requise pour atteindre cette QoS de 90 %. La figure 6.7(b) montre que le mécanisme Egoïste nécessite un nombre supplémentaire de véhicules qui est presque le double de DCOP et 3 fois de ORNInA. (concernant l'optimal pour le Dispatching).

<figure><img src="image_13.png" /><figcaption>(a) La taille de flotte requise pour répondre à 90 % des demandes</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(b) pourcentage du nombre de véhicules supplémentaires nécessaires</figcaption></figure>

FIGURE 6.7 – Comparaison de l'approche de la solution sur la taille de flotte requise pour un niveau de QoS

<footnote>(5)En pratique, servir 90 % des demandes représente une faible QoS. Cependant, ce seuil est choisi à titre d'exemple à des fins de comparaison, la même comparaison peut être effectuée avec n'importe quel seuil supérieur ou inférieur</footnote>
## 6.5. CHARGE RÉSEAU

Le tableau 6.1 présente des indicateurs liés à la communication obtenus en simulant un scénario sur 1000 cycles, avec 10 véhicules, pour les différents comportements étudiés. Ici, les deuxième et troisième colonnes indiquent la taille maximale et moyenne des messages échangés (en octets) représentant l'indicateur **MsgSize**. La quatrième colonne rapporte l'indicateur **MsgCount** en termes de nombre moyen de messages reçus par un agent par cycle de simulation.

Même sans coordination, les agents échangent des messages d'information sur les nouvelles demandes annoncées. Ce type de message dépend du mécanisme de coordination. De nouveaux types de messages sont utilisés dans le mécanisme avec répartiteur : les messages de requête et de réponse échangés entre les véhicules et le répartiteur central. Les messages de requêtage contiennent simplement le contexte global de l'ensemble des véhicules connectés qui demandent au répartiteur de construire leurs plannings. Les messages de réponse sont envoyés par le répartiteur aux véhicules de manière individuelle et contiennent le planning potentiel de chacun. Ces messages peuvent être volumineux, en fonction de la taille du sous-problème. Les messages d'offre et de réponse utilisés par le mécanisme de coordination basé sur les enchères sont légers, de sorte que les valeurs de l'indicateur **MsgSize** restent proches de l'approche égoïste, tandis que la valeur **MsgSize** devient polynomiale dans le nombre d'agents dans l'ensemble connecté et le nombre de leurs demandes connues. Dans les deux mécanismes de coordination basés sur un DCOP (DSA et MGM-2), les agents d'un ensemble connecté instancient un DCOP entre eux chaque fois qu'ils doivent décider d'une mise à jour du planning. L'obtention d'une solution par l'un de ces algorithmes nécessite l'échange d'un grand nombre de messages. Ces deux algorithmes ne sont pas complets, ce qui signifie qu'ils poursuivent leurs essais pour améliorer la solution jusqu'à atteindre le timeout ou un optimum (local). Ceci accroît le nombre de messages échangés. D'autre part, la taille des messages échangés par ces deux approches est très faible par rapport aux autres approches.

<figure><img src="image_15.png" /><figcaption>FIGURE 6.8 – Nombre moyen de messages reçus par un véhicule dans un ensemble connecté</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>FIGURE 6.9 – Taille moyenne des messages reçus par un véhicule dans l'ensemble connecté</figcaption></figure>

On note pour le temps *t* et pour un ensemble connecté *cs* le nombre d'agents véhicules $n_{cs}^t$ et $m_{cs}^t$ le nombre total de demandes connues par les membres de *cs*, **MsgCount** pour un seul sous-problème peut être proportionnel à $n_{cs}^t$ pour Selfish, $n_{cs}^t \times m_{cs}^t$ pour ORNInA, $2n_{cs}^t$ pour Dispatching et $n_{cs}^t$ pour DCOPs. La figure 6.9 illustre la taille moyenne relative des messages (**MsgSize**). En général, la taille des messages d'information sur les demandes (qui est le type de message commun à tous les mécanismes) croît linéairement avec $m_{cs}^t$, et donc avec la taille du CS.

Pour le mécanisme Dispatching, nous avons en plus des messages *query* et *response* dont la taille est proportionnelle à $n_{cs}^t \times m_{cs}^t$. Les messages d'enchère et de demande de tirage pour ORNInA ont une taille stable indépendante de la taille du sous-problème, car chacun d'eux est un message biunivoque ne concernant qu'une seule demande à la fois. Il en va de même pour les messages de décisions du DCOP, qui sont de petite taille. Cependant, la densité des messages de décision des DCOPs réduit fortement l'effet de la taille des messages d'information sur les valeurs moyennes de **MsgSize**, ainsi nous pouvons voir les lignes de DSA et MGM-2 dans la figure 6.9 comme presque constantes.

<table><caption>TABLE 6.1 – Statistiques des coûts de communication et de prise de décision pour les différents mécanismes de coordination étudiés pour un scénario avec 10 véhicules.</caption><thead><tr><th>Coordination</th><th>max msg size</th><th>avg msg size</th><th>msg per agent</th><th>comm. load</th><th>reschedule rate</th></tr></thead><tbody><tr><td>Egoïste</td><td>140</td><td>88</td><td>6</td><td>2,21 MB</td><td>2,0</td></tr><tr><td>Répartiteur</td><td>3500</td><td>168</td><td>21</td><td>11,2 MB</td><td>3,0</td></tr><tr><td>Enchères(ORNInA)</td><td>140</td><td>112</td><td>53</td><td>37,7 MB</td><td>1,5</td></tr><tr><td>DCOP(MGM-2)</td><td>210</td><td>25</td><td>5040</td><td>297,6 MB</td><td>12,0</td></tr><tr><td>DCOP(DSA-A)</td><td>236</td><td>20</td><td>5015</td><td>75,1 MB</td><td>13,0</td></tr></tbody></table>
## 6.6. STABILITÉ DES PLANNINGS

Le tableau 6.1 présente également la fréquence des reprogrammations de plannings en considérant l'intervalle moyen entre deux cycles de simulation au cours desquels les véhicules mettent à jour leurs plannings. Plus cette valeur est élevée, plus les plannings des véhicules sont stables. Dans ces contextes dynamiques, le fait d'avoir des plannings stables pendant une longue période signifie qu'aucune nouvelle demande n'est insérée, ce qui affecte la qualité de service. D'autre part, lorsque les horaires des véhicules changent fréquemment, les véhicules peuvent changer de destination et osciller pendant un certain temps avant d'effectuer un trajet réussi, ce qui peut diminuer la qualité de service. Dans nos scénarios, la coordination fondée sur des DCOPs permet d'obtenir des horaires très stables et de bonne qualité au détriment d'une charge de communication plus importante. Si la stabilité n'est pas une contrainte, mais que la communication est limitée, une approche utilisant des enchères est une très bonne alternative de stratégie d'allocation.

## 7. CONCLUSION

Cet article propose un modèle générique pour un problème d'allocation des ressources rencontré dans la gestion de flottes de véhicules autonomes connectés. Notre modèle est bien adapté au domaine de l'ODT, où les flottes répondent en ligne aux demandes des passagers dans des environnements dynamiques. La composante communication de notre modèle prend en charge la transmission directe, par diffusion de messages et transitivité, et repose sur le concept d'ensembles connectés. Nous proposons également un modèle SMA comme support au déploiement de différentes approches pour trouver des solutions et coordonner les véhicules. L'utilisation de ces deux modèles offre une généricité sur les dimensions de la communication et de la coordination. D'une part, la portée limitée de la communication caractérise le problème en affectant le niveau de connectivité et en limitant ainsi les possibilités de centralisation. D'autre part, étant donné qu'il dépend du processus d'attribution, le choix du sous-comportement de planification des véhicules définit le mécanisme de coordination qui affecte le contexte spatio-temporel dynamique des instances du problème.

Pour expérimer et évaluer ce modèle générique, nous avons mis en œuvre plusieurs mécanismes de coordination et les comparons in silico suivant des indicateurs fonctionnels et techniques. Le recours aux DCOPs ou aux enchères en ligne pour coordonner les décisions décentralisées permet d'obtenir des allocations de qualité raisonnable par rapport à une allocation optimale ou à une flotte de taxis non coordonnés. Les stratégies d'allocation basées sur les DCOPs ne modifient pas trop fréquemment les plans des véhicules mais induisent tout de même plus de communication que la stratégie fondée sur les enchères.

Dans ce travail, nous avons fait l'hypothèse que la coordination est plus rapide (voire instantanée) que le déplacement. Mais il s'agit d'une hypothèse à valider dans la vie réelle. Nous prévoyons d'analyser en profondeur la relation entre la stabilité, l'exhaustivité et la faisabilité des solutions à l'avenir. Il s'agirait également d'étudier
l'impact de la dynamique (propagation des requêtes dans le réseau) des ensembles connectés sur la qualité des solutions. Pour ce faire, nous devons mettre en œuvre d'autres approches et comparer systématiquement leurs performances, leur qualité, leur faisabilité, la stabilité et les questions techniques pour leur application pratique.

BIBLIOGRAPHIE

[1] Y. CHEVALEYRE, P. E. DUNNE, U. ENDRISS, J. LANG, M. LEMAÎTRE, N. MAUDET, J. A. PADGET, S. PHELPS, J. A. RODR & P. SOUSA, « Issues in Multiagent Resource Allocation », *Informatica* **30** (2006), p. 3-32.

[2] A. DAoud, F. BALBO, P. GIANESSI & G. PICARD, « ORNInA: A decentralized, auction-based multi-agent coordination in ODT systems », *AI Communications* **34** (2021), n° 1, p. 37-53.

[3] M. EGAN & M. JAKOB, « Market mechanism design for profitable on-demand transport services », *Transportation Research Part B: Methodological* **89** (2016), p. 178-195.

[4] M. EL FALOU, M. ITMI, S. EL FALOU & A. CARDON, « On demand transport system's approach as a multi-agent planning problem », in *2014 International Conference on Advanced Logistics and Transport (ICALT)* (Tunis, Tunisia), IEEE, 2014, p. 53-58.

[5] F. FIORETTO, E. PONTELLI & W. YEOH, « Distributed Constraint Optimization Problems and Applications: A Survey », *Journal of Artificial Intelligence Research* **61** (2018), p. 623-698.

[6] A. GLASCHENKO, A. IVASCHENKO, G. RZEVSKI & P. SKOBELEV, « Multi-Agent Real Time Scheduling System for Taxi Companies », *AAMAS* (2009), p. 29-36.

[7] X. JIN & L. JIE, « A Study Of Multi-Agent Based Model For Urban Intelligent Transport Systems », *International Journal of Advancements in Computing Technology* **4** (2012), n° 6, p. 126-134.

[8] A. LAMMOGLIA, R. M. FAYE & D. JOSSELIN, « A dynamic cooperation modelling for improving taxi fleet efficiency », in *proceeding of AGILE'2012* (Avignon) (J. Gensel, D. Josselin & D. Vandenbroucke, éds.), AGILE, 2012, p. 163-168.

[9] T. LÉAUTÉ, B. OTTENS & R. SZYMANEK, « FRODO 2.0: An Open-Source Framework for Distributed Constraint Optimization », in *Proceedings of the IJCAI'09 Distributed Constraint Reasoning Workshop (DCR'09)* (Pasadena, California, USA), 2009, https://frodo-ai.tech, p. 160-164.

[10] D.-H. LEE, H. WANG, R. CHEU & S. TEO, « Taxi Dispatch System Based on Current Demands and Real-Time Traffic Conditions », *Transportation Research Record : Journal of the Transportation Research Board* **1882** (2004), p. 193-200.

[11] R. R. S. VAN LON, T. HOLVOET, G. VANDEN BERGHE, T. WENSELEERS & J. BRANKE, « Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems », in *international conference on Genetic and evolutionary computation conference companion - GECCO Companion '12* (Philadelphia, Pennsylvania, USA), ACM Press, 2012, p. 331-336.

[12] M. MACIEJEWSKI & K. NAGEL, « The influence of multi-agent cooperation on the efficiency of taxi dispatching », in *International conference on parallel processing and applied mathematics*, Springer, 2013, p. 751-760.

[13] J. P. PEARCE & M. TAMBE, « Quality Guarantees on K-Optimal Solutions for Distributed Constraint Optimization Problems », in *Proceedings of the 20th International Joint Conference on Artificial Intelligence* (San Francisco, CA, USA), IJCAI'07, Morgan Kaufmann Publishers Inc., 2007, p. 1446-1451.

[14] N. RONALD, R. THOMPSON & S. WINTER, « Simulating demand-responsive transportation: a review of agent-based approaches », *Transport Reviews* **35** (2015), n° 4, p. 404-421.

[15] S. SATUNIN & E. BABKIN, « A multi-agent approach to Intelligent Transportation Systems modeling with combinatorial auctions », *Expert Systems with Applications* **41** (2014), n° 15, p. 6622-6633.

[16] K. T. SEOW, N. H. DANG & D.-H. LEE, « A Collaborative Multiagent Taxi-Dispatch System », *IEEE Transactions on Automation Science and Engineering* **7** (2010), n° 3, p. 607-616.

[17] W. SHEN & C. LOPES, « Managing Autonomous Mobility on Demand Systems for Better Passenger Experience », in *PRIMA 2015: Principles and Practice of Multi-Agent Systems* (Cham), Lecture Notes in Computer Science, vol. 9387, Springer, 2015, p. 20-35.

[18] Y. SHOHAM & K. LEYTON-BROWN, *Multiagent systems: Algorithmic, game-theoretic, and logical foundations*, Cambridge University Press, 2009.
[19] R. VAN PARYS, M. VERBANDT, M. KOTZÉ, J. SWEVERS, H. BRUYNINCKX, J. PHILIPS & G. PIPELEERS, «Flexible Multi-Agent System for Distributed Coordination, Transportation & Localisation», in *Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems* (Richtland, SC), AAMAS '18, International Foundation for Autonomous Agents and Multiagent Systems, 2018, p. 1832–1834.

[20] L. YANG, Z. JIERU, C. JINGXIN & T. ZHIYONG, «Central Decision Intellective Taxi System and Multi Ride Algorithm», in *International Conference on Artificial Intelligence, Automation and Control Technologies* (New York, NY, USA), AIACT '17, ACM, 2017, event-place: Wuhan, China, p. 1-6.

[21] M. ZARGAYOUNA, F. BALBO & K. NDIAYE, «Generic model for resource allocation in transportation. Application to urban parking management», *Transportation Research Part C: Emerging Technologies* 71 (2016), p. 538-554.

[22] W. ZHANG, G. WANG, Z. XING & L. WITTENBURG, «Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks», *Artificial Intelligence* 161 (2005), n° 1, p. 55-87.

**ABSTRACT.** — The development of autonomous vehicles, capable of peer-to-peer communication, as well as the interest in on-demand solutions (e.g., Uber, Lyft, Heetch), are the primary motivations for this study. Allocation problems are of major importance in the management of on-demand transportation systems (ODT). They have been studied for decades, and various solutions have been proposed. The solution approaches can be classified into two categories: centralized and decentralized. In practice, each has its advantages and disadvantages. In this work, we aim to provide a generic model for the problem of online on-demand transportation with autonomous vehicles and a multi-agent model dedicated to resource allocation and fleet planning. The latter considers autonomous vehicles that communicate in an inter-vehicular network to satisfy ride requests in an ODT system. We evaluate the generality of this model by applying several allocation approaches (mathematical programming, greedy heuristics, distributed constraint optimization and auctions) and compare their performances in terms of solution quality and technical and communicational indicators on synthetic scenarios generated from real data.

**KEYWORDS.** — Multiagent Systems, Coordination, On demand Transport, Resource Allocation, Connected Autonomous Vehicles, Simulation.

Manuscrit reçu le 18 mars 2022, accepté le 22 septembre 2022.