Les travaux effectués dans cette thèse industrielle concernent l'amélioration du calculateur d'itinéraire de Cityway, société spécialisée dans les technologies de l’information appliquées à la mobilité.Nous avons d'abord établi un état de l'art exhaustif, accompagné d'une mise en perspective de l'existant Cityway avec celui-ci. Cela nous a permis d'aider l'entreprise à prendre du recul sur son produit et de justifier les axes de recherche choisis pour nos travaux.Nous nous sommes ensuite intéressés à l'aspect multicritère du problème. En effet, le calculateur, basé sur l'algorithme de Dijkstra, permet de trouver des trajets minimisant une somme pondérée de critères. Nous avons développé un algorithme multilabel permettant de conserver et étendre plusieurs labels au même nœud. Malgré une légère augmentation des temps de calculs, des résultats satisfaisants ont été obtenus dans une application bicritère de ce nouvel algorithme.Nous avons également travaillé sur la génération et la sélection de trajets alternatifs. La génération s'appuie sur les algorithmes monolabel ou multilabel. La sélection s'appuie quant à elle sur la définition d'une distance entre les solutions et des méthodes de regroupement.Enfin, nous nous sommes intéressés à l'optimisation du calcul du critère lexicographique de durée minimale dans le cas bicritère. Pour qu'un trajet soit intéressant, il faut qu'il soit optimal sur les critères usuels, mais aussi qu'il dure le moins longtemps possible. L'utilisation de certaines propriétés sur ce critère permet de réduire des temps de calcul initialement trop longs. / The work carried out in this industrial PhD aims at improving the route planner of Cityway, a company specialized in information technologies applied to mobility. We first established an exhaustive state of the art, and compared it to the existing Cityway product. This allowed us to help the company take a step back from its urgent needs, and justify the research guidelines chosen for our work.We then looked at the multi-criteria aspect of the problem. Indeed, the trip planner, based on the Dijkstra algorithm, makes it possible to find paths minimizing a weighted sum of criteria. We have developed a multilabel algorithm to maintain and extend multiple labels at the same node. Despite a slight increase in computation time, satisfactory results were obtained in a bicriteria application of this new algorithm.We also worked on the generation and selection of alternative routes. The generation algorithm relies on the existing monolabel or newly developed multilabel algorithms. The selection algorithm is based on the definition of a distance between trips and adaptations of existing clustering algorithms to this specific case.Finally, we were interested in what we called the lexicographic criterion. For a trip to be interesting, it must be optimal on the usual criterion of earliest arrival, and, for trips arriving at the same time, on the latest departure criterion. The use of certain properties on this criterion makes it possible to reduce computation times on the bicriteria case.
| Identifer | oai:union.ndltd.org:theses.fr/2017LYSEM025 |
| Date | 12 October 2017 |
| Creators | Iglesias, Alexandre |
| Contributors | Lyon, Feillet, Dominique |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0025 seconds