La convergence, une manière de concevoir un TAD

Le principe de convergence

Du point de vue mathématique, la convergence existe par exemple dans l’étude des suites réelles. Une suite réelle u est dite convergente lorsque l’ensemble de ses points un se rapprochent d’un point limite u ∗ , on dit dans ce cas que u tend vers u ∗ : lim n→+∞ un = u ∗ ⇔ lim n→+∞ (un − u ∗ ) = 0 En géographie, la convergence caractérise le rapprochement de flux jusqu’à leurs rencontres en un lieu. Elle est visible notamment pour des flux maritimes, nuageux… En géographie humaine, les déplacements de fret ou de personnes sont des flux émis et reçus selon un ensemble de phénomènes comme ceux décrits dans le chapitre 3. D’une manière générale, le principe de convergence traduit la réunion en un point (lieu) de plusieurs courants. Ainsi les déplacements humains sont animés par les polarités du territoire et se structurent en flux convergeant vers des lieux communs particulièrement attractifs comme les centres-villes pour les commerces et les administrations, les grandes zones commerciales périphériques ou encore les « lieux de vie » (cinémas, salles de concert, stades…). Les TAD n’échappent pas à cette règle, car ils sont par essence même les produits de la mobilité humaine. Dans la thèse de Castex (2007), figure une typologie exhaustive des différents types de TAD. Parmi les différentes topologies et organisations spatiales des services figurent les formes dites en convergence : – la monoconvergence qui traduit l’attraction d’un seul point du territoire.

La convergence simple

– la multiconvergence occasionnée par plusieurs points faisant chacun converger à lui-même plusieurs flux de personnes (C1,C2, fig. 4.1(b). Demande de service Convergence/Desserte C (a) Monoconvergence Convergences/Dessertes Demandes de service C 1 C 2 (b) Multiconvergence FIG. 4.1: Deux exemples de convergence : l’exemple (a) traduit une seule convergence (C), le (b) indique plusieurs convergences, c’est-à-dire plusieurs dessertes (C1,C2). 

La convergence simple

La monoconvergence peut paraître artificielle dans la mesure où il y a nécessairement plusieurs attracteurs sur le territoire. Néanmoins elle traduit une réalité créée par les transporteurs eux-mêmes sur les réseaux de transport, pour répondre à un besoin de mobilité en direction de lieux particuliers comme les gares TGV ou les aéroports. Ces places, souvent excentrées et pourtant fortement attractives, demeurent peu voire mal desservies par les transports publics, nottamment en horaires de frange (très tôt ou très tard). Les systèmes de TAD comme « Evolis-Gare » à Besançon répondent à cette demande de mobilité. Cette polarisation unique permet l’introduction d’un ensemble d’optimisations à travers l’élaboration d’un graphe de convergence représentant le problème de transport à solutionner d’une part, et d’autre part à travers les Arbres Couvrants Tentaculaires (Canalda et al., 2004; Chevrier et al., 2006c) décrivant la solution de transport sous la forme d’un graphe particulier : un arbre. Par la suite, pour assurer le service, nous disposons d’une flotte de n véhicules à capacités différentes. La méthode que nous proposons est statique dans la mesure où nous connaissons l’ensemble des demandes de service à l’avance. 69 Chapitre 4. La convergence, une manière de concevoir un TAD

Graphe de convergence issu de la polarisation

Nous souhaitons dresser un 1-graphe G(V, E) orienté acyclique (Directed Acyclic Graph, DAG), avec V l’ensemble des nœuds du graphe (indiquant une prise en charge ou montée et la descente unique du service) et E l’ensemble des arcs (indiquant les chemins possibles). Pour établir ce « graphe de convergence » comme celui de la figure 4.2(a), nous disposons au préalable d’un ensemble de données nécessaires : – l’horaire hC de desserte au point C. – les requêtes de transport r exprimées sous la forme : – r + pour le point de prise en charge ; – hr+ pour les horaires de prise en charge souhaités ; – wr pour le nombre de personnes à transporter de r + à C. – la matrice origines/destinations (OD) en temps (MT ) des points du territoire à desservir, obtenue sur SIG1 . Les temps relevés correspondent aux plus courts chemins ; – un coefficient de relaxation k appliqué aux temps de parcours tx→y des points x vers y : tx→y = k.MT xy, pour faciliter les détours dans l’ensemble des plus courts chemins possibles. k est un coefficient à calibrer, qui détend les temps de parcours pour autoriser des détours (dans ce cas k ≥ 1.0), irréalisables si les temps de parcours sont tendus (k = 1.0). La construction du graphe se fait de la manière suivante. Préalablement les nœuds r + de prise en charge sont ordonnés selon leurs temps de parcours nécessaires pour gagner la convergence, c’est l’ordre total des nœuds (Chevrier et al., 2006b), tel que ∀x, y ∈ V, tx→C > ty→C ⇔ x ≺ y La séquence Θ des sommets V ordonnés est une construction par insertion. Comme les horaires sont déterminés par rapport à l’horaire de convergence, les points de départ les plus éloignés à la convergence se voient attribués un horaire de passage plus tôt. L’ordre de la séquence Θ correspond à l’ordre des horaires de départ, du plus tôt au plus tardif. 

La convergence simple

La séquence Θ est construite par insertion (x, y sont deux points de ramassage) : 1. Θ(V) ← ⊘ 2. Pour chaque x ∈ V faire (a) inséré ← FAUX (b) Pour chaque y ∈ Θ(V) faire Si tx→C > ty→C alors i. insérer x avant y dans Θ(V) # x doit être desservi avant y ii. inséré ← VRAI Fin si Fait (c) Si inséré = FAUX alors ajouter x à Θ(V) # x est en fin de liste Fin si Fait Les retours arrière ne sont donc pas autorisés. Quant aux connexions entre chacun des nœuds, celles-ci doivent répondre à la condition temporelle selon laquelle un point x peut gagner un point y si et seulement si hx + tx→y ≤ hy, et nous notons hxyi l’arc correspondant. Les arcs notés en pointillés indiquent quant à eux les transitivités : ∀x, y, z ∈ V, hx + tx→y + ty→z ≤ hz ⇒ ∃hxzi ∈ E Demande de service Convergence/Desserte C 1 2 3 Transitivite (a) DAG construit à partir de la demande Demande de service Convergence/Desserte C Trajet emprunte (b) Une solution sous forme d’ACT FIG. 4.2: DAG (a) associé au problème de TAD de la figure 4.1(a) et un arbre couvrant tentaculaire optimal (b) 71 Chapitre 4. La convergence, une manière de concevoir un TAD Les liaisons ainsi faites, l’ensemble des nœuds a à la fois des prédécesseurs (des arcs incidents) et des successeurs (arcs sortants). Quant aux autres nœuds, certains n’ont pas de prédécesseurs : ce sont les nœuds minimaux du graphe (fig. 4.2(a) sommets 1, 2 et 3) et un seul n’a pas de successeur : c’est le nœud terminal (l’antiracine de l’arbre) qui correspond au point de desserte, la convergence C. Connaître et distinguer ces sommets nous permet maintenant d’utiliser les arbres couvrants tentaculaires pour couvrir le graphe ainsi créé et ensuite d’apporter des optimisations de résolution dans l’algorithme génétique, qui se révèle particulièrement efficace dans ce type d’application (Julstrom et Raidl, 2002; Raidl et Julstrom, 2003). 

Les arbres couvrants tentaculaires : une solution à la monoconvergence

Les arbres couvrants tentaculaires (ACT) sont issus de travaux consacrés au transport à la demande en convergence simple (Chevrier et al., 2006a,c). Définitions Nous posons préalablement un ensemble de définitions nécessaires à l’explicitation des ACT : 1. un arbre A(V, E) est un graphe connexe sans cycle (ayant une arête de moins que de sommets) ; 2. un arbre couvrant A(V, E) est un sous-graphe de G(V, E) contenant tous les sommets de G ; 3. l’antiracine de l’arbre couvrant A(V, E) est le sommet n’ayant que des arcs incidents (i.e. pas d’arcs sortants) ; 4. un chemin terminant est une branche de l’arbre couvrant A(V, E), se terminant à l’antiracine de l’arbre ; 5. un arbre couvrant tentaculaire est un arbre couvrant dont tous les chemins terminants sont arcs-disjoints deux à deux et sommets-disjoints deux à deux (hormis à l’antiracine). L’unique jonction des branches de l’arbre couvrant tentaculaire correspond à l’antiracine. En effet, ce sommet ne peut être une racine en raison de l’orientation des arcs, ceux-ci indiquant une destination et non une source. Les figures 4.3(b,c,d,e,f) sont des exemples d’ACT du graphe de la figure 4.3(a). Un ACT est dit minimal lorsque le nombre de branches le composant est minimal.