Introduction

L'optimisation des tournées de véhicules concerne l'optimisation des parcours d'un ou plusieurs véhicules destinés à rendre un service. De nombreuses variantes du problème ont été étudiées. Ces recherches, souvent menées de manière indépendante, ont parfois abouti à des terminologies différentes pour des problèmes proches.

Nous intéressons dans ce travail au problème de transport de personnel entre plates-formes pétrolières. Celui-ci est un problème réel que les compagnies pétrolières rencontrent lorsqu'elles doivent déplacer leur personnel entre sites terrestres très éloignés ou entre des plates-formes en haute mer. Pour faire ces déplacements, les compagnies se servent d'hélicoptères ayant une capacité en nombre de passagers et une autonomie de vol limitées. Le problème consiste à déterminer pour un ensemble donné de demandes de transport, dans quelle tournée de l'hélicoptère elles seront satisfaites, et à quel moment dans la tournée.

Notre travail consistera à proposer une solution au problème en se basant sur la méthode d'optimisation par essaimes particulaires. Ainsi pour le faire quatre section serons développées dans la suite de ce travail : premièrement une présentation du problème avec les contraintes liées, puis les méthodes de résolution utilisés pour résoudre les types de ce problème, la section qui suit est consacrée à un algorithme à base de population (Algorithme Mimétique) qui sert comme base pour comparer notre méthode proposée. La dernière section est réservée à la méthode proposée pour résoudre le PCL.

Présentation du Problème

Le problème de Collectes et Livraisons Général -PCLG (GPDP : General Pick-up and Delivery Problem), est un problème d'optimisation qui consiste à trouver un ensemble de tournées, satisfont un ensemble de demandes de transport. Pour réaliser ces tournées, une flotte de véhicules est disponible. Chaque demande de transport est caractérisée par une charge de transport, un ou plusieurs sites d'origine ou de collecte (pick-up), et un ou plusieurs sites de destination ou de livraison (delivery). Lorsqu'une demande de livraison est prise en charge, elle ne peut être effectuée que par un seul véhicule et sans livraison intermédiaire de cette charge sur un site autre que la destination. Ces problèmes ont de nombreuses applications parmi lesquelles nous trouvons, par exemple, le transport de marchandises, la distribution de colis, le transport de personnes par taxi, le transport de personnes handicapées et le transport de personnel. Le problème général (PCL) est défini de la façon suivante : Soit n le nombre de demandes de transport. Chaque demande de transport i est caractérisée par une charge i q à transporter de l'ensemble des origines

+ i

N vers l'ensemble des destinations − i N . On suppose que cette charge est répartie sur les origines et les destinations de la façon suivante :

∑ ∑ − + ∈ ∈ = = i i N j j N j j i q q q

. De cette façon, les sites de collecte ont une charge positive et les sites de livraison une charge négative.

Soit+ ∈ + ∪ = i N i N N l'ensemble de toutes les origines, − ∈ + ∪ = i N i N N l'ensemble de toutes les destinations, et − + ∪ = N N N . Soit M l'ensemble des véhicules disponibles. Chaque véhicule M m ∈ a une capacité maximale m Q . Soit { } M m m M ∈ = + + l'ensemble des sites de départ (dépôts) des véhicules, { } M m m M ∈ = − − l'ensemble des sites d'arrivée des véhicules, et − + ∪ = M M W . Pour tout W N j i ∪ ∈ ) , ( , on note ij d la distance, ij t le temps et ij c le coût associés au trajet ) , ( j i .

Problème traité

Notre travail consiste à l'application de la méthode d'optimisation par essaimes particulaires (OEP), au problème PCL, et plus particulièrement aux problèmes des compagnies pétrolières. Chaque jour des personnes doivent être transportées de plate-forme à plate-forme. Chaque demande de transport concerne une ou plusieurs personnes qui désirent être transportées d'une plate-forme de départ à une plate-forme d'arrivée. Ces transports sont faits par des hélicoptères ayant une capacité limitée. L'objectif des compagnies pétrolières est de déterminer les tournées de façon à minimiser les coûts de transport par hélicoptères, tout en satisfaisant les demandes de transport. Nous disposons d'un jeux de données généré aléatoirement et téléchargeable de www.emn.fr/guéret., ainsi généré des problèmes sur une carte de 50 km de côté pour lesquels 5% des sites ont une capacité d'approche limitée à 5 passagers. L'hélicoptère a une capacité de 13 passagers. Quatre séries de 100 problèmes chacune ont été générées, dans lesquelles le nombre de sites et le nombre de demandes de transport sont variés. Ainsi la première série contient des problèmes avec 10 demandes sur 5 sites (5S-10D), la deuxième des problèmes avec 20 demandes sur 5 sites (5S-20D), la troisième des problèmes de 30 demandes sur 10 sites (10S-30D), et la dernière des problèmes avec 50 demandes sur 20 sites (20S-50D).

Description et Contraintes liés au problème

Soit n le nombre de demandes de transport à satisfaire. Chaque demande de transport k concerne un seul passager qui doit être transporté d'un site d'origine k p à un site de destination k d . Le temps nécessaire pour embarquer ou débarquer un passager sur un site i est appelé temps de service et est noté i s . Pour satisfaire les n demandes de transport, un seul hélicoptère est disponible. Celui-ci est caractérisé par une capacité maximale Q en nombre de passagers et une durée maximale de vol T au bout de laquelle il doit se ravitailler en carburant à la base. Une capacité d'approche i a est affectée à chaque site.

Elle correspond au nombre maximal de passagers dans l'hélicoptère au moment de son atterrissage sur un site, ceci pour des raisons de sécurité. Dans ce problème les distances sont euclidiennes. Ainsi pour deux

sites i et j , la distance ij d respecte l'inégalité triangulaire ) ( kj ik ij d d d + ≤ et k j i d d ji ij ∀ ∀ ∀ = , , .

Le temps de trajet ij t entre deux noeuds i et j est pré-calculé à partir de la distance entre les sites et de la vitesse moyenne de l'hélicoptère. Capacité : Le nombre de passagers dans l'hélicoptère ne doit pas dépasser Q .

Les deux contraintes spécifiques suivantes doivent de plus être respectées :

Capacité d'approche : Pour des raisons de sécurité, le nombre maximal de passagers dans l'hélicoptère lors de son atterrissage sur un site peut être limité.

Durée maximale des tournées : Étant donné que l'hélicoptère a une durée de vol limitée T au bout de laquelle il doit retourner se ravitailler en carburant à sa base et qu'il ne peut retourner à la base s'il a des passagers à son bord, la durée des tournées est elle aussi limitée à T .

L'objectif de ce problème est de satisfaire toutes les demandes de transport en minimisant la distance totale parcourue.

Méthodes de Résolutions Utilisées

En ce qui concerne l'application du transport de personnel par hélicoptère, nous trouvons peu de travaux et des problèmes comportant des caractéristiques différentes. Les méthodes utilisées pour résoudre ces problèmes, sont également variées.

Heuristiques D'insertion et d'amélioration

Les heuristiques gloutonnes utilisées pour les problèmes classiques de tournées de véhicules. Ce sont des méthodes d'insertion qui construisent un ensemble de tournées en insérant les demandes de transport les unes après les autres dans un certain ordre. . (iv) Voisinage Déplacement Site : Cette méthode de voisinage permet de déplacer une séquence de noeuds consécutifs représentant le même site géographique à un autre emplacement dans la tournée.

Algorithme Mimétique

Nous décrivant dans cette section un algorithme mimétique proposé dans (Prins, 2004) et utilisé dans (Velasco et al. 2005) pour le transport du personnel par hélicoptère. Il sert comme une base pour comparer notre méthode proposée. Les algorithmes mimétiques construisent une population composée d'un ensemble de solutions. Comme dans les algorithmes génétiques, de plus contiennent une recherche locale qui peut être appliquée dans différentes phases de l'algorithme. Récemment Prins (Prins, 2004) a présenté un AM pour résoudre un problème de tournées de véhicules. Dans son approche l'auteur utilise un chromosome sans délimiteurs de tournées et une procédure "Split" qui permet de couper un chromosome en tournées optimales en respectant l'ordre de la séquence du chromosome.

Description de l'Algorithme Mimétique

L'algorithme mimétique proposé dans (Prins, 2004) pour les tournées de véhicules, et utilisés après dans (Velasco et al. 2005) pour le PCL. Comme tout algorithme génétique, un AM est défini par : (i) un codage des solutions, (ii) l'initialisation de la population, (iii) un opérateur de croisement, (iv) un opérateur de mutation, (v) des règles de remplacement, et (vi) des critères d'arrêt. Comme dans plusieurs algorithmes génétiques pour le problème de voyageur de commerce (PVC), un chromosome est une séquence (permutation) S de noeuds, sans délimiteurs de tournées. Le chromosome adopté est une liste de demandes de transport indexées, dans laquelle chaque demande de transport k apparaît deux fois : une fois comme k+ qui indique le noeud de collecte et l'autre fois comme k-pour le noeud de livraison. Un exemple de chromosome est donné par : S = (0, 1+, 1-, 2+, 2-, 3+, 4+, 4, 3-), 0 représentant la base de l'hélicoptère. Afin de couper ce chromosome en tournées, une procédure optimale appelée ''Split'' est utilisée, qui permet de déterminer la meilleure solution respectant la séquence et avec respect des contraintes de problème. La complexité de split est calculé en ) ( 2 n O en utilisant l'algorithme de Bellman pour des graphes acycliques (Cormen et al.1990). À chaque itération, deux parents sont sélectionnés par la technique du tournoi binaire. Un opérateur de croisement est appliqué à ces deux parents pour générer deux fils. Une fois le croisement des deux parents effectué, un enfant est sélectionné aléatoirement. Il est transformé en une solution composée de plusieurs tournées grâce à la procédure Split et il est amélioré par une procédure de recherche locale avec une probabilité fixée. Cet enfant remplacera un chromosome de la population. Pour cette recherche locale, les différents voisinages mentionnés en dessus ont été testés.

La méthode d'Essaimes Particulaires et le Problème de Tournées.

A notre connaissance il n'y a que peu de travaux, consacrés au problème de tournés de véhicules (voir deux à trois articles), adoptant la méthode d'optimisation OEP au problème de tournés de véhicules. Par exemple dans (Qing et al. 2006), l'OEP est adaptée au problème de tournées de véhicules avec fenêtre horaires. Une des représentations est d'utiliser un vecteur composé de séquence de noeuds pour lequel les tournées sont séparées par le noeud représentant la base (d'ailleurs c'est la même représentation utilisée aussi pour le problème PDP). Supposons que la base est représentée par le noeud 0 un exemple de solution pour 6 clients est représenté comme suit (Fig. 1) : 0 5 0 4 3 6 0 2 1 0 1 2 3 4 5 6 0 0 8 7 4 3 1 5 2 6

Fig. 2 -Représentation d'un individu

Les deux derniers emplacements dans index de tableau de la figure Fig. 2, représentent les positions de séparation des tournées. La méthode est appelée uniquement pour des problèmes de petite taille. Il est bien évident que la recherche de la solution à base de cette méthode consiste à trouver les meilleurs positions dans le vecteur index , ce qui n'est pas facile avec l'utilisation directe de la méthode OEP.

Méthode Proposée

Nous pensons que l'application de la méthode OEP pour des problèmes de tournés, passe par la modification de système d'équation en préservant la philosophie de la méthode. Ce point de vue a été bien appelé par (Allahverdi et Alanzi, 2006) pour le problème d'ordonnancement dans les bases de données distribuées. Nous utilisant ici la même philosophie, avec quelques modifications appropriés afin que la méthode s'applique bien pour le problème de collecte et de livraison (PCL). La méthode d'Optimisation en Essaims Particulaires (OEP), consiste en un essaime de particules. Ces particules coexistes et en évolution dans l'espace de recherche, basés sur leurs expérience et le savoir partagés avec le voisinage. Chaque particule possède deux paramètres, la position et la vitesse

)) ( ), ( ( t v t x

, la population vole dans un espace de recherche à base des deux équations suivantes : est la part de l'apprentissage social.

) 1 ( ) ( ) 1 ( + + = + t v t x t x (1) ) ( ) ( ) ( ) 1 ( 2 2 1 1 x gbest c x pbest c t wv t v − ϕ + − ϕ + = + (2) ) (

Représentation de données

Il est bien évident que la représentation des données proposée dans les travaux ci-dessus, et plus particulièrement la représentation de chromosome utilisée dans les algorithmes mimétiques, présente les inconvénients :

L'application des opérateurs de croisement sur les chromosomes solutions, conduit à la violation des contraintes de problème (contrainte de précédence, contrainte de la durée maximale d'une tournée).

Quelque soit le traitement proposé pour respecter les contraintes : de précédence et de la durée d'une tournée, le résultat conduit toujours à un nombre important de solutions non réalisables.

Dans ce qui suit nous utilisons une représentation avec les noeuds de collectes seulement. Les autres noeuds seront insérés à l'aide d'une procédure d'insertion des noeuds de livraison, dont la description est la suivante : . A chaque insertion d'un noeud de livraison, les contraintes du problème doivent être vérifié. Si l'insertion d'un nouveau noeud de livraison provoque la violation des contraintes, ce dernier sera inséré avec le noeud de collecte correspondant dans la tournée suivante. La construction de la totalité du vecteur évaluable (vecteur contenant les noeuds de collecte et de livraison) s'effectue en parallèle dans un autre vecteur qui sera évalué à l'aide de la procédure split décrite ci-dessus. Il est à noté que l'utilisation de la procédure split ici sert pour évaluer uniquement la séquence.

Méthode d'insertion des noeuds de collectes

Par exemple, pour insérer le noeud de collecte ) 1 ( il y a deux possibilités :

Soit avec le respect de l'ordre des noeuds de livraison, dans ce cas le noeud peut avoir quatre possibilités, à partir de la position entre les noeuds Soit n : le nombre de noeuds de requête.

Adaptation de l'OEP pour le PCL

Adapter la méthode OEP pour le problème de collectes et de livraisons, avec préservation de la philosophie de la méthode, nécessite en premier une réécriture de système équations de base de l'OEP (équation (1) et ( 2

___________________________________________

Les résultats obtenus pour les quatre types de problèmes de collectes et de livraisons, montrent que la méthode proposée permet l'amélioration dans les résultats pour la majorité des instances des problèmes. Le taux de changement varie de 0% pour les problèmes de petite taille (5s10r) jusqu'à 50% pour les problèmes de grande taille (20s50r).

Le temps d'exécution dépend de la taille du problème et varie de quelques secondes pour les problèmes de petite taille (5s10r) jusqu'à quelques minutes (20s50r).

Conclusion

La méthode d'optimisation par essaimes particulaires partage beaucoup de similarité avec la algorithmes génétiques dans le sens où les propriétés d'un individu sont influencés par les caractéristiques des autres. La méthode a été appelée efficacement dans ces dernières années pour les problèmes dites d'optimisation continue. Néanmoins son application aux problèmes discrets s'avère difficile pour les deux raisons suivantes : (i) Modélisation : L'application de la méthode aux problèmes discret nécessite une phase d'adaptation de modèle d'équations de l'OEP. (ii) Voisinage : L'OEP de base est basée sur deux topologies de voisinage social, global best pour lequel l'individu est influencé par un voisinage global et local best pour lequel l'individu est influencé par un voisinage local. Chacun des deux types de voisinage présente des avantages et des inconvénients. Une bonne utilisation de la méthode nécessite la définition de la topologie de voisinage qui convient au problème. Nous avons tenues compte des deux derniers raisons dans notre application de l'OEP au problème de collecte et de livraison, ainsi le système d'équation de base de l'OEP est modifié afin qu'elle s'adapte mieux au problème, en deuxième un opérateur (qui n'ai pas détaillé ci-dessus) est définie qui permet l'échanges entre les noeuds des deux tournées choisisses aléatoirement afin de remédier à la faiblesse de la topologie global best en face les optimums locaux. Les résultats ainsi présentés dans les tableaux précédents montrent l'efficacité de telle approche pour les problèmes de tournées de véhicules et de collectes et livraison, et que la méthode proposée est favorablement comparée aux algorithmes génétiques combinés avec les recherches locales. En perspective nous retenons d'appeler la méthode à des instances de grande taille par exemple à partir de deux cents noeuds, et aussi d'appeler la méthode aux problème de tournés des véhicules en utilisant les benchmarks de la littérature.