Rapport de stage société pétroliere SONATRACH

Ce travail a été effectué à la société PétrolièreSONATRACH. Nos remerciments vont àladresse de

Mr. BOUDINAR Chef de département Evaluation Economique et Commercial et Mr. GOUIRA pourleurs aides et leurs encouragements.Nous avons été profondément touchés par la confiance manifestée ànotreégard en nous proposant ce travail. Puissiez-vous ytrouver matière à satisfaction.

Mme BENMEZIANE qui a dirigé ce travail.

Son expérience mathématique, sa connaissancede larecherche opérationnelle, et son sens critique aigu ont été des leçons que nous noublierons amais.

Qu'elle trouve ici témoignage de notresincère gratitude et ce poura bienveillance des ses conseils, ses critiques précieuses et es encouragements qu'elle nous a prodigué tout au long de notre travailet qui enont permisa réalisation.

Ce travail et ceux qui l'ont réalisé lui doivent beaucoup.

Nous l'assurons de notre considération.

REMERCIEMENTS

Nous remercions nos familles respectives pourleurs encouragements et leurs aides tout au long de nos études.

Nous remercions tous ceux qui par leurs encouragements, eur aide ntell lectuelles ou matérielles, leurs conseils ou leurs critiques, ont contribué a réalisation de ce travail

Nous remercions vivement Monsieur REGHIS Abdeldjallilpour sa gentillesse et sa patience. Nous voudrions aussi lui témoigner notre reconnaiss sance pour nous avoir fait découvrir le plaisir detravailler avecL^?TEX.

Nous remercions les membres du jury davoirbien voulu nous faire''honneur de lire et d'apprécier notre travail.

DEDICA CES

Je dédie ce modeste travail à

~ la mémoire de mes grands-parents et de mon oncle

~ Ma famille :

~ ma mère pour m'avoir soutenu tout au longde ma vie

~ mon père pour avoir cru en moi quand jai moi-même cessé de le

faire, en espérant que ce travail soit à la hauteur de ces attentes ~ mes frères Faouzi,Karim et Lotfima belle soeur Wissem

~ mes oncles et mes tantes spécialement ma tante Sacia

~ mes cousins et cousines ;

~ tous mes amis, spécialement ZhourHarane, Samiret Mehdi

~ la famille BENSACI, HAFIDI et ZITOUNE

~ la famille BENSEBA.

BENSACI Mounir

Je dédie ce modeste travail à

~ la mémoire de mon grand-pèrequi a toujours cru en moi

~ ceux qui ont attendu ce travail avec impatience, qui nont pas cesséde m'encourager, ma mère et mon père

~ mes soeurs et mon frère que jaime beaucoupMeriem, Ghalia et Kamel

~ mes oncles, mes tantes, mes cousinset mes cousines

~ tous les amis, en particulier Nedjma

~ la famille BENSEBA et la famille HIDAR.

~ la famille BENSACI.

BENSEBA Rachid

Table des matières

Introduction 1 Présentation de l'organisme d'accueil					4 6
	1.1		Les missions de Sonatrach		7
	1.2		La vision de Sonatrach		7
	1.3		Les métiers de Sonatrach		8
	1.4		Organisation de la Sonatrach		9
			1.4.1 Organisation de lactivité Commercialisation		10
			1.4.2 La Division Exportation Gaz		10
	1.5		Organigramme de Sonatrach		11
2	Définitions et Etude de marché				12
	2.1		Définitions. . .... . . . . . . . . . . . . . . . . . . . . . . .		13
			2.1.1 Les gaz GPL. . . . . . . . . . . . . . . . . . . . . .		13
			2.1.2 Types de Livraisons . . . . .		14
			2.1.3 Types de Transactions		14
			2.1.4 Saisonnalité. . . . . . . . . . . . . . . . . . . . . . . .		15
			2.1.5 Coût de transport		15
	2.2		Etude de marché. . . . . . . . . . . . . . . . . . . . . . . . .		17
			2.2.1 L'Algerie dans le marchéinternational		17
			2.2.2 Les exportations par région		19
			2.2.3 Perspéctives d'éxportations des gaz GPL par region à
			l'horizon 2007 . . . . . . . . . . . . . . . . . . . . . . .		19
			2.2.4 Perspéctives de production et déxportations desgaz
			GPL à l'horizon 2015. . . . . . . . . . . . . .		20
			2.2.5 Perspéctives en matière de transport maritime		20
3	Problématique				22
	3.1		Position du problème. . . . . . . . . . . . . . . . . .		23
			3.1.1 Les ports de chargements		23
			3.1.2 Les navires. . . . . . . . . . . . . . . . . . . . . . . .		24
TABLE DES MATIÈRES 3.1.3 Les ports de déchargement 3.2 Les déstinations 2006 3.3 Description de la procédure actuelle 3.4 Notre contribution. . . . 26 27 28						2 28
4		Modélisation				29
		4.1		Hypothèses . .. . . . . . . . . . . . . . . . . . . . . . . . . .		30
				4.1.1 Au niveau des postes de chargement		30
				4.1.2 Au niveau des ports de déchargement		31
				4.1.3 Au niveau de la flotte. . . . . . . . . . . .		31
				4.1.4 Sur la période d'étude. . . . . . . .		31
				4.1.5 Aux niveaux des demandes. . . . . . . . . . .		31
		4.2		Objectifs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		32
		4.3		Contraintes. . . . . . . . . . . . . . . . . . . . . . . . . . .		33
				4.3.1 Contraintes Portuaires		33
				4.3.2 Contraintes de demandes		33
				4.3.3 Contraintes de rotations des navires		33
		4.4		Modèle Mathématique. . . . . . . . . . . .		34
				4.4.1 Notations et Définitions		34
				4.4.2 Définition des variables .		35
				4.4.3 Définition de la fonction objectif		35
				4.4.4 Définition des contraintes		35
				4.4.5 Résumé du modèle. . . . . . . . . . . . . . . . . . . .		37
5		Approche théorique de résolution				38
		5.1		Présentation de la méthode de Recherche Tabou . . .		39
				5.1.1 Principe de la méthode de Recherche Tabou		39
				5.1.2 Algorithme général dela méthode Recherche Tabou		40
		5.2		Les algorithmes génétiques		43
				5.2.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . .		43
				5.2.2 Mécanisme .. . . . . . . . . . . . . . . . . . . . . . . .		44
				5.2.3 La boucle évolutionnaire		44
				5.2.4 Description détaillée des éléments de lalgorithme		46
				5.2.5 Considérations surla convergencedes algorithmes évoo
				lutionnaires ..... . . . .... . . . . . . . . . . . .		54
				5.2.6 Optimisation évolutionnaire avec contraintes		55
6		Résolution du problème				59
		6.1		Choix des méthodes. . . . . . . . . . . . . . . . . . . . . . .		60
		6.2		Justifications du choix. . . . . . . . . . . .		60
		6.3		Adaptation de la méthode génétique		61

TABLE DES MATIÈRES 3

6.3.1 Codage de la solution et des données 61

6.3.2 Procedure Recherche de solutions réalisables 64

6.3.3 Justification de l'algorithme SolReal 67

6.3.4 Paramètres de l'algorithme Génétique 68

6.3.5 Adaptation des opérateurs 69

6.4 Adaptation de la méthode de la recherche tabou . . 73

6.4.1 Le codage de la solution 73

6.4.2 Génération d'une solution réalisable 73

6.4.3 Génération des solutions voisines 73

6.4.4 Listes Tabous adaptées à notre problème 74

6.4.5 Tailles des Listes. . . . . . . . . . . . . . . 75

6.4.6 Critère d'aspiration 75

6.4.7 Critére d'arrêt . 75
6.4.8 Algorithme Recherche Tabou Adapté à notre problème 76

7 Logiciel 81

7.1 Qu'est-ce que Delphi7. . . . . . . . . . . . . . . . . . . . . 82

7.2 Qu'est ce qu'une application MDI7 82

7.3 Présentation du logiciel 83

Conclusion 94

Annexe 101

Introduction

Les Hydrocarbures restent la source dénergie la plus utilisée pourebon fonctionnement de l'économie mondiale et ils continueront à jouer ce rrle stratégique aussi longtemps que lhomme naura pastrouvé d'autres sources d'énergies, qui pourront remplir leurs rôles avec plus de rentabilité et d'eafficacité.

Inexistantes avant 1974 les exportations algériennes en GPL gaa depéé trole liquéfié) n'ont cessé daugmenterdepuis et comparativement aux autres ressources énergétiques (charbon, pétroleet gaznaturel)₎e GPL est de plus en plus récupéré et valorisé grâce au relèvement des prix pétroliersduranta décennie 1970.

La production nationale de GPL toutes origines confonduesraaffinage, liquéfaction et production aux champs) atteindraitplus de 14 millions de tonnes en l'an 2015 grâce au plan de développement des filières Amont et Aval. L'exportation est estimée à 11 millions de tonnes àcethoriion.Ces perspectives ont amené Sonatrach à préconiser une politique axée surquatre grands volets :

1. privilégier les contrats coût et fret (CFR) aussibien versesmarchés traditionnels que versles nouveaux marchés et établir des relations directes avec les utilisateurs finaux

2. cibler les marchés les plus valorisants, particulièrement améditerranée

3. être un acteur sur le marché à travers une présence active suremarché spot;

4. diversifier les débouchés.

La tendance concurrentielle du marché international confirme anécessité de se doter d'une stratégie de commercialisation des GPL.Cette stratégieui permettra d'assurer une fluidité dans lécoulement de son exportation etune valorisation optimale pour ses produits.Commeles fraisde transport des GPL occupe une bonne part dansles coûts dexportation de cesproduits, alors une identification en moyens de transport s'impose pour a

Sonatrach. D'où la détermination de la taille et lastructure d'une flotte maritime optimale qui fera lobjet de ce projet.

Chapitre 1

Présentation de l'organisme

d'accueil

Sonatrach est un Groupe pétrolier et gazier intégré sur toutea chaane des hydrocarbures. Il détienten totalité ouen majorité absolue, plus de vingt entreprises importantes sur tous les métiers connexes à 'industrie pétrolière tel que le forage , le raffinageIl possède aussi des participations significatives (entre 10 et 49% du capital) dans près de 50entreprisesmplantées tant en Algérie qu'à l'étranger.

En 2004, le Groupe Sonatrach sest classé 12^eme mondial parmi les compagnies pétrolières selonla revue internationale PIWqui prend en considéé ration des critères physiques (réserves dhydrocarbures, production) et des critères financiers (chiffres daffaires, résultats).

Cette même revue indique que le Groupe Sonatrach est le 2^eme fournisseur mondial pour le gaz naturelliquéfié, le gaz de pétrole liquéfiée et e 3^eme pour le gaz naturel.

En 2004, Sonatrach, sans ses filiales, a réalisé unchiffred'affaires à 'exx portation de 31,5 milliards de dollars USEn matièrede commercialisation, 157,6 millions de TEP^' ont été vendues.

Sonatrach a produit 40 millions de m³ de GNL, séparé 8,6 millions de tonnes de GPL.

1.1 Les missions de Sonatrach

Les missions confiées à Sonatrach par lEtat, unique actionnaire, sontes suivantes :

~ contribuer au développement national par la maximisationde a valeur long terme des ressources hydrocarbures en Algérie

~ satisfaire les besoins actuels et futurs de l'Algérie enhydrocarbures et produits pétroliers ;

~ contribuer au développement national notamment en lui procurant es devises étrangères nécessaires

1.2 La vision de Sonatrach

Pour la Direction Générale, et conformément aux orientations de son actionnaire, Sonatrach deviendra un groupe pétrolier et gazier

~ avec une vocation internationale

^'Tonnes Equivalent Pétrole

~ leader du gaz sur le marché méditerranéen, avec un niveau élevé de performance par la focalisation sur les projets àhaute rentabilité eta maîtrise des coûts.

1.3 Les métiers de Sonatrach

Les métiers de base de Sonatrach portent sur toute a chaîne deshydroo carbures, en commençant par la recherche et l'exploration, usqu'àa transs formation des hydrocarbures et leur commercialisationaux consommateurs finaux.

Il est possible de regrouper ces métiers en quatre activitésglobales ~ l'amont pétrolier

~ l'aval pétrolier ;

~ le transport par canalisation

~ la commercialisation des hydrocarbures et des produits pétroliers.

Nous allons les présenter brièvement

a) l'amont pétrolier

~ l'exploration ;

~ le forage;

~ les services au puits ;

~ le développement des gisements ~ l'exploitation des gisements

b) l'aval pétrolier

~ la liquéfaction du Gaz Naturel ~ la séparation des GPL ;

~ le raffinage;

~ la pétrochimie.

c) le transport par canalisation (TRC)

~ le développement et la réalisation des canalisations detransport des hydrocarbures produits à partirdes gisements pétrolebrut, condensst, gaz naturel et GPL ;

~ l'exploitation du système de transport par canalisation

~ la maintenance du système de transport par canalisation.

d) la commercialisation

~ la commercialisation des hydrocarbures et des produits pétroliers tant sur le marché international que sur le marché national

~ le trading et le shipping des hydrocarbures (Sonatrachdispose d'une flotte importante de méthaniers, de GPLiers et de pétroliers)

~ le business développement à l'étranger

1.4 Organisation de la Sonatrach

Le schéma de la macrostructure sarticule autour

~ de la Direction Générale ;

~ des Activités Opérationnelles ~ des Directions Fonctionnelles

La Direction Générale du Groupe est assurée par le Président Directeur Général assisté du Comité Exécutif.Le SecrétaireGénéral assiste ePrésident Directeur Général dansle suivi et la cohésion du management duGroupee Un Comité d'Examen et d'Orientation, auprès du Président DirecteurGéné ral, apporte l'appui nécessaire aux travaux des organes sociaux du Groupee

Les Activités Opérationnelles exercent les métiers du Groupe et dévee loppent son potentiel d'affaires tant en Algérie qua 'étrangerrIls'agit de l'Activité Amont (AMT), de l'Activité Aval (AVL) de lActivité Transport par Canalisations (TRC) et de lActivité Commercialisation COM))

Les Activités Internationales sont, pour leur part, organisées sousa forme d'un Holding International, Sonatrach InternationalHolding Corpoo ration (SIHC) chargé de lélaboration et de l'applicationde apolitique et de la stratégie de développement et dexpansion à l'étranger

Les Directions Fonctionnelles élaborent et veillent à 'application des poo litiques et stratégies du Groupe. Elles fournissent 'expertise et'appuiné cessaires aux Activités Opérationnelles du Groupe.

Elles sont organisées en quatre Directions CoordinationGroupe DCG) ~ Ressources Humaines (RHU) ;

~ Stratégie, Planification et Economie (SPE)

~ Finances (FIN);

~ Activités Centrales (ACT)

et trois Directions Centrales

- Audit Groupe (ADG) ;

- Juridique (JUR);

- Santé, Sécurité et Environnement (HSE)

CHAPITRE 1. PRÉSENTATION DE L'ORGANISME DACCUEIL 10 1.4.1 Organisation de l'activité Commercialisation

L'activité Commercialisation est organiséecomme suit

~ Division Exportations Pétrole Brut et Produits Pétroliers

~ Division Exportations Gaz

~ Division Marché Intérieur et Filiales ~ Division Business Development ;

~ Direction Finances ;

~ Direction Etudes, et modèles

~ Direction Ressources Humaines

~ Direction Administration et Moyens ~ Direction systèmes d'informations

~ Conseillers et Assistants

1.4.2 La Division Exportation Gaz

A travers ses deux Directions Opérations Gaz et TransportMaritime, la division exportation gazest chargée de l'exécutionet de a gestion des contrats de vente des hydrocarbures gazeuxet a pour mission essentielle

~ l'établissement et la mise à jour des programmes de ivraisons men-

suelles trimestriel et annuel avec ses clients, en relation avec esActi-

vités Amont, Aval et TRC ;

~ les opérations technico-commerciales des chargements/déchargements des hydrocarbures gazeux

~ la coordination des arrêts techniques pour les opérationsde maintenance;

~ le suivi des programmes de maintenance des navires enconformité avec les organismes de contrôle et administrationconcernés

~ le suivi des arrêts techniques des navires et lacoordinationdes arrêts avec les installations de chargement et de déchargement et aveca programmation des livraisons

1.5 Organigramme de Sonatrach

FIG. 1.1 Organigramme De La SONATRACH

Chapitre 2

Définitions et Etude de marché

2.1 Définitions

2.1.1 Les gaz GPL

Les G.P.L. (Gaz des pétrolesliquéfiés) sont deux hydrocarbures, e propane C3H8 et le butane C4H10. Ces corps sont à l'état gazeux aux conditions normales de température et de pression et peuvent tre facilementiquééables par abaissement de la température à -42^°C pour le propane et -6^°C pour le butane, ou par compression modérée.

Décomposition molaire des GPL

C2H6	C3H8	iC4H10	nC4H10	iC5H12	nC5H12
1.83%	60.62%	13.61%	23.55%	0.34%	0.05%

TAB. 2.1 Décomposition molaire des GPL

Origines

Les GPL sont obtenus à partir de

1. Les GPL à partir des champs

Les GPL sont produit au sud à partir des champs pétroliersde Hassi Messaoud Nord et Sud, Haoud Berkaoui et à partir dutraitement de gaz à Hassi R'mel.

2. Production à partir des unités GNL

Additionnellement aux champs, trois unités deliquéfactionde gaznaturel produisent des GPL, il sagit de GL1K Skikda, GL2K Béthioua et GL4Z Arzew.

3. Production des raffineries

La production des raffineries varie en fonction des quantitésde brut
traitées.La totalité de la production est orientée versemarchénational.

2.1.2 Types de Livraisons

Sonatrach dispose de plusieurs formules delivraisons

- F.O.B. " Fret On Bord " ou " Franco en Bord "

Signifie que le vendeur a rempli ses obligations delivraison, quand a marchandise passe le bastingage du navire au portd'embarquement désigné. Cela signifie que l'acheteur doit supporter tous es frais etes risques de perte ou de dommage que peut courir la marchandise àpartir de ce point .

- C.F.R. " Cost And Freight "(en Français Coût et Fret) Signifie que le vendeur doit payer tous les frais y compris e fretnécessaire pour acheminerla marchandise au port dedestinationdésigné. Cependant le risque de perte ou de dommage que peutcourir a marchandise après qu'elle ait étélivré à bord du navireest transférédu vendeur à l'acheteur quand la marchandise passe lebastingage^' du navire au port d'embarquement

- C.I.F. " Cost Insurance Freight " (en Français Coût Assurance Fret "

Signifie que le vendeur a les mêmes obligations que dans le cas précédent, perte ou de dommage que peut courir la marchandise aucours du transport. Le vendeur contracte avec l'assureur etpaieune prime d'assurance .

L'acheteur notera que selon ce terme, le vendeur nest tenude souscrire l'assurance que pour une couverture minimum

2.1.3 Types de Transactions

Le marché des GPL se caractérise par deux types de ventes oude transactions :

1. Par Contrat :

Un contrat prévoit

~ les quantités annuelles de base ;

~ les types de livraisons en FOBCFR ou CIF

~ la durée du contrat Elle est généralement dune année, répartieen deux périodes : Hiver et Eté ;

~ la destination du produit ou les ports de déchargement

~ les prix de facturation ;

~ les forces majeures oùles deux parties sontexonérés de responsabilii tés face à des évènements qui peuvent survenir indépendamment de leurs volonté respectives telles que les tremblements de terre, tempêtes,..., etc;

~ les programmes des livraisonsIls définissent larépartitiondesivraii
sons et les lots durant la période du contrat (mois, trimestre,...,etc.)

2. En Spot

Signifie vente du moment et dulieu oùles deux parties se mettent d'accord sur toutes les conditions énumérées plus haut, sauf a e Ces ventes sont issues de cinq centres de production

~ le nord ouest Europe ;

~ l'Amérique (principalement les USA) ;

~ l'Afrique (principalement l'Algérie)

~ le Moyen Orient (principalement lArabie Saoudite)

2.1.4 Saisonnalité

La consommation des GPL varie selon deux périodes Hiver Eté.

~ HIVER : (Octobre à Mars)Il se caractérise par une forte demande domestique à cause du froid qui touche les grands centres de consommation (Europe, USA, Japon)

~ ETE : (Avril à Septembre) : La consommation domestique desGPL diminue en tiraillant une baisse des prix favorisant la substitution du Naphta par les GPL dans l'industrie pétrochimique.Les GPL ne sont utilisés dans la pétrochimie quà condition que leurs prix soient égaux à environ 85 pour cent de celui du Naphta.

2.1.5 Coût de transport

Les G.P.L exportés à partir de lAlgérie sont vendus en CIIF& CFR, eurs prix de facturation sont composés dune partie FOBet d'une partiefret' qui est le coût de transport

L'élément 'fret' est déterminant pour la pénétrationd'un produit sur un marché donné. Ainsi la proximité du produit permet au fournisseur de béé néficier du coût de transport réduit (toutechose étant égal par ailleurs),ui confèrent ainsi un avantage comparatif précieux.

Ce dernier comprend :

1. Les frais d'exploitation

Se décomposent en deux parties

~ une part fixe ou semi fixe telle queles frais du personnel, assurance, taxes;

~ une autre proportionnelle au tonnage telle que le remorquage, etes services divers.

2. Consommation du fuel ~ Fuel oïl en mer ;

~ Diesel oïl au port.

3. Coût d'affrètement des navires On distingue trois sortes daffrètements

- affrètement spot ou au voyage

L'armateur s'engage à transporter unecargaison d'unport à un autre port désigné;

- affrètement aux voyages consécutifs

Le navire sera utilisé pendant un certain temps, moins de deux ans en général, ou pour un nombre de voyages fixé davance

Les prix de transport dans ces deux cas sont fixés àa tonne suivant des barèmes de cotation tenant compte des fluctuations des tarifs de transport

- affrètement au temps ou 'Time Charter'

L'armateur met à la disposition de laffréteur pour une période donn née un an ou six mois, un navire avec son équipage, moyennant une location mensuelle.

L'affréteur a libre disposition du navire, ildoitpayer es frais d'exx ploitation, il est responsable de lexécution du contrat de transport.

Charter' parce qu'il lui est le plus rentable, cependant, ilui arrive aussi de recourir aux deux autres types da~rètement pour aauster sa flotte en cas de besoin.

2.2 Etude de marché

2.2.1 L'Algerie dans le marché international

Deuxième exportateur mondial des GPL derrière l'ArabieSaoudite, LAll gérie a exporté plus de 7,9 millions de tonnes de GPLen2004.Sur es quatre continents, 23 pays ont été approvisionnés.La Méditerranée représentee principal débouché de Sonatrachavec plus de 80% des exportations.Elle est suivie par les USA, l'Amérique LatinelAsie et lEurope du Nord.

1. Marché méditerranéen

C'est un marché a caractère saisonnier ou lusagedomestique préé domine. D'une manière générale, ce dernier donne la meilleure valorii sation à nos exportations du fait desa proximité et surtout, en raison de la forte demande pourlusage domestique notamment enhiver.

Ce marché ne dispose pas d'infrastructure destockages su~sante et la consommation en période dété esttrès réduite.

L'Italie et la France sontles principaux importateurs suivisde 'Ess pagne, et à un degré moindrele Portugal et le Maroc.

La Turquie est un nouveau débouché que Sonatrachcompte dévee lopper actuellement, elle importe plus de deux millions de tonnes de GPL en CIF (90% en provenance de lArabie Saoudite) elle auntaux de croissance annuel moyen de 8%

2. Marché du Nord Ouest Europe

Orienté principalement vers la pétrochimie, ce marché consomme moins de G.P.L en hiver, en raison dela forte concurrence avec a NAPHTA. Par contre, il constitue un débouche important en été du fait de la baisse de la demande domestique en Europedu sud.

3. Marché des USA

(a) Marché de la Cote Est

Il présente l'avantage de disposer dune infrastructurede réé ception et de stockageimportante. Cette région esthabituellement approvisionnée par Pipe à partirdu Golfedu Mexique, ce qui rend ce marché plus attractif à cause des coûts detransport parPipe qui viennent majorer les prix FOB des GPL. C'est ainsi qu'en période de forte demande (hiver) une fois lacapacité parPipe saturée, le recours à l'importations'avère indispensable.

(b) Marché du Golfe du Mexique

Il dispose d'une infrastructure de réception et destockage m- portante, mais comparativement aux autres marchés, la rarement donné des prix avantageux, cest pour cetteraison qu'il estconsii déré par Sonatrach comme un marché marginal à moins d'une favorable hausse des prix.

En dépit de leurs capacités d'absorption (en quantités), et pour les raison (de prix)la stratégie de Sonatrach estde cibler ce marché à chaque fois que les prix sont attractifs(casde hausse de prix ou difficultés d'écoulement des produits sur les autres marr chés).

L'éloignement et la faiblesse des prix du marché US incitent Sonatrach à utiliser des gros navires (30.000 TM etplus)₎ pour l'approvisionnement de ce marché (Cote Est etGolfeduMexique).

4. Marché Brésilien

Ce marché importe 2 millions de GPL par an en CIF/CFR avec un taux de croissance annuel moyen denviron 8%.

Il est approvisionné essentiellement du Moyen Orient, soit 90% sur le volume total.

Actuellement, les exportations de Sonatrach à destination de ce marché s'élèvent à environ 100000 TM par an.

2.2.2 Les exportations par région

FIG. 2.1 Organigramme Des Exportations Par Region

2.2.3 Perspéctives d'éxportations des gaz GPL par region à l'horizon 2007

FIG. 2.2 Carte Des Exportations Par Region

2.2.4 Perspéctives de production et d'éxportations des gaz GPL à l'horizon 2015

FIG. 2.3 Diagramme Des Eixportations des gaz GPL àLhorizon 2015

2.2.5 Perspéctives en matière de transport maritime

Sonatrach Pétroleum Corporation (SPC) négocielachatde navires pour le transport des gaz de pétroleliquéfiés (butanet propane).La compagnie, qui est une filiale à 100% de la Sonatrach, possède déà sept transporteurs de G.P.L.qui sont :

~ Jemila (mise en service 1983)capacités( 8000 m³);

~ Nejma (mise en service 1983) capacités.( 57000 m³); ~ Reggane(mise en service 1999)capacités.( 84000 m³); ~ Djanet(mise en service 2000)capacités( 84000 m³);

~ Alrar(mise en service2004)capacités( 59000 m³) ;

~ Rhourd Nouss(mise en service 2004) capacités (59000 m³);

~ Hassi Messaoud2(mise en service 2005) capacités (59000 m³).

Elle affrète aussi de façon permanente une quinzaine de navirespour e transport des hydrocarbures. Par ailleurs, une soiixantaine debateauixpar an

sont affrétés ponctuellement pour des échanges spott

Crée en août 1989, SPC a pour principale activité le tradingdes hydroo carbures (pétrole brutproduits raffinés, GPLet condensats, 'exclusion du gaz naturel). La compagnie commercialise une partiede a productionAlgé rienne d'hydrocarbures et travaille enliaison avec ladirection de commerr cialisation de l'entreprise nationale mais s'approvisionne également auprès d'autres sources, comme le font régulièrement les autres sociétés de trading appartenant aux grands groupes pétroliersnternationauxxUne autre liale de Sonatrach Sonatrading Amsterdam BVégalement contrrlée 100%, est spécialisée dans le commerce international du gaz naturell

Outre le trading, les autres responsabilités de SPC sont etransportmaa ritime et les investissementsen particulier dans lestockage, esterminaux et la distribution des GPL. En matière de commercialisation desGPL, a stratégie de la Sonatrach est daller de plus en plus vers'utilisation finale afin de s'assurer des débouchés, de capter une plus grande partde avaleur des produits vendus et d'être en position de résister aux pressions des spécuu lateurs sur les prix. Aujourdhui, 95% des GPL exportés para onatrache sont sous forme coût et fret et non plus fob(free onboard)₎ ce uimpliiue évidemment de disposer de navires pour le transportt

Chapitre 3

Problématique

Compte tenu de l'augmentation constante de la productionde Sonatrach en produits GPL, ainsi que pour tirer le meilleur profit de ces produits, Sonatrach a décidé dansla mesure du possible de vendre ses GPL en (CIF CFR).

3.1 Position du problème

Pour vendre ses produits en (CIFCFR) Sonatrach abesoinde détermii ner avec précision la taille etla structure de laflotte nécessaire pour assurer le transport des produits GPL sur les deux saisons (hivernale et estivale), avec le meilleur coût possible

Cette flotte sera chargé de transporter esquantités vendues, danse cadre des ventes par contrat (CIFCFR) ces quantitésseront prélevées essentiell lement des ports d'Arzew et Batioua pour les transporter directement vers des ports de déchargement bien définisqui ont une demande mensuelle avec une marge de flexibilité de livraison bien définie.

Les demandes mensuelles de chaque clientet les marges de flexibilité de la livraison de ces demandes mensuellessont stipulées dans es contratsann nuels de vente.

Les deux gaz GPL (ButanePropane) seront transportésdans des réserr voirs séparés. Un navire peut transporter un seul ou esdeux type de gaz en même temps.

Une quantité de produit chargée sur un navire, est considérée ivrée au client, des que ce navire reçoitle document prouvant que cette quantité a passé le bastingage de ce dernieret elle est prête pour êtretransporté vers ce client, la date de parution de ce document estconsidérée comme adate de livraison.

3.1.1 Les ports de chargements

Sonatrach dispose de 3 ports de chargement

1. Arzew : Equipé de 3 postes de chargement SiS2 et S3 permettent de charger des navires de i000 à 20 000tonnes.

2. Betioua: Equipé de 2 postes de chargement Di (3 000à 45000tonnes) et M6 (supérieur à 30 000 tonnes)

3. Skikda: Un poste de chargement (P5)

La grande majorité des exportations sont faitesà partir des ports d'Arzew et de Betioua, car le port de Skikda estréservéen grande partie à a distribution nationale, et les volumes exportés occasionnellement àpartir de ce port sont insignifiants, et ne sont sujet à un quelconque développement dans le future.

3.1.2 L es navires

Sonatrach dispose de sa propre flotte detransportdes GPL, mais cette dernière n'est pas suffisante pour assurer lévacuationde toute sa production destinée à l'exportation. Pour assurer la livraison de sesproduits enCIF CFR), Sonatrach doit affréter la majorité des GPLiers^'.

L'acceptabilité des navires

Les Navires sont acceptés ou non, selon les capacités de chargement seule ment, car les navires d'une même capacité possèdent aussi, (àpeu-près)e même tirant d'eau², et la même longueur.

Le tirant d'eau et lalongueur du navire doivent être respectivement nférieurs, à la profondeur et à la longueur du poste à quaide chargement.

Temps de chargement des navires

Le temps de chargement des navires varie en fonctionde a taillede ces derniers, il est mesuré en heureetil varie de 16h pour les navires de 4.000 tonnes jusqu'à 30h pour ceux de 42000 tonnes.

Le tableau (1-1) résumel'acceptabilité de chaqueclasse de navire pour chaque poste de chargementet donne les temps dechargement.

Durées de rotations des navires

Les rotations sont définies par un aller-retour entreeport de chargement et une destination de déchargementcar les navires ne peuvent pas être chargés partiellement pour des raisons techniques.

^'Navires de transport des gaz GPL

²la hauteur de la partie submergée du navire.

Les durées de rotation entre le port de chargement et esdifférents ports de déchargement sont connueselles sont différentes d'une classesde navire à une autre, l'unité de mesure des durées de rotationest ejour, elles varient entre 4 à 37 jours, d'après la destination, la vitessedunavire, ainsi quee temps de déchargement.

	Postes de chargement
Tailles des navires (Tonnes)	S1 (heures)	S2 (heures)	S3 (heures)	D1 (heures)	M6 (heures)
4.000	20	20	20	16	-
8.000	22	22	22	20	-
17.000	-	-	-	21	-
22.000	-	-	-	24	22
32.000	-	-	-	30	26
42.000	-	-	-	-	30

TAB. 3.1 - Temps de chargement

Affrètement des navires

L'affrètement des navires se fait généralement sur une année, cette ormule est la moins coûteuse, carles affrètements par voyage reviennent eaucoup plus cher.

3.1.3 Les ports de déchargement

Le tableau (1-2) nous renseigne sur lordrede grandeur de notre problème, et nous donne les classes de navires acceptées parchaque port.

Pays	Ports	Taille Min	Taille Max
Brésil	Santos	32.000	42.000
	Rocife	32.000	42.000
	Raranague	32.000	42.000
Espagne	Tarragone	4.000	32.000
	Carthagène
France	Lavera	4.000	32.000
Italie	Naples	4.000	8.0000
	Brindisi	4.000	22.000
	Livourne	4.000	22.000
Japon	Japon	32.000	42.000
Mexique	pagaritos	32.000	42.000
Maroc	Agadir	4.000	4.000
	Djorf	4.000	4.000
	Mohammadia	4.000	22.000
	Nador	4.000	4.000
N.W.Europe	N.W.E	22.000	42.000
Portugal	Lisbonne	4.000	22.000
Turquie	Izmir	22.000	42.000
	Izmit	22.000	42.000
	dortyol	22.000	42.000
USA	Cote Est(USEC)	32.000	32.000
	Golf du Mexique(USGC)	32.000	42.000

TAB. 3.2 Ensembles des ports de destination

3.2 Les déstinations 2006

La figure (4.1) nous renseigne sur les ports de déstination pourPannée 2006.

FIG. 3.1 Ensemble des ports de destination

3.3 Description de la procédure actuelle

Actuellement, le plan d'affrètement contractuel se faitd'aprèses expéé riences des années précédenteset de cette façon Sonatrach se retrouve soit avec un déficit, soit avec un excédant de navires, dans lecasd'undéficit elle a recourt à l'affrètement Spot (par voyage), qui estplus cher que'affrètement par contrat, et dansle cas de lexcédant Sonatrach est obligée d'affréter ces navires à son tour pourles rentabiliser

3.4 Notre contribution

Notre contribution consiste à déterminer la tailleet a structure dea flotte nécessaire pourlacheminement de toutes les exportationsde Sonatrach vendu en (CIF, CFR), et la détermination pour chaque naviredesdates de chargements vers chaque destination, qui permette de satisfairees demandes mensuelles des clients avec une certaine marge de flexibilité, car une flotte ne peut pas être optimale pour tous les plans detransportt

Chapitre 4

Modélisation

Avant de dresser une modélisation du système, nous allons présenteres hypothèses retenues sur le système étudié, sans quecela ne remette en quess tion la représentativité du modèle.

4.1 Hypothèses

Le but de toute modélisation est de représenter de lamanièrea plusfidèle possible la réalité ; pour celala disponibilité de données fiables et su~santes est indispensable.

La complexité du système étudié nécessite la formulation d'uncertain nombre d'hypothèses permettant de mieux cerner les aspects mportants et influents du système sans altérer son comportement réel c'est ainsique nous avons défini l'ensemble des hypothèses suivantes

4.1.1 Au niveau des postes de chargement

~ dans notre étude on considère que les ports dArzewet de Betioua comme ports d'exportationcar les volumes exportésoccasionnellement à partir du port de Skikda sont insignifiants

~ ces deux ports sont considérés comme étant un seul portde chargee ment, vu leur proximité ;

~ le port considéré dans notre étude, comprenddonccinq postesde charr gements (Si, S2, S3, Di, M6)

~ on suppose que le produit surle port de chargement est tout etemps

disponible (en réalité l'épuisement du stock arrivetrès rarement)

~ on suppose que le temps de chargement est dune journée pour toutes les classes de navire (car en réalitéil est àpeu-prèsd'une ournée pour toutes les classes) ;

~ le travail se fait dans des conditions normales (pasde grèvedes employés, ou tout autre organisme dont dépend lebon fonctionnement de la procédure de chargement)

~ les conditions climatiques sont favorables au chargement desnavires ~ dés son débarquement surle quai, le chargement du navirecommence ~ le matériel de chargement est dans un état de fonctionnement normall

4.1.2 Au niveau des ports de déchargement

~ chaque port de déchargement possède une demande mensuelle

~ Le client est tenu responsable du déchargementdans les délaisdesquann

tités transportées, du moment que ces quantités sont demandées

~ Le client est tenu responsable du stockagede la quantité déchargée, du moment qu'elle se situe dans la marge de flexibilité mensuelle.

4.1.3 Au niveau de la flotte

La flotte qu'on est chargé de déterminer sera constituée desnavires de Sonatrach, plus les navires affrétés.

Pour que tous les navires de cette flotte auront e même statut, on consii dère que les navire de Sonatrach, sont des navires affrétés avecun coot null

4.1.4 Sur la période d'étude

La période d'étude sera soit une saison, soit une annéede touteses faa çons elle sera partitionnée en mois, qui seront partitionnés à eurs tours en jours, ces jours seront numéroté dune façoncontinue, pour faciliter'écrii ture des contraintes (si la période détude sera une année, esjours seront numérotés de 1 à 365)

4.1.5 Aux niveaux des demandes

On considère les deux gaz GPL transportés commeétant un seul gaz, car chaque client demande une quantités mensuelle de chaque gaz, donc on doit tout simplement assurer le transportde la somme desdeux quantité en tonnes, puis charger les navires avec les portions correspondantess

4.2 Objectifs

Les objectifs principaux de notre étudesont

~ identification de la taille etla structure de laflotte àa~réterpour'exx portation des produits GPL

~ détermination des dates de chargement de chaque navireverses di~éé rents clients, permettant à cette flotte de livrer es GPL selon esots mensuels stipulés dans les contrats annuels.

Nos objectifs nous renvoient à deux notions doptimisation

1. Maximisation des recettes

2. Minimisation des coûts de transport.

On note que le premier objectif est plus large que le deuxième enterme d'optimisation, cependant cette option fait interveniranotion de prix qui à l'instar des autres prix des produits énergétiques variedans etemps d'une façon imprévisible. A défaut de prévision rigoureuse quant à'évolution des prix des GPL sur les différents marchés, cette alternative ne serapas retenue comme fonction objectif dans notre étude.

Quand à la deuxième, elle peut être réalisé compte tenude ladisponibilité

~ des prévisions sur l'évolution des coûts da~rètement des navires

~ des données sur les infrastructures portuaires desmarchés ciblés par Sonatrach.

Le problème se reformulera comme suite

" Quelle serait la structure de la flotte à a~réter susceptible de permettre

Sonatrach de réaliser son programme prévisionnel d'exportation en
minimisant les coûts de transport"

Une fois la fonction objectif a été retenue pour 'étude du problème, es contraintes de notre étude sont à définir

4.3 Contraintes

La minimisation des coûts de transport des exportations est régie par plusieurs contraintes dontles principales sont

~ Contraintes portuaires

~ Contraintes de la demande

~ Contraintes de rotation des navires.

4.3.1 Contraintes Portuaires

1. Aux postes de chargement

Un poste de chargement ne peut recevoir quun seul navirele même jour, car le temps de chargement de tous les navires est a peu présde 24h.

2. Aux ports de déchargement :

Chaque navire présente des caractéristiques techniques spécifiques qui doivent être conformes aux restrictions portuairesde chaque port de livraison, qui sont.

~ La capacité de chargement ~ Le tirant d'eau ;

~ La longueur.

4.3.2 Contraintes de demandes

Chaque client possède une demande mensuelleCette demande doitêtre livré avec une marge de flexibilité.

4.3.3 Contraintes de rotations des navires

~ un navire ne peut pas servir plus d'un client en même temps

~ un navire ne peut pas effectuer un chargement pour unclient, alors qu'il n'est pas rentré d'une rotation précédenteéventuelle.

~ tous les navires doivent démarrer leurs rotations éventuelles, avanta fin de la période d'étude.

4.4 Modèle Mathématique

4.4.1 Notations et Définitions

Indices

~ i : indice navire;

~ j : indice jour;

~ k : indice client(port de déchargement

~ l: indice quai; ~ m : indice mois.

Données

~ NN : nombre de navires (ce nombre comprend les navires de Sonatrach

plus les navires susceptibles d'êtres affréterend'autrestermes, c'esta

liste de tous les navires candidats pour constituer notreflotte) ~ NJ : nombre de jours sur toute la période détude

~ NC : nombre de clients (destinations)

- NQ: nombre de quais ;

~ NM : nombre de mois sur la durée d'étude

~ D_m : date du début du mois m ;

~ F_m : date de la fin du mois m ;

~ Q : capacité du navire i ;

~ DMkm : demande du client (port) kle mois m

~ ákm : la marge de flexibilité de la demande du client k le mois m

~ DR k : durées de rotation du navire i entre le port de chargement et e client (destination) k ;

(

1 si le client k peut recevoir le navire i ~ a k : 0 sinon

~ CA : le coût d'affrètement du navire i sur la période détude

~ CR k : coût de la rotation entre le port de chargement et eclient kdu navire i.

ce coût comprend :

~ le coût de consommation du fuel oïl et du diesel oïl

~ les frais du personnels navigants

~ les frais portuaires du navire i pour accoster dans eportde décharr gement k;

4.4.2 Définition des variables

(

1 si le navire i effectue un chargement le jour j pour le client k dans e quai Xijkl= O sinon

j=1,NJ i=1,NN k=1,NC l=1,NQ

4.4.3 Définition de la fonction objectif

Notre objectif est de minimiser le coût detransport, qui comprend e coût d'exploitation et le coût daffrètement des navires.

La fonction "objectif" sera donc

Xiikl

NC_P
k=1

NQ_P
l=1

NQ_P
l=1

CAi

NN_P
i=1

NJ_P
J=1

NN_P
i=1

NC_P
k=1

CEikXijkl +

NJ_P
i=1

NJ×NC×NQ

MinZ =

ou

MinZ =

NNP i=1

NJP j=1

NCP k=1

NQP l=1

CEikXijkl +

NNP i=1

CAi max j E {1,..,NJ} k E {1,..,NC} l E {1,..,NQ}

{Xijkl }

4.4.4 Définition des contraintes

1. Contraintes de demandes

Ces contraintes garantissent que lademande mensuelle duclient sera satisfaite avec une marge flexibilité.

NN_P NQ_P Fm_P i=1 l=1 j=D_m

DMkm - ákm =

QiXijkl =DMkm + ákm m = 1, NM

k = 1,NC

2. Contraintes portuaires - Au port de chargement

Ces contraintes expriment quun quai ne peut accueillir qu'un navire dans le même jour.

NN_P NC_P j=1 K=1

Xjjkl < 1 j=1,NJ l=1,NQ

- Aux ports de déchargement:

Ce type de contraintes expriment quun client ne peut recevoir que certains types de navires.

Xjjkl <ajK i = 1, NN J = 1, NJ k = 1, NC

l= 1,NQ

3. Contraintes de rotations Ce type de contraintes exprime à la fois

~ un navire ne peut pas servir plus dun client en même temps

~ un navire ne peut pas effectuer un chargement aprés la finde lannée.

mjn{J+DRi ,NJ} P 8=J	NCP t=1
		Xjj8t < 1 i = 1, NN J = 1, NJ

k=1,NC l=1,NQ

?

?????????????????????????????????????? ?

???????????????????????????????????????

	NNP i=1	NQP l=1	FmP j=Dm
DMkm - ákm <				QiXijkl <DMkm + ákm m= 1, NM k = 1, NC

Xijkl < 1 j=1,NJ l=1,NQ

NN_P NC_P i=1 K=1

4.4.5 Résumé du modèle

min{J+DRik ,NJ} P s=J	NCP t=1
		Xijst <1 i=1,NN J=1,NJ k=1,NC l=1,NQ

Xijkl<aiK i=1,NN J=1,NJ k=1,NC l=1,NQ

MinZ = NN_P NJ_P NC_P NQ_P CEikXijkl + NN_P CAi

i=1 J=1 k=1 l=1 i=1

NJ_P NC_P NQ_P Xiikl i=1 k=1 l=1

NJ×NC×NQ

Xijkl?{0,1} i=1,NN j=1,NJ k=1,NC l=1,NQ

Chapitre 5

Approche théorique de résolution

5.1 Présentation de la méthode de Recherche Tabou

La méthode Tabou est une technique itérative généralepour 'optimii sation combinatoire, introduite par FRED CLOVER en 1977 et développée plus tard. La recherche Tabou est considérée comme étant une puissante proo cédure d'optimisation capable dorganiser et de diriger es opérations d'une méthode subordonnée.

La Recherche Tabou a remporté un immense succès dans de nombreux proo blèmes d'optimisation combinatoire à savoir les problèmesd'affectations quaa dratiques ainsi que l'ordonnancement et autres.

5.1.1 Principe de la méthode de Recherche Tabou

La procédure de la Recherche Tabou est destinée àtrouverun minimum global d'une fonction F définie sur un ensemble desolutions réalisablesX. pour chaque solution S de X on définit un voisinage N(S) constitué de toutes les solutions réalisables qui peuvent être obtenues par'application d'une simple modification m sur S.

La procédure commence par une solution réalisable initialeet tente d'att teindre un optimum global du problème par un déplacement àchaque étape, dés qu'une solution réalisable est obtenue, on génère un soussensembleV^* de N(S) et on se déplace versla meilleure solution S^* dans V *. Si l'ensemble N(S) n'est pas très large, il est possible de prendreV^* = N(S).

L'utilité du critère du meilleur déplacement dans la Recherche Tabou est basée sur la supposition que des placements avec beaucoupd'évaluations ont de plus grandes probabilités datteindre une solution optimale ou proche de l'optimal) en peu d'étapes.

Afin d'échapper aux minimums locaux, le déplacement vers S^* est effectué même si S^* est plus mauvaise que S (F(S^*) = F(S))

1. Liste Tabou

La stratégie de la Recherche Tabou peut clairement nduiree ccycle de l'algorithme. Afin de prévenir cela, on introduit une liste notée T Cette liste contient les modifications effectuées dans un passéde T étapes de l'algorithme.

Lors de la constructionon introduit la génération des solutions qui sont obtenues de S par application inverse mémoriséedans a iste Tabou.

Le principe réduit le risque de cyclage dés lors qui nous ne garantisse pas un retour pour un nombre donné dirritations à une solution déjà visitée au par avant.

2. Critère d'aspiration

Malheureusement, la liste Tabou pourrait jouer le rôlequi consiste ànterdire de se déplacer vers des nouvelles régions susceptiblesde contenir de meilleures solutions. Dans le but davoir une plus grande iberté dans la génération d'un sous-ensemble V il devrait être possible de perdre le statut Tabou d'une modification quandil sembleraisonnable de e faire. C'est pourquoi onintroduit pour chaque valeur possibleZde a fonction objectif une valeur daspirationA(Z). une solution Sdans N(SS qui veut devenir Tabou à cause de lalisteTabou peut quand même être prise en compte si F(S) < A(F(S)), la fonction A est appelée fonction d'aspiration.

3. Critère d'arrêt

La règle pouvant être définie pour interromprele déroulement du processus de la Recherche Tabou est darrêterdés quemax térations sont effectuées sans diminuer la valeur de la fonction objectifqui correspond à la solution courante atteint une valeur F_mn de F qui est connue dans certains problèmes.

Remarque

La notationS = S m veut dire : S est obtenue à partir de S par application de la modification mi.

5.1.2 Algorithme général de la méthode Recherche Ta- hou

1. Générer une solution réalisable S dans X

S() :=S; S() la meilleure solution rencontrée

FIG. 5.1 Organigramme de la méthode de Recherche Tabou

niter := 0; Compteur d'itérations

bestiter := 0; L'itération à laquelle une meilleure solution aététrouvée. T:=Ø;

Initialiser la fonction daspiration

2. Tant que (F(S) ~ Fmnetniter - bestiter < i_max) faire :

Générer un ensemble V * de solutions Si = S midans N(S) tel que : mi ? T ou F(Si) <A(F(S));

choisir la meilleure solution S^* dans V *

mettre à jour la liste Tabou T et la fonction daspiration SiF(S^*) < F(S()) alors

S() := S^* ;

Bestiter := niter ;

S:=S^*; Fin;

5.2 Les algorithmes génétiques

L'observation des phénomènes biologiques est unetrès riche source d'inss piration pour les ingénieursLe concept dalgorithme génétique notamment, généralisé ces dix dernières années sous le termed'algorithme évolutionnaire en est un excellent exemple. Les principes de base de ces algorithmes on dit aussi "AE" pour "Algorithme évolutionnaire") sont une transpositionnforr matique simplifiée de la très célèbre théorie de Darwin.

En d'autres termes, on imite au sein dun programme lacapacité d'une population d'organismes vivants àsadapter à son environnement à'aide de mécanismes de sélection et d'héritage génétique.

5.2.1 Historique

La transposition des principes dévolution darwinistes entechnique d'opp timisation globale est née indépendamment des deux côtés de 'océanAtlann tique il y a une quarantaine d'années

L'idée maîtresse en est l'imitation du phénomènedapprentissage collectif ou d'adaptation d'une population naturelle.

Deux courants ont évolué parallèlement usquà ily a une quinzaine d'ann nées, chacun ayant son champ d'application propre.La récente fusion de ces différents courants sous le terme dalgorithme évolutionnaire est corrélée à leur attrait actuel pourles chercheurs et les industriels, grrcenotamment à la vulgarisation des calculateurs parallèles et à 'accroissement despuissances de calculs.

Le courant américain, initialisé par Hollanddans les années soixante, est à l'origine de ce que l'on appelleles Algorithmes Génétiques AG). Bien qu'ils aient été prévus initialement dans le cadre doptimisation ou d'adaptation dans le domaine discret, les AG ont été facilementétendus à 'optimisation sur des domaines continus.

En Allemagne sont apparuesà peu près en même temps, des méthodes appelées Stratégies d'Evolution (SE) Ces méthodes étaient au contraire préé vues pour explorer des domaines continus, et ont été étendues à desapplicaa tions en optimisation discrète

Ce livre est issu d'un certain nombre didées et de concepts sur esquelsl a travaillé à partir des années 60Quelques-uns deses élèves à 'universitédu Michigan ont pris la suite.

Jusque dans les années 80, l'intérêt pour ces méthodes étaitplutôt anec dotique car il existait assez peu dapplications réelles.

Durant cette même décennie sont apparues de nombreuses applicationsdans des domaines très divers. Les travaux de Goldberg,et notamment ses app plications au contrôle de pipelines de gaz en sont un exemple maintenant classique.

5.2.2 Mécanisme

Le principe de base des algorithmes génétiques est la manipulation de po0 pulations qui évoluent sousl'action dopérateurs stochastiques.Lévolution est usuellement organisée en générations et copiede façontrès simpli~éea génétique naturelle.

Les moteurs de cette évolution sont dune part asélection, iée àa perr formance d'un individu, vis à vis du problème que lon cherche à résoudre, et d'autre part les opérateurs génétiques, usuellement nommés croisement et mutation, qui génèrent lesindividus dune nouvelle génération action d'exx ploration).

L'idée fondamentale des algorithmes génétiques est a suivante e paa trimoine génétique d'une population donnée contient potentiellement a soo lution, ou plutôt une meilleure solution au problème donnéCette solution n'est pas exprimée car la combinaison génétique sur laquelle elle repose est dispersée chez plusieurs individus ; ce n'est que par lassociationde ces combinaisons génétiques au cours dela reproduction quea solution pourras'exx primer.

De cette façon, de génération en génération, les meilleursgènes se proo pagent dans la population, en se combinant et en échangeant esmeilleurs traits.

5.2.3 La boucle évolutionnaire

1. la reproduction: sélection des parents parmi une populationde ,t individus pour engendrer À enfants;

2. croisement et mutation à partir des À individus engendrant les À enfants;

3. évaluation des performances des enfants

4. sélection pour la survie de ,t individus parmi les À enfants et ,t parents selon les paramètres choisis pour lalgorithme, afinde formera population à la génération suivante.

Pour l'utiliser, on doit disposer des cinq éléments suivants

1. Un principe de codage des éléments de la population

Cette étape associe à chacun des pointsde lespaced'état une structure de données en éléments sur lesquels peuvent s'appliquer es trois opérateurs présentés ci-dessous.

Le choix du codage des données conditionne le succès des algorithmes génétiques. Les codages binaires ont ététrès emplooyés à 'origine.

Les codages réels sont désormais largement utilisés, notamment dans les domaines applicatifspour loptimisation de problèmes àvariables continues.

Ce codage intervient après une phase indispensablede modélisation mathématique du problème.

2. Un mécanisme de génération de la population initiale

Ce mécanisme doit être capable de produire une population d'individus non homogène qui servira de base pour les générations futures. Le choix de la population initiale est important car lpeut rendre plus ou moins rapide la convergence vers loptimum global.

Dans le cas où l'on ne connaît rien du problème àrésoudre, lest essentiel que la populationinitiale soit répartie sur tout edomaine de recherche.

3. Une fonction de performance :

Celle-ci prend ses valeurs dans R⁺ ; elle est appelée fitness ou fonction d'évaluation de l'individu. Elle est utilisée pour sélectionner et reproduire les meilleurs individus de la population.

4. Des opérateurs de croisement et de mutation

Ces opérateurs permettent de diversifier la population aucours des générations et d'explorer lespace détat. Lopérateur de croisement recompose les gènes d'individus existants dans la population, 'opérateur de mutation a pour but de garantir lexplorationde 'espace d'état.

5. Des paramètres de dimensionnement

Taille de la population, critère darrêt, probabilités de croisement (Pc) et de mutation (Pin).

FIG. 5.2 Organigramme del'algorithme évolutionnairegénétique

5.2.4 Description détaillée des éléments de llalgorithme

Codage des données

La première étape est de définir et de coder convenablement eproblème. A chaque variable d'optimisation xi, nous faisons correspondre un gène. Nous appelons chromosome un ensemble de gènes.

Chaque solution est représentée par un individu doté d'un génotype constitué d'un ou plusieurs chromosomes. Nous appelons populationun ensemble de N individus que nous allons faire évoluer

Un chromosome est un tableau de gènes (Fig 4.3) Un individuest un tableau de chromosomes. La population est un tableaud'individus.

FIG. 5.3 Illustration schématique du codage des variables xi.

On aboutit à une structure présentant cinq niveauxd'organisation(ig 4.2):

FIG. 5.4 Les cinq niveaux d'organisation de l'AG

Historiquement, le codage utilisé par les algorithmes génétiques était ree présenté sous forme de chaînes de bits contenant toute 'informationnécess saire à la description d'un point dans lespace détat.Ce type de codage a pour intérêt de permettre de créer des opérateursde croisement et demutaa tion simples.

Pour des problèmes d'optimisation dansdes espaces de grande dimension, le codage binaire peut rapidement devenir mauvais.Généralement, chaque variable est représentée par une partiede la chaîne de bits eta structure du problème n'est pas bien reflétée lordre des variables ayant une mportance dans la structure du chromosome, alors quilnen a pas forcément dansa structure du problème.

Les algorithmes génétiques utilisant des vecteurs réels évitent ce proo blème en conservant les variables du problème dans le codage de 'élément de population, sans passer par le codage binaire intermédiaire.

Génération de la population initiale

Elle est usuellement aléatoire (diverses stratégies sont d'ailleurs envisaa geables pour échantillonner correctement un espace de recherche complexe ou de grande dimension).

Le choix de la population initiale dindividus conditionne fortement a rapidité de l'algorithme.

Si la position de l'optimum dans l'espace détat est totalement nconnue, il est naturel d'engendrer aléatoirement des individus en faisant des tirages uniformes dans chacun des domaines associés aux composantesde 'espace d'état, en veillant à ce que les individus produits respectent es contraintess Si par contre, des informations à priori sur le problème sont disponibles, l paraît bien évidemment naturel dengendrer les individus dans un sous-domaine particulier afin d'accélérerla convergence.

Dans l'hypothèse où la gestion des contraintes ne peut se faire directe ment, les contraintes sont généralement incluses dans e critère à optimiser sous forme de pénalités.

Opérateurs

A- Opérateurs de sélection :

A chaque génération, des individus se reproduisent, survivent oudisparaissent de la population sous lactiondedeux opérateursde sélection

~ la sélection pour la reproductionou plus simplement sélection, qui dé-
termine combien de fois un individu sera reproduit en une génération

~ la sélection pour le remplacementou toutsimplement, le remplacement, qui détermine quels individus devront disparaîtrede la population à chaque génération

La capacité d'un individu à être sélectionné, que ce soitpour a reproduction ou pour le remplacementdépend de sa performance un ndividu sera sélectionné d'autant plus souvent quilest meilleurr l faut donc, qu'une valeur de performance soit attachée àchaque ndividu, et qu'elle soit évaluée pour les nouveaux individus créés lors de chaque générationn

(a) Sélection pour la reproduction

On trouve dans la littérature un nombre important de principes de sélection plus ou moins adaptés aux problèmes quils traitent, parmi ces principes nous citerons

~ N/2-élitisme :

Les individus sont triés selon leur fonctiondadaptation. eule la moitié supérieure de la populationcorrespondant auxmeilleurs composants, est sélectionnée. Il a été constaté quecette méthode induisait une convergence prématurée de lalgorithme a pression de sélection est trop forte

Il est en effet nécessaire de maintenir une diversité génétique su~- sante dans la population, celle-ci constituant un réservoirde gènes pouvant être utiles par la suite.

- La méthode de la roulette :

Cette méthode, appelée aussi Roulette wheel selection, RWS, consiste à associer à chaque individu un segment dont a longueur est proportionnelle à sa fonction de performance.On reproduitci le principe de tirage aléatoire utilisé dans les roulettesde casinos avec une structure linéaireCes segments sont ensuite concaténés sur un axe que l'on normalise entre 0 et 1. On tire alors un nombre aléatoire de distribution uniforme entre 0 et 1, puis on "observe" quel est le segment sélectionné

Avec ce système, les grands segments, cest-àdire les bons ndividus, seront plus souvent choisis que les petits.

Lorsque la dimension de la population est réduite, ilest di~- cile d'obtenir en pratiquel'espérance mathématique de sélection en raison du peu de tirages effectués.

- La méthode de la roulette modifiée :

Cette méthode, appelée aussi Stochastic remainder without replacement selection, SRWRS, découle de celle de la roulette.

La SRWRS évite le problème rencontré dans la méthode ^précédente et donne de bons résultats

Le principe de cette méthode consiste tout dabord, àsélecc tionner n individus (n À) tel que:

~ l'individu xi est sélectionné si sa valeur de performance est supérieure à la moyenne (moy) de toutes les performances

~ chaque individu xi est représenté m(xi) fois où m(xi) est la partie entière du rapport de la valeur de la performancede xi et la moyenne de toutes les performances (moy) :

[h'(xi) ]

m(xi) := moy

Ensuite, la sélection des (À - n) individus restants se fait par la méthode RWS.

(b) Sélection pour le remplacement

Le remplacement gère la constitution de la génération (g + 1).

Pour cette sélection aussi, il existe plusieurs stratégiespour constituer la génération suivante.Par exemple les stratégies d'évoo lution (u, À) et (u + À) signifient que À descendants sont générés à partir d'une population de u individus.

La stratégie "," consiste à gérer l'élitisme par le biais de la différence (u - À) (on garde les (u - À) meilleurs individus de la population courante et on complète par les À descendants), tandis que la stratégie "+" est une version plus adaptative dans sa gestionde l'élitisme : à partir d'un ensemble intermédiairedetaille u+À constitué des u individus de la population courante et des À descendants, on sélectionne les u meilleurs individus de la génération suivante.

la génération g + 1 les enfants engendrés à la génération g. Ainsi on a u= À.

B- Opérateurs de variations

(a) Opérateur de croisement

Le croisement a pour but denrichir la diversitéde la population en manipulant la structure des chromosomes.

Classiquement, les croisements sont envisagés avecdeux parents et génèrent deux enfants.

Initialement, le croisement associé au codage parchaînesde bits est le croisement à découpage de chromosomes (slicingcrossover). Pour effectuer ce type de croisement sur des chromosomesconstitués de M gènes, on tire aléatoirement une position dans chacun des parents. On échange ensuite les deuxsous-chaînes terminales de chacun des deux chromosomes, ce qui produit deux enfants.

On peut étendre ce principe en découpant le chromosome non pas en 2 sous chaînes mais en 34, etc

FIG. 5.5 - Représentation schématique du croisement en un point

FIG. 5.6 Représentation schématique du croisement endeux points

L'opérateur respecte généralement les propriétés suivantes

~ le croisement de deux parentsidentiques donnerades descendants identiques aux parents ;

~ par extension, deux parents proches lun de lautre dans l'ess pace de recherche engendreront des descendants qui leur seront proches;

Le taux de croisement détermine la proportiondes ndividus qui sont croisés parmi ceux qui remplaceront lancienne génération.Plus le taux de croisement est élevéplusil y aurade nouvelles structures qui apparaissent dans la population. Mais ilne faut pasqu'ilsoit trop élevé car de "bonnes" structures risqueraient d'êtrecassées trop vite par rapport àl'amélioration que peut apporter a sélectionl ne faut pas non plus qu'il soit trop faibles car la recherche risque de stagner à cause du faible taux dexploration.

Le taux habituel est choisi entre 60% et 90%. (b) Opérateur de mutation

L'opérateur de mutation apporte aux algorithmesgénétiques la propriété d'ergodicité de parcours despace.Cette propriéténn dique que l'algorithme génétique sera susceptible datteindretous les points de l'espace d'état, sans pour autantles parcourirtous dans le processus de résolution

Pour les problèmes discretslopérateurde mutation consiste géé néralement à tirer aléatoirement un gène dans lechromosome et à le remplacer par une valeur aléatoire.

La proportion des individus mutés dans la populationest égale au taux de mutation qui est typiquement faible, de l'ordrede 0.001 et 0.05.

Un taux de mutation trop élevé rend la recherchetrop aléatoire par contre avec un taux de mutation trop faible, la recherche risque de se concentrer toujours sur les mêmes individus et de mal explorer le domaine de recherche.

FIG. 5.7 Représentation schématique de la mutation Critère d'arrêt

L'arrêt de l'évolution d'un algorithme génétiqueest 'une desdifficultés majeures car il est souvent difficile desavoirsi lon atrouvé 'optimum.

Actuellement les critèresles plus utilisés sont les suivants

~ arrêt de l'algorithme après un certain nombre de générations, fixé au départ; c'est ce que l'on est tenté de faire lorsque l'ondoittrouverune solution dans un temps limité

~ l'algorithme peut être arrêté lorsque la populationnévolue plus ou plus suffisamment rapidement, c-à-d les meilleurs individus nes'améliorent plus depuis un certain nombre de générations.

5.2.5 Considérations sur la convergence des algorithmes évolutionnaires :

On dira qu'un algorithme évolutionnaire a convergé versunoptimum global si, après un nombre suffisant de générations, au moins un ndividu a pu se trouver dans un voisinage arbitrairement petitde cetoptimum.

La question de cette convergence se formule de la manière suivante quelles sont les propriétés que doivent respecter es opérateurs de variation et de sélection pour que la convergence soit garantie ? Et dans ce cas, quelle vitesse de convergence peut-on espérer?

Des réponses partielles ont été apportées pour des représentations et opérateurs particulierset des réponses précises existent mais seulementpour quelques problèmes très simples.

5.2.6 Optimisation évolutionnaire avec contraintes

Les problémes d'optimisation doivent souvent respecter uncertainnombre de contraintes. Celles-ci se traduisent par unensemblede relationsquedoivent

satisfaire les variables qui sont généralement exprimées comme un ensemble de q inégalités :

Gi(x) = 0 ?i = 1,..,q

où x est une solution du problème d'optimisation. On appelle F l'ensemble des solutions réalisables

Dans le cas des algorithmes évolutionnaires, le vecteur x est un individu. Les opérateurs de variation standard décrits plus haut, poura représentation binaire ou réelle, engendrent des individus de façon aveugle, ne tenant pas compte des contrainteset qui peuvent correspondre à des solutionsrréalisables.

Les approches les plus classiques et les plus faciles à mettre enoeuvre sont celles qui agissent directement sur la fonction de performance, et ceci par l'application de méthodes de pénalisation de afonctton de peeroomanne. Le principe est simple : la performance dun individu irréalisable est réduite par la soustraction d'une pénalité

f_p(x) = f(x) - p(x)

où p(x) est définie dans le cas général comme une fonction positive, croissante par rapport aux mesures de violationdes contraintesçi(x), telles que :

f

çi(x) > 0 si la i^eme contrainte n'est pas respectée, çi(x) = 0 {sinon}. Typiquement,

P(x) = P( _Xq áiçâ _i (x))

i=1

P : est une fonction croissante

ái : un coefficient positif dontla valeur est autant plus grande qu'il est accordé d'importance au respect dela i^eme contrainte;

â: est fixée typiquement à 1 ou 2

Pour fixer les paramètresplutôt quutiliser une pénalité statique, on a opté pour une pénalité dynamique caril peut être avantageux de faire varier les pénalités aussi bien dans ledomaineréalisable, qu'irréalisableePuis, lorsque l'évolution est bien avancée, les coefficients de pénalité doivent alors prendre des valeurs élevées en faveur des individus réalisabless

Comme méthode utilisant cette forme de pénalité, on peut citer oines et Houk qui ont proposé en 1994 la fonction de pénalité suivante

Pi(x)=t^k _Xq áiçâ _i (x)

i=1

où :

t : représente le nombre de générations accomplies k : prend la valeur constante de 1 ou 2

Calcul de la fonction de performance a- Fonction de performance (fitness)

La construction d'une fonction de fitness appropriée esttrèsmpor-

tante pour obtenir un bon fonctionnementdun algorithme évolutionnairee On peut citer quelques caractéristiques de la fonctiond'évaluation des

individus :

~ la fonction de performance dépend des critères que 'on veut maximiser ou minimiser;

~ elle peut changer de façon dynamique pendant le processus de recherche ~ elle peut être si compliquée qu'on ne peut calculer que sa valeur approchée;

~ elle doit, si elle est correctement construite, attribuer des valeurs très différentes aux individus afin de faciliter la sélection

~ elle doit considérer les contraintes du problème.S'ilpeut apparaatre des solutions invalides, la fonction de fitness doit pouvoir attribuerune valeur proportionnelle au non respect des contraintes

~ la valeur de la fonction de fitness peut être aussi attribuée par'utilisaa teur.

On définit le "rang" d'un individu commele nombre dindividus qui le dominent. Par exemple, si l'on considère un individu x à la génération t qui est dominé par Pi(x), le rang de l'individu considéré est donné par

Rangt(x) = 1 + Pi(x)

A tous les individus non dominés on affecte le rang 1Les ndividus dominés se voient donc affectés un rang important.

Pour le calcule de l'efficacité, on passe par les étapes suivantes

(a) classer les individus selon leur rang

(b) affecter une efficacité à chaque individu en interpolant du meilleur (rang 1) jusqu'au plus mauvais (rang n), et cela en utilisant une fonction linéaire dynamique ft(x) donnée comme suit :

ft(x) = t x (,t + 1 - Rangt(x))

Pour ce type de méthode, le nombre de comparaisons effectuéespar générations est égal à ,t x (,t - 1) x k

où ,t correspond au nombre d'individus dans la population, et k le nombre d'objectifs(Dans notre cas k=1)

Chapitre 6

Résolution du problème

Ce chapitre porte sur la description et la mise en oeuvrede deuxméthodes heuristiques pour résoudre ce problème, entre autre choisirdeux méthodes adéquates, les adapter au problème, puis comparer les résultats etes performances des deux méthodes.

6.1 Choix des méthodes

Notre choix s'est porté sur la méthodede la recherche tabou etaméthode génétique. La résolution peut être envisagéeen deux étapes, apremière consiste à trouver une solution réalisablededépartpour améthode recherche tabou, et un ensemble de solutions réalisables pour la méthode génétique.La seconde étape consiste à améliorer la solution obtenue dans a première étape.

6.2 Justifications du choix

Rappelons que notre problème est un problème en variables bivalentes. Si ce problème pourrait se formuler en un nombre restreint de variables, on aurait pu peut-être utiliser une méthode de séparation etévaluation par exemple, mais vu le nombre important de variables, et compte tenu que ces variables soient bivalentes, on était contraint àse diriger versesmétaheuristiques.

1. Méthode 1

Vu la complexité du problème, la nature de la fonction objectiffqui est non linéaire, et qu'il n'existe pas de méthodes exactes pour a résolution de ce type de problème, nous avons décidé derésoudrenotre problème avec une métaheuristique Génétique

Ce choix est justifié par la facilité dadaptation des algorithmes génétiques aux différents problèmes, et par le temps decalcul de ces algorithmes qui est acceptable, et aussi de vouloir comparer deux approches fondamentalement différentes, la méthode génétique qui est une méthode évolutive, etla méthode de recherche tabou qui estune méthode séquentielle.

2. Méthode 2

L'application de la méthode Recherche Tabou " sur des problèmes d'affectations de grande dimension, a généralement abouti àdes résull tats très satisfaisants, et envisageables dans a pratique si cetteméé thode est bien exploitée, dansle sens ou lefficacité de cette méthode générale, est flexible et dépendante particulièrement de la façonde son adaptations au problèmecest pour cela quon achoisi a méthode de la recherche tabou comme méthode de résolution à notreproblème.

6.3 Adaptation de la méthode génétique

L'adaptation de la méthode génétique à un problème, consiste d'abord à établir un bon codage dela solution, puis à ladaptationde tous esopérateurs de cette méthode à ce problème, car en seins de ces opérateurs que 'adapp tation sera la plus aigueet bien sûr ladaptationde 'algorithme général, en choisissant les probabilités de reproduction, et de mutation.

6.3.1 Codage de la solution et des données

Avant de procéder au codage de la solution, on doitétablirun codage précis des données.

Codage des données

Pour le codage des donnéeson définieles variables suivantes

1. NbNavire : représente le nombre de navires de Sonatrach plus les navires susceptibles d'être affrétés

2. NbPort : représente le nombre de ports de déchargement

3. NbMois : représente le nombre de mois de la période détude

4. NbMaxRotation : représente le nombre maximum de rotation que le navire le plus rapide pourra effectuer

Les données des navires et des ports de déchargement, seront respectivee ment stockés dans les enregistrements CelluleNavire et CellulePort, détaillé dans le tableau suivant :

CelluleNavire=Enregistrement

Num : entier Positif ; {Numéro du navirej

Cap : entier Positif ; {Capacité du navirej

Vit: entier Postif ; {Vitesse du navirej

Deb : entier Positif ; { Débit de déchargement du navire}

Fin;

CellulePort= Enregistrement

Num : entier Positif ; {Numéro du port}

CapMin: entier Positf{Capacité d'accueil minimumj

CapMax : entier Postf{Capacité d'accueilmaximumj

FraisP: entier Postf{Frais portuairesj

Deb : entier Positif ; {Débit de déchargement du porttj

DMin :Tableau[1..nbPort,1nbMos]dentier Positif{Demandes mensuelles minimumj DMax :Tableau[1..nbPort1nbMos]dentier Positif{Demandes mensuelles maximumj Fin;

Codage de la solution

A fin d'économiser l'espace mémoireet de faciliter la programmation de ces méthodes de résolutionson a opté pour le codage suivantt

CelulleRotation =Enregistrement

J :entier positif ; {Jour de chargement de la rotationj

D :entier positif ; {Destination de chargement de la rotation J

Q :entier positif ; {Quai de chargement de larotation}

Fin;

Sol =Tableaij[1..nbNavire,1..nbRotaton] de CeueRotation

Exemple

SoI[i,r].J : {Le jour de chargement de larotation r e~ectuée par enavirei; SoI[i,r].D : {Le numéro de la destination de la rotation r efectuée pare naairei; SoI[i,r].Q : {Le numéro du quai de chargementde la rotation r efectuée pare naaire i;

Explication du codage de la solution

La solution du problème sera représentée par une matrice, Sol, de taille NbNavire × NbMaxRotation, entre autre la matrice Sol comporte NbNavire lignes, qui comporte chacune d'elles NbMaxRotationde cellule CelleleRotaa tion.

Une cellule CelluleRotation, représente les informations relative à une seule rotation, elle comporte trois entiers positifqui représente respective ment, le jour de chargement de la rotation,ladestinationde a rotation, ete poste de chargement dela rotation.

Notons que le navire qui effectue la rotation nest pas représenté par un entier, il est en fait donné par lalignede la cellule CelluleRotation, car chaque ligne représente les rotations effectuées par un naviretout au ong de'année.

En fin, L'ensemble de la population (des solutions dune génération sera représenté par le tableau suivant

TSol=Tableau[1..100] de Sol;

Illustration

Le codage d'une seule solution estillustré dans lexemple suivant.

Pour cet exemple le nombre maximum de rotation sera égalà3, etenombre de navires sera aussi égal à 3

	Rotation 1			Rotation 2			Rotation 3
	Jour	Destination	Quai	Jour	Destination	Quai	Jour	Destination	Quai
Navire 1	5	6	2	14	2	3	0	0	0
Navire 2	4	3	5	30	5	5	49	1	5
Navire 3	0	0	0	0	0	0	0	0	0

Dans l'exemple précédent Le navire 1 effectuera

~ Le chargement pour sa première rotationle our verse port6, à partir du poste de chargement 2

~ Le chargement pour la deuxième rotation le jour 14 verse port2, à partir du poste de chargement 3et aveccette rotation enavire 1 accomplira sont programme

Par contre le navire 3, n'effectuera aucunerotation, ce navirene serapas affrété.

6.3.2 Procedure Recherche de solutions réallsables

la procédure suivante génère une solutionréalisable pour notre problème

Procedure Sol-réal(E/S Sol Solution) Var

i : entier positif ; {indice navirej

j : entier positif ; {indice port}

m : entier positif ; { indice moisj

DM :Tableau[1..nbMois] d'enter positif FM :Tableau[1..nbMois] d'enter positif

{Les tableaux precedents representent les datesdedébut, et dea fn des mois dea durée détude Exemple : FM[mJ : date dela fn du mois[m]}

QT :réel;

{QT est utilisé par l'algorithme pour calculera somme dea quantitéransportée chaque mois vers leclient}

JourDisCour[i]Tableau[1Nb-Navire ] de entier positif

{Numéro du jour de disponibilité courant dunavire[i]j

RotCour [i] : Tableau[1NbNavire ] de entier positif

{Numéro de la Rotation courantedu navire[iiJJ

Début

Pour m :=1 à Nb-Mois faire {pour chaque mois fairej

Tri-Aléa-Port(TabPort,NbPort)

{Cette procedure trie aléatoirement le tableau TabPortt

Le tri des ports selon l'ordre décroissant des quantitésmensuelles aurais du nous donner une solution plus proche de l'optimum que celle qui sera trouvéepareri aléatoire, mais on doit introduire laléatoire

pour garantir de trouver un nombre important de solutions réalisables diiferentes en unemps acceptable.}

Pour i :=1 à Nb-Navire faire {pour chaque navire faire}

Si jourDis[i] <DM[m] alors JourDis[i] :=DM[m] ; Finsi ;

Fait;

{Les demandes des mois précédents au mois[mJ supposées satisfaites,a boucle précedente a~ecte auxjours de disponibilité des navires qui pourront etreibre(disponiblee avantle début du mois en cour a date de début

de ce dernier,pour garantir que les naviresne fassent pas de rotations avant le début du mois en courr

Pour j :=1 à Nb-Port faire {pour chaque por[jJ faire J

Tri-Navire(TabNavire,nb-Navire)

{Cette procedure trie le tableau TabNavireconstitué de CelluleNavire par ordre croissant du rapport (coût de Rotation du navire[iijau port[jj/quantitéransportée parle navire[i[au port[j[j/ De cette manière, on favorise lesnavires lesplus rentables, et on fait un pas vers loptimumm

Suite de l'algorithme SolReal

I :=1; {Prendre le premier navire de la listeListeNavireAccc

QT :=0;

{ce compteur compte la quantité qui peut tre transportée_e paresotations affectéesjusquàla, au port[jJ le mois en cour [mJJ

Tant que (QT<port[j].DMn[m]) et (i<Nb-Navire-Acc) faire

{si quantité QT ne satisfait pas lademandeminimalemensuelle du port[j[j le mois[mm_Juiestreprésentéepar Port[j/.DMin[mJetles naviresde la liste ListeNavireAcc ne sont pasous eeplorés, lors pourccaque navire[i[de la liste ListeNavireAcc faireej

Si (JourDis[i] <FM[m]) et (QT+Navire[i] cap <= Port[j]DMax) alors

{Si le navire[i] dela Liste ListeNavireAcc est disponible avantla n du mois en cour et la quantité QT plus la quantité qui peutêtre transportée parenavire[i] ne dépasse paslauantité maaimale demandéepar le Port[j/ le mois en cour [mJ alors}

Début Quai :=AffetQuai(TabNavire[i]JourDsNavire[i]) Si quai<>0 alors

{si un quai compatible est disponiblee jour de disponibilité de navire alors}

Début

SoI[i,RotCour[i]] J := JourDsNav[i] SoI[i,RotCour [i]] D :=j

SoI[i,RotCour [i]] Q :=Qua

{Affectation d'une rotation au navireTabNavire[i]}

Qt :=Qt+TabNavire[i] cap ; {mise à jour du compteur QTJ

RotCour [i] := RotCour []+1

{incrementer la Cellulerotation encourrj

JourDisNav[i] := JourDsNav[i]+DureeRotationIj]

{mise à jour de la date de disponibilitédu navirei

Fin;

Sinon JourDisNav[i] := JourDsNav[i] +1

{si aucun quai compatible nest disponiblee jour ourDisNav[i]alorsle navire est considéré comme indisponible cejourla,donc le jour dedisponibilité du naviret incrementé par unjourr

Finsi;

Fin;

Sinon i :=i+1;

{Si le jour de disponibilité du navire , dépassea fn dumois en cour, on passe au navire suivant dans le tableau TabNavire J

Finsi; Fait; Fait; Fin.

Remarque 1

On a préféré donner l'algorithme détaillé de la procédureSolReal, car cette procédure est trés importante dans larésolution, et permet à 'algorithme de résolution de faire un grand pas vers loptimum.

Remarque 2

L'organigramme de cette procedure est donné parafigure 7..

6.3.3 Justification de l'algorithme SolReal

~ Le nombre de ports de déchargement est fini. A chaque foisqu'on saa tisfait la demande d'un port, on passe à un autre portde déchargement suivant l'ordre aléatoire des demandes. Les ports sont triés aléatoire ment à chaque mois pour générer un grand nombres de solutions réaa lisables differentes. Le processus sarrêteradés qu'on parcourt touses ports. Et à la fin de l'algorithme tous les ports seront satisfaits.

~ Le nombre de navires disponibles et compatibles avec un portde déé chargement est fini et non nul, car les navires disponibles dans a iste des navires candidats àl'affrétemetent, qui comporte es navires de Sonatrach plus les navires susceptibles dêtre affrétés sont argement suffisants pour satisfaire la demandedetous les ports de déchargement.

~ L'algorithme exploreles navires compatibles selon l'ordredutri établi par rapport à chaque portce tri se faitpar 'ordre croissantdu rapport (coût de la rotation du navire i vers le portj) / (la quantité transporr tée vers ce port par cette rotation decette maniire, on favorisees navires de meilleur rendement, donc on effectue un pas vers 'optimum.

~ Une rotation n'est affectée à un navire quedans e casoù enavire est disponible, plus exactement si il n'effectue aucune rotation, et ondiss pose d'un quai de chargementle jour de chargement dea rotation.La disponibilité du navire i est exprimée dans lalgorithme par a variable " JourDisNav[i] ".

~ La disponibilité d'un quai de chargement un jour donnéest vérifiée par la fonction " AffectQuai ", cette fonctionrenvoieenumérodu quai si ce dernier est disponible, et renvoi zéro si aucun quai nest disponible.

~ Si aucun quai n'est disponible le jour JourDisNav[iice dernièr sera incrémenté d'un jour, et le navire sera considérécomme indisponible jusqu'au prochain jour, car la durée de chargement de tous esnavires est à peu près de 24h, contrairement aux durées dedéchargements qui sont très différentes dun navire à un autre.

~ Les quantités transportées par les rotations affectéesemois en cours, jusqu'à le jour en cours, sont comptées par la variable QT sia somme de cette quantité avecla quantité éventuellement transportée pare navire en cours de traitement par lalgorithme se situe dansamarge de flexibilité de la demande mensuelle du portet un quai compatible et disponible, et le navire concerné est aussi disponible, une rotation sera affectée à ce navire, qui aura comme jour de chargement e premier jour de disponibilité du navire, de cette manière on minimise letemps de repos des navires.

~ Lorsque on affecte une rotationà un navire il faut précisera destination de la rotation, qui est tout simplement le portencoursde traitement par l'algorithme, et il faut préciser aussi le quai de chargement qui sera déterminé par la fonction " AffectQuai "

~ A chaque fois qu'une rotation est affectée à un navire, ejour de disponibilité de ce navire seraincrémenté par le nombrede jour qu'ilmet pour faire cette rotation.

6.3.4 Paramètres de l'algorithme Génétique

Population initiale

Pour l'application de l'algorithmenous avons choisi de prendreune population initiale de ,t = 100 individus, tous réalisables.

La génération d'une population non-homogène se faitde manière aléatoire avec la procédure "SolRéal"

6.3.5 Adaptation des opérateurs

L'opérateur de sélection

l'opérateur sélection sélectionne À = 50 pour la reproduction, par la méthode la roulette ,détaillée dans le chapitre précèdent.Rappelons que cette méthode favorise les individus les plus adaptés proportionnellement àeurs fonction d'adaptation.

L'opérateur de croisement

L'opérateur de croisement permetde créerdes nouvelles combinaisons des paramètres des composants. Nous avons choisi dans notre cas d'utiliser le croisement à découpage de chromosomes à un point.

Pour effectuer ce type de croisement sur des chromosomes, on tire aléatoirement une position de croisement identique dans chacun des parents.On échange ensuite les deux sous-chaînes terminales de chacun des deux chromosomes, ce qui produit deux enfants

Pour ce qui est du taux de croisement nous avons choisi, Pc = 0, 6. Exemple

Soient deux individus X, Y tirés aléatoirement de la population courante. Dans cet exemple, on croise àla ^6ieme position.

X = {2,2,1,2,3 ,

|{z} 5,1,1,3,4,5,4,0,0,0,0,0,0}

Y= {1,1,2,3,4 ,

|{z} 4,2,1,5,2,3,2,4,2,2,2,3,1}

Après croisement on obtient

X' = {2,2,1,2,3 ,

|{z} 4,2,1,5,2,3,2,4,2,2,2,3,1}

Y' = {1,1,2,3,4 ,

|{z} 5,1,1,3,4,5,4,0,0,0,0,0,0}

La procédure de croisement est décrite ci dessous

Pour i := 1 à À faire

1- Tirer au hasard deux individus X et Y de la population séléctonnée à la reproduction

2- Tirer aléatoirement et uniformément "r" un réel entre 0 et 1 ;

3- Si (r < Pc) Alors

-Générer aléatoirement une position"P" ;

-Croiser les individus X et Y à la position "P" pour obtenir X ' et Y'

Sinon

Garder les deux vecteurs X et Y;

Fin Si

Fin Pour

Algorithme 1: Procédure Croisement

L'opérateur de mutation

L'opérateur de mutation est un opérateur unaire, générant un seul individu à partir d'un autre et qui consiste àtirer aléatoirement un gène dans le chromosome et àle remplacer par une valeur aléatoire.

Pour ce qui est du taux de mutation nous avons choisi, Pm = 0, 02. Exemple

Soit un individus X tiré aléatoirement de la population courante. Dans cet exemple, on mute X à la ^5ieme position.

X= {2,2,1,2,3

_|{z},5,1,1,3,4,5,4,,0,0,0,0,0,0}

Aprés mutation on obtient

X= {2,2,1,2,5

_|{z},5,1,1,3,4,5,4,,0,0,0,0,0,0}

La procédure de mutation est décrite ci dessous

Pour i := 1 à À faire

1-Tirer un individus de la population séléctionnée à la reproduc tion; 2-Tirer un réel "a" uniformément dans [0,1] ;

2- Si (a < Pin) Alors

Muter l'individu:

2.1-Tirer au hasard une position i entre 1 et nbNavire 3- Si (Le nombre de rotations affectées au navireest

superieure à 1) Alors

3.1-Tirer au hasard un jour j de lannée

3.2- Si (Le navire i effectue une rotation je jour j) Alors Enlever la rotation r au navire i

Sinon

Affecter au navire i une nouvelle rotation, à partir du jour j, si la contrainte Rotation est toujours verifiée

Fin Si

Sinon

Affecter au navire i une nouvelle rotation Fin Si

Fin Si

Fin Pour

Algorithme 2: Procédure Mutation

L'opérateur de sélection pour le remplacement

L'opérateur sélection pour le remplacement sélectionne tout simplement les À = 50 plus mauvais individus pour les remplacer avec les À = 50 meilleurs individus parmi les i+À individus constitués par génération courante plus les enfants reproduits parles opérateurs croisement etmutation. Donc on utilise la stratégie (i + À), cette stratégie a été détaillé dans le chapitre précèdent.

Critére d'arrêt

le critère d'arrêt pour lequel on à opté, est celui de fixer enombremaximum d'itération.

6.4 Adaptation de la méthode de la recherche tabou 6.4.1 Le codage de la solution

La solution qui sera créer et en suite manipuler par 'algorithme, sera représentée par le type Sol déclaré précédemment.

6.4.2 Génération d'une solution réalisable

Pour générer une sotution réalisable on utilise la même Procedureuntisée pour générer des solutions réalisables pour la méthode génétique, avecune petite modification, au niveau du tri aléatoiredes demandesmensuelles, qui sera remplacé par le tri décroissant des demandes mensuellessOn peut se permettre de faire ce tricar avec la méthode Tabou, onn'a pasbesoin de générer plusieurs solutions differentes. Donc l'organigramme de a procedure qui gegère des solutions réalisable pour la méthodedea recherche tabou, est repésentée dans la figure 46

6.4.3 Génération des solutions voisines

La génération de solutions voisines est une étape trésmportantedans l'application de l'algorithme de la recherchetabou.Lalgorithme doit avoir accès à toutes les solutions réalisables.

Pour cette raison qu'on definie lalgorithme suivant

1-Tirer aléatoirement deux navires N1 et N2de La iste desnaviresaller

en 2

2-Tirer aléatoirement un mois parmi les mois de la période d'étude aller

en 3

3- Si (N1 et N2 effectuent des rotations le mois m) Alors

3.1-Choisir aléatoirement de chaque navire une Rotation, etes substituer

4- Si (la solution est toujours réalisable) Alors

aller en 8

Sinon

Aller en 1

Fin Si

Fin Si

5- Si (L'un des navires N1,N2 effectue des rotations le moism, et 'autre

non) Alors

5.1-Choisir aléatoirement une rotationdu premier navire et'affec

ter au deuxieme

6- Si (la solution est toujours réalisablle) Alors

aller en 8 Sinon

Aller en 1

Fin Si

Sinon

8- Si (les deux navires N1,N2 n'effectuent aucune rotation emois m)

Alors

Aller en 1 Sinon

Fin Si

Fin Si

8-Une solution voisine est générée,fin

Algorithme 3: Procédure Génération desolutions voisines

6.4.4 Listes Tabous adaptées à notre problème

Pour éviter le cyclage de l'algorithme, on définie deux listesTabous, ListeTran et ListeSub.

1. ListeSub

Mémorise un nombre fixe de types substitutions de rotations.es cellules de la liste sont représentées par des Quadruplés dea forme suivante (Rotationi, Rotation2NavirelNavire2). et on it(La rotation1 et la rotation2 effectuées respectivement par le navire1 et enavire2 sont substituées), donc on interdira toute candidatured'une solution obtenue par la modification inverse à celles contenuedans la liste ListeSub.

2. ListeTran

Mémorise un nombre fixé de types transferts derotations.es cellules de la liste sont représentées par des triplés dea forme suivante (RotationÄ, Navirel, Navire2) . et onlit(La rot ationÄsera transférée du navirel versle navire2) donc on interdiratoute candidature d'une solution obtenue par la modification inverse àcelles contenue dans la liste ListeTran

6.4.5 Tailles des Listes

En effectuant des tests, on a fixé les tailles des deux listes à 7 Cette taille est trés envisageble dansl'adaptation de la méthode recherche tabou.

6.4.6 Critère d'aspiration

Une solution tabou doit dans certains cas perdre son statut tabou pour devenir candidate à la meilleure solution voisine, et daméliorer ameilleure solution rencontrée, pour cela on definit la fonction d'aspiration suivante A(F(s)) = F(s^°).

6.4.7 Critére d'arrêt

Le critère d'arrêt pourlequel on à opté, est celui de fixer enombremaximum d'itération.

6.4.8 Algorithme Recherche Tabou Adapté à notre problème

Var

niter : entier positif ;

{Compte le nombre d'itération e~ectuées dans 'éxploration deouteses solution passéess

bestiter : entier positif; {Mémorise l'itération de la meilleure solution retrouvéee

maxiter : entier positif ; {Nombre maximum d'itérationj

1-Trouver une solution initiale réalisable par la procedure SolRéalTabou;

2-Initialiser les listes ListeSub et ListeTran;

3-niter := 0;

4-bestiter := 0;

5- Tant que (niter maxiter) faire

5.1-niter := niter + 1;

5.2- Tant que (il existe toujours des solutions voisines non explorées et n nbV) faire

5.2.1-Générer s^' une solution voisine avec GénéVoisin 5.2.3- Si (f(s^') < A(f(s)) ou (le mouvement vers s^' n'est pas dans listeSub ou listeTran)) Alors

ajouter s^' à l'ensemble des solutions voisines Fin Si

Fait

5.3-Retenir la meilleure solution dans lensemble des solutions voisines;

'

5.4- s := s;

5.5-Mettre à jourles listes ListeSub et listeTrans

5.6-Mettre à jourla fonction daspiratonA

5.7- Si (f(s) <f(s^°)) Alors

s° := s; bestiter := niter;

Fait

Fin Si

FIG. 6.1 Procédure population initiale

FIG. 6.2 - Organigramme de la procedure croisement

FIG. 6.3 - Organigramme de la procedure mutation

FIG. 6.4 Procedure SolRéalTabou

Chapitre 7

Logiciel

Lors de la réalisation de cette étude, nous avons été amenés concevoir un logiciel dans le but d'appliquerles méthodes de résolution au problème posé. En effet il serait déraisonnable dessayer detrouver une solution au problème sans l'aide d'une machineétant donné la complexitédu problème et la méthode utilisée.

Notre logiciel est une application MDI qui a été conçue avec Borland Delphi 7 Entreprise.

7.1 Qu'est-ce que Delphi?

Delphi est un environnement de programmation visuel orienté objetpour le développement rapide d'application (RAD) En utilisant Delphi, vous pouvez créer de puissantes applications pour MicrosoftWindowsXPMicrosoft Windows 2000 et Microsoft Windows 98, avec un minimum de programmation. Delphi fournit tousles outils nécessaires pour développer, tester et déployer des applications, notamment une importante bibliothèque de composants réutilisables, une suite doutils de conception, des modèlesd'applii cations et de fiches et des experts de programmation.

Delphi permet de concevoir tout type dapplication 32bits, qu'ils'agisse d'un utilitaire de portée généraledun programmecomplexe de gestion de données ou d'une application distribuée

7.2 Qu'est ce qu'une application MDI?

Dans une application MDI (Interface de Document Multiple) plusieurs documents ou fenêtres enfants peuvent être ouverts dans une seule fenêtre parent. Cela est courant dans les applications tellesque estableursou es traitements de texte

7.3 Présentation du logiciel

Le logiciel Flotte GPL 2006 est destiné à la prise en chargede a sélection et de la planification de la flotte de GPLiers, susceptibles de permettre à Sonatrach de satisfaire tousses clients en minimisant e coûde transport. Donc Flotte GPL 2006 permet de

1. Séléctionner la flotte optimale parmi uneliste de navires

2. Etablir un planing sur toute lannée ou sur une saison, en précisant ~ La date de chargement pour chaque rotation

~ La date du retour du navire de cetterotation

~ Le quai de chargement du navire

3. La gestion de toutesles données en relation avece probllme, cette gestion est possibe grâce à une base dedonnées locales mplémentée sur La SGBD Paradox, et une panoplie de masques de saisies qui facilitent et organisent la manipulation de ces données

Présentation de la "fiche principale"

Cette fiche est la fenêtre principale du logiciel, elle permet d'acceder à toutes les autres fichessoit par lutilisationdu menudéfilant, soit enutilisant les bouttons de raccourci

Chaque fois que l'utilisateur pointe le curseur sur un boutton raccourci, a barre d'état affiche la commande corespondante.

Présentation de la fiche "nouveau port"

Cette Fiche permet l'enregistrement des informations d'unnouveau port de déchargement, en toute sécurité.

Cette fiche renvoie des méssages davertissements, àchaque ois que'utilisaa teur essaye d'introduire des données incohérentess

Ces données pourront être modifiées ousupprimeés avec a même acilité, en utilisant d'autres fiches similaires disponibles sur ce logiciell

Présentation de la fiche "nouveau navire"

Cette Fiche permet l'enregistrement des informations d'unnouveau naa vire, en toute sécurité.

Cette fiche renvoie des méssages davertissements, àchaque fois que'utilisaa teur essaye d'introduire des données incohérentess

Ces données pourront être modifiées ousupprimées avec a même facilité, en utilisant d'autres fiches similaires disponibles sur ce logiciell

Présentation de la fiche "nouveau poste de chargement"

Cette Fiche permet l'enregistrement des informations d'unnouveau poste de chargement, en toute sécurité.

Cette fiche renvoie des méssages davertissements, àchaque fois que'utilisaa teur essaye d'introduire des données incohérentess

Ces données pourront être modifier ousupprimer avec a même facilité, en utilisant d'autres fiches similaires disponibles sur ce logiciell

Présentation de la fiche "suppression"

Cette Fiche permet la suppression logique ou physique des informations d'un port, un navire ou un quai, en toute sécurité.

Présentation de la fiche "listes"

Cette Fiche permet d'afficherla liste des navires, ports ou postesde charr gement.

Il est recommandé de ne pas modifier les données en utilisant cette fiche, car l'utilisateur risque de saisir des données incohérentes.

Présentation de la fiche "durées des rotations"

Cette Fiche permet simplement dafficher les durées derotation de chaque navire, vers chaque port compatible.

Présentation de la fiche "comparaison des méthodes"

Cette Fiche permet de lancerl'exécution des deux algorithmesde réé solutions, ainsi que la comparaison de ces méthodes, et le choix du mode d'affichage graphique ou numérique de la solution.

Présentation de la fiche "résolution"

Cette Fiche permet de lancer lexécution de algorithme de a recherche Tabou seul car ce dernier est généralement plus perrormant que lagorithme génétique, ainsi que le choix du mode daffichage graphique ou numérique de la solution.

Présentation de la fiche "affichage alphanumérique de la solution"

Cette Fiche permet l'affichage de la solution. Elle permet aussilimpress. sion de la solution. La répartition de la solution sur des feuillede formatAA, est faite automatiquement par le logiciell

Présentation de la fiche "affichage graphique de la solution"

Cette Fiche permet l'affichage intuitiifde la solution, cara soluion numéé rique est difficile à comprendre

Conclusion

Se trouvant dans un environnement concurrentiel, la Société Pétrolière Sonatrach envisage l'adaptation dune stratégie de transportmaritime des GPL à la mesure de ses ambitionsà savoirAssurer etransport dea totaa lité des volumes des GPL disponibles à lexportation par ses propresmooens (CIF / CFR). Cette stratégie implique entre autre'élaboration d'un plann ning d'affectation et la détermination de lataille et de a structure d'une flotte optimale Compte tenu delimportance que peut susciter amise en place d'un planning d'affectation et la déterminationde a taillede a struc ture d'une flotte optimaleune compagnie pétrolièrede grande envergure telle que Sonatrach, doit s'orienter vers lutilisationdes méthodes scientiiques baa sées sur des techniques de la recherche opérationnelle.

Dans ce contexte, le département des ventes GPL, branche commerciale, nous a chargé de réaliser un modèle qui minimise le coût totaldutransport entre autre le coût d'affretement qui constitue 70 %de ce coûttotal, et ainsi réduit au mieux les besoins en navires à affréter

Une formulation mathématique en terme de programme inéaire à variables bivalentes est faite. Cette formulationtient compte de touteses contraintes imposées.

Quant à l'objectif, il exprime le voeu doptimiser le coût totalde 'opéraa tion de transport. Pour sa résolution, lutilisationdesméthodes exactes en un temps raisonnable s'avère prohibitive, ce qui nous a amené àadopter des méthodes approchées, d'autant plus que certaines d'entresellesont prouvées leurs grande efficacité pour des problèmesde naturesimilaire.Dans notre cas ( La Recherche Tabou ) et (La Méthode Génétique)ont étées heuristiques utilisées à titre comparatif

C'est dans cette optique que nous avons conçu le logiciel (Flotte GPL 000( ). Du point de vu des décideurs, le résultat obtenu dans l'optimisation des coûts de l'investissement surl'ensemble de la flotte requise était satisfaisant, du moment que les navires propres à la Sonatrachseront utilisés sur toutea période d'étude .

Quant à l'idée d'avoir mis en place un planning daffectation concretperr mettant la maîtrise totale de leurs navires à tous moments dea période était la bienvenue. Sans oublier que lavantage dans tout ça se résume pare fait, qu'au moment de la signature des contrats avec esclients, es décideurs peuvent négocier des dates delivraisons à partir du planning.

L'étude qui vient ainsi de s'achever nous a permis datteindrees objectifs qui nous ont été assignés au début de notre travaill

Au cours de cette étude notre savoir a été enrichi endécouvrant edomaine du transport maritime et celui de la commercialisation des hydrocarburess Mais, il nous reste tant à découvrir car larecherche opérationnelle est un champ bien vaste et fascinantPasser de la théorie à 'application est certes difficile mais passionnant.

Sur ce, nous terminons par dire que notre travailnest ni parfait ni complet mais peut être l'objet d'une voie de recherche.

Bibliographie

Bibliographie

[1] Yann Collette-Patrick SiarryOptimisation Multiobjetifs, Eyrolles, 2002.

[2] Goldb Berg. Algoritthme Génétique, Eyrolles, 1994.

[3] Deb.L 'utilisation des Algoritthmes Génétiquesdansun contexte multiobb jectifs, Eyrolles, 2001.

[4] www.recherhe.enac.fr/opti/papers/thesis/HABIT/main002.html

[5] www.Polytech-Lille.fr

[6] www.Univ-Orleans.fr

[7] www.Developper.com

[8] Guerrache H. Nebli F. Optimisation des expeditions duGPL par navires à partir des ports d'Arzew, PFE USTHB, 1996.

[9] Slimana S. Kerbou B. Strategie du Transport Maritime des GPL, PFE USTHB, 2001.

Table des figures

1.1	Organigramme De La SONATRACH	11
2.1	Organigramme Des Exportations ParRegion	19
2.2	Carte Des Exportations Par Region	19
2.3	Diagramme Des Exportations des gaz GPL àLhorizon 2015	20
3.1	Ensemble des ports de destination	27
5.1	Organigramme de la méthode de Recherche Tabou	41
5.2	Organigramme de l'algorithme évolutionnairegénétique	46
5.3	Illustration schématique du codage des variables x 47
5.4	Les cinq niveaux d'organisation de lAG	48
5.5	Représentation schématique du croisement en un point	52
5.6	Représentation schématique du croisement endeux points	52
5.7	Représentation schématique de la mutation	54
5.8	Organigramme d'un Algorithme Génétiquestandard	58
6.1	Procédure population initiale	77
6.2	Organigramme de la procedure croisement	78
6.3	Organigramme de la procedure mutation	79
6.4	Procedure SolRéalTabou	80

Liste des Algorithmes

1	Procédure Croisement . . . . .	70
2	Procédure Mutation . . . . . . . . . .	72
3	Procédure Génération de solutions voisines	74
4	Algorithme de la recherche Tabou adapté à notreprobllme	76

Annexe