Optimization of sea routes: a multi-criteria and time-dependent resolution system
Optimisation des routes maritimes : un système de résolution multicritère et dépendant du temps
Résumé
Maritime charter companies try to use weather forecast in order to optimize the journeys of their fleet. Let consider a boat transporting merchandise (or goods) from a port to another. Given the date and time of departure and trying to minimize fuel consumption, determining the best route to take is a difficult problem in the meaning of complexity theory. Moreover, the best route likely changes during the journey leading to an even more difficult problem. To tackle this type of issues, many routing software are available. However, to our knowledge, the state of the art still lacks of algorithms capable of efficiently solving the problem while considering multiple and sometime contradictory criteria.
The aim of the this PhD thesis is to build a relevant modeling framework to solve this problem as well as to develop algorithms to be used and validated in industrial conditions.
The first task undertaken was the development of a methodology to format raw data, mainly spatial and weather data, into usable input data for mathematical model. This first step was essential as it conditioned which algorithms could be used, and consequently their efficiency. We chose to model the problem as a graph that takes time into account.
The second task was the development of a multi-objective and time dependent algorithm. This algorithm identifies pareto-optimum paths within the graph.
A third work focused on processing the paths in order to optimize speed during the whole journey, and as a consequence, fuel consumption.
Finally, we present an operational software that includes all these developments. This software was used to experimentally validate the developed model and algorithms, using real data.
Les compagnies d'affrètement maritime cherchent à utiliser les prévisions météorologiques en vue d'optimiser les déplacements de leur flotte. En effet, si un bateau doit amener des marchandises depuis un port d'origine jusqu'à un port de destination, en partant à une date donnée, et ce, tout en veillant à minimiser la consommation de carburant, la détermination de la meilleure route à emprunter constitue un problème difficile au sens de la théorie de la complexité. De plus, cette meilleure route peut évoluer pendant le trajet, ce qui rend le problème pratique encore plus complexe. Pour répondre à ce type de problématique, de nombreux logiciels de routage existent, mais dès lors qu'il s'agit de prendre en considération plusieurs critères qui parfois sont contradictoires, on se rend compte de
l'absence dans l'état de l'art d'algorithmes qui résoudraient efficacement ce problème.
L'objectif de cette thèse est de répondre à cette problématique en proposant un cadre de modélisation adéquat et des algorithmes qui devront être validés dans des conditions industrielles.
Le premier travail réalisé porte sur la mise en place d'une méthodologie permettant de transformer les données brutes récupérées en entrée (principalement les données géographiques et météorologiques), en un modèle mathématique exploitable. Cette première étape est essentielle puisqu'elle conditionne ensuite les algorithmes utilisés, et donc leur efficacité. Ainsi, nous choisissons de modéliser le problème sous la forme d'un graphe qui
prend en compte le temps.
La seconde contribution est la proposition d'un algorithme multi-objectif et dépendant du temps, permettant d'identifier les chemins pareto-optimaux dans ce graphe. Un troisième apport concerne le traitement des ces chemins, de sorte à optimiser la vitesse tout au long d'un trajet et par voie de conséquence, optimiser la consommation de carburant.
Enfin, nous présentons le système logiciel opérationnel qui intègre l'ensemble de ces contributions et qui a par ailleurs permis de valider expérimentalement, sur des données réelles, le modèle de représentation que nous avons proposé ainsi que les algorithmes qui l'exploitent.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...