Enseignements de notre start-up sur les files d’attente
Cytec est une start-up où j’ai travaillé avec François Giraud sur les transports collectifs, notamment sur le développementet la promotion du Système VEC. Nous avons organisé, en 1973, un séminaire pour exposer aux chercheurs de la NASA, convertis après 1969 en chercheurs du TRI (Transportation Research Institute) à Boston, les résultats de nos réflexions et de nos réalisations dans le domaine des transports urbains automatiques.
Par la suite il me fut demandé en 1975 par Pierre Gilles de Gennes, nouveau directeur de l’Ecole de Physique et Chimie de la Ville de Paris d’exposer ces réflexions techniques aux élèves ingénieurs de cette École.
Le même séminaire fut proposé aux cadres de la RATP, mais au contraire du TRI ils estimèrent ne pas avoir d’enseignement utile à recevoir de Cytec. Cependant son directeur de l’information Robert Faure, informé de nos études, me fit organiser à la RATP un séminaire sur les files d’attente, en 1975.
J’ai cru naïvement que le personnel de la RATP s’intéressait aux files d’attente d’usagers de ses véhicules : autobus et rames de métro, que des nouveaux moyens de transport proposent de réduire.
Mais la plupart des auditeurs étaient des informaticiens : c’était encore l’époque des perforatrices-vérificatrices, des opérateurs qui chargeaient la nuit de lourds disques de programmes à traiter sur ces disques des dinosaures Bull et IBM 360, et les programmeurs s’inquiétaient de la file d’attente… des résultats des programmes en cours de traitement.
Mes exemples d’application ont dû être modifiés pour répondre à cette finalité informatique de l’époque: Steve Jobs et Bill Gates ne s’étaient pas encore manifestés! Internet encore moins! Léonard Kleinrock venait tout juste de publier”Queuing Systems“, où il exposait les principes de la commutation par paquets, à l’origine du réseau Arpanet de transport d’informations, ancêtre du futur Internet.
Je regrettais de n’avoir pu exposer, à des auditeurs professionnels, l’étude originale du Temps d’attente dans les transports urbains en commun que j’avais préparée: reproduite ici sous ce titre[1]; publiée par la suite en 1976 dans la Revue d’Automatique, Informatique et Recherche Opérationnelle : l’idée de cette étude m’avait été inspirée en partie par le travail de Kleinrock, adapté au transport de personnes, mutatis mutandis, résumé ci-après.
La commutation par paquets est le remplacement de l’information à transmettre sur un réseau de stations, par des paquets (de 1024 octets) obtenus en découpant cette information, acheminés vers celle de destination à travers des stations hosts disponibles pour recevoir le paquet sans attente, et munis d’adresses pour y permettre la reconstitution de l’information à l’arrivée. Ces paquets réels sont acheminés sur un circuit virtuel, adapté au message.
J’ai proposé de commuter un véhicule d’un réseau de transport : autobus ou rame de métro, en le découpant en “places” à transporter, avec attente, ces places étant, dans chaque station: des sièges occupés par une usager en transit ; ou vidés par un usager descendant à la station; ou utilisés par un usager de la file d’attente montant de la station; ou des sièges restant vides; et aux heures de pointe, des places supplémentaires, formées par les centimètres carrés occupés par les pieds de chaque usager arrivant à monter dans le véhicule! Ces places virtuelles (le véhicule n’est pas découpé!) sont acheminées sur un circuit réel: le réseau de transport.
La reconstitution du véhicule à la station terminale correspondait alors à l’opération mathématique de convolution de ce flux de “places”.
Le temps d’attente d’un autobus ou d’une rame de métro par un usager arrivant au hasard a tout de même été au moins évoqué à ma demande. Deux conceptions du hasard furent confrontées.
Les véhicules se suivent à des intervalles de temps aléatoires sans influence les uns sur les autres et sans influence de l’instant t à laquelle l’usager arrive «au hasard» sans information sur les véhicules quand il n’y a pas d’horaire affiché.
On m’a assuré que l’usager attendait le demi-intervalle (son espérance mathématique) entre deux véhicules, pour des raisons de symétrie. J’ai avancé un raisonnement simple expliquant que c’était l’espérance de l’intervalle entier : les intervalles successifs sont indépendants, n’ont pas de mémoire, et ne dépendent pas du tout de l’instant t; leur espérance non plus. On me répondit que ce temps d’attente avait été mesuré expérimentalement à Birmingham, que c’était évidemment le demi-intervalle,… à multiplier d’après la mesure par un coefficient correctif : 1,91! C’était donc bien l’intervalle entier à 4% près.
En fait, on commence par évaluer le temps d’attente d’un usager arrivant à une heure précise t : disons 8h 47 pile, 9h, 11h 44, etc.
Si (n-1) véhicules sont déjà passés, et que cet usager attend le n-ème, il n’arrive pas dans n’importe quel intervalle au hasard, mais dans le n-ème, tel que la somme des (n-1) premiers intervalles soit inférieure à t et que la somme de n intervalles soit égale ou supérieure à t, et c’est l’espérance de ce n-ème-là qui importe. En calcul des probabilités il s’agit d’un processus stochastique de renouvellement[2].
Le calcul, plutôt complexe, montre que l’espérance de l’intervalle d’arrivée satisfaisant à la contrainte de contenir un instant t fixé à l’avance est le double de l’espérance de l’intervalle entre véhicules sans cette contrainte : intuitivement, un intervalle long a plus de chances de contenir l’usager et l’arrivée du véhicule qu’il va prendre qu’un intervalle court, qui a davantage de chances de se trouver ailleurs.
Finalement le temps d’attente théorique de l’usager qui arrive au hasard, et non à une heure fixée, est bien la moitié de ce double en moyenne ! Et il est le double de la moitié à 4% près selon l’évaluation expérimentale de Birmingham! Accord malgré tout entre la théorie et les mesures : la morale est sauve, et le mythe du demi-intervalle peut perdurer… Il aura été l’objet d’une illusion créatrice dans le domaine des files d’attente, d’un bon exemple du « temps qui est invention ou qui n’est rien du tout » de Bergson.
Pourrait-on imaginer un service de transport où le temps d’attente soit vraiment le demi-intervalle « moyen » de passage du transporteur, comme le croient les exploitants ? Cela pourrait être le cas si l’exploitant assure un service à horaire annoncé, comme pour le chemin de fer, mais quand l’usager ne connaît pas cet horaire : si l’usager le connaît, son temps d’attente est la latitude qu’il s’accorde pour arriver à la station à temps ; s’il a raté le train, c’est l’intervalle de temps entier jusqu’au passage du train suivant. Mais s’il ne connaît pas l’horaire ?
Lorsque je suis arrivé à Casablanca en 1937, la population était l’objet d’un important exode rural, et au surplus une épidémie de typhus sévissait, dont Albert Camus s’est inspiré pour son roman La Peste, qu’il a située à Oran. Elle n’a pas été grave au point de déclencher une mise en quarantaine de la ville: les communications n’ont pas été interrompues, et la compagnie de chemins de fer devait assurer un trafic assez important de bédouins venant de leur campagne ou y retournant. C’était une population qui comme au Moyen Âge n’avait pas d’autre notion du temps qui passe que la succession des jours et des nuits et les moments où le muezzin appelait les fidèles à l’une des cinq prières obligatoires, selon des critères dont la compagnie des chemins de fer n’avait certainement pas tenu compte. Au surplus il n’y avait pas de minaret dans le voisinage audible de la gare. Les bédouins venaient donc au hasard, guidés par le soleil, sans savoir quand il y avait un train. Il arrivait souvent que le chef de gare leur annonce : — Le train pour Marrakech est déjà parti, revenez demain.
Ils allaient alors s’asseoir dans un coin de la gare avec leurs baluchons, sortaient une théière, un pain de sucre candi, et un réchaud méta, préparaient du thé à la menthe et s’installaient là jusqu’au passage du train suivant.
Dans les exemples précédents le temps d’attente est défini comme temps qui s’écoule entre le moment où l’usager arrive à la station et celui où un véhicule se présente pour le transporter : c’est une relation entre système de transport et usager présent.
Il est intéressant de définir en parallèle une relation de l’usager que nous appellerions son temps disponible : considérons le temps qui s’écoule entre le moment où il n’a plus rien à faire dans l’endroit où il se trouve, et celui où il a quelque chose à faire dans un autre endroit éloigné, desservi par un moyen de transport : le temps disponible hors transport est celui qu’il lui reste si on retranche de ce temps écoulé le temps du transport, le temps d’attente du transport, et les temps terminaux de marche à pied. Il est d’autant plus grand que la fréquence de la desserte est faible. L’usager dispose alors du temps qui reste : pour tailler un crayon, visiter des magasins, lire un livre, préparer un travail, faire l’amour, tuer un ennemi, discuter pour changer le monde, boire du thé à la menthe… ou ne rien faire du tout! comme l’ont recommandé Sénèque (otium, vs negotium: le travail), Paul Lafargue (paresse), Bertrand Russell (oisiveté), et dessiné Kazimir Malévitch (carré noir sur fond blanc)…
Suite => Architectes vs transporteurs
[1 ]Cf. : Temps d’attente dans les transports urbains en commun, in:Problèmes techniques; Recherche Opérationnelle
[2] FELLER W. : An Introduction to Probability Theory and its Applications, Wiley N.Y. 1966 II pp. 12-13
