Projet 8 : Enrichissement du site Internet ALBIBUS par une

Projet 8 : Enrichissement du site Internet ALBIBUS par une fonction

d’optimisation d’itinéraire

Rapport de projet 3A

Carlet Dimitri Landi Fabien Mannheim Sébastien Moghrabi Xavier Rosières Jean-Philippe

Maître d’ouvrage externe : M. DUBOIS Maître d’ouvrage EMAC : M. OTTON

- Avril 2002 -

Projet 8 Ecole des Mines d’Albi Carmaux Page 2

Remerciements

Nous tenons à remercier Jacques LAMOTHE, enseignant chercheur à l’École des Mines d’Albi Carmaux au centre Génie Industriel. Il nous a aidés à modéliser le problème et nous a conseillé l’algorithme à adopter. Il nous a consacré de nombreuses heures en dehors de son travail pour trouver des solutions aux problèmes rencontrés.

Nous souhaitons également remercier notre maître d’ouvrage interne, Emmanuel OTTON. En tant que responsable du service informatique de l’École des Mines d’Albi Carmaux, il nous a conseillés lorsque nous avions des problèmes d’ordre technique

Finalement, nous remercions le directeur d’ALBIBUS, Philippe DUBOIS qui a été notre maître d’ouvrage externe. Il a suivi notre projet attentivement et était toujours disponible pour répondre à nos questions. Nous le remercions également pour le choix du sujet qui nous a beaucoup intéressés.


Résumé

La mise en place d’une application d’optimisation d’itinéraire sur le site Internet d’ALBIBUS suppose d’être informé sur l’état de l’art dans ce domaine. L’implantation d’un Système d’Information Géographique représente un investissement important et aucun logiciel SIG du marché ne permet de résoudre directement notre problème.

Des sociétés spécialisées ont pour leur part développé de telles applications, mais celles-ci sont protégées par les grands groupes de transport de personnes qui les mettent en œuvre. La seule solution de sous-traitance concerne les agences web et les SSII que nous avons contactées et dont les offres ont été étudiées techniquement et économiquement.

Parallèlement, une étude technique du problème a été réalisée pour permettre le développement de l’application en interne. Reprenant des notions de théorie des graphes et de recherche opérationnelle, l’analyse et la modélisation du réseau de bus ont permis de trouver l’algorithme de chemin le plus court approprié. Après une phase de tests, celui-ci a été traduit dans un langage informatique et associé à une base de données relative aux horaires et arrêts du réseau de bus réel.


Table des matières

Introduction 7

Partie 1 : Rapport d’action 8

1. Présentation et spécificité du projet 8

1.1 Contexte 8

1.1.1 Présentation d’ALBIBUS 8

1.1.2 Le site Internet réalisé par un stagiaire de l’école 8

1.2 Problématique et enjeux du projet et de sa continuation 8

1.3 Objectifs du projet 9

1.3.1 Définition des objectifs 9

1.3.2 Appels à variantes 9

2. Les conclusions 10

3. Justification 11

3.1 Recherche de savoir-faire et de réalisations dans les autres sites de transports 11

3.2 Organisation du projet et choix stratégiques 11

3.2.1 Développement interne de l'application 11

3.2.2 Travail avec des sous-traitants 12

3.2.2.1 Les groupes spécialisés dans les sociétés de transports 12

3.2.2.2 Les SSII et les agences Web 12

4. Suite à donner au projet 13

5. Rappel de la démarche 14

5.1 Actualisation du cahier des charges 14

5.2 Délimitation des objectifs opérationnels 14

5.3 Répartition des tâches 14

5.4 Planification des tâches 14

5.5 Succès et échecs 14


Partie 2 : Rapport d’étude 15

1. Recherche d’informations et identification des solutions existantes 15

1.1 Etude des logiciels SIG/Optimisation du marché 15

1.1.1 Le marché des SIG 15

1.1.2 Les principaux logiciels du marché 16

1.2 Sites Internet existants 17

1.3 Sociétés réalisant des solutions adaptées 19

1.3.1 SYNOPTIS 19

1.3.2 PTV ONLINE 19

1.3.3 XUAN 20

1.4 Groupes de transports de personnes 20

1.4.1 KEOLIS 21

1.4.2 TRANSDEV 21

1.4.3 CONNEX (ex: CGEA-CGFTE) 22

2. Recours à la sous-traitance 22

2.1 Introduction 22

2.2 ALBIBUS : une régie municipale 23

2.3 Classification des activités informatiques : quel domaine d’activité ? 24

2.4 SSII ou agence Web : quel type d’entreprise ? 25

2.5 Comparaison des services proposés 26

2.5.1 La société WZ Conseil 26

2.5.1.1 Présentation de la société 26

2.5.1.2 Étude des compétences 26

2.5.1.3 Devis 26

2.5.2 L’agence web o10c 27

2.5.2.1 Présentation de la société 27

2.5.2.2 Étude des compétences 27

2.5.2.3 Devis 27

2.6 Caractéristiques du service exigé et étude financière 28

3. Le développement en interne 30

3.1 Présentation du problème 30

3.2 Utilisation de l’algorithme de Dijkstra 31

3.2.1 Définition d’un graphe orienté 31

3.2.2 Le problème du chemin le plus court 31

3.2.3 Principe de l’algorithme de Dijkstra 32

3.2.4 Procédure 32


3.2.5 Preuve de l’algorithme de Dijkstra 33

3.3 Traduction de l’algorithme dans un langage informatique 34

3.3.1 Explications sur le programme 34

3.3.2 Test du programme 35

3.4 Adaptation de l’algorithme au réseau ALBIBUS 36

3.4.1 Création d’une base de données 36

3.4.2 Création de la matrice associée au réseau d’ALBIBUS 38

3.4.3 Création du programme 39

3.4.4 Les difficultés rencontrées lors de la phase de programmation 40

4. Démarche projet 41

4.1 Objet de l’étude et cadre du projet : 41

4.2 La prise en compte des risques 42

4.2.1 Cas du projet développé en interne 42

4.2.2 Cas de l’appel à la sous-traitance 42

4.3 L’organisation du projet 43

4.3.1 Les acteurs 43

4.3.1.1 Les maîtres d’ouvrage : 43

4.3.1.2 L’équipe projet de l’École des Mines d’Albi : 43

4.3.1.3 Les experts 43

4.3.2 L’organisation 43

4.3.2.1 Organigramme des tâches : 43

4.3.2.2 Planning du projet : le Gantt et le Pert 44

4.3.2.3 Le diagramme des ressources 44

4.3.2.4 Les tâches transversales du projet 44

4.3.2.5 Tâches spécifiques du projet 50

4.3.2.6 Gestion des points "durs" 54

4.3.3 Gestion de la documentation 55

4.3.3.1 Les différents types de documents 55

4.3.3.2 Codification des documents 56

4.3.3.3 Classement des documents 56

Conclusion 57

Bibliographie 58

Table des illustrations 59

Annexes 60


Introduction

Depuis quelques années, les progrès en matière de SIG (Systèmes d’Information Géographique) ont permis l’apparition d’applications d’optimisation d’itinéraire sur les sites Internet des grandes sociétés de transports (SNCF,RATP). L’usager internaute peut déterminer à partir d’un point de départ et d’un point d’arrivée, le trajet le plus rapide entre ces deux points. L’implantation d’une telle application a deux objectifs principaux : tout d’abord permettre à l’usager d’accéder à un service pratique supplémentaire, mais aussi de renforcer l’image novatrice des sociétés qui mettent en œuvre de telles applications.

A ALBIBUS , la volonté est forte d’utiliser les nouvelles technologies, Internet en particulier, pour renouveler l’image des transports de bus albigeois en mettant en place de nouveaux services pour l’usager. Après la création du site Internet d’ALBIBUS par l’intermédiaire d’un stagiaire de l’EMAC, M. DUBOIS, directeur de cette régie municipale fait de nouveau appel à l’école afin de voir s’il serait possible d’intégrer une application d’optimisation d’itinéraire au site existant.

Pour appréhender efficacement le sujet du projet et être informé sur l’état de l’art dans ce domaine, une recherche d’informations était nécessaire. De plus, sachant que nos capacités en informatique et le temps imparti étaient limités, il était prévu de rechercher d’éventuels sous-traitants afin d’obtenir une idée du coût d’une telle prestation. En parallèle, il a été choisi d’affecter deux personnes du groupe projet à l’étude technique et au développement interne de l’application.


Partie 1 : Rapport d’action

1. Présentation et spécificité du projet

1.1 Contexte

1.1.1 Présentation d’ALBIBUS

La régie municipale ALBIBUS, dirigée par la mairie d’Albi, gère les transports en commun de cette ville. Elle met à la disposition des habitants 22 autobus organisés en un réseau de 6 lignes. Celles-ci, réparties sur la ville, disposent de plus de 200 arrêts, visant à assurer au mieux le transport de ses usagers. ALBIBUS est représenté par son directeur, Monsieur Philippe DUBOIS.

La régie est composée de 51 employés dont 36 conducteurs et 5 agents d’ambiance qui renseignent et conseillent les voyageurs. La municipalité estime desservir 1 500 000 clients chaque année. Elle s’est également engagée dans une voie écologique puisque ses autobus roulent actuellement au diester. Son utilisation permet une réduction allant jusqu’à 30% de certains polluants.

1.1.2 Le site Internet réalisé par un stagiaire de l’école

Un stagiaire de l’EMAC a réalisé, pendant l’été 2001, le site Internet d’ALBIBUS . Ce dernier a été ouvert vers la Toussaint. Il semble avoir été conçu, originellement, dans un but purement informatif (renseignement sur ALBIBUS, les horaires de bus, les tarifs des billets…). Une page du site contient les horaires de passage d’un bus aux différents arrêts suivant la ligne sélectionnée. Une analyse du site Internet a été réalisée et se trouve en annexe 1. Le site se trouve à l’adresse Internet suivante : http://www.albibus.com.

1.2 Problématique et enjeux du projet et de sa continuation

La consultation du site ALBIBUS ne justifie pas forcément à elle seule un investissement dans un projet de développement de leur site Internet.

Pourtant, ALBIBUS souhaite enrichir son site par une application d'optimisation de trajet. Cette application aura pour but d’aider l’usager dans sa planification d’itinéraire. Mais au-delà de cet aspect pratique, ALBIBUS espère en étoffant son site Internet améliorer son image auprès de ses usagers et promouvoir un certain dynamisme dans leur activité. Le site actuel pouvant être largement modifié, il sera donc important de tenir compte dans le projet de l'aspect esthétique et attractif du site.

Par le renforcement de sa volonté de communication sur Internet, ALBIBUS cherche aussi à créer un impact séduisant sur un public sensible aux nouvelles technologies


de l'information. Il faudra donc que l'application soit simple d'utilisation avec une interface conviviale. Rentrer dans la dimension des nouvelles technologies de l'information permettra peut être à ALBIBUS d’attirer un public plus large et de plus en plus exigeant quant à la qualité de la prestation.

De plus Monsieur DUBOIS, pour la commune d'Albi, travaille sur un projet de pôle multimodal. Il s'agit d'une structure qui permettrait la collaboration de toutes les sociétés et régies de transports d'Albi. Son objectif serait de gérer plus efficacement les différents réseaux de transports et d'harmoniser leur complémentarité pour proposer aux usager un service optimal.

Ainsi le projet d'optimisation d'itinéraire, réalisé pour le site d'ALBIBUS , pourrait aussi servir de test grandeur nature pour une application future concernant ce pôle multimodal qui aura vraisemblablement des moyens budgétaires plus conséquents.

1.3 Objectifs du projet

1.3.1 Définition des objectifs

Le projet consiste donc à enrichir le site déjà existant de la manière fonctionnelle suivante :

• Le consultant du site saisit son point de montée (par un clic sur un plan) et son point de descente.

• Il saisit la date et l’heure de départ, par un clic sur un calendrier

• Le systèmes répond en donnant le parcours optimisé (la ligne, les arrêts) et les horaires les plus proches avec les correspondances.

Pour cela, le projet a consisté à identifier dans un premier temps un algorithme mathématique d'optimisation qui permettrait de résoudre ce problème de « chemin le plus rapide ».

Dans un deuxième temps, il fallait traduire cet algorithme en une application sur Internet dans le langage le plus approprié pour répondre aux exigences fixées.

1.3.2 Appels à variantes

Compte tenu de la relative complexité d’un tel algorithme et de sa traduction informatique, une recherche parallèle des applications existantes en la matière a été préalablement effectuée.

On a donc effectué des recherches (sur Internet, puisque c’est le support qui nous intéresse) sur les sites qui proposent des services de calcul de parcours. Ceci dans le but de contacter leurs concepteurs de manière à réaliser une étude de faisabilité sur le recours à la sous-traitance.

On s'est vite aperçu lors de la phase développement que l'on n’aurait ni les compétences ni le temps nécessaire pour mener à bien ce projet, avec seulement des ressources internes. En parallèle du travail de développement interne, on a donc effectué un travail d'identification de sous-traitants.


Ce travail a consisté à rechercher :

• dans les sites Internet des réseaux de transports français ou étrangers

• dans les logiciels d’optimisation de parcours tels que MICHELIN, ITI…

Si la recherche a donné des éléments exploitables, l’étude concernera :

• l’analyse de ces éléments

• l’intégration au site Internet pour offrir une fonctionnalité d’optimisation de parcours

2. Les conclusions

• Les systèmes d’Information Géographique classiques ne répondent pas exactement aux exigences du projet et présentent d’ailleurs un prix de revient rédhibitoire (prix de la licence de 1,5 à 10 k�). Il est nécessaire de rechercher des applications ou des logiciels plus appropriés à l’optimisation de trajet.

• Concernant la sous-traitance, on ne peut pas faire appel aux grands groupes de transports tels que KEOLIS et la RATP. Ces derniers détiennent en effet la propriété exclusive des applications Internet d’optimisation de parcours pour d’autres sites de transports développés par des entreprises comme XUAN ou PTV ONLINE.

• La sous-traitance reste possible en faisant appel aux SSII ou agences web. Pour cela nous avons recherché des entreprises basées dans le Tarn afin de pouvoir les rencontrer et faciliter les futurs contacts avec ALBIBUS. Cette solution permettrait de mettre en place une maintenance effective, chose impossible pour une solution exclusivement développée en interne. Dans cette optique nous avons identifié deux candidats principaux situés sur Albi : WZ CONSEIL et o10c.

• Le développement en interne nous a permis d’identifier les principales difficultés techniques du projet et donc de préciser les exigences du CDCF. Grâce à cette analyse, nous avons pu estimer le coût horaire du développement d’une telle application et ainsi évaluer la pertinence des offres des sociétés contactées. Malgré les difficultés techniques et les contraintes horaires nous sommes parvenus, avec l’aide de notre maître d’ouvrage interne et d’un enseignant chercheur du centre génie industriel, à élaborer un moteur de calcul qui fonctionne.


3. Justification

3.1 Recherche de savoir-faire et de réalisations dans les autres sites de transports

L'intitulé du sujet de ce projet proposait tout d'abord de regarder l'état du savoir faire pour l'application Internet considérée, dans les autres sites de sociétés ou de régies de transports. Toute l'équipe s'est donc mobilisée autour des directives de notre maître d'ouvrage, M OTTON, pour faire une synthèse large mais précise de ce qui avait été réalisé sur d'autres sites. Cette recherche nous a permis tout d'abord de dégager certains noms de groupes ou d'entreprises qui ont des compétences dans l'optimisation d'itinéraire ( MAPPY, MICHELIN, TRANDEV, SNCF, …). Très vite on s'est aperçu que les logiciels commerciaux très généraux comme celui développé par MICHELIN ou MAPPY ne nous seraient pas très utiles. En effet, ces logiciels restent beaucoup trop difficiles à adapter à une application telle qu'elle est désirée chez ALBIBUS. Ils n'ont pas pour vocation de servir d'optimiser de tournées pour des lignes de bus. Beaucoup plus commerciaux et grand public, ils ne peuvent pas contribuer efficacement au développement de notre projet. De plus il était bien entendu impossible de se procurer les programmes sources pour les adapter au projet et très peu offraient une possibilité d'utilisation de licence (MAPPY). Enfin le budget potentiellement allouable à ce projet par ALBIBUS (� 8000�) ne correspondrait pas du tout au coût engendré par la collaboration avec l’un de ces grands groupes pour l'utilisation de leur logiciel.

Cependant, grâces à des requêtes sur des forums et à l'étude du site de La Roche- sur-Yon, on a réussi à isoler quelques partenaires potentiels, ayant réalisé auparavant des applications très similaires à celle demandée par ALBIBUS. Ce fût surtout le cas de KEOLIS, maître d'œuvre du site de la Roche-sur-Yon.

3.2 Organisation du projet et choix stratégiques

Après l'identification des groupes comme Kéolis et Connex on a décidé, en accord avec les maîtres d'ouvrage, de poursuivre en parallèle deux pistes de travail pour notre projet. La première consistait à commencer l'application Internet par nous- mêmes. La seconde proposait de continuer à développer les contacts avec les groupes qui nous paraissaient intéressants. Précisons ces deux pistes.

3.2.1 Développement interne de l'application

Le travail a débuté par une modélisation très simplifiée du problème grâce à la théorie des graphes et par l'établissement (en collaboration avec M. LAMOTHE du centre GI) d'un algorithme d'optimisation basé sur celui de Dijsktra. Après avoir été testé "à la main", cet algorithme à été traduit dans un langage informatique pour s’assurer de son bon fonctionnement grâce à une série de tests et de démonstrations.

Cette recherche de solution en interne nous a conduit à l'identification de certains problèmes techniques non remarquables a priori mais pourtant assez restrictifs. La prise en compte de l'évolution des fréquences de passage des bus en est un bon


exemple. De plus, on a aussi pu identifier de nouvelles contraintes à respecter (ex : extraction de données de feuilles Excel pour remplir la base de données nécessaire à l'application). Cette démarche nous a permis de connaître les détails techniques de l'application que l'on souhaite réaliser et donc d'être plus précis dans les exigences répertoriées dans le cahier des charges adressé à d'éventuels sous-traitants. Cette partie technique nous a aussi servi à avoir un regard plus critique sur les prestations proposées par les sous-traitants et à mieux évaluer les coûts horaires et donc financiers engendrés par le développement de ce projet.

A ce stade du développement interne, il nous est paru judicieux de privilégier la piste des sous-traitants menée en parallèle. En effet, le temps imparti étant trop court, le travail technique trop complexe et surtout à cause de contraintes fortes comme la maintenance de l'application et du site d'ALBIBUS, la solution de la sous-traitance s'est imposée d'elle même.

3.2.2 Travail avec des sous-traitants

L'idée était de contacter les sous-traitants ayant déjà réalisé de telles applications pour d'autres sites de transports. On a décidé d'élaborer un cahier des charges précisant les exigences techniques et d'organisation d'ALBIBUS. Dans cette étape on s'est appuyé sur l'analyse du développement interne qui nous a permis d'être pertinents dans nos exigences et de bien expliciter le projet dans ses détails. Le cahier des charges nous a servi de base de dialogue avec les différentes entreprises contactées et le travail sur l'algorithmique nous a permis de gagner du temps dans nos négociations.

3.2.2.1 Les groupes spécialisés dans les sociétés de transports

La collaboration éventuelle avec un sous-traitant s'annonçait assez prometteuse. D'un point de vue technique, nous avions trouvé des sous-traitants, qui avaient déjà réalisé de telles applications pour le réseau de bus d'autres communes. Leur savoir-faire satisfaisant entièrement nos exigences techniques, nous avons donc décidé de concentrer une grande partie de nos efforts sur les contacts de ces entreprises et la demande d'un premier devis.

Cependant, ces contacts se sont révélés quelque peu décevants car ces groupes spécialisés dans de telles applications comme KEOLIS ne s'intéressent pas à la seule création d'application Internet, ils préfèrent gérer le système de transport dans son ensemble. En effet ces groupes ne sont pas seulement des groupes spécialisés dans les applications Internet pour les sites de transports. Ils prennent en charge tous les organes de gestion des moyens de transports et se substituent entièrement à la régie ou au service municipal qui en avait la responsabilité (cas de La Roche-sur-Yon). D'autre part, la RATP, sans surprise, nous a expliqué que l’application très complexe gérant leurs réseaux de transports était le résultat d'années de développement et ne pouvait être commercialisée. Cette application a été réalisée pour leur utilisation exclusive.

3.2.2.2 Les SSII et les agences Web

Après notre échec dans le domaine de la sous-traitance auprès des groupes spécialisés dans les sociétés de transport, nous nous sommes tournés vers des


entreprises beaucoup plus adaptables et souples dans leurs activités. On a essayé de lister les SSII et les agences Web pour pouvoir les contacter de manière efficace.

Tout d'abord, la différence entre ces deux types d'entreprise mérite d'être explicitée. La SSII est une entreprise spécialisée le plus souvent dans le conseil informatique, mais surtout pour des applications ou des logiciels autour de projets demandés par leurs clients. L’agence Web est plutôt orientée vers du développement de sites Internet mais fondamentalement moins tournée vers le développement d'application.

Pour notre application Internet, les compétences requises se situaient à l'intersection de ces deux types d'entreprise. De plus, d'un point de vue budgétaire, les agences Web offraient des prestations de coût moins élevé que les SSII et se montrent souvent très adaptables au besoin du client. Notre recherche s'est donc orientée vers une agence Web ayant des capacités de développement d'application d'optimisation à partir d'un algorithme et d'un travail sur le "state of the art" de ce type d'application. Ce travail d'algorithmique et de recherche étant réalisé par nos soins, dans la partie développement interne du projet, cela permettait de faciliter le travail de l'entreprise contactée et d'alléger le volume horaire consacré. Malgré notre travail, de telles agences Web n'étaient pas si courantes surtout lorsqu'on cherchait dans la zone d'activité tarnaise. Voulant privilégier une recherche d'un sous-traitant proche géographiquement pour faciliter les contacts et le futur partenariat, nous avons contacté la plupart des SSII et agences Web du Tarn. Peu avaient la capacité ou les moyens de réaliser notre application mais parmi ces contacts, deux noms d’agences Web se sont dégagés, celui de la société WZ Conseil et celle de 010C Informatique. Ces deux sociétés se proposaient de réaliser l'application demandée. On a donc comparé les offres et regardé de plus près la situation financière et structurelle de ces entreprises.

4. Suite à donner au projet

A l’issu de notre projet et vu l’état d’avancement du développement interne, nous avons pensé à deux possibilités pour poursuivre et terminer ce projet :

• Développer les contacts avec les SSII et les agences Web pour aboutir à finalisation de l’application et à sa maintenance.

• Proposer à ALBIBUS de prendre un stagiaire de l’Ecole qui pourrait achever le développement. Le moteur de recherche du logiciel étant déjà réalisé, il ne lui restera qu’à le tester entièrement pour en corriger les éventuels bogues puis à créer l’interface entre l’application et le site Internet. Ce stagiaire pourra dans un second temps automatiser la procédure de mise à jour de la base de données des horaires de bus.


5. Rappel de la démarche

5.1 Actualisation du cahier des charges

Afin de définir des conditions claires d’avancement de notre projet, nous avons dû fixer la date butoir du 7 janvier afin de signer un cahier des charges. Il fallait absolument fixer des objectifs précis en termes de caractéristiques de l’application que celle-ci soit développée en interne ou acheté à un tiers.

5.2 Délimitation des objectifs opérationnels

Le projet était constitué de deux phases effectuées en parallèle :

1. La recherche de logiciels ou sous-traitants pouvant répondre à nos attentes, avec d’éventuelles négociations de devis voire même une émission d’un appel d’offres.

2. Le développement interne d‘une application répondant aux conditions de calculs d’itinéraires optimisés sur un réseau de bus. Le développement aurait dû aboutir à une mise en place sur le site Web d’ALBIBUS afin d’en permettre l’accès au public.

Etant donné que le problème était délicat nous avons demandé de l’aide extérieure, en la personne de M. LAMOTHE.

5.3 Répartition des tâches

Deux grandes voies de recherches nous étaient ouvertes, nous nous sommes donc répartis les tâches en deux groupes distincts. L’un s’attachant à la recherche de sous-traitants et de logiciels existant, l’autre au développement interne de l’application.

5.4 Planification des tâches

Nous avons planifié les tâches dès le 17 décembre 2001. Nous avons décidé de remettre à jour cette planification tous les mois afin de recentrer nos activités en fonctions des avancées et problèmes rencontrés. Ainsi d’un planning à l’autre de nombreuses tâches ont été amenées à disparaître ou à se décaler dans le temps en fonction de nouveaux impératifs.

5.5 Succès et échecs

La recherche de sous-traitants ou de logiciels existants est restée infructueuse ou très coûteuse. Ce travail peut être considéré comme un échec car de nombreuses ressources ont été concentrées sans résultats effectifs. Cependant malgré de nombreux problèmes techniques le développement interne a finalement abouti à une version d’évaluation répondant partiellement aux attentes d’ALBIBUS.


Partie 2 : Rapport d’étude

1. Recherche d’informations et identification des solutions existantes

Parallèlement à l’étude technique et au développement interne, il nous paraissait nécessaire de nous informer sur les solutions existantes en la matière. La recherche, qui s’est effectuée en majeure partie sur Internet, a visé tout d’abord les logiciels SIG (Systèmes d’Information Géographique) et d’optimisation de parcours, puis les sites Internet des réseaux de transport français et étrangers.

1.1 Etude des logiciels SIG/Optimisation du marché

Au fil des recherches, il est apparu qu’aucune solution logicielle commerciale ne répondait spécifiquement à notre problème. En effet, les logiciels du marché ne concernent pas seulement l’optimisation de parcours, mais permettent de couvrir des besoins bien plus étendus et trouvent des applications dans les collectivités locales, l'environnement, la gestion des ressources naturelles, la cartographie, les compagnies pétrolières et forestières, au sein des ministères et dans les entreprises (Réseaux, Télécom, Distribution, Commerce, Banque, Assurance, Industrie…) et le secteur de la Défense.

1.1.1 Le marché des SIG

Le marché mondial des SIG (part logicielle) représente un montant de 939 Millions de dollars. Le domaine le plus important en matière de SIG est le marché des Collectivités Locales (20%), suivi de près par ceux des Télécommunications et des Réseaux. Avec 36 % de parts de marché, ESRI est classé premier éditeur mondial des Systèmes d'Information Géographique. (chiffres 2000) (cf Figure 1).


Figure 1 : Parts de marché de chaque éditeur de SIG Source : DARATECH,"Geographic Information Systems Markets and Opportunities 2001"

1.1.2 Les principaux logiciels du marché

L'offre actuelle en matière de SIG est très fournie et il est difficile de se faire une opinion sur l'adéquation entre un logiciel et une application à mettre en place. Les logiciels existant sur le marché ont des spécificités et des utilisations différentes. Voici la description des logiciels les plus utilisés :

• ArcInfo

ArcInfo est le produit phare d’ESRI. Il combine de manière unique les possibilités cartographiques des outils traditionnels avec des possibilités très puissantes d’analyse construites autour d’un système de gestion de base de données. Arc/Info dispose d’un choix étendu de fonctions d’analyse de données géographiques. Il s’agit de l’outil le plus utilisé dans les problématiques environnementales avides d’analyses d’informations spatiales.

• MGE

MGE est une solution géoinformatique complète avec plus de 50 composants logiciels individuels. MGE permet l’acquisition, l’analyse de données spatiales, le traitement d’images, pour la photogrammétrie et la publication de cartes. En plus, MGE propose une très grande variété d’utilitaires pour incorporer des données de types différents dans un environnement unique. Ce produit est certainement le plus puissant et le plus complet du marché avec ArcInfo.

• MapInfo

MapInfo Professionnel (350 000 licences au niveau mondial) est l’outil phare de la société qui propose une gamme de produits assez étendue. Il s’agit d’un outil simple, puissant et flexible pour la visualisation de données, l’analyse thématique et la représentation de données sous forme de graphiques, de tables ou de cartes. Il


s’agit certainement du logiciel qui est le mieux intégré dans un environnement bureautique. MapInfo a développé les possibilités cartographiques du logiciel Excel de Microsoft. Très bon rapport qualité-prix.

• ArcView�

ArcView (500 000 licences au niveau mondial) est un logiciel qui a connu un développement et un succès très important. L’objectif initial était de fournir un outil de visualisation simple et convivial de données gérées par ArcInfo. La version actuelle est beaucoup plus qu’un simple outil de visualisation. Il s’agit d’une solution complète qui est un concurrent de logiciels comme MapInfo ou Atlas GIS. On dispose d’un panel complet de fonctions d’analyse thématique, de représentation, de stockage et d’acquisition de données. La mise en place de Systèmes d'Information Géographique (SIG) représente généralement un investissement considérable, pour lequel les éléments économiques doivent être connus et maîtrisés. Le prix des licences (de 1.5 à 10k�) est rédhibitoire dans le cadre d’ALBIBUS , d’autant plus que l’achat d’un tel logiciel ne peut résoudre d’autres problèmes qui nous sont posés comme la mise en ligne sur Internet, l’interfaçage avec le site existant, etc.

D’après les descriptifs des logiciels les moins chers (MapInfo et Arcview), ils ne semblaient pas adaptés au besoin actuel et futur d’ALBIBUS . En effet, ils sont avant tout destinés à résoudre des problèmes de cartographie.

Cette recherche n’ayant pas été fructueuse en termes de briques logicielles utilisables, nous nous sommes dirigés vers les sites Internet de communes et de sociétés de transport proposant des solutions analogues à celle dont voudrait s’équiper la régie municipale ALBIBUS.

1.2 Sites Internet existants

L’exemple le plus proche de l’application envisagée par ALBIBUS est mis à disposition des usagers de transports en commun de la Roche sur Yon :

L’interface est la même que celle qu’ALBIBUS voudrait mettre en place, avec la possibilité de choisir les points de départ et d’arrivée au choix en tapant l’adresse directement ou en cliquant sur un plan. (cf Figures 2 et 3)

De même, sur le site de la RATP, l’application qui nous intéresse est disponible, et l’interface est sensiblement la même. Nous avons donc décidé d’utiliser tous les contacts mis à disposition sur les sites visités. Nous demandions des informations au sujet de la réalisation de l’application et d’un partenariat éventuel avec ALBIBUS. Malheureusement, nos interlocuteurs nous ont fait comprendre qu’ils n’étaient évidemment pas enclins à divulguer des informations sur des projets de cette envergure, destinés tout d’abord à mettre à disposition des usagers un service pratique, mais aussi à donner une image novatrice des sociétés qui les ont développées.


Figure 2 : Interface de saisie utilisateur du site sty.fr Source : www.sty.fr

Figure 3 : Outil de cartographie du stie sty.fr Source : www.sty.fr

Comme il était impossible d’en savoir plus en contactant les webmasters des sites ou les personnes ayant travaillé sur les projets, nous avons du chercher des informations plus en amont. Nous avons par conséquent contacté des sociétés de Conseil et de Développement informatique dont nous avions trouvé les coordonnées sur le site de la Roche sur Yon. Nous avons également effectué une recherche par mots clés afin de cibler des spécialistes de l’optimisation d’itinéraire et de la cartographie.


1.3 Sociétés réalisant des solutions adaptées

Nous avons donc réalisé une recherche Internet permettant de trouver les contacts de sociétés de Conseil et Développement spécialisées dans l’informatique pour l’optimisation de tournées et d’itinéraires. Trois sociétés intéressantes ont émergé : SYNOPTIS, PTV ONLINE et XUAN. Nous les avons contactées afin d’avoir un aperçu de leurs domaines de compétence et dans l’idée d’obtenir une étude de prix détaillée.

1.3.1 SYNOPTIS

Née en 1998, la société SYNOPTIS s’est spécialisée dans le développement d’applications informatiques spécifiques à l’optimisation de tournées. Le logiciel standard qu’ils développent ne correspond pas tout à fait au besoin d’ALBIBUS et dispose de fonctionnalités qui ne nous intéressent pas.

Au téléphone, le Directeur technique semblait intéressé par le projet et envisageait de réaliser une étude de prix au vu des exigences de notre cahier des charges. Cette étude prendrait en compte le prix du logiciel allégé des fonctionnalités en surplus et celui de la licence Internet. Cependant une solution intermédiaire fut envisagée, où l’un des membres du groupe projet pourrait effectuer son stage au sein de SYNOPTIS, et ainsi avancer une partie du projet à moindre coût.

L’étude de prix posa finalement problème car ayant compris que le choix d’un sous-traitant éventuel se ferait par appel d’offres, l’étude de prix détaillée serait réservée au dossier qu’ils rempliraient le cas échéant. De toute façon, après de multiples conversations téléphoniques, M. Fabien Rodes nous fit comprendre que le prix serait supérieur au budget prévu.

1.3.2 PTV ONLINE

Depuis septembre 2000, la société PTV ONLINE est quant à elle spécialisée dans les métiers liés à la cartographie et au calcul d’itinéraires sur la base de cartes routières numériques.

Nous avons été en contact avec M. Jerome Pernollet qui a tout de suite précisé que PTV n’assurait pas la commercialisation de ses produits, laquelle est gérée par une filiale allemande. Ses clients sont purement technologiques (automotive principalement).

La création de l’application a paru envisageable aux yeux de notre contact même s’il nous a précisé que leur préférence allait aux marchés privés pour des raisons de délais de paiement. Comme avec SYNOPTIS, la perspective de travailler en collaboration avec un stagiaire de l’EMAC leur paraissait tout à fait envisageable.

Techniquement, M. Pernollet nous a fait part de possibilités qui pourraient s’avérer intéressantes pour ALBIBUS. Tout d’abord, l’application pourrait fonctionner de manière multimodale, c’est à dire qu’il est possible de prendre en compte, lors de l’optimisation, la correspondance avec d’autres moyens de transports (train, marche à pied, etc…). Cette possibilité n’est peut-être pas cruciale pour le travail qui nous est demandé, mais pourrait gagner de l’importance dans le cadre des Centrales de Mobilités et Du Pôle multimodal dont nous a parlé M. DUBOIS. Ensuite, il y aurait


des possibilités de « flipmonitoring » : l’évolution du parc de bus pourrait être observée en temps réel sur une carte du réseau.

Incapables de donner un prix approximatif, nous avons envoyé à leur demande un mail avec en fichiers attachés le cahier des charges du projet, les délais et les recommandations qui nous ont été remises par ALBIBUS. Le dossier a normalement été transmis à la société allemande assurant la commercialisation des produits de PTV ONLINE, mais aucune réponse de leur part ne nous est parvenue.

La société PTV a réalisé l’application d’optimisation de trajet figurant sur le site de la compagnie des trains allemands : www.Dbahn.de .

1.3.3 XUAN

Nous avons contacté M. Guillaume Crouigneau qui nous a aussitôt redirigé vers KEOLIS qui s’occupe de la commercialisation des outils et des applications que l’entreprise développe.

L’une des applications développées par XUAN nous intéresse plus particulièrement : ObiTi. Ce progiciel destiné aux autorités organisatrices ou aux réseaux de transports permet de gérer l'information horaire et la réservation des transports en communs à l'échelle d'une ville, d'un département ou d'une région. Totalement multimodal, OBiTi sait combiner plusieurs modes de transports pour relier 2 points. Il permet de calculer des itinéraires entre deux points (adresse, lieu remarquable d'une ville, arrêt, etc.). La sélection des points de départ et d'arrivée peut s'effectuer depuis une liste ou depuis un plan. Une fois la date et l'heure choisies pour le déplacement, le calculateur recherche l'ensemble des possibilités de transports possibles pour cette origine-destination.

Malheureusement, ce logiciel est développé en partenariat avec le groupe de transport KEOLIS, filiale de la SNCF, née du rapprochement entre VIA-GTI et CARIANE. KEOLIS en est donc le copropriétaire.

Ceci explique que des sites comme celui de la SNCF ou de villes dont KEOLIS assure l'exploitation et la gestion du service public de transport disposent de cette application d’optimisation d’itinéraire.

On a donc avec XUAN et PTV ONLINE des situations analogues : la commercialisation est assurée par un partenaire qui est aussi copropriétaire de l’application. Etant donné le coût de développement d’une telle application et l’image d’innovation qu’elle véhicule en offrant un service supplémentaire aux usagers, il nous paraissait alors fort probable que le jumelage entre ces sociétés de Conseil et Développement Informatique et des groupes de transports soit scellé par un contrat d’exclusivité. C’est pourquoi nous avons contacté KEOLIS pour essayer d’en savoir plus.

1.4 Groupes de transports de personnes

En général, les entreprises privées qui exploitent les réseaux ne sont pas indépendantes. En France, trois groupes majeurs se partagent en effet plus de 80 % du marché des transports urbains : KEOLIS (40 % des réseaux), TRANSDEV (24 %) et CONNEX (16 %).


1.4.1 KEOLIS

KEOLIS, groupe privé européen, est un opérateur multimodal du secteur du transport de voyageurs, délégataire de service public. Il est né de la fusion entre VIA GTI et CARIANE en avril 2001.

Le groupe KEOLIS en quelques chiffres :

• 21000 salariés

• Chiffre d’Affaires 2001 : 1,51 milliard d'euros

• Capital : 48,7% Paribas Affaires Industrielles

43,5% SNCF Participations

7,8% Vivendi

• KEOLIS est présent dans 9 pays

• 40 % de part de marché pour le secteur urbain (88 agglomérations)

La société XUAN nous a mis en contact avec Aurélie Becqueriot, responsable du marketing à KEOLIS, qui a confirmé nos pressentiments. En effet, la société KEOLIS ne propose pas de systèmes informatiques mais seulement leur mise en œuvre. Seulement, ce service suppose la création d’un contrat avec la collectivité locale et la société de transport. Donc le statut de régie municipale d’ALBIBUS pose problème dans cette optique. KEOLIS sous-traite à XUAN tout le travail de conseil et de développement dans le cas de services à effectuer au sein d’une société de transport d’une collectivité partenaire. Une partie de ses services s’appuie sur des outils propriétaires, comme le logiciel ObiTi, dont KEOLIS a l’exclusivité.

En conclusion, la seule possibilité pour qu’un tel logiciel soit mis à la disposition des usagers d’Albi serait de déléguer la totalité de la gestion des transports en commun à KEOLIS, logique qui est à l’opposé de celle choisie à Albi dont les transports en bus sont gérés par une régie municipale.

1.4.2 TRANSDEV

TRANSDEV (Société Européenne pour le Développement des Transports Publics) a été créée en 1990. TRANSDEV est l'un des trois premiers opérateurs français de transport collectif de voyageurs, soit plus 60 réseaux urbains et 30 réseaux interurbains de tailles diverses.

Les chiffres clés :

• 13 800 personnes

• Chiffre d’affaires 2000 : 0.87 milliard d'euros

• 24 % de part de marché pour le secteur urbain


D’après notre contact à KEOLIS, les réseaux urbains gérés par TRANSDEV risquent de profiter prochainement d’une application analogue, dans la mesure où cette dernière se rapproche de la RATP qui dispose déjà de l’application.

1.4.3 CONNEX (ex: CGEA-CGFTE)

Enfin, dernier groupe de transports susceptible de disposer d’une application du type qui nous intéresse, CONNEX représente la troisième part de marché des transports urbains.

CGEA Transport (Compagnie Générale d'Entreprises Automobiles) est une filiale de Vivendi. CONNEX est la marque commerciale de l'activité transport de CGEA.

D’après le responsable du marketing de KEOLIS, cette société pourrait à l’avenir s’équiper elle aussi d’une application d’optimisation d’itinéraire, d’autant plus que le nombre des réseaux gérés par CONNEX devrait augmenter avec le rachat de VERNEY.

Par la présentation de ces différents groupes de transports, nous comprenons qu’ALBIBUS n’a pas la même position et ne dispose pas du tout des mêmes moyens pour développer une application d’optimisation d’itinéraires. Les partenariats avec de telles sociétés sont exclus du fait du statut de régie municipale d’ALBIBUS, contrairement à ce qui avait été imaginé à priori au commencement de ce projet.

Cette recherche a néanmoins justifié le fonctionnement parallèle entre développement interne et recherche de sous-traitants, permettant d’assurer l’avancement technique du projet malgré l’échec de cette première réflexion. Sur le conseil de notre contact à KEOLIS, nous avons alors entrepris d’orienter notre recherche vers des sociétés de conseil informatique généralistes et des agences Web. La réalisation d’une application destinée à être mise en accès sur Internet se situe en effet à l’interface entre les deux.

2. Recours à la sous-traitance

2.1 Introduction

Comme nous venons de la voir l’adaptation des solutions déjà existantes à notre projet est difficilement envisageable.

D’un autre coté, le développement en interne de l’application est également difficile à envisager pour des raisons principales de maintenance et de faisabilité technique : en effet, nos compétences techniques ne nous auraient sûrement pas permis de développer cette application entièrement dans le temps imparti. Et dans l’éventualité où nous l’aurions développée, nous n’aurions pas pu lui assurer une maintenance et une mise à jour efficaces.

Notre objectif consistait donc à trouver une autre solution pour faire avancer notre projet.


La solution de la sous-traitance n’avait, jusqu’ici, pas fait particulièrement l’objet de notre attention. En effet, nous avions jusqu’alors porté nos efforts dans le développement interne de l’application pour une partie de l’équipe projet et dans la recherche de solutions existantes pour l’autre partie.

Nous avons donc continué le développement en interne de l’application avec pour objectif que le travail technique que nous avions réalisé puisse servir de base à un « futur » sous-traitant.

Le reste de l’équipe a donc entamé une procédure de recherche de sous-traitants1 …

2.2 ALBIBUS : une régie municipale

Avant de détailler la méthode que nous avons mise en œuvre pour la recherche de sous-traitance, il nous a semblé intéressant de rappeler brièvement le contexte un peu spécial de la société ALBIBUS.

ALBIBUS est en fait une régie municipale.

Une régie municipale est administrée sous l’autorité du maire et du conseil municipal par un conseil d’exploitation et un directeur. C’est donc la mairie qui fixe chaque année un budget à la régie.

Lorsque la régie veut effectuer une sous-traitance, elle est soumise aux lois des marchés publics et tout particulièrement aux lois sur les appels d’offres.

« Qu’est ce qu’un appel d’offres ? »

Une régie municipale n’a pas le droit de sous-traiter directement : elle est soumise à une réglementation particulière :

• Elle doit dans un premier temps rédiger un cahier des charges précis.

• Ensuite, elle publie son besoin par l’intermédiaire d’une presse spécialisée : c’est la mise en concurrence.

• Dès lors, toutes les entreprises intéressées par l’avis émis par la régie peuvent se manifester en envoyant une offre (devis, compétences) à cette même régie.

• Au delà d’une certaine période (52 jours dans la plupart des cas), la régie clos la réception des offres et la commission des appels d’offres classe les offres par ordre décroissant : de la plus avantageuse économiquement, à la moins avantageuse, en fonction des critères de compétence des entreprises.

• L’offre la mieux classée est retenue.

On voit clairement que ce schéma interdit formellement à la régie de désigner son sous-traitant : c’est un processus de classification des offres qui désigne la plus avantageuse.

Avant de publier son avis d’appel à la concurrence, la régie n’est donc pas en mesure de savoir à l’avance quelle entreprise sera son sous-traitant.

1 Nous avons distingué les sociétés qui possèdent des solutions déjà existantes des sociétés dites sous-traitantes qui seraient amenées à développer l’application à partir de rien (ou du moins à partir des recherches algorithmique que nous avions déjà effectuée).


Dans le cadre de notre projet, le fait qu’ALBIBUS soit une régie posait le problème suivant : nous devions contacter des entreprises dans le but de leur proposer la sous-traitance du développement de l’application pour obtenir une étude de prix, en sachant pertinemment qu’elles ne seront pas forcément retenues pour la réaliser.

La recherche de la sous-traitance n’a donc pas été réalisée dans le but de trouver le meilleur sous-traitant mais plutôt d’en évaluer la compétence générale ainsi qu’un ordre de grandeur du montant du devis qu’une telle application pourrait coûter.

Nous nous sommes cependant efforcés de réaliser une « grille de comparaison » permettant de comparer les compétences et les devis des différents sous-traitants « potentiels ».

Voyons maintenant plus en détail la méthodologie que nous avons suivis pour trouver des sous-traitants susceptibles d’êtres intéressés par le développement de l’application.

2.3 Classification des activités informatiques : quel domaine d’activité ?

Notre recherche de sous-traitance s’est donc portée sur les sociétés de conseil en informatique. Ci-dessous, nous avons la liste des codes NAF qui correspondent aux sociétés de conseil en informatique.

721Z : Conseil en systèmes informatiques 722Z : Réalisation de logiciels 723Z : Traitement de données 724Z : Activités de banques de données 725Z : Entretien, réparation machines de bureau et matériel informatique 726Z : Autres activités rattachées à l'informatique

Ce sont les 3 premières activités de cette liste qui correspondent le mieux au type de société que nous recherchions. Nos recherches se sont donc principalement portées sur les entreprises représentées par ce code NAF.

Pour des raisons de simplicité et de mobilité, nous nous sommes limités à l’ensemble des entreprises de la région, de manière à avoir la possibilité de pouvoir les rencontrer.

Le lecteur pourra trouver en annexe 2 la liste des entreprises retenues par notre recherche effectuée sur des bases de données CD-ROM ou obtenues par des moteurs de recherches spécialisés d’Internet.


2.4 SSII ou agence Web : quel type d’entreprise ?

Une SSII est une « Société de Service en Ingénierie Informatique ». Son but est principalement de proposer des ingénieurs (en informatique mais aussi en électronique etc.) aux « grands comptes ». « Grand compte » est le nom donné aux grandes entreprises.

En comparaison avec une SSII, une agence Web (Web Agency en Anglais) est une société spécialisée dans le domaine de l’Internet comme son nom l’indique. Elles sont souvent de plus petite taille et leur personnel est en général moins qualifié : le domaine de compétence d’une agence Web est moins étendu que celui d’une SSII.

Dans une SSII il y a généralement des techniciens spécialisés dans les technologies du Web, des infographistes et les personnes chargées du marketing, de la communication …

Dans notre cas, doit-on préférer s’adresser à des Sociétés de Services ou bien une agence Web ?

L’application qui fait l’objet de notre projet est destinée à enrichir un site Internet. Il ne serait donc pas absurde de penser qu’une agence Web serait en mesure de mener à bien ce travail. Cependant, le noyau de l’application (la partie calculatoire) demande certaines compétences en optimisation qu’une agence Web n’a pas forcément.

D’un autre coté, se tourner vers une SSII rendrait le coût de l’application beaucoup trop élevé : il n’est peut être pas nécessaire de se munir d’une « artillerie si lourde ».

L’application à réaliser demande des compétences dans un domaine qui se situe entre une SSII et une agence Web. L’idéal serait de trouver une interface entre ces deux structures.

Pour nos recherches, nous n’avons donc pas préféré l’un ou l’autre type de société dans la mesure ou chacun a ses avantages et ses inconvénients.


2.5 Comparaison des services proposés

L’ensemble des critères que nous venons de détailler nous a permis d’établir une liste de sociétés à contacter. Sur l’ensemble de cette liste, 2 sociétés ont été intéressées par le projet que nous leur proposions. Nous avons donc programmé une réunion avec chacune de ces sociétés de manière à évaluer leurs compétences (sur le développement de l’application), mais aussi afin d’obtenir un ordre de grandeur du coût de leur prestation.

Nous allons donc présenter maintenant les prestations des 2 sociétés en détail.

2.5.1 La société WZ Conseil

2.5.1.1 Présentation de la société

La SARL WZ Conseil est situé à Albi dans le Sud-Ouest de la France, proche du pôle technologique toulousain.

Une équipe de 2 personnes, Julian Adelman (gérant) plongé depuis 3 ans dans le développement Internet/Intranet/Multimédia et Frédéric Munoz ingénieur maître télécom et réseaux informatiques qui prend en charge le développement base de données et la programmation PHP, Perl, C etc...

La société existe depuis mai 2000, elle se concentre sur la sous-traitance de la gestion de la plate-forme technique et le développement pour la société ILINK (ISP) en 2002.

2.5.1.2 Étude des compétences

Les associés de WZ sont intéressés par le développement de l’application. Nous leur avons montré les sites similaires (de STY et de la RATP) pour leur donner une idée du résultat attendu.

Les associés de la société WZ nous ont fait comprendre que reprendre l’application que nous aurions développée en interne pour la maintenir par la suite ne les intéressaient pas.

Ils sont cependant intéressés par la partie algorithmique de l’application qui a été traduite en PHP.

2.5.1.3 Devis

Voici le devis que nous a proposé la société WZ après avoir analysé le Cahier des Charges que nous leur avons présenté :

Leur prestation comprend :

- La création de l’application (PHP/PostgreSQL) et de la base de données à partir de cartes du réseau de bus et des feuilles d’horaires (au format Excel) fournis par ALBIBUS ainsi que leur hébergement.

6100� HT


- La maintenance annuelle de l’outil comprenant une mise à jour des grilles d’horaires par an :

750� HT/an

- L’hébergement de la base de données PostgreSQL :

360� HT/an

2.5.2 L’agence Web o10c

2.5.2.1 Présentation de la société

o10c Webgineering est une petite agence Web située au centre ville d’Albi : 9 rue Saint Antoine (derrière le théâtre municipal).

Elle est spécialisée comme toute agence Web dans la création de sites Internet.

Elle réalise la plupart de son chiffre d’affaires dans la maintenance et la réactualisation de sites « plaquettes » qu’elle a déjà réalisée pour des entreprises.

Elle est composée d’un technicien en informatique qui réalise le côté développement des sites, d’un infographiste qui s’occupe du design et de l’ergonomie et d’un directeur qui dirige la petite société (communication, gestion, marketing).

2.5.2.2 Étude des compétences

Nous avons également présenté le projet à la société o10c puis expliqué la démarche que nous avons effectué jusqu’ici : recherche de solutions, sites Web existants… et la raison pour laquelle nous nous tournons aujourd’hui vers des agences Web pour leur proposer de réaliser cette application.

Les associés sont intéressés par la reprise du travail (essentiellement la partie algorithmique) que nous avons déjà effectué de manière à diminuer le coût de la prestation.

2.5.2.3 Devis

Le devis de la société WZ ramené en nombre d’heures de travail s’élève à 115 h environ : durée jugée un peu courte par o10c pour effectuer cette application.

L’agence o10c, propose en contrepartie une maintenance du site plus avantageuse (en termes de coût) que la société o10c.


2.6 Caractéristiques du service exigé et étude financière

Les études de faisabilité et les devis que nous avons pu obtenir auprès des sociétés que nous avons rencontrées nous ont permis d’avoir un aperçu concret du coût de développement de l‘application par une agence Web.

Notre maître d’ouvrage externe nous a cependant demandé de réaliser nous même une telle étude qui viserait dans un premier temps à justifier le coût de cette application. Cette étude serait aussi l’occasion, dans un deuxième temps, de vérifier que l’estimation réalisée par l’agence Web WZ était cohérente par rapport au service exigé.

Nous avons raisonné en nombre d’heures de travail pour réaliser notre estimation.

Nous avons décomposé le développement de l’application en plusieurs étapes indépendantes de manière à mieux estimer le temps de réalisation de chacune de ces étapes unitaires (faisant de toute manière appel à des compétences techniques distinctes).

• La récupération du fichier des horaires de bus Excel et son transfert vers une base de données exploitable par une architecture Web est la première étape. Ce travail a été réalisé avec succès dans le cadre du développement interne.

10 heures ont été nécessaires pour mener à bien cette tâche.

• La partie algorithmique de recherche du chemin le plus court est de loin le moteur de l’application : c’est elle qui demandera le plus de travail.

Réalisée avec un langage type PHP ou PERL (langage interface Web - bases de données).

10 heures nous ont été nécessaires pour trouver l’algorithme adéquat.

20 heures pour la modélisation du problème.

10 heures de traduction dans le langage approprié.

30 heures de tests et d’amélioration.

70 heures sont estimées pour interfacer l’algorithme avec la base de données des horaires de bus.

Soit un total de 150 heures de travail pour la partie algorithmique.


• Il reste maintenant toute la partie interface graphique Web à réaliser directement sur le site d’ALBIBUS lui-même :

Cette étape comprend la cartographie du réseau ALBIBUS ainsi que la présentation des résultats générés par le moteur de l’application.

20 heures de travail sont estimées nécessaires à cette tâche.

170 heures de travail ont donc été estimées pour mener à bien la réalisation de cette application.

Le coût de l’heure de travail2 dans une société de type agence Web s’élève à 53.5� HT soit 350Fr HT.

Pour 170 heures de prestation, nous avons un coût propre au développement de l’application qui s’élève donc à 9100� HT environ soit 60000Fr HT.

L’évaluation que nous avons faite va donc bien dans le sens de la société o10c qui nous avait fait comprendre que le coût de leur prestation dépasserait légèrement celui annoncé par la société WZ qui s’élevait à 6100� HT.

2 Cette valeur est la valeur du coût de la prestation horaire de la société o10c. Elle nous a servi d’étalon pour notre calcul du coût de l’appliaction.


3. Le développement en interne

3.1 Présentation du problème

La première étape dans le développement d’une telle application est la modélisation du problème. Dans notre cas celle-ci a consisté en une représentation graphique du réseau de bus permettant le calcul du chemin le plus court entre deux points. En effet le langage des graphes permet de représenter simplement la structure d’un grand nombre de situation.

Figure 4 : Liaisons entre les stations

Il a donc été décidé de séparer chaque station physique de bus entre les différentes lignes passant par ce point et le sens de parcours de chaque bus ; une station de bus réelle à laquelle passe deux lignes différentes sera donc modélisée par 4 sommets virtuels. Les liaisons entre tous ces nœuds seront établies en fonction de la réalité du réseau. Une difficulté persiste en ce qui concerne les poids de ces arcs, ceux-ci doivent en effet évoluer dynamiquement au cours du temps puisque la durée du parcours entre deux stations peut être différente au cours de la journée.

Pour permettre à l’application de choisir entre tous les parcours possibles, un nœud de départ « virtuel » est créé. Il est relié à la station de bus réelle donc à plusieurs sommets virtuels, il en est de même en ce qui concerne l’arrivée, de cette manière on est absolument sûr de traiter tous les cas de figure.

Réseau

Ligne 1Sens 1

Ligne 1Sens 2

Ligne 4Sens 1

Ligne 4Sens 2

Arrêt Hôpital

Ligne 1Sens 1

Ligne 1Sens 2

Ligne 5Sens 1

Ligne 5Sens 2

Arrêt Carnot


Figure 5 : Départ-Réseau-Arrivée

3.2 Utilisation de l’algorithme de Dijkstra

L’application demandée par ALBIBUS consiste à calculer le chemin le plus rapide entre deux stations de bus. Ce problème peut être résolu en utilisant un algorithme d’optimisation de parcours si on considère que le réseau de bus est un graphe orienté. Dans ce cas-là, le calcul du chemin au poids minimum, où chaque pondération représente le temps de parcours entre deux stations, est réalisable par l’algorithme de Dijkstra. Cet algorithme est le plus performant dans le cas où toute pondération, c’est-à-dire tout temps de parcours, est forcément un nombre réel positif. Reste à voir comment cet algorithme fonctionne.

3.2.1 Définition d’un graphe orienté

On appelle graphe orienté un couple G=(S,A) où S est un ensemble dont les éléments sont appelés sommets et A est l’ensemble des ars tel que A ⊆ S∗S\{(x,x), x ∈S}. Ainsi les arêtes sont « fléchées » et on interdit les boucles.

Autrement dit, un graphe orienté G est constitué d’un ensemble de sommets S et d’un ensemble d’arcs A. Les sommets sont également appelés « nœuds ». Un arc est un couple de sommets (s,t) : s est l’extrémité initiale de l’arc et t son extrémité finale. Cet arc est souvent symbolisé par une flèche. On dit que l’arc (s,t) va de s vers t et que t est adjacent à s.

La figure montre un graphe orienté à quatre sommets et cinq arcs.

Figure 6 : Exemple de graphe orienté

3.2.2 Le problème du chemin le plus court

On considère un graphe orienté G(S,A) et une pondération v, fonction de A dans R. Si �=(x1,..,xn) est un chemin de G, on appelle coût de � le réel :

D ARéseau


( ) ( )�−

=+=

1

11

n

iii xxvv µ

Le calcul du chemin le plus court consiste alors à résoudre le problème du chemin de coût minimum. La pondération v représente le temps intermédiaire entre chaque sommet. Le problème est : étant donnés une source s et un puits p, de trouver un chemin � allant de s à p en minimisant �(�).

3.2.3 Principe de l’algorithme de Dijkstra

L’algorithme de Dijkstra permet de calculer le chemin de coût minimum depuis une source unique. Il ne peut s’appliquer qu’à des graphes orientés avec une pondération positive (chaque arc possède une étiquette positive ou nulle).

L’idée est de calculer une arborescence de plus courts chemins entre s et tous les autres sommets. L’initialisation se fait en mettant comme coût : 0 à s, et infini aux autres. On part de s, puis on empile tous ses voisins avec leur distance à s. On choisit alors a un de ceux de coût minimal, on le dépile et on examine ses voisins. Parmi ceux-ci, on empile ceux que l’on n’a pas encore visités.

Pour les autres, on regarde si on peut modifier leur coût en remplaçant leur prédécesseur par a. Dans le cas positif, on remplace le sommet de leur « ancêtre » par a.

On recommence avec un sommet de la pile qui a le coût minimum. À la fin, on obtient le poids minimum pour atteindre p, et en plus le chemin qui permet de l’obtenir, en remontant les prédécesseurs.

À noter que l’algorithme est facilement implémentable en O(n2).

3.2.4 Procédure

Soient : -S l’ensemble des sommets,

-E l’ensemble des sommets xi dont le poids �i atteint sa valeur minimale.

-vij la pondération sur l’arc allant de i à j, cette valeur représente le temps de parcours de i à j s’il l’arc existe.

Début

1. Initialisation

Poser : S={ x0 , x1 ,…, xn }

E={ x0 }

�0=0

�i = v0i si (x0,xi) est un arc

�i = +� sinon


2. Calcul du poids minimal

Tant que (E � S) Faire :

Choisir : xi � S-E tel que ESxki

k −∈= )min(λλ /* on sélectionne le sommet xi de S

dont le poids est minimal */

Poser : { }ixEE Υ= /* on sélectionne xi définitivement en l’ajoutant à E */

Pour tout xj � S-E Poser : �j=min( �i + Vij , �j ) /* à partir du sommet xi on ajuste le poids de tous les sommets suivants */

FinFaire

Fin

3.2.5 Preuve de l’algorithme de Dijkstra

Tout d’abord, l’algorithme se fait en un nombre fini d’étapes. On fait l’étape 1, une fois et l’étape 2, n-1 fois.

Ensuite dès que xi appartient à E alors �i est fixé. En effet, si on fixe i, �i décroît jusqu’à ce que xi � E, alors il reste fixe comme on le voit sur la procédure ci-dessus.

L’algorithme aura fait sa preuve si, en cours d’algorithme, la valeur �i est la valeur minimale des chemins allant de x0 à xi et n’empruntant que des sommets de E.

Remarquons d’abord que les valeurs étant positives, il y aura toujours un chemin de valeur minimale passant par les sommets de E qui soit élémentaire. On pourra donc considérer élémentaires les chemins considérés.

En résonnant par récurrence :

Supposons qu’au début de l’itération r, E ne contienne bien que des sommets dont le poids est minimal. Lors de l’itération r, on inclut xi dans E.

Supposons que ESxki

k −∈= )min(λλ ne soit pas le poids minimal de xi. �i est néanmoins la

valeur d’un chemin de x0 à xi . Il existerait alors un chemin de x0 à xi de valeur v(�) strictement inférieure à �i. Soit xh le premier sommet non sélectionné (donc appartenant à S-E) rencontré sur �, on note �1 le sous-chemin de � allant de x0 à xh et �2, celui de xh à xi.

D’où :

( ) ( ) ( ) 021 +≥+= hvvv λµµµ

car ( ) hv λµ ≥1 et ( ) 02 ≥µv

Mais ( )µλ vi > et donc hi λλ > , ce qui contredit le choix de xi.

L’hypothèse de récurrence étant vraie (initialement E contient un seul sommet, x0, donc le poids �0 est bien minimal), l’algorithme est bien démontré.

On en déduit ainsi que l’algorithme est valable du fait qu’à la fin, on a : E=S. Ainsi l’ensemble des sommets du graphe a été parcouru.


L’algorithme de Dijkstra est le plus efficace pour calculer le coût minimal à partir d’un sommet à tous les autres lorsque tous les arcs du graphe sont positifs.

3.3 Traduction de l’algorithme dans un langage informatique

Nous avons tout d’abord traduit l’algorithme précédent pour calculer le chemin le plus court dans des graphes orientés. Dans cette partie nous ne nous préoccupons pas encore du réseau de transport d’ALBIBUS . Nous travaillons seulement sur des cas simples.

3.3.1 Explications sur le programme

L’algorithme a tout d’abord été traduit en langage C. Le fichier commenté se trouve en annexe 3. Pour créer ce programme, il a fallut choisir une structure de données pour représenter le graphe orienté. Une représentation fréquente d’un graphe orienté G=(S, A) est la matrice valuée associée.

Supposons que S contienne n sommets. La matrice associée est la matrice P de dimension n*n constituée de réels. La valeur P[i, j] est égale au poids associé à l’arc allant de i à j. Si un tel arc n’existe pas, la matrice contient un valeur arbitraire. C’est-à-dire une valeur absente de l’ensemble des étiquettes des arcs du graphe, pour nos tests nous prenons la valeur -1. Les valeurs sur la diagonale sont posées nulles, ainsi P[i, i]=0. Cette dernière égalité traduit le fait que le temps de parcours pour aller d’un point i au même point i est nul.

Soit le graphe orienté suivant, il faut trouver sa matrice associée afin de pouvoir l’exploiter par un programme informatique. Le graphe contient 5 points et 8 arcs. La matrice sera de dimension 5*5. Elle comprendra 8 valeurs (différentes de –1 et pas sur la diagonale) qui représenteront la valeur de chacun des arcs.

Matrice valuée associée P :

0 5 2 -1 6

-1 0 1 -1 -1

-1 2 0 3 -1

-1 -1 -1 0 2

-1 -1 -1 2 0

Figure 7 : Passage d’un graphe orienté à sa matrice associée P

Le programme en C utilise également d’autres tableaux de dimension n. Le tableau D garde en mémoire les coûts minimaux des parcours à partir du sommet 0. La valeur D[i] représente le temps minimal calculé pour aller du sommet 0 à au i.


La ième valeur du tableau C correspond au prédécesseur du sommet i pour le chemin le plus court. Pour déterminer le parcours minimum entre le sommet de départ et celui d’arrivée, il faut remonter dans les prédécesseurs. Ce tableau ne contient que des entiers, les numéros des sommets.

Le tableau E contient l’ensemble des sommets non-sélectionnés, pour lesquels le chemin le plus court n’a pas été encore déterminé. Ainsi contrairement à précédemment, l’ensemble que l’on appelait S-E correspond à ce tableau E. Lorsque le sommet i est sélectionné, on affecte à la ième valeur du tableau le nombre –1. Cette action permettra de savoir sur quels sommets l’algorithme doit tourner en sélectionnant les valeurs positives.

En appliquant le graphe ci-dessus au programme pour chaque itération, on obtient le tableau suivant :

Itération E b D C

0 {-1, 1, 2, 3, 4} {0, 5, 2, -1, 6} {0, 0, 0, 0, 0}

1 {-1, 1, -1, 3, 4} 2 {0, 4, 2, 5, 6} {0, 2, 0, 2, 0}

2 {-1, -1, -1, 3, 4} 1 {0, 4, 2, 5, 6} {0, 2, 0, 2, 0}

3 {-1, -1, -1, -1, 4} 3 {0, 4, 2, 5, 6} {0, 2, 0, 2, 0}

4 {-1, -1, -1, -1, -1} 4 {0, 4, 2, 5, 6} {0, 2, 0, 2, 0}

Figure 8 : Résultats de l’algorithme pas à pas

À la fin, toutes les valeurs de E sont à –1, ce qui veut dire que tous les points ont été sélectionnés. L’algorithme ressort que, pour le chemin le plus court partant de 0, les antécédents de 2 et 4 sont 0, ceux de 1 et 3 sont 2.

3.3.2 Test du programme

Le programme a été testé sur différents cas (ne dépassant pas 11 sommets) et les résultats étaient tous corrects. Il était également intéressant de déterminer le temps de calcul suivant le nombre de sommets. Nous avons donc testé le programme sur des graphes allant de 5 à 5000 arrêts. Les données du graphe ont été remplies par une fonction pseudo-aléatoire. Nous avons affecté des poids réels allant de 0 à 100 sur les arcs. En utilisant la fonction « time programme », il a été possible de relever le temps de réponse utilisateur.

Nous avons aussi testé le programme en l’optimisant au niveau 3 lors de la compilation. L’instruction de compilation était : « gcc –O3 –o nom nom.c ». Les résultats obtenus sont fournis dans le tableau suivant.

Nombre d’arrêts 5 10 20 50 100 150 200 250 350 500 750 1000 1500 2000 5000

Temps (s) sans optimisation

0 0 0.01 0.01 0.05 0.12 0.2 0.31 0.64 1.21 2.86 5.21 9.31 16.91 70.91

Temps (s) avec optimisation niv3

0 0 0 0 0.04 0.1 0.15 0.24 0.49 1 2.2 3.86 8.77 15.68 57.16


En traçant sur la courbe l’évolution du temps de réponse en fonction du nombre d’arrêts (ou de sommets), la figure a été obtenue. On voit que la courbe a bien une évolution d’ordre 2. L’algorithme est bien implémenté en O(n2).

0

10

20

30

40

50

60

70

80

0 1000 2000 3000 4000 5000 6000

nombre d'arrêts

tem

ps (s

)

sans optimisation

avec optimisation

Figure 9 : Evolution du temps de réponse en fonction du nombre d'arrêts.

Pour modéliser le réseau de bus d’ALBIBUS, nous avons estimé le nombre d’arrêts virtuels à 500 (environ 80 arrêts sur chacune des six lignes). Le programme aurait ainsi un temps de réponse de l’ordre de 1,2 secondes. Cependant celui que nous avons réalisé n’utilise pas encore une base de données, nous pensons qu’avec, les temps de calcul seront plus importants. Toutefois, comme le programme devra être accessible par Internet, les temps de transmission des données seront nettement plus élevés que ceux de calcul.

3.4 Adaptation de l’algorithme au réseau ALBIBUS

Pour passer du modèle simple à celui d’ALBIBUS, nous avons créé une matrice associée représentant le réseau. Ensuite nous avons adapté le programme précédent pour qu’il puisse au mieux s’appliquer à notre problème. Cependant nous nous sommes confrontés à de nombreuses difficultés.

3.4.1 Création d’une base de données

Une application, telle que celle demandée, exige un grand nombre de données. Il faut en effet répertorier toutes les lignes de bus ainsi que tous les arrêts, puis archiver une liste détaillée de tous les passages de bus à chaque arrêt. Pour cela nous avons décidé de centraliser toutes ces informations au sein d’une base de données.

Les données nécessaires ne sont disponibles que sous la forme d’un tableau Excel. Il a donc été nécessaire d’exporter ces informations au sein d’une base de données. Nous avons choisi d’utiliser une base de données MySQL permettant une grande compatibilité avec un grand nombre de serveurs Web. L’exportation de toutes ces données n’a pas pu être automatisée, nous avons dû créer une nouvelle feuille de


calcul contenant les différents tableaux horaires. Ce condensé est établi grâce à la technique manuelle du copier-coller. Quelques informations sont ensuite rajoutées dans les cinq premières colonnes :

N° Arrêt Période N°ligne Sens Nom Arrêt Horaire 1 Horaire 2 …

Puis l’ensemble de ce tableau est enregistré au format CSV, ceci génère un fichier texte contenant les données séparées par des points-virgules.

Une solution simple pour importer ces données dans une base de donnée a été de modifier le fichier afin d’obtenir le format de la base. Ceci se fait grâce à la commande Unix gawk :

gawk -F";" '{print $1 ";" $3 ";" $4 ";" $5}' donnee.csv > arret

gawk -F";" '{for (i=6;i<=NF;i++) {print $1 ";" i-5 ";" $i ";" $2}}' donnee.csv > horaire

Figure 10 : Schéma relationnel

La base de données se compose de trois tables dont les commandes de création sont fournies en annexe 4 :

3. La ligne : cette table identifie la ligne de bus par son numéro ainsi que son nom.

4. L’arrêt : cette table contient tous les arrêts virtuels présents dans le graphe, il contient le numéro de la ligne, le sens de parcours de cette ligne par le bus ainsi que le nom de l’arrêt réel.

5. L’horaire : cette table contient l’essentiel de l’information, à savoir, le numéro de l’arrêt, le numéro du bus passant par cette arrêt dans la journée, les heures de passage ainsi que la période de l’année concernée par ces horaires.

En effet, il existe sur le planning des horaires d’ALBIBUS une division de l’année en trois périodes distinctes :

1. Les périodes scolaires du lundi au vendredi

2. Les vacances scolaires et les samedis

3. Les grandes vacances

La base de données actuelle ne contient pour l’instant que des données concernant la première période de l’année

Ligne

N° ligneLibellé ligne

Arrêt

N° ligneN° arrêtSensLibellé arrêt

Horaire

N° arrêtN° BusHeurePériode


3.4.2 Création de la matrice associée au réseau d’ALBIBUS

Pour le programme de calcul d’itinéraire sur le réseau ALBIBUS, nous avons choisi de conserver la matrice associée au réseau. Cependant cette dernière sera composée de deux valeurs. Nous avons choisi de mettre un 1 aux intersections où le passage d’un arrêt à un autre est possible et un 0 lorsqu’il est impossible. Nous lirons dans la base de données les horaires de passage de bus qui remplaceront les pondérations dans les graphes orientés. Nous avons comptabilisé 432 arrêts virtuels. Ainsi cette matrice est de dimension 432*432. Pour automatiser sa construction, nous avons construit un programme en C qui se trouve en annexe 5.

Tout d’abord, avec les bases de données nous avons comptabilisé le nombre d’arrêts par bus et par sens et renvoyé le résultat dans un fichier nommé ‘nb_arret’. L’instruction SQL était la suivante :

SELECT count(id) INTO OUTFILE ‘/home/moghrabi/ifi3/projet/nb_arret’ FROM arret GROUP BY num_ligne,sens ORDER BY num_ligne,sens;

Le fichier obtenu est ainsi lu dans un tableau par le programme qui ressort qu’un arrêt n est relié à celui n+1 s’ils sont sur une même ligne dans un même sens. On met donc dans la matrice P[n][n+1]=1. On met ainsi des 1 sur la surdiagonale sauf au passage entre deux arrêts sur deux lignes différentes. Cependant ce raisonnement est généralement vrai sauf pour les cas où le bus saute des arrêts à certaines périodes de la journée pour changer de parcours. Il faudra donc corriger la matrice manuellement pour ces cas. Dans l’exemple du tableau, il est possible d’aller de « Majesté » au « Collège J.Jaurès » ou à « Albert-Thomas ». Cependant il n’existe pas d’arc entre les deux dernières stations.

Majesté 14 : 40 15 : 01 15 : 16 15 : 30

Collège J.Jaurès 14 : 44 xx : xx xx : xx 15 : 34

Albert-Thomas xx : xx 15: 02 15: 17 xx : xx

Visitation 14 : 48 15 : 05 15 : 20 15 : 38

Figure 11 : Exemple d'un saut d'arrêt sur la ligne 1

Il a donc fallu répertorier tous les cas où il y avait un saut d’arrêt. Pour cela, nous avons regardé les imprimés des horaires des lignes. Ensuite grâce à la base de données, nous avons relevé dans un fichier nommé « cas » les numéros des stations qui avait un arc et celles qui ne devaient pas en avoir. Pour l’exemple précédent, nous avons rempli dans le fichier : n°Majesté n°Albert-Thomas 1 passage autorisé entre ces stations n°Collège J.Jaurès n°Visitation 1 passage autorisé entre ces stations n°Collège J.Jaurès n°Albert-Thomas 0 passage interdit entre ces stations

Le fichier créé contenait ainsi 23 lignes correspondant aux valeurs à changer. Il suffit de prendre la valeur de la première colonne comme numéro de ligne dans la matrice, la seconde comme colonne et la troisième comme valeur à y mettre.

Ensuite, nous avons mis des 1 dans la matrice aux endroits où il est possible de changer de ligne, c’est-à-dire lorsque deux noms d’arrêts de numéros différents sont identiques. Nous avons créé comme précédemment un fichier nommé ‘liaisons’ issu de la base. L’instruction était cette fois-ci :


SELECT t1.id, t2.id INTO OUTFILE ‘/home/moghrabi/ifi3/projet/liaisons’ FROM arret AS t1, arret AS t2 WHERE t1.nom_arret=t2.nom_arret AND t1.id<>t2.id;

Le fichier obtenu contient deux colonnes où les arrêts virtuels les uns en face des autres sont les mêmes arrêts réels. Il suffira de mettre à l’intersection de ces deux arrêts la valeur 1 dans la matrice. Ainsi il sera possible de changer de ligne lors du calcul d’itinéraire.

3.4.3 Création du programme

Nous avons également choisi de traduire ce programme sous un langage informatique plus facile à utiliser pour réaliser des applications Web. Nous avons, suite au conseil de notre maître d’ouvrage, décidé de le faire en Perl. Nous avons aussi tenté au début de le créer en PHP dont le code est fourni en annexe 6.

Le programme Perl proposé en annexe 7 est très proche de la philosophie de celui en C. Les principales différences viennent du choix de supprimer du tableau des sommets non sélectionnés les arrêts dès qu’ils sont sélectionnés. Ainsi à chaque itération sa dimension diminue de 1. Ce choix a été fait afin de pouvoir utiliser l’instruction foreach. Elle prend une série de valeurs contenue dans la liste @NON_SELECT et les assigne l’une après l’autre à une variable scalaire $t, en exécutant un bloc de code à chaque assignation successive. Ainsi le scalaire $t prend le numéro de chacun des sommets non sélectionnés. Nous avons renommé la matrice associée au réseau, précédemment appelée P, par @MAT_RESEAU.

Le programme utilise les horaires contenus dans la base comme pondération. Pour cela, nous avons introduit des fonctions permettant d’interroger la base de données, d’obtenir les horaires souhaités et de les mettre dans la liste @HORAIRE_MARQUE. La requête sélectionne le prochain passage d’un bus sur un arrêt en fonction de l’heure de passage sur l’arrêt précédent. Le résultat renvoyé est soit une heure si elle existe sinon rien. Si le résultat est rien on met un –1 dans le tableau précédent.

Nous avons créé des fonctions pour transformer les dates de type « hh:mm:ss » (sortant de la base) en secondes. Cette fonction s’appelle heuretosec, la transformation inverse se fait par la fonction sectoheure. Nous avons utilisé ces transformations car nous avons remarqué que le programme n’arrivait pas à comparer les heures issues des bases de données. L’ordinateur considérait les heures comme des caractères. En les transformant en secondes, la comparaison avec les opérateurs numériques devient possible.

Pour éviter de parcourir tout le graphe, le programme arrête les calculs dès qu’il a rajouté à la liste @NON_SELECT le sommet d’arrivée. Pour tester le programme, il faut donc rajouter à l’exécution les numéros de départ, d’arrivée et l’heure de départ. Pour calculer le chemin le plus court partant de l’arrêt 0 pour aller au 40 à 12h20, il faut taper : prog4.pl 0 40 12:20:00

Chacune des entrées est contenue dans le tableau @ARGV dans l’exemple il vaut : (0, 40, 12:20:00). La boucle de calcul s’arrête dès que l’arrivée est sélectionnée grâce à l’instruction last.

Nous avons choisi d’afficher pour nos tests le chemin de parcours s’il est possible d’aller au point d’arrivée. Une boucle permet de rentrer les antécédents des sommets en commençant par l’arrivée dans le tableau @CHEMIN. Dès que le départ est


introduit, la boucle s’arrête. Le tableau contient ainsi le chemin inverse. Grâce à la fonction reverse le tableau contient le chemin dans le bon ordre. Nous aurions pu également parcourir le tableau en partant de la fin. Ensuite pour chaque valeur de ce tableau nous affichons l’heure de passage, le nom de l’arrêt, la ligne, et le sens. Ces trois derniers champs ainsi que le numéro de bus sont obtenu par une seconde requête SQL qui sélectionne ces données pour le numéro d’arrêt désiré et l’horaire de passage.

D’après quelques tests, le programme paraît fonctionner. Les temps de réponse varient suivant le nombre de stations à parcourir. Nous avons remarqué que les temps renvoyés se situaient en 1 et 3 secondes. Il renvoie parfois des messages d’erreur. Par exemple, lorsque l’on se déconnecte de la base de données le système renvoie qu’une transmission est encore active. Cependant nous n’avons pas eu le temps de tester beaucoup de cas.

3.4.4 Les difficultés rencontrées lors de la phase de programmation

La programmation a été pour nous une étape assez difficile car nous manquions d’expérience. Le programme en Perl a été fait dans l’optique de rechercher dans des bases de données les horaires des bus et de réaliser une application pour Internet. Néanmoins, nous n’avions aucune compétence dans ce langage et nous avons donc essayé d’apprendre à l’utiliser grâce à différents ouvrages. Nous avons réussi avec peine à traduire l’algorithme de Dijkstra mais le résultat obtenu dépasse nos premières ambitions. En effet, le programme utilise les possibilités offertes par les bases de données. La syntaxe a été réalisée en se basant des fichiers Perl de M. OTTON que nous avions utilisés dans le cours « Système de gestion des bases de données ».

Le principal problème provenait du fait que les données des horaires contenaient beaucoup de points particuliers ou d’exceptions. Initialement nous avions remarqué qu’il existe deux périodes d’horaires (les vacances et les périodes scolaires). Cependant lorsque nous avons essayé de rentrer ces données dans la base nous nous sommes rendus compte qu’il existait en fait trois périodes : les périodes scolaire, les grandes vacances et les vacances scolaires avec le samedi. Ceci pose le problème de savoir à quelle période l’utilisateur saisit sa requête. Pour la période grandes vacances nous aurions pu dire qu’elle est valable du 1er juillet au 3 septembre de chaque année. Cependant pour les deux autres périodes il est difficile de savoir quand elles sont en vigueur puisque les dates varient chaque année. Pour simplifier le problème, nous avons décidé de ne prendre que les données de la période scolaire. Ainsi nous n’aurons besoin que d’une matrice @MAT_RESEAU (il en faudrait une par période) qui exprime l’existence ou non d’un arc entre les stations.

De plus, les horaires fournis ne sont pas réguliers. Selon les périodes de la journée, le passage des bus sur les lignes est modifié. Il arrive qu’ils ne s’arrêtent plus à un arrêt pour s’arrêter sur un autre arrêt particulier (tel qu’un établissement scolaire à l’heure de sortie). Il existe un certain nombre de cas particuliers qui impliquent que la matrice associée soit en partie remplie à la main pour ces exceptions. Heureusement ces cas n’étaient qu’au nombre de 23.


Le développement interne à donné des résultats qu’initialement nous n’espérions pas atteindre. Tout d’abord, M. LAMOTHE nous a accordé sa précieuse aide pour les problème de modélisation et le programme. L’application développée fonctionne et calcule le chemin le plus court avec un départ au plus tôt. Pour proposer une option de départ au plus tard, il faudrait utiliser l’algorithme dans le chemin inverse et prendre l’horaire inférieur du suivant le plus tard. Cependant le projet n’est pas encore achevé. Nous pensons que la partie la plus difficile a été réalisée. Il reste effectivement à tester plus profondément le programme, créer les bases de données avec les horaires des vacances et prendre en compte la période. Il faudra ensuite intégrer l’application sur le site Internet d’ALBIBUS et se prémunir contre d’éventuels risques de piratage. Il serait également très intéressant d’optimiser l’application pour en diminuer le temps de réponse. Effectivement nous utilisons pour l’instant une matrice représentant le réseau. Or celle-ci contient beaucoup de 0, il doit y en avoir plus de 16 000 sur les quelques 18 000 valeurs contenues. M. LAMOTHE nous a indiqué qu’il serait préférable d’utiliser des listes chaînées. Le problème du développement en interne est l’obligation de refaire les procédures de création de la matrice associée et de la base de données si le réseau de bus était modifié. L’idéal serait qu’ALBIBUS gère ses horaires dans une base de données.

4. Démarche projet

4.1 Objet de l’étude et cadre du projet :

Enrichissement du site Internet d’ALBIBUS par une fonction d’optimisation d’itinéraire. L’application doit fournir à l’utilisateur le chemin le plus rapide entre sa station de départ et celle d’arrivée. Le cahier des charges se trouve en annexe 8.

Pour le développement en interne, l’atteinte des objectifs ne peut être garantie en raison de la complexité relative des algorithmes à mettre en œuvre et du niveau informatique des maîtres d’œuvre. L’étude se limitera à identifier un algorithme, le traduire sous forme informatique et essayer de l’intégrer au site.

Dans le cas de la sous-traitance, le projet se rapprocherait d’une étude de faisabilité et d’évaluation des coûts. La finalité du projet dépendrait alors du budget alloué à l’acquisition d’un tel logiciel et de son approbation par les autorités concernées. ALBIBUS étant soumis règles des marchés publics au-delà d'un budget seuil (voir partie***), on ne pourra entamer aucune démarche officielle de sous-traitance. Seul un premier contact et un bref devis des entreprises intéressées seront possibles.


4.2 La prise en compte des risques

4.2.1 Cas du projet développé en interne

Risque Mesures pour la prévention du risque

Projet inachevé dans le temps imparti

- Simplifier le développement en fixant des objectifs concrets

- Se faire aider par les experts

- Faire du travail en dehors des heures projet

- Mieux répartir les tâches

Le programme ne répond que partiellement aux attentes

- Définition des objectifs avec le directeur d’ALBIBUS

- Bien définir le cahier des charges en le faisant valider et s’y référer

- Faire des tests afin de corriger les éventuels bugs

L’équipe a des difficultés techniques et bloque sur le développement

- Utiliser des ouvrages techniques d’informatique

- S’aider des experts ou de personnes compétentes en informatique

- Ne pas être trop ambitieux

Le projet a un coût supérieur aux prévisions

- Utiliser des logiciels libres et donc gratuits

- Faire tout le développement en interne

Le programme n’est pas mis à jour par ALBIBUS

- Proposer des outils de mise à jour des horaires simples

- Former les utilisateurs

Le site Internet n’est pas utilisé par les albigeois

- Créer un site de qualité (convivial, rapide, précis et esthétique)

4.2.2 Cas de l’appel à la sous-traitance

Risque Mesures pour la prévention du risque

Le coût du projet est important (>7 500�)

- Négocier avec les sous-traitants

- Préparer un appel public d’offre

Les délais des sous-traitants sont difficilement contrôlables

- Fixer par une convention les délais à respecter

- Rechercher des sous-traitants ayant déjà résolu un problème identique pour un autre client


Il est difficile d’obtenir une version d’évaluation de l’application

- Mettre en valeur que le travail est destiné à une municipalité

4.3 L’organisation du projet

4.3.1 Les acteurs

4.3.1.1 Les maîtres d’ouvrage :

Philippe DUBOIS, Directeur d’ALBIBUS

Emmanuel OTTON, responsable informatique de l’École des Mines d’Albi

4.3.1.2 L’équipe projet de l’École des Mines d’Albi :

4.3.1.3 Les experts

Emmanuel OTTON pour l’ensemble du projet et l’informatique

Jacques LAMOTHE pour le développement de l’algorithme du calcul d’itinéraire

4.3.2 L’organisation

4.3.2.1 Organigramme des tâches :

L’organigramme des tâches se trouve en annexe 9. Il a été utilisé pour créer le Gantt et le PERT.


4.3.2.2 Planning du projet : le Gantt et le Pert

Le premier diagramme de Gantt présenté en annexe 10 correspond au diagramme initial. Le Gantt mis à jour au 7 janvier 2002 est le second disponible. Il tient en compte de l’avancement du projet. Le diagramme sera réactualisé toutes les deux semaines et modifié en fonction de la situation du projet. Le Pert est quant à lui présent en annexe 11.

4.3.2.3 Le diagramme des ressources

En annexe 12 se trouve le diagramme des ressources. Il arrive qu’un membre de l’équipe soit en surcapacité. Cette situation est évitée autant que possible cependant il nous arrive quelques fois de travailler en dehors des heures de projet afin d’accélérer le travail.

4.3.2.4 Les tâches transversales du projet

• Définition du projet

Tâche 4 : Rencontre avec le maître d’ouvrage

Acteurs : Toute l’équipe projet.

Charge : 1h

But : Profiter de la réunion pour définir clairement les attentes du maître d’ouvrage externe (Monsieur DUBOIS). Etablissement des objectifs du projet, ses contraintes et connaissance plus approfondie du contexte du projet.

Démarche : Suite à la préparation de la réunion durant laquelle nous avons établi une liste exhaustive des questions à poser au maître d’ouvrage, nous avons profité de cette réunion pour lui demander de répondre à ces interrogations.

Nous avons ensuite demandé à monsieur DUBOIS de nous en apprendre un peu plus sur ALBIBUS et sur le contexte du projet. Nous avons ainsi acquis quelques connaissances relatives à la gestion des lignes de bus qui étaient nécessaires au bon déroulement du projet d’un point de vue technique.

La réunion a aussi été l’occasion de définir de manière plus précise les objectifs du projet et de clarifier les attentes du maître d’ouvrage.

Nous avons également renseigné le maître d’ouvrage sur l’aspect pédagogique de l’exercice de gestion de projet.

Tâche 5 : Assimilation de la réunion


Charge : 1h

But : L’assimilation de la réunion a pour but de faire ressortir les éléments clés de la réunion. Certains vont pouvoir être repris dans le CDCF,


d’autres seront utiles dans la suite du projet. La réunion a permis a l’équipe projet d’établir un Gantt et un Pert qu’il était difficile d’établir auparavant compte tenu du manque d’information ou de l’imprécision des objectifs du projet.

Démarche : Dans un premier temps, il a été jugé nécessaire de noter par écrit les points forts de la réunion.

La réunion a permis de lister l’ensemble des tâches du projet que l’on a pu par la suite rentrer dans le Gantt.

L’assimilation de la réunion a permis de clarifier les objectifs du projet et les attentes du maître d’ouvrage. Le contexte du projet est lui aussi devenu plus clair.

Ces éléments ont soigneusement été noté de manière à pouvoir être réutilisés dans la rédaction du CDCF.

La partie technique du travail pouvait dès lors être commencée.

Tâche 8 : Etude de l'état initial du projet (1) : appropriation du travail du stagiaire

Acteurs : Moghrabi, Mannheim.

Charge : 1.5h

But : Eclaircir le contexte du projet d’un point de vue technique.

Démarche : Recherche du rapport du stagiaire de l’EMAC qui a réalisé le site Internet d’ALBIBUS . Lecture de la partie du rapport technique relative à la construction du site Internet de manière à savoir comment a été réalisé le site (structure du site, langages …)

Tâche 9 : Etude de l'état initial du projet (2) : étude du site Internet

Acteurs : Moghrabi, Mannheim

Charge : 1h

But : Etudier d’un point de vue technique et ergonomique la structure du site Internet d’ALBIBUS dans le but de déterminer la partie du site exploitable par notre application.

Présenter les résultats de cette étude à Monsieur OTTON.

Démarche : Dans un premier temps, nous avons parcouru l’ensemble des pages qui composent le site, puis nous nous sommes focalisés sur la page relative à la gestion des horaires (seule partie du site exploitable par l’application qui est l’objet de notre projet).

Nous avons étudié la manière dont a été construite cette page (HTML


classique ou pages dynamiques …) de manière à savoir comment il serait possible d’interfacer notre application avec le reste de cette page.

Rédaction d’un rapport afin de présenter les résultats de cette recherche à Monsieur OTTON.

Tâche 11 : Préparation et réunion avec M. DUBOIS

Acteurs : Toute l’équipe

Charge : 4h

But : Définir les objectifs et les limites du projet, faire part à M. DUBOIS de notre démarche.

Démarche : Après avoir pris connaissance du travail du stagiaire et des logiciels d’optimisation existants nous faisons part à notre maître d’ouvrage externe notre démarche. Nous avons décidé d’explorer plusieurs voies.

Tâche 12 : Création du CdCF

Acteurs : Rosières

Charge : 4h

But : Définir les objectifs et les limites du projet afin d'avoir une approbation des différents maîtres d’ouvrage.

Démarche : Après les réunions avec le maître d’ouvrage, les principales caractéristiques ont été regroupées et rédigées au sein du CdCF.

Tâche 13 : Prise en compte des risques du projet

Acteurs : Mannheim

Charge : 2h

But : Prévenir les éventuels risques d’échec du projet.

Démarche : Un listing de toutes les causes d’échec du projet à été réalisé puis il en a été question lors d’une réunion de l’équipe. Une décision à été prise concernant les principales causes.

• Gestion de projet


Cette partie nous a permis de construire la première trame de notre projet et de la faire évoluer pour tenir compte des changements survenus par rapport à nos prévisions. Elle nous a poussé à fixer des objectifs à atteindre à court terme. Ainsi elle s'est révélée un moyen efficace pour nous faire progresser dans notre projet et franchir les étapes successives. Les différentes tâches qui la composent sont les suivantes :

Tâche 14 : Planification du projet

Acteurs : Landi, Moghrabi, Carlet

Charge : 4h

But : Il s’agit d’organiser au mieux notre travail, tout au long du projet, en déterminant les tâches nécessaires et suffisantes au succès de notre entreprise. Cette planification sert aussi de ligne directrice et permet de bien cadrer notre ouvrage afin de suivre au plus près les objectifs fixés au préalable dans le cahier des charges fonctionnel (CDCF).

Une démarche structurée, suivant des étapes clairement définies, nous permet aussi de répartir judicieusement le travail entre toutes les ressources du groupe projet et donc d’augmenter notre efficacité pour chaque séance.

Démarche : Lors des toutes premières séances, on a commencé par définir les tâches et les ressources en personnes et en temps, nécessaires à la réalisation du projet. On a affecté à chacune des tâches un groupe de personnes pour une durée déterminée, en essayant de rester dans les limites du temps accordé. Ces démarches se sont appuyées sur les conclusions du cahier des charges fonctionnel, établi auparavant avec nos maîtres d’ouvrage. En effet, chaque tâche a été définie dans le but de répondre à toutes les exigences du groupe ALBIBUS répertoriées et analysées dans le cahier des charges. Cette définition de tâches a abouti à un diagramme des tâches, donnant une hiérarchisation graphique des tâches.

Nous avons ensuite présenté ces tâches dans deux autres diagrammes le Pert et le Gantt. Le diagramme de Gantt nous a permis de représenter leurs dispositions chronologiques et de s’assurer que nos prévisions sur les ressources sont cohérentes avec le temps alloué au projet.

Le diagramme P.E.R.T. organise le projet sous forme de réseau et permet de vérifier les liaisons entre tâches.

Tâche 15 : Réactualisation du planning

Acteurs : Landi, Moghrabi Charge : Répartie tout au long du projet But : On a vu, dans la tâche 14, l’intérêt de la planification du projet. Cependant cette planification ne peut assurément pas être figée dans le temps et fixée au début du projet. Elle doit évoluer pour prendre en compte les nouveaux paramètres tels que les changements d’exigences du maître d’ouvrage, la renégociation du cahier des charges fonctionnel


ou les difficultés non prévues au commencement du projet. Certes la première planification doit être aussi fidèle que possible au déroulement du projet, cependant sa réactualisation est indispensable pour évaluer les conséquences de tous les aléas qui nous éloignent du déroulement prévu initialement.

Démarche : A chaque étape du projet, on vérifie que le travail effectif est en accord avec la dernière planification réalisée. Chaque fois qu’un imprévu ou une mauvaise estimation de la tâche entraîne une grande différence avec ce qui était estimé, nous revoyons notre planification en essayant d’incorporer la différence induite dans l’évaluation des tâches futures. Ayant une date limite de fin de projet définitivement fixé, la priorité est donnée au respect du délai imposé en essayant de répondre au mieux aux exigences d’ALBIBUS .

Il faut savoir que dans la première planification il est laissé une marge de temps pour prendre en compte les futurs et inévitables aléas du projet. Cela laisse donc une petite marge de manœuvre pour la réactualisation du planning.

On a pu constater à travers d'autres expériences comme le projet de 2ème année, que la gestion de projet est un outil indispensable lorsque l'on veut mener efficacement un projet ne s'étalant que sur quelques semaines. Mais à travers ce projet, cette réalité nous est apparue encore plus clairement. Dans un groupe de cinq personnes avec des compétences et des visions différentes, avec un planning extrême précis de créneaux horaires s'étalant sur toute l'année scolaire et des échéances régulières (réunions, rapport d'avancement), il est plus que nécessaire de faire preuve d'organisation et de structurer nos actions autour d'un planning prédéfini mais évolutif. La planification et l'actualisation de celui-ci s'imposent d’elles-mêmes et on ne peut en faire l'économie.

• La rédaction de rapports, de compte-rendus et préparation de la présentation orale

La rédaction régulière de comptes-rendus nous est tout d'abord apparue fastidieuse. Pourtant très vite on a pu apprécier l'intérêt de cette tâche. Ces comptes-rendus se sont révélés indispensables pour tenir des objectifs, garder en mémoires les conclusions des dernières séances et pour constituer une trame écrite retraçant le cheminement de notre projet étape par étape. Ils nous permettaient de valider avec nos maîtres d'ouvrage les divers objectifs à atteindre pour les séances suivantes. La rédaction des divers rapports s'est largement appuyée sur la structure du projet dessiné par l'ensemble de ces comptes-rendus.

Tâche 17 : Rédaction des comptes rendus


Charge : Répartie tout au long du projet

But : Afin d’avoir un suivi au jour le jour des toutes décisions et


informations concernant le projet, un compte rendu est rédigé par un membre de l’équipe à chaque fin de séance.

Un projet bien mené s'accompagne toujours d'une bonne présentation des résultats obtenus aux commanditaires du projet. Ici nous étions tenus de rendre un rapport d'avancement et un rapport final à nos maîtres d'ouvrage, de faire une présentation orale à la mairie d'Albi et à l'Ecole des Mines. Notre démarche pour préparer ce travail de présentation a été défini dès le début du projet : durant tout le projet on devait garder des traces écrites de toutes les idées et les décisions prises, de ce qui les avait motivées et d'essayer à chaque fois de structurer notre travail de recherche autour d'un plan prédéfini. La rédaction régulière de comptes-rendus de séances rentrait tout à fait dans cette méthode travail. Ainsi, utilisant ce travail effectué tout au long du projet, la rédaction des rapports s'en est trouvé grandement simplifié. Toute ces notes ont été mises en formes, structurées et articulées autour de notre problématique pour former une synthèse de notre travail.

Tâche 18 : Rédaction du rapport d’avancement


Charge : 16h

But : Présenter la démarche projet. Ce rapport est à remettre au maître d’ouvrage le 17 janvier 2002.

Démarche : La rédaction du rapport d’avancement a débuté le 17 décembre 2001. A cet effet, une synthèse complète des données a été dressée ; un plan détaillé a été établi et le travail réparti.

Tâche 19 : Rédaction du rapport final


Charge : 60h

But : Cette tâche comporte la présentation du sujet, un plan détaillé des tâches afin de présenter le projet en profondeur, une rectification des diagrammes prévisionnels, commentaires sur les problèmes et erreurs de l’équipe.

Afin d’établir un plan et de le valider, il est nécessaire d’organiser clairement les informations recueillies tout au long du projet, en rédigeant un rapport d’action (synthèse de la totalité du projet), un rapport d’étude (détail de la démarche projet), et à travers une discussion de l’ensemble du groupe pour un avis général du plan.

Par la suite, les rapports sont corrigés par chaque membre du groupe et discutés pour en établir la cohérence. Ils sont alors validés par l’ensemble du groupe.


Tâche 20 : Préparation de l’oral


Charge : 3h

But : Préparer la présentation orale et rédiger les différents transparents à exposer.

Démarche : L’oral est préparé de façon à tendre vers une présentation claire, convaincante et synthétique.

4.3.2.5 Tâches spécifiques du projet

Tâche 6 : Recherche de logiciels d’optimisation d’itinéraires

Acteurs : Carlet, Landi, Rosières

Charge : 4h

But : L’objectif est de rechercher sur le marché des logiciels de Systèmes d’Information Géographique (SIG) un qui répondrait parfaitement au besoin de gestion de bus (contraintes des horaires).

Démarche : Avant de commencer le projet, il nous paraissait intéressant de savoir s’ils existent une solution adaptée à la gestion des bus. Nous avons donc regardé sur des sites Internet des sociétés de transport françaises telles que la RATP, STY… Nous avons contacté les possesseurs des sites (telle que KEOLIS)ou les webmasters. Ils nous ont orientés vers les sociétés telles que XUAN ou PTV Online qui ont développé leur programme. Cependant il s’est avéré que ces logiciels sont les propriétés exclusives des sociétés de transport.

• Estimation du coût et étude de faisabilité par la sous-traitance : tâches spécifiques

Tâche 22 : Liste des sous-traitants possibles

Acteurs : Carlet, Landi

Charge : 6h

But : Synthétiser par une liste les différentes solutions de sous-traitance trouvées lors de la recherche documentaire afin de les présenter au maître d’ouvrage externe et de préparer la tâche suivante de prise de contact.

Démarche : Au cours de la recherche documentaire de solutions


existantes, on a relevé les informations concernant chaque possibilité. Lorsque la recherche documentaire est arrivé à son terme, on a regroupé les informations relevées en les ordonnant.

Tâche 23 : Prise de contact avec les sous-traitants


Charge : 30h

But : Obtenir des informations ou des briques logicielles permettant de répondre aux impératifs de l’application à créer.

Obtenir des devis de sous-traitance.

Démarche : A partir du listing des sous-traitants créée, on a utilisé un à un les différents contacts et collecter les informations pour pouvoir les comparer.

Tâche 24 : Recherche de nouveaux sous-traitants


Charge : 30h

But : Le but est de se concentrer sur les sociétés informatiques tarnaises afin de pouvoir les rencontrer et d’obtenir d’éventuels devis.

Démarche : A partir du listing des sous-traitants créée, on a utilisé un à un les différents contacts et collecter les informations pour pouvoir les comparer.

Tâche 25 : Discussion sur faisabilité technique


Charge : 10h

But : Après voir contacté les sous-traitants, il était nécessaire de vérifier qu’ils sont capables et qu’ils souhaitent réaliser l’application dont nous avons besoin dans un délais respectable et pour un budget raisonnable.

Démarche : Après avoir exposé notre projet et nos besoins aux sous-traitants, nous avons écouté leurs proposition en espérant que l’une d’elle conviendrait parfaitement à la réalisation du projet. Ce ne fut pas le cas, tous ne répondant qu’en partie à nos attentes, nous avons discuté avec les maîtres d’ouvrage d’une renégociation du CDCF .


Tâches 26 : Négociation de devis


Charge : 6h

But : L’objectif est ici très clair, il s’agit d’obtenir le meilleur prix pour les services de sous-traitants. En effet, ALBIBUS sera peut être prêt à investir dans l’application proposé par le projet et donc d’allouer un budget consacré au développement de la solution informatique, cependant ce budget sera limité et certainement modeste (~ 10000 euros). Il était donc indispensable de réduire le coût de développement à son minimum.

Démarche : Nous avons comparé les offres suivant les critères de qualité et coût. Nous avons sélectionné ceux qui ne dépassent pas notre plafond budgétaire et qui proposent une prestation proche de notre application. Puis parmi ces propositions nous avons essayé de négocier le meilleur tarif en faisant jouer la concurrence et en expliquant que le site d’ALBIBUS peut leur fournir une publicité gratuite en mentionnant leur collaboration et en leur accordant un bordereau publicitaire.

Tâches 27 : Recherche de la meilleure offre

Acteurs : Landi, Carlet, Rosières

Charge : 6h

But : Nous avons essayé d’évaluer l’offre la moins chère et la plus fidèle à notre cahier des charges.

Démarche :Nous avons reçu deux devis. Nous avons ensuite évaluer le temps de travail qu’il faudrait pour réaliser un tel projet d’après notre expérience. Nous avons comparer notre propre devis aux deux reçus.

• Recherche d’une solution en développement interne : tâches spécifiques

Tâche 29 : Modélisation du problème

Acteurs : Moghrabi, Mannheim, Rosières

Charge : 8h

But : Il s'agit de modéliser le réseau de lignes de bus et le comportement de ces derniers.

Démarche : A l'aide d'une cartographie d'Albi et de son réseau de bus (avec ses arrêts) nous avons modélisé le problème en utilisant la théorie des graphes.


Tâche 30 : Recherche d’algorithmes d’optimisation adaptés

Acteurs : Moghrabi, Mannheim, Rosières

Charge : 12h

But : La recherche d’algorithmes permet de concevoir la difficulté de programmation et la faisabilité d’un tel projet dans le cadre d’un développement en interne d’un logiciel de calcul d’itinéraires. Cependant après avoir modélisé le réseau d'ALBIBUS , on est revenu à modéliser un problème beaucoup plus simple pour résoudre le cœur de l'optimisation de trajet. Démarche : C’est grâce à l'aide de M. LAMOTHE qu’un algorithme à été développé pour modéliser le réseau d'ALBIBUS entier. Par la suite on s'est tourné vers le cours de recherche opérationnelle d'IFI2 pour identifier l'algorithme (Dijkstra) nous permettant de résoudre la forme simplifiée de notre problème d'optimisation.

Tâche 31 : Traduction de l’algorithme en langage informatique

Acteur : Moghrabi, Mannheim, Rosières

Charge : 12h

But : Il faut dans cette tâche que l’algorithme décidé et développé à l’étape 29 soit converti sous forme informatique.

Démarche : Nous avons choisi un langage de programmation connu des développeurs et adapté aux technologies de l’Internet.

Tâche 32 : Tests d’efficacité du programme

Acteur : Moghrabi, Mannheim

Charge : 13h

But : L’objectif est de déterminer si le programme fonctionne bien, de corriger les problèmes et d’évaluer les temps de réponse.

Démarche : Nous avons testé le programme sur différents exemples. Le programme avait des défauts, nous les avons corrigés. Ensuite nous avons testé le programme sur des cas de plus en plus importants afin d’évaluer le temps de réponse en fonction du temps.

• Finalisation du projet

Tâche 32 : Tests d’efficacité du programme

Acteur : Moghrabi, Mannheim

Charge : 40h


But : Le but est de développer l’application pour le modèle réel d’ALBIBUS

Démarche : Nous avons tout d’abord générer une base de données à partir du réseau et des horaires de passage de bus. Ensuite nous avons adapté le programme développé précédemment afin qu’il puisse chercher ses informations dans la base. Nous avons ensuite rajouté des conditions afin que le parcours proposé soit le meilleur selon nos critères. Nous avons travailler le programme pour qu’il affiche à l’utilisateur les actions qu’il devra faire pour réaliser correctement son parcours. Nous avons testé rapidement le programme.

Tâche 35 et 36 : Analyse de l'état du projet et détermination des suites du projet


Charge : 4h

But : Au terme de notre travail, il reste certaines parties à développer qui ne peuvent se faire sans l'attribution d'un véritable budget. Pour avoir une idée précise de ce qu'il reste à accomplir, il fut nécessaire d'expliciter l'état du projet et de donner les directives pour un éventuel futur projet.

Démarche : Après analyse de notre travail et discussion avec nos maîtres d'ouvrage, nous avons essayé de synthétiser la démarche à poursuivre et le travail qu'il reste à accomplir pour finaliser ce projet. Tout cela bien sûr n'a de sens que si ALBIBUS souhaite poursuivre ce projet pour le mener à terme en lui donnant des moyens financier.

4.3.2.6 Gestion des points "durs"

Nous appellerons points durs les problèmes liés à des éléments imprévus comme des retards ou à des concours de circonstances exceptionnelles.

Nous avons recensé les points durs suivants :

• Engorgement des salles informatiques de l’école pendant les heures projet.

Solution : soit travailler sur le système Unix, soit travailler chez soi.

• Retard au début pour la réunion avec le maître d’ouvrage extérieur M. DUBOIS. La réunion avec le directeur d’ALBIBUS a eu lieu seulement au bout de la troisième semaine. Cette réunion était indispensable pour démarrer le projet et réaliser le cahier des charges.

Solution : commencer la recherche documentaire et de sites traitant de l'optimisation de parcours sans attendre cette réunion.


• Longues attentes de réponses de la part des entreprises contactées pour envisager la sous-traitance.

Solution : relancer régulièrement et par téléphone les contacts qui ne répondaient pas.

• Difficultés techniques dans le développement interne d'une solution.

Solution : effectuer des recherches documentaires ou à travers des forums et solliciter l’aide des experts (M. OTTON, M. Gaborit).

• -Difficultés dans les négociations avec des sous-traitants dues au fait qu'ALBIBUS ne prévoit pas de réaliser ce projet dans l'immédiat et n'a pas encore de budget alloué pour ce projet.

Solution : les contacts avec les sous-traitant doivent se faire avec prudence lors de l'évocation de l'obtention du projet, il ne faut parler que de devis sans trop s'engager, d'autant plus qu'ALBIBUS est soumis à la réglementation des marchés publics.

4.3.3 Gestion de la documentation

4.3.3.1 Les différents types de documents

Il existe différents types de documents que nous conservons.

Les documents internes :

• les comptes-rendus de séance,

• les rapports (d’avancement et final),

• le cahier des charges,

• les synthèse de documents.

Les documents externes :

• la documentation d’organismes,

• la documentation d’entreprises,

• la documentation technique de langages informatiques,

• les rapports d’élèves de l’école,

• des périodiques et des ouvrages.

Autres :

• Correspondance (lettres, fax, mails)


• Internet

4.3.3.2 Codification des documents

Les documents sont indexés selon le codage suivant et recensés sur une liste tenue à jour :

• Comptes-rendus : CR + date

exemple : CR-070102 pour le compte rendu du 7 janvier 2002.

• Correspondances : L (Lettre), F (Fax) ou E (Email) + date

exemple : E-070102

• Rapports ou ouvrages : I (Interne ou E (Externe) + Te (Techmique), Ec (Ecomomique) ou Gp (Gestion de Projet) + date

exemple : E-Gp-070102

• Documentations diverses : E (Externe) + EN (Entreprise), MO (Maître d'ouvrage) ou ST (sous-traitants) + Te (Technique) ou Ec (Economique) + Date

exemple : E-EN-Te-070102

4.3.3.3 Classement des documents

Tous les documents informatiques sont imprimés pour être communiqués à l'ensemble du groupe et sont ensuite archivés. Ils doivent être tout de même conservés par leur auteur pour une éventuelle modification.

En interne, tous les documents sont disponibles dans la salle projet. Ils sont classés suivant les quatre catégories précédentes dans des boîtes en carton.

Les comptes-rendus de séance sont diffusés au maître d'ouvrage, M. OTTON, à la séance suivante après avoir été validé par le chef de projet. L’annexe contient tous les comptes-rendus réalisés.

Enfin, le cahier des charges et les rapports finaux seront communiqués à ALBIBUS lors de la présentation orale du projet à la municipalité d'Albi.


Conclusion

L’application qui faisait l’objet de notre projet n’est à ce jour pas encore finalisée.

Cependant, il est juste de remarquer que Monsieur Dubois, notre maître d’ouvrage, n’attendait pas de nous un programme qui fonctionne parfaitement compte tenu des difficultés techniques que comporte la réalisation de ce type d’application. Il attendait de nous une étude plus générale qui consistait à balayer l’ensemble des solutions possibles susceptibles d’aboutir à la finalisation de cette application.

C’est dans cette voie que nous nous sommes finalement dirigés afin de présenter à notre maître d’ouvrage un panel qui explique précisément pourquoi une solution aurait pu aboutir ou non. Ainsi nous avons exploré trois pistes différentes : la recherche d’une solution existante, le recours à la sous-traitance et le développement en interne.

La première a été infructueuse du fait de l’absence d’un logiciel de calcul d’itinéraire adapté sur le marché. Les sociétés de bus proposant ce service sur Internet l’ont toutes développé en exclusivité. Qui plus est, le statut de régie municipale d’ALBIBUS, qui témoigne d’une volonté de garder une gestion indépendante du réseau, ne permet pas de faire appel aux solutions existantes développées par les grands groupes de transport comme KEOLIS.

Nous avons donc été amené à rechercher des entreprises intéressées par la finalisation de l’application dans le cadre d’une sous-traitance. Le coût de la prestation d’une agence Web n’est pas très élevé et n’exclut donc pas le recours à la sous-traitance qui a l’avantage, comparé au développement interne, de proposer une maintenance et une mise à jour de l’application pour les années à venir.

Nous étions dès le début du projet attiré par le côté technique et pratique du projet. Néanmoins il a fallu se rendre à l’évidence que le développement interne de l’application était techniquement difficilement réalisable compte tenu de nos compétences et du temps alloué. Grâce à l’aide de notre maître d’ouvrage interne et d’un enseignant chercheur du centre génie industriel, nous sommes parvenu à un résultat intermédiaire satisfaisant. L’application développée réalise le calcul du plus court chemin d’un point à un autre. Cependant il reste quelques tâches supplémentaires à réaliser.

Nous pensons qu’un stagiaire de l’école ou une agence web sous-traitante pourraient achever le développement. En effet, le moteur de calcul du logiciel est réalisé. Il reste à le tester entièrement pour en corriger les éventuels bogues puis à créer l’interface entre l’application et le site Internet.


Bibliographie

Contacts :

Pierre BASTOUL

Gérant O10c Informatique

2, rue Puits de la Grâce

81000 ALBI

Julien ADELMAN

Gérant WZ Conseil

Frédéric MUNOZ

Ingénieur à WZ Conseil

Impasse croix de Clary

81000 ALBI

Ouvrages :

• ROSEAUX, Exercices et problèmes résolus de recherche opérationnelle, Tome 1, Graphes : leurs usages, leurs algorithmes, Paris, Masson, 1991, p.120-123.

• CORMEN (Thomas), LEISERSON (Charles), RIVEST (Ronald), Introduction à l’algorithmique, Paris, Dunod, 1994, p504-568.

• SCHWARTZ (Randal L.) et CHRISTIANSEN (Tom), Introduction à Perl, 2ème édition, Paris, O’Reilly, 1999, 305 p.

• KERNIGHAN (Brian W.) et RITCHIE (Denis M.), La langage C, Norme ANSI, 2ème édition, Paris, Masson, 1997, 280 p.

Articles de périodiques

• Un petit clic pour KEOLIS, C.N., La Vie du Rail – 31 octobre 2001, p41

• SNCF.COM trois petits clics pour un choc commercial, Pascal GRASSART, La vie du Rail – 9 mai 2001, p26

• Toulouse ligne par ligne sur tous les réseaux, A.L.R., La vie du Rail – 10 octobre 2001, p41

Sites Internet

• www.sty.fr : Site de la Société des Transports Yonnais

• www.keolis.fr : Site de la Société KEOLIS

• www.albibus.com : Site de la régie municipale des transports urbains d’Albi


Table des illustrations

Figure 1 : Parts de marché de chaque éditeur de SIG 16

Figure 2 : Interface de saisie utilisateur du site sty.fr 18

Figure 3 : Outil de cartographie du stie sty.fr 18

Figure 4 : Liaisons entre les stations 30

Figure 5 : Départ-Réseau-Arrivée 31

Figure 6 : Exemple de graphe orienté 31

Figure 7 : Passage d’un graphe orienté à sa matrice associée P 34

Figure 8 : Résultats de l’algorithme pas à pas 35

Figure 9 : Evolution du temps de réponse en fonction du nombre d'arrêts. 36

Figure 10 : Schéma relationnel 37

Figure 11 : Exemple d'un saut d'arrêt sur la ligne 1 38


Annexes

Annexe 1 : Analyse du site Web d’Albibus 61

Annexe 2 : Liste des SSII du Tarn 62

Annexe 3 : Programme en C 63

Annexe 4 : Commandes de création des tables de la base 67

Annexe 5 : Programme de construction de la matrice P 69

Annexe 6 : Algorithme de Dijkstra codé en PHP4 73

Annexe 7 : Programme en Perl 75

Annexe 8 : Cahier de Charges Fonctionnel 82

Annexe 9 : Organigramme des tâches 89

Annexe 10 : Les diagrammes de Gantt 91

Annexe 11 : Pert 95

Annexe 12 : Diagramme des ressources 97

Annexe 13 : Comptes-Rendus 103


Annexe 1 : Analyse du site Web d’Albibus

Le site d’Albibus se trouve sur l’adresse Internet : www.albibus.com. La page de présentation donne accès à plusieurs rubriques. Celle qui nous intéresse est la page des horaires. Au passage des erreurs de codage des caractères accentués ont été relevées.

Description du contenu de la rubrique « Horaires »

Les horaires sont consultables de deux façons : soit en précisant le numéro de la ligne de bus que l’on souhaite prendre, soit en cliquant sur les stations de bus représentées sur une carte d’Albi. Ensuite dans chacun des cas, l’utilisateur doit préciser le sens de parcours de la ligne et la période (« scolaire » ou « vacances »).

Si l’utilisateur utilise la carte cliquable, il doit parfois définir quelle ligne il souhaite prendre si l’arrêt est parcouru par plusieurs lignes. En fin de compte la carte permet seulement de pouvoir se repérer pour sélectionner le bus à prendre.

Les sélections précédentes doivent normalement faire afficher une page sur laquelle figure les horaires de passage des bus pour tous les arrêts de la ligne. Cependant, la plupart des liens on l’air d’être faussés. Les tables que nous avons vues sont figées et difficiles à lire à cause de l’importance des données.

Fonctionnement de l’affichage des horaires

Le site s’appuie sur des pages statiques contenant tous les horaires des arrêts. Visiblement, ces pages ont été crées par un tableur (Excel) afin de permettre une mise à jour facile.

L’absence de bases de données rend difficilement exploitables ces données pour réaliser le travail demandé. Il sera ainsi souhaitable d’utiliser un système de gestion de bases de données pour pouvoir exploiter les horaires.

L’état actuel du site semble inintéressant pour réaliser le projet. Dans un premier temps il serait souhaitable de reprendre une partie du travail effectué par le stagiaire.


Annexe 2 : Liste des SSII du Tarn

NOM ADRESSE TELEPHONE E-MAIL SITE

L’ATELIER 7 7 place Dom Devic

81540 SORÈZE

05 63 50 88 96 [email protected] www.latelier7.com

CD-XP 32 avenue d'Albi

81100 CASTRES

05 63 59 69 68 [email protected]

[email protected]

www.cd-xp.com

ACONCEPT

MULTIMEDIA


www.aconceptmultimedia.fr

LCM (Logiciels Clé en Main)

Z.I. Albi - ST Juery 9, rue Jean Mermoz

81160 St Juery


Stéphane Herrenschmidt

www.lcm81.com

o10c Webgineering

9 rue Saint Antoine

81000 ALBI

05 63 49 27 27 [email protected] www.o10c.fr

B@t’INET Formulaire à compléter sur le site Internet www.cyberfoire.com/batinet

BASTARD INFORMATIQUE

Les Loumans 81700 GARREVAQUES

05 63 75 06 03 [email protected] www.bastard-info.com

Io Micro Systèmes

En Coste

81440 Puycalvel

05 63 42 10 15 [email protected] iomicro.org

Cabinet Logisud

9, Chemin du Clos d'Armand 81150 TERSSAC

05.63.48.42.70 [email protected] www.logisud.com

Westimages, Studio Multimédia

Formulaire à compléter sur le site Internet www.westimages.com

Génér@tion Internet

91 Av de Lattre de Tassigny

81000 Albi France

05.63.54.96.11 [email protected]

www.vitrinet.com

Musty Chemin Mascrabières 81000 ALBI

05.63.77.33.90 [email protected] musty.net

AbLink 32, Place de la Courtade

81600 GAILLAC

05.63.33.60.70 [email protected] www.ablink.com

APGI La Maynadié

81350 ANDOUQUE

05.63.56.55.69 [email protected] www.apgi.net

Source : Chambre du Commerce et de l’Industrie d’Albi, www.albi.cci.fr


Annexe 3 : Programme en C

#include <stdio.h>

#include <stdlib.h>

#include <float.h>

/* Déclaration des variable */

#define no 6 /* no correspond au nombre de sommets du graphe */

double D[no]; /* Ce tableau contient les temps de parcours minimaux */

double P[no][no]; /* P est la matrice valuée associée au graphe */

int C[no]; /* C contient les prédécésseurs des sommets pour le chemin le plus rapide */

int E[no]; /* E permet de connaître les points non-selectionnés */

double a; /* a est une variable aui permettra de prendre le point de point minimal de E (non séléctionné) */

int c;

int t; /* t est une variable qui prendra la valeur des numéros des sommets de E */

int b; /* b est le numéro de sommet tel que son point soit minimal */

int i,j,k; /* ce sont les variables d'incrémentation */

/* la fonction valeur permet de lire le tableau P à partir d'un fichier */

void valeur(char filename[]){

FILE * fichier;

/* ouverture du fichier en lecture */


fichier = fopen(filename, "r");

if (fichier == NULL) {

printf ("Impossible d'ouvrir le fichier '%s'\n",filename);

exit(1);

}

for (i=0;i<no;i++){ /* on lit les valeurs successives du fichier */

for (j=0;j<no;j++){ /* que l'on rentre ainsi dans le tableau P */

fscanf(fichier, "%lf",&P[i][j]);

}

}

/* fermeture du fichier */

fclose(fichier);

}

/* le programme principal */

int main()

{

printf("selectionner le point de départ (de 0 à %u):",no-1);

scanf("%u",&c);

printf("\n");

valeur("data"); /* cet appel à la fonction valeur permet d'initialiser le tableau P avec les valeurs contenues dans le fichier data */

/* initialisation des tableaux E, D et C */

for(i=0;i<no;i++){

E[i]=i;

}

E[0]=-1;

/* E contient tous les points du graphe sauf celui de départ : le point 0. Lorsque un point i est sélectionné, on met -1 -> E[i] */


for(i=0;i<no;i++){

D[i]=P[c][i]; /* D contient les temps entre le point 0 tous les autres */

C[i]=c; /* Tous les points ont pour prédécesseur 0 */

}

for(k=0;k<no;k++){

a=FLT_MAX; /* a a un valeur infinie au début de chaque boucle */

for(i=0;i<no;i++){

t=E[i]; /* t prend les valeurs des numéros de sommets */

if((t>=0)&&(D[t]>=0)&&(a>D[t])){ /* si( les sommets ne sont pas sélectionnés ET qu'il existe un arc entre le sommet et le point de poids minimum ET a et supérieur à la valeur de l'arc) */

b=t; /* alors t -> b : à la fin ce cette boucle b sera le sommet dont le poids est minimal */

a=D[t]; /* D[t] -> a : et a contiendra la valeur du poids */

}

}

E[b]=-1; /* on selectionne le sommet contenu dans b en mettant -1 -> E[b] */

for(j=1;j<no;j++){

t=E[j]; /* t prend encore les valeurs des numéros de sommets */

if((t>=0)&&(P[b][t]>=0)&&((D[t]<0)||(D[t]>(D[b]+P[b][t])))){/* si( les sommets ne sont pas sélectionnés ET qu'il existe un arc entre les sommets b et t ET ( qu'il n'existait pas d'arc entre le précédent sommet séléctionné et t OU que le temps pour aller en t plus court avec b prédécesseur de t)) */

D[t]=D[b]+P[b][t]; /* alors on ajuste le poids du sommet t à partir du sommet b */

C[t]=b; /* le prédécesseur de t devient b */

}

}


}

/* on affiche les résultats */

for(i=0;i<no;i++){

if(D[i]>=0){ /* s'il est possible d'aller au point i */

printf("%u : %u : %lf\n",i,C[i],D[i]); /* alors on affiche le numéro du point, son prédécesseur et le temps mis à partir du point 0 avec le chemin le plus court */

}else{

printf("%u : impossible d'y aller\n",i); /* sinon on affiche le numéro du point et on dit qu'il est impossible d'y aller */

}

}

return 0;

}


Annexe 4 : Commandes de création des tables de la base

# MySQL dump 8.12

#

# Host: localhost Database: mannheim

#--------------------------------------------------------

# Server version 3.22.27

#

# Table structure for table 'arret'

#

CREATE TABLE arret (

id int(11),

num_ligne int(11),

sens int(11),

nom_arret text,

n_arret int(11)

);

#

# Table structure for table 'horaire'

#

CREATE TABLE horaire (

num_arret int(11) DEFAULT '0' NOT NULL,

num_bus int(11) DEFAULT '0' NOT NULL,

heure time DEFAULT '00:00:00' NOT NULL,

periode int(11) DEFAULT '0' NOT NULL,

PRIMARY KEY (num_arret,heure,periode,num_bus)

);

#

# Table structure for table 'lignes'


#

CREATE TABLE lignes (

id int(11),

nom_ligne text

);


Annexe 5 : Programme de construction de la matrice P

#include <stdio.h>

#include <stdlib.h>

#define no 432

int i,j;

int data[no][no];

int P[1408][2];

int Cas[23][3];

int a,b;

int D[13];

int c,d;

void lirefichier(char filename[])

{

FILE *fichier;



printf ("Impossible de lire le fichier '%s'\n",filename);

exit(1);

}

for (i=0;i<1408;i++){ /* on lit les valeurs successives du fichier */

for (j=0;j<2;j++){ /* que l'on rentre ainsi dans le tableau data */

fscanf(fichier,"%d",&P[i][j]);

}

}

fclose(fichier);

}

void lirefichier2(char filename[])


{

FILE *fichier;




exit(1);

}


for (j=0;j<3;j++){ /* que l'on rentre ainsi dans le tableau data */

fscanf(fichier,"%d",&Cas[i][j]);

}

}

fclose(fichier);

}

void lirefichier1(char filename[])

{

FILE *fichier;




exit(1);

}

D[0]=0;


fscanf(fichier, "%d",&D[i]);

}

fclose(fichier);

}


void ecrirefichier(char filename[])

{

FILE *fichier;

fichier = fopen(filename, "w");


printf ("Impossible d'ecrire dans le fichier '%s'\n",filename);

exit(1);

}

for (i=0;i<no;i++){ /* on lit les valeurs successives du fichier */

for (j=0;j<no;j++){ /* que l'on rentre ainsi dans le tableau data */

fprintf(fichier, "%d ",data[i][j]);

}

fprintf(fichier, "\n");

}

fclose(fichier);

}

int main (){

lirefichier1("arret");

/*for (i=0;i<no;i++){ on lit les valeurs successives du fichier */

/* for (j=0;j<no;j++){ que l'on rentre ainsi dans le tableau data */

/* data[i][j]=-1;

}

}*/

for(i=0;i<no+1;i++){

data[i][i]=1;

}

lirefichier("liaisons");


for(i=0;i<1408;i++){

a=P[i][0]-1;

b=P[i][1]-1;

data[a][b]=1;

}

c=0;d=D[1];

for(i=0;i<12;i++){

for(j=c;j<d-1;j++){

data[j][j+1]=1;

}

c=c+D[i+1];

d=d+D[i+2];

}

lirefichier2("cas");

for(i=0;i<23;i++){

a=Cas[i][0]-1;

b=Cas[i][1]-1;

c=Cas[i][2];

data[a][b]=c;

}

ecrirefichier("data1");

return 0;

}


Annexe 6 : Algorithme de Dijkstra codé en PHP4

<?

function reset_temp($var)

{

return(0);

}

$S=array(0,1,2,3,4);

$P=array(

array(0,19,200,3,1000),

array(1000,0,5,1000,6),

array(1000,1000,0,1000,17),

array(1000,1000,4,0,8),

array(1000,1,1000,1000,0));

$E[0]=0;

for ($i=1;$i<5;$i++)

{

$D[$i]=$P[0][$i];

$C[$i]=0;

}

for ($i=0;$i<4;$i++)

{

$SmE=array_diff($S,$E);

foreach($SmE as $c => $v)

{

$temp[$c]=$D[$v];

}

$Dmin=min($temp);

$t=min(array_keys($temp,$Dmin));

$E[$i+1]=$t;

$SmE=array_diff($S,$E);

foreach($SmE as $s)


{

$temp1=$D[$t]+$P[$t][$s];

if ($temp1<$D[$s])

$C[$s]=$t;

$D[$s]=min($D[$s],$temp1);

}

$temp = array_filter($temp,"reset_temp");

}

print_r($C);

?>


Annexe 7 : Programme en Perl

#!/usr/bin/perl

#ON SE CONNECTE A LA BASE DE DONNEES

use DBI();

$MaConnexion=DBI->connect("DBI:mysql:database=mannheim;host=localhost");

$no=432; #NOMBRE D'ARRETS

#CETTE FONCTION CONVERTIT DES SECONDE EN HEURE (DE TYPE HH:MM:SS)

sub sectoheure{

$date = $_[0];

$cut[0]= ($date -($date % 3600))/3600; #UNE DIVISION ENTIERE DES SECONDES PAR 3600 POUR AVOIR LE NOMBRE D'HEURES

$cut[1]= (($date % 3600) -(($date % 3600)%60))/60; #UNE DIVISION ENTIERE DU RESTE PAR 60 POUR AVOIR LE NOMBRE DE MIN

$cut[2]= $date % 60; #LE RESTE DE LA DIVISION ENTIERE PAR 60 POUR AVOIR LES SECONDES

return join(":",@cut); #RETOUR DES HEURES, MIN, SEC SEPARES PAR :

}

#CETTE FONCTION CONVERTIT DES HEURES EN SECONDES

sub heuretosec{

@cut = split(/:/,$_[0]); #DECOUPE L'HEURE EN CHAMPS SEPARES LA OU IL Y A :

return $cut[0]*3600 + $cut[1] * 60 + $cut[2] ; #RETOUR DU NOMBRE DE SEC

}

#CETTE FONCTION ENVOIE DES REQUETES A LA BD POUR AVOIR LE PROCHAIN HORAIRE SUR UN ARRET

sub base{

$dateDB = sectoheure($_[1]); #CONVERTION DU NOMBRE DE SEC EN HEURE POUR FAIRE LA REQUETE


$MonOrdre=$MaConnexion->prepare("select min(heure) from horaire where num_arret=$_[0] and heure>='$dateDB'");

$MonOrdre->execute;

$result = $MonOrdre->fetchrow_array;

if(defined($result)) #CA NE MARCHE PAS ON VEUT : SI LA BD RENVOIE UN HORAIRE

{return heuretosec($result); #ON RETOURNE L'HORAIRE

}else{ #SINON

return -1; #ON RETOURNE -1 POUR DIRE QUE RIEN N'A ETE RENVOYE

}

}

#CETTE FONCTION ENVOIE DES REQUETES A LA BD POUR OBTENIR EN FONCTION D'UN ARRET, DE L'HEURE DE PASSAGE

#LE NOM DE L'ARRET, LA LGINE, LE SENS ET LE BUS

sub base2{

$MonOrdre=$MaConnexion->prepare("select arret.nom_arret,arret.num_ligne,arret.sens,horaire.num_bus from arret, horaire where arret.id=$_[0] and arret.id=horaire.num_arret and horaire.heure='$_[1]'");

$MonOrdre->execute;

return $MonOrdre->fetchrow_array; #ON RETOURNE DIRECTEMENT LE RESULTAT CAR ON EST SUR QU'IL N'EST PAS VIDE

}

#CETTE FONCTION COMPLETE LA MATRICE ASSOCIEE AU RESEAU @MAT_RESEAU A PARTIR DES DONNEES CONTENU DANS LE FICHIER "data1"

sub valeur{

open(IN,"data1")||die("Ne peut pas ouvrir le fichier\n"); #ON OUVRE LE FICHIER

while(<IN>){ #TANT QU'IL Y A DES VALEURS

@tmp= split; #ON PREND LIGNE PAR LIGNE EN DECOUPANT LES LIGNES LA OU IL Y A DES ESPACES

push @MAT_RESEAU, [@tmp]; #ON RAJOUTE LA LIGNE SELECTIONNE A LA MATRICE ASSOCIEE AU RESEAU

}


close(IN); #ON FERME LE FICHIER

}

#DEBUT

valeur(); #ON ENVOIE LA FONCTION VALEUR()

($dep,$arr)=($ARGV[0],$ARGV[1]); #L'UTILISATEUR DOIT SAISIR LA STATION DE DEPART ET D'ARRIVEE LORS DE L'EXECUTION

$heure=$ARGV[2]; #IL SAISIT SON HEURE DE DEPART

$heure=heuretosec($heure); #ON TRANSFORME CETTE HEURE EN SECONDE

for($I=0;$I<$no;$I++)

{$NON_SELECT[$I]=$I;} #ON CONSTRUIT LA MATRICE DES SOMMETS NON SELECTIONNEES

$NON_SELECT[$dep]=0; #ON ELEVE LE SOMMET SELECTIONNE

shift(@NON_SELECT);

for($I=0;$I<$no;$I++)

{if($MAT_RESEAU[$dep][$I]>0){ #SI LE PASSAGE EST POSSIBLE

$HORAIRE_MARQUE[$I]=base($I+1,$heure);#ON RENTRE L'HEURE DU SOMMET I DANS LE TABLEAU @HORAIRE_MARQUE

$PRECEDENT_MARQUE[$I]=$dep; #ON RENTRE L'HEURE DU SOMMET I DANS LE TABLEAU @PRECEDENT_MARQUE

}else{

$HORAIRE_MARQUE[$I]=-1; #SINON ON MET -1 DANS CES 2 TABLEAUX

$PRECEDENT_MARQUE[$I]=-1;

}

}

for($k=0;$k<$no-1;$k++)

{$a= 24*3600;


#ON SELECTIONNE LE SOMMET DONT @HORAIRE_MARQUE EST LA PLUS PETITE

foreach $t(@NON_SELECT){ #POUR CHAQUE SOMMET NON SELECTIONNE

if(($HORAIRE_MARQUE[$t]>=0)&&($a >$HORAIRE_MARQUE[$t])) #SI ON PEUT Y ALLER

{$b=$t; #ON REGARDE LEQUEL A L'HEURE LE PLUS FAIBLE

$a=$HORAIRE_MARQUE[$t];

}

}

if($b==$arr) #SI L'ARRIVEE EST SELECTIONNE

{last;} #ON SORT DE AL BOUCLE

#ON SORT DU TABLEAU @NON_SELECT LE SOMMET B QU'ON VIENT DE SELECTIONNER

$f=@NON_SELECT;

$l=0;

while($l<$f){

if($NON_SELECT[$l]==$b){

$d=$l;

last;}

$l++;

}

($NON_SELECT[0],$NON_SELECT[$d])=($NON_SELECT[$d],$NON_SELECT[0]);

shift(@NON_SELECT);

#ON RECALCULE LES SOMMETS SUIVANTS EN FONCTION DU NOUVEAU SOMMET SELECTIONNE

foreach $t(@NON_SELECT) #POUR CHAQUE SOMMET NON SELECTIONNE

{if($MAT_RESEAU[$b][$t]>0){ #SI ON PEUT ALLER DE B A T

$var=base($t+1,$HORAIRE_MARQUE[$b]); #ON CHERCHE DANS LA BD L'HORAIRE SUIVANT DE T


if(($HORAIRE_MARQUE[$t]<0)||($HORAIRE_MARQUE[$t]>$var)) #SI LA MARQUE DE L'HORAIRE DE T EST -1 OU SI ELLE EST > A L'HEURE RETOURNEE PAR LA BD

{$HORAIRE_MARQUE[$t]=$var; #ALORS LA MARQUE DE L'HORAIRE EST REACTUALISE PAR CELLE DE LA BD

$PRECEDENT_MARQUE[$t]=$b; #ON MET DANS LA MARQUE DE L'ANTECEDENT LE SOMMET B

}

}

}

}

#ON VA CREER LE CHEMIN POUR ALLER DU DEPART A L'ARRIVEE

$I=$arr; #ON INITIALISE I AU POINT D'ARRIVEE

if($HORAIRE_MARQUE[$arr]>0){ #SI L'HORAIRE SUR LE POINT D'ARRIVEE EST POSITIVE

for($J=0;$J<$no;$J++){ #ALORS POUR J ALLANT DE 0 A no-1

$CHEMIN[$J]=$I; #LE TABLEAU CHEMIN EST CONSTITUE DES VALEURS DE I

if($I==$dep){ #SI I EST LE DEPART

last;} #ALORS ON SORT DE LA BOUBLE

$I=$PRECEDENT_MARQUE[$I];#I DEVIENT LE PRECEDENT DU SOMMET I

}

@CHEMIN=reverse(@CHEMIN); #LE CHEMIN EST AINSI L'INVERSE DU TABLEAU CHEMIN CREE AU-DESSUS

$taille=@CHEMIN;

$heuredep=sectoheure($HORAIRE_MARQUE[$dep]);

@dep=base2($dep+1,$heuredep);#ON REMPLIT LES TABLEAUX PAR LES RESULTATS DE LA FONCTION BASE

$heurearr=sectoheure($HORAIRE_MARQUE[$arr]);

@arr=base2($arr+1,$heurearr);

if($taille>1){ #SI LE CHEMIN A PLUS D'UNE STATION

shift(@CHEMIN);#ON ENLEVE LE SOMMET DE DEPART

foreach $J (@CHEMIN){ #POUR CHAQUE SOMMET DU CHEMIN


$heure=sectoheure($HORAIRE_MARQUE[$J]); #ON TRANSFORME L'HORAIRE (EN SEC) EN HEURE

@AA=base2($J+1,$heure); #ON REMPLIT LE TABLEAU @AA PAR LES RESULTATS DE LA FONCTION base2

if(($J==$CHEMIN[0])&&($AA[0] ne $dep[0])){#SI LE PREMIER POINT DU @CHEMIN N'A PAS LE NOM DU DEPART

print("Partir de $dep[0] à $heuredep\n");#ALORS ON ECRIT QUE L'ON PART DE CETTE STATION

print("Prendre la ligne no : $dep[1] dans le sens $dep[2]\n");

if($taille==2){print("Vous arriverez à $AA[0] à $heure\n");

last;}

($arret,$ligne,$sens,$bus)=@AA;#ON RETIENT LE NOM D'ARRET, LA LIGNE, LE SENS ET LE BUS

}elsif($AA[0] eq $dep[0]){#SINON SI LE NOM DE L'ARRET EST CELUI DU POINT DE DEPART

if($taille==2){print("Restez où vous êtes à $dep[0]\n");

last;}

print("Partir de $AA[0] à $heure\n");#ALORS ON ECRIT QUE L'ON PART DE CETTE STATION

print("Prendre la ligne no : $AA[1] dans le sens $AA[2]\n");

($arret,$ligne,$sens,$bus)=@AA;

}elsif($AA[0] eq $arr[0]){#SINON SI ON EST AU POINT D'ARRIVEE

print("Vous arriverez à $AA[0] à $heure\n");#ON ECRIT QUE L'ON EST ARRIVE A CETTE STATION

last;#ON QUITE LA BOUCLE

}elsif($AA[1]!=$ligne){#SINON SI LE NUMERO DE LIGNE CHANGE PAR RAPPORT AU PRECEDENT

print("Changer de ligne à $AA[0] à $heure\n");#ON ECRIT QUE L'ON CHANGE DE LIGNE



}elsif($AA[2]!=$sens){#SINON SI LE NUMERO DU SENS CHANGE PAR RAPPORT AU PRECEDENT

print("Changer de sens à $AA[0] à $heure\n");#ON ECRIT QUE L'ON CHANGE DE SENS




}elsif($AA[3]!=$bus){#SINON SI LE NUMERO DE BUS CHANGE PAR RAPPORT AU PRECEDENT

print("Changer de bus à $AA[0] à $heure\n");#ON ECRIT QUE L'ON CHANGE DE BUS



}else{


}

}

}else{

print("Restez où vous êtes à $dep[0]\n");

}

}else{ #SI ON NE PEUT PAS ALLER A L'ARRIVE

print("Impossible d'aller à $arr[0] en partant de $dep[0]\n"); #ON AFFICHE LE MESSAGE

}

$MaConnexion->disconnect; #ON SE DECONNECTE DE LA BD

__END__


Annexe 8 : Cahier de Charges Fonctionnel








Annexe 9 : Organigramme des tâches



Annexe 10 : Les diagrammes de Gantt





Annexe 11 : Pert



Annexe 12 : Diagramme des ressources







Annexe 13 : Comptes-Rendus

Documents

Projet 8 : Enrichissement du site Internet ALBIBUS par une