Résumé : Le problème de collectes et livraisons (PDP : 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). Dans ce travail une nouvelle méthode d'optimisation par essaimes particulaires est proposée pour le résolution de ce problème. Les résultats trouvés, montrent que la méthode proposée est favorablement comparée aux algorithmes proposés dans la littérature, et particulièrement l'algorithme mimétique (AM) .
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.
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 qi à transporter de l’ensemble des origines Ni+ vers l’ensemble des destinations N i- . On suppose que cette charge est répartie sur les origines et les destinations de la façon suivante : qi = ∑ j∈Ni+ q j = ∑ j∈Ni- q j . De cette façon, les sites de collecte ont une charge positive et les sites de livraison une charge négative.
Soit N + = ∪i∈N Ni+ l’ensemble de toutes les origines, N + = ∪i∈N N i- 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
Qm . 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 W = M + ∪ M - . Pour tout (i, j) ∈ N ∪W , on note dij la distance, tij le temps et cij le coût associés au trajet (i, j) .
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 (5S10D), 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 (20S50D).
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 pk à un site de destination d k . Le temps nécessaire pour embarquer ou débarquer un passager sur un site i est appelé temps de service et est noté si . 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 ai 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 d ij respecte l’inégalité triangulaire (d ij ≤ d ik + d kj ) et d ij = d ji ∀i, ∀j, ∀k . Le temps de trajet tij 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.
Ce problème contient les contraintes classiques du PCL qui sont :
Couplage : Pour chaque demande de transport k , le site de collecte pk et le site de livraison d k doivent être visités dans la même tournée.
Précédence : Pour une demande de transport k , le site de collecte pk doit être visité avant le site de livraison d k .
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.
À notre connaissance peu de chercheurs se sont intéressés aux PCL rencontrés dans les problèmes de
transport de personnel par hélicoptère. Fiala-Timlin et autres ont résolu un problème de transport de
personnel avec plusieurs hélicoptères et des priorités sur les demandes
Parmi les méthodes exactes, une approche de partitionnement avec génération de colonnes a été
développée par Tijssen pour résoudre un problème avec 51 sites et plusieurs hélicoptères dans lequel la
préemption des demandes (possibilité de partitionner la charge d’une demande) est autorisée et dans
laquelle à chaque fois qu’une personne monte dans l’hélicoptère, une autre descend
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.
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. Plusieurs critères peuvent être utilisés pour trier les demandes: (i) Plus Proche Demande (PPD) , (ii) Plus Lointaine Demande (PLD), (iii) Plus Proche Centre de Gravité (PPCG), (iv) Plus Lointain Centre de Gravité (PLCG), (v) Meilleure Insertion (MI), et la dernière (vi) Insertion Aléatoire (IA). La complexité globale de ces heuristiques est O(n3) pour les versions PPD,
Les méthodes de recherches locales utilisés dans le cadre de tournés de véhicules appartiennent à quatre classes de voisinages : (i) Voisinage Déplacement d’une Demande, L’exploration de ce voisinage est de complexité O(n3) . (ii) Voisinage Permutation de Demandes : La complexité totale pour explorer ce voisinage est O(n4 ) . (iii) Voisinage 2-Opt : Ce voisinage contient O(n2 ) solutions. Chaque voisin est construit en O(n ) . L’exploration du voisinage coûte donc O(n3) . (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.
Nous décrivant dans cette section un algorithme mimétique proposé dans
L’algorithme mimétique proposé dans
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 O(n2 ) 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.
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
0 5 0 4 3 6 0 2 1 0 La représentation d’un individu est basée sur ce principe, et pour lequel les noeuds en extrémité sont supprimer et ceux au milieu sont décalés à gauche, un individu est représenté à l’aide d’un vecteur de dimension n + k - 1 et a la forme suivante pour le vecteur en figure Fig 1. 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.
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
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 (x(t), v(t)) , la population vole dans un espace de recherche à base des deux équations suivantes :
x(t + 1) = x(t ) + v(t + 1) (1) v(t +1) = wv(t) + c1φ 1 ( pbest - x) + c2 φ 2 (gbest - x) v(t ) : est la vitesse au temps t . x(t ) : la position au temps t . p(t) : la meilleure position antérieure obtenue par le particule. g (t) : la meilleure position obtenue dans le voisinage de particule. w : le facteur d’inertie. φ1, φ 2 : deux variables aléatoire dans [0,1] . c1φ1( p(t) - x(t)) est la part de l’apprentissage cognitive, et c2φ 2(g(t) - x(t)) est la part de l’apprentissage social.
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 :
Considérons l’exemple suivant, avec la séquence des requêtes {1,2,3,4}, représentant un problème de quatre demandes. La représentation d’une solution quelconque, à l’aide d’un vecteur de dimension 2n et à l’aide d’un vecteur de dimension n peut être donnée comme suit : Les noeuds {- 2,- 3,- 4,- 1} seront insérés en respectant l’ordre de la séquence des requêtes, c'est-à-dire l’ordre de traitement des noeuds de collectes {2,3,4,1}. 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. 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 (4,- 2) , comme le montre la figure Fig. 4. Le nombre de possibilité pour insérer un noeud de livraison est inférieur ou égale à n , avec n est le nombre de requêtes.
Soit sans respect de l’ordre des noeuds de collectes, dans ce cas le noeud est inséré à la première position et le nombre de possibilité pour insérer les noeuds de collecte égale à 2 n .
Dans le but de trouver une meilleure insertion, pour tous les noeuds de livraison insérés. Les noeuds de livraisons insérés en premiers sont déplacés vers les nouvelles positions crées, comme le montre l’exemple de la figure Fig. 5. Le test de toutes les positions de l’ensemble des noeuds de livraisons s’effectué en O(n2 ) .
Pour les deux cas, le nombre de possibilité totale d’insertion des noeuds de livraison NL , en tenant compte de toutes les possibilités d’insertion des noeuds de collectes.
Soit n : le nombre de noeuds de requête.
NL =
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) ) on se basant uniquement sur les deux parts d’accélération ou proprement dit sur les parts d’apprentissages. Ce qui fait sur les deux mémoires de l’individu et de la population. Il est évident que les deux parties de l’accélération, cognitive ou social, permet le changement dans la position des individus vers le meilleure dans l’expérience, et le meilleur de la population par c1φ 1 ( pbest - x) , et c2 φ 2 ( gbest - x) respectueusement.
Soit x, pbest, et gbest trois vecteurs, représentant des tournées de véhicules pour le problème de collecte et de livraison. Avec x : la solution actuelle. pbest : la meilleure solution obtenue par l’individu dans le passé. gbest : la meilleure solution obtenue par la totalité de l’essaim.
Les équations (1) et (2) seront modifiés comme suit :
La solution actuelle x obtenue par un individu sera modifiée, en déplaçant l’individu vers son meilleure position visité jusqu’ici pbest , c'est-à-dire son expérience par la grandeur suivante : Le résultat obtenu à l’aide de l’équation (5), c'est-à-dire la nouvelle position de l’individu sera soumise à des changements à base de la deuxième part de l’accélération. Par conséquent l’individu est déplacé vers la meilleure position obtenue par la totalité de l’essaim gbest , comme suit : V1 = c1φ 1d1 (6) Où d1 et d 2 sont deux scalaires appartenant à l’intervalle [0 1] implémentant la différence entre les couples de vecteurs ( pbest, x) et (gbest, ( pbest, x)) , et V1 , V2 sont les vitesses de déplacements. L’exemple suivant explique l’utilisation des équations (5) et (6). Soit X 1,
représentant les noeuds d’un graphe. Chacun des noeuds est codé en un entier positif : Trouver une mesure de différence entre deux vecteurs peut s’effectuer à l’aide de la distance de Hamming. L’inconvénient majeur de cette distance est lorsque l’un des vecteurs est le décalage circulaire de l’autre, la distance entre les deux vecteurs est maximale pourtant ces derniers sont les mêmes. Pour cela nous cherchons tout d’abords à trouver une mesure de ressemblance R( X 2 , X1) entre deux vecteurs, cette mesure représente l’ensemble des arrêtes appartenant au deux vecteurs. Formellement soit A , 1
A2 les arrêtes représentant X 1 , et X 2 .
A1 = {(2,1) (1,3) (3,4) (4,6) (6,7) (7,9) (9,8) (8,10) (10,5)} A2 = {(9,5) (5,6) (6,7) (7,3) (3,4) (4,1) (1,8) (8,10) (10,2)}
N - 1 R( X 2 , X 1 ) = (∑ ni ) /(N - 1)
i=1 1 ni = 0
Si l ' arrête i ∈ A1 , i ∈ A2
Sinon Dans l’exemple R( X 2 , X 1 ) = 1 / 3 , la différence entre les deux vecteurs est :
d ( X 2 , X 1 ) = 1 - R( X 2 , X 1 ) Nous appelons cette distance la distance des paires. Dans l’exemple la différence est 2 / 3 . Une fois la différence entre les deux vecteurs est calculée, la vitesse de changement de l’un des deux vecteurs vers l’autre est obtenue à l’aide de l’équation V = cφd . Admettons que c = 1, et φ = 0.5 , alors la vitesse de déplacement de vecteur X 1 vers X 2 est de V = 1/ 3.
Afin d’appliquer les changements sur le vecteur X 1 , une variable aléatoire ρ est générée pour chaque arrête dans X 2 . Si ρ < V l’arrête en question est sélectionnée pour participer au vecteur résultat. Si à la fin le vecteur résultat n’est pas encore complet, celui-ci est complété à partir des éléments de X 1 , ce dernier est parcouru d’une manière circulaire du dernier élément trouvé dans le vecteur résultat. Admettons que ρ = {0.3, 0.5, 0.2, 0.9, 0.1, 0.2, 0.3, 0.7, 0.05} , le vecteur résultat sera : L’algorithme suivant, explique l’utilisation de la méthode pour le problème de collecte et de livraison. (7) (8)
Algorithme 2 – Algorithme d’optimisation par essaimes pour le PCL.
Les algorithmes décrits ci-dessus ont été réalisés en Java Eclipse© testés sur une machine Pentium VI d’horloge 3Mhz et sur le jeu de données aléatoire décrit ci-dessus téléchargeable sur www.emn.fr/guéret. Le choix des paramètres dépend de problème en question. Les valeurs suivantes ont été fixées pour chaque type de problème c1 = 1 / 2, c2 = 1 / 2 . La vitesse de déplacement Di avec i = 1,2 , variée d’un problème à l’autre. Pour les problèmes de types 5s10r la vitesse Di ∈ [1 / 2 9 / 10] . Les problèmes de types 5s20r Di ∈ [4 / 10 6 / 10] . Les problèmes de types 10s30r Di ∈ [2 / 10 4 / 10] . et les problèmes La taille de l’essaim est fixée au nombre de demandes et elle varié de 10 à 50 individus. de types 20s50r Di ∈ [0
2 / 10]. Le choix des intervalles dépend de la dimension du vecteur solution.
___________________________________________ 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).
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.