View
28
Download
0
Category
Preview:
DESCRIPTION
Méthodes exactes et approchées pour l’optimisation des systèmes à moyen de transport. Philippe Lacomme Maître de conférences – 27 ème section. HABILITATION À DIRIGER DES RECHERCHES. 6 juillet 2005. Contenu de la présentation. Curriculum Vitae Activités pédagogiques - PowerPoint PPT Presentation
Citation preview
1
Méthodes exactes et approchées pour l’optimisation des systèmes
à moyen de transport
Philippe Lacomme
Maître de conférences – 27ème section
HABILITATION À DIRIGER DES RECHERCHES
6 juillet 2005
2
Contenu de la présentation
Curriculum Vitae Activités pédagogiques Activités de recherche Synthèse scientifique
Problèmes de tournées sur arcs Ateliers à ressources de transport
Conclusion Perspectives
3
Curriculum Vitae
Fonction actuelle Maître de Conférences depuis 1999 27ème section, Membre du LIMOS IUT de Montluçon
Formation Ingénieur Informatique CUST (1993) DEA Informatique Industrielle (1993) Doctorat, Université Blaise Pascal (1998)
Fonctions précédentes Maître de Conférences à l’UTT de Troyes ATER de Sep. 97 à Janv. 99
4
Activités pédagogiques Recherche Opérationnelle (Simulation, optimisation…) Gestion des Stocks Algorithmique programmation
2 à 5 étudiants/an en stage
Exemples de projets tutorés Mise en place d'un suivi des stocks à la caserne de
pompiers de Montluçon Dimensionnement d'un stock et traçabilité des
pièces pour la société S2MI
5
Encadrements d’étudiants en liaison avec la recherche (1/2)
Eric Soutera. Auditeur CNAM. 2005. Problèmes de tournées sur nœuds Co-Encadrement avec M. Gourgand 2 publications (ROADEF’05, IESM’05)
Mathieu Bécart– Projet CUST Génie Mathématiques. 2003. Modèle linéaire pour la planification des
systèmes flexibles de production Co-Encadrement avec N. Tchernev 2 publications (INOC’03, MOSIM’04)
6
Encadrements d’étudiants en liaison avec la recherche (2/2)
Khata Mohammed Nadir. Stage de Maîtrise d’Informatique. Problème de tournées sur nœuds
Fabrice Franquenk et Lorine Pornet. 2ème Année d'Ingénieur ISIMA Solutions robustes et/ou flexibles du job-shop
Cédric Caron, Nicolas Antoine. 3ème Année d’Ingénieur ISIMA. Réalisation d’un logiciel en OpenGL pour la visualisation de graphes en
3D
Rachid Driouch et Nicolass Kuchciak. 2ème Année d’Ingénieur ISIMA. Optimisation de la collecte des déchets ménagers (algorithmes de
fourmis)
7
Projet international de coopération Partenariat entre l’Université de
Clermont-Ferrand et l’Université Ferhat Abbas de Sétif
Participation à la mise en place du LMD à l'Université Ferhat Abbas de Sétif
Co-responsable du cours de théorie des graphes (G. Fleury, P. Lacomme)
8
Autres activités
P. Lacomme, C. Prins et M. Sevaux
"Algorithmes de graphes"
Editeur : Eyrolles, 2003
G. Fleury, P. Lacomme, A. Tanguy"La simulation par l’exemple"
Editeur : Eyrolles
Prévu fin 2005
9
Activités de recherche
Évolution des activités Contexte des différentes études Participation à des projets de
recherche Encadrements de thèse Bilan des publications
10
Évolution des activités
HSP : Atelier de traitement de surfaces (ATS)FMS : Système Flexibles de Production (SFP)CARP : Capacitated Arc Routing ProblemSCARP : Stochastic CARP
VRP : Vehicle Routing Problem
11
Contexte des différentes études
Problèmes Contexte Déterministe Contexte Stochastique
Flow-Shop Hybride X X
Job-Shop X
FMS X
HSP X X
VRP X
Multi-Objective CARP X X
CARP X X
TSP X
12
Participation à des projets de recherche
Projet stratégique : Logistique du transport : problèmes de tournées complexes (2002-2004)
Responsable du projet : C. Prins
Projet PICASSO Membre du projet PICASSO déposé avec l’équipe de recherche
de Valence. Responsable du projet : C. Prins
Projet "Ordonnancement de jobs et gestion des moyens de transport dans les ateliers flexibles de production»
Responsable du projet : A. Moukrim Action Spécifique Recherche Opérationnelle Rédaction d’un article regroupant la communauté française sur
les FMS en cours d’acceptation à JESA
13
Encadrements de thèse
Wahiba Ramdane Chérif Encadrement : Philippe Lacomme (50%) et Christian
Prins (50%) Problèmes d’optimisation en collecte de déchets 12 décembre 2002.
Anthony Caumond Encadrement : Michel Gourgand (20%), Philippe
Lacomme (40%) et Nikolay Tchernev (40%) Métaheuristiques et modèles d'évaluation de
performances pour le Job-Shop flexible avec transport Décembre 2005
14
Bilan des publications depuis 1999
Livres Revues LNCS Publications en Anglais
Publicationsen Français
2005 Eyrolles CAOR (2), JORS IJPR, EJOR
IESM’05 (2)MIC’05 (2)
ROADEF (2)
2004 AOR ANTSEVOSTOC
PMS’04ESMc’04
MOSIM(2)
2003 Eyrolles IJCIM EMO CORAL(2), OSYSSEUS, INOC, ESMc
MOSIM, EARO
2002 MOMH, IFORS, IFAC (2), IPMU, CO, AIS, PMS
ROADEF
2001 IJPR Euro-GP ESS (2) MOSIM (2)
2000 IMACS, ESM, MCPL ROADEF
1999 JESA, JIM ACS, CARs&COF,ETFA, IEPM
Total 1+1 10 4 28 10
15
Synthèse scientifique
Démarche globale Problèmes de tournées Problèmes d’atelier à ressources
de transport
16
Démarche globalele problème
Résolution exacte
hypothèses simplificatrices
'
mise en oeuvresur des instances de
taille limitée
solutions exactes
réalisation d un modèle mathématique
Optimisation
Modélisation
Modèle
Problème
Solution
Validation
1
2
3
4
5
6
17
Problèmes de tournées sur arcs
1998 1999 2000 2001 2002 2003 2004
Multi-Objective CARP
TSP
2005
VRP
Multi-Objective SCARP
SCARP
CARP
CARP : Capacitated Arc Routing Problem VRP : Vehicle Routing Problem TSP : Traveling Salesman Problem
18
Le problème de tournées sur arcs
But : Collecter les
déchets sur les rues
Objectif : Au moindre
coût
Contraintes : Capacité
limitée des camions
dépôt
10
5 9
93
3
1.5
1.5
3
5
6
10
10
12
3
33
3
11
12
4
3 3.5
10
12
3
610.5
3
3
1.5 5
19
Le problème et sa modélisation Le problème
Des arcs à collecter Des véhicules de capacité identique
Déterminer un ensemble de tournées de coût minimal
La modélisation Graphe orienté Chemin le plus court entre les arcs Distancier arc à arc Dépôt = arc fictif
1
2
3a
b
c
d e u x a rc s
une arêteinv(2) = 4, inv (4) = 2
suc (4) = 2
1
2
31
4
2
5
3
inv(3) = i inv (5) = 0
20
Proposition pour le CARPinterface
algorithme génétique graphe
les paramètresde l'algorithme
meilleure solutiontrouvée
méthode SPLIT
graphe auxiliaire
un tour géant une solution du CARP
Modélise le problème
21
Méthode de découpage exacte
Paramètre d’entrée Paramètre de sortie
22
Exemples de résultats
Carpet : algorithme de Hertz MA : Memetic Algorithm
meilleure méthode publiée pour le CARP
23
Exemple de problème stochastique : le SCARP
Variation des quantités à collecter Allers/retours supplémentaires au dépôt
Recherche de solutions robustes :peu sensibles aux variations de la demande
24
Démarche générale pour un problème stochastique
Résolution du problème initial Modification de certaines
contraintes Intégrer les lois représentants
l’aspect stochastique
Vérifier statistiquement les propriétés des solutions obtenues
25
Différentes « approches » possibles
Résoudre le problème Déterministe mesurer la robustesse des solutions
Modifier certaines contraintes du problème Intégrer lors de l’optimisation l’objectif de
robustesse obtenir des solutions robustes
Etudes Atelier de traitement de surfaces (temps de transport
stochastiques) Flow-Shop Hybride (temps d’usinage stochastiques) Tournées sur arcs
26
Difficultés / voie de résolution
Problème déterministe
Problème stochastique
27
Exemple sur le CARP
28
Résultats sur le CARP
Résolution du CARP : utilisation à 100% de la capacité des véhicules
Résolution du CARP : utilisation à 80% de la capacité des véhicules
Résultats à la fin de l’optimisation
Résultats évaluésAu cours des réplications
29
Approche intégrant des lois
Fonction objectif :
1H
Problème déterministe
Problème stochastique 11 . HH
Exprimer mathématiquement :
1Het 1H
Utiliser les schémas classiques d’optimisation
Choisir pour obtenir des valeurs de et de 1H comparables
Deux critères agrégés
30
Mise en œuvre sur le CARP
Nécessité de minimiser : La moyenne L’écart-type
Ecart entre la solution déterministe et la solution en minimisant
Ecart entre la moyenne et la solution déterministe
Minimiser
31
Résolution d’un problème stochastique sur deux critères
But : Obtenir des solutions robustes selon deux critères simultanément
)(1 xh
)(2 xh
)(1 xH
)(2 xH
32
)(.)()( 111 xHxHxf
)(.)()( 222 xHxHxf
Principe
Utiliser un schéma « classique » multi-objectif
Lien entre le multi-objectif et le stochastique
Utiliser un schéma « classique » multi-objectif
33
Application de la démarchepour le CARP
Coût moyen Ecart-typedu coût
Ecart-type de la loongueur moyenne dela tournée la pluslongue
Longueur moyenne de la tournée la plus longue
34
Mise en œuvre : population initiale
35
Mise en œuvre : population finale
36
Comparaison – échelle identique
Population initiale Population finale
37
Validation des résultats
Gdb1- résultats finaux
Gdb1-validation des résultats par simulation
Coût moyen calculémathématiquement
Coût moyen calculépar réplications
Ecart-type calculémathématiquement
Ecart-type calculépar réplications
38
Bilan sur les problèmes de tournées
Modélisation sous la forme d ‘un graphe orienté
Mono-Objectif Multi-Objectifs
Déterministe Stochastique Déterministe Stochastique
Meilleure méthode publiéeMeilleure que la méthode CARPET
Aussi performante quel’approche mono-objectif
3 approches possiblesDétermination de solutionsrobustes
Aussi performante quel’approche mono-
objectifstochastique
Effort de formalisationUne instance
16s 27s
39
Ateliers à ressources de transport
HSP : Atelier de traitement de surfaces (ATS)FMS : Systèmes Flexibles de Production (SFP)
40
Les SFP = Job-Shop avec contraintes
Une station = une machine + un stock d’entrée + un stock de sortie
2 demandes de transportDécision de gestion
41
Travaux réalisés sur les SFP
Ordre d’entrée des pièces
Gestion des mouvements du
chariot
Gestion des pièces dans les stocks
Modèle linéaire Résolution exacte Résolution exacteRésolution exacte
ou FIFO
Simulation réflective Résolution exacte Résolution exacte FIFO
Couplage Branch-and-Bound/règle de
priorité/simulationRésolution exacte
Résolution approchée(règle de priorité)
FIFO
Couplage Algorithme Stochastique/règle de priorité/simulation
Résolution approchéeRésolution approchée
(règle de priorité)FIFO
42
Synthèse du modèle linéaire
Type de contraintes Formulation de Bilge et Ulusoy
1995
Formulation de MacCarthy
1997
Notre formulation
Contraintes de précédence Oui Oui Oui
Contraintes d’ordonnancement Oui Oui Oui
Contraintes de transport en charge Oui Oui Oui
Contrainte de transport à vide Oui
Capacité des stocks d’entrée Oui Oui
Capacité des stocks de sortie Oui
Nombre maximal de pièces simultanées Oui
Blocage des machines Oui
Règle de gestion des stocks Oui
43
Travaux réalisés sur le Job-Shop But : Proposer un algorithme
No-Wait
Time-Lags
Job-Shop
interface
algorithme génétique
les paramètresde l'algorithme
meilleure solutiontrouvée
un ordre des opérations sur les
machinesune solution
Module de Modélisation /Optimisation
Graphe Disjonctif non orienté
algorithme de type Bellman
Graphe disjonctif orienté
Modélise le problème
44
Le problème et sa modélisation
Graphe disjonctif Graphe disjonctif avec Time-Lags
45
Un chromosome et la solution associée
Un chromosome une orientation du graphe
Un calcul de chemin le plus court le makespan
Mise en œuvre : Instances no-wait Instances de Job-Shop Instances avec TL
Sur les instances no-wait résultats proches (en terme de qualité) de ceux des méthodes dédiées
46
Le problème du Job-Shop avec transport et sa
modélisation Modéliser les transports à charge Modéliser la capacité limitée des stocks Modéliser la politique de gestion FIFO
Objectif : Proposer une modélisation sous les mêmes
hypothèses que le modèle linéaire des FMS
47
Quelques idées
0
1
5
2
6
3
7
4
8 *
0
0
18 8 28 16 310 12
8
48 20 510 10 68 18 12
9 10 11 12
0
712 12 88 8 912 1514
208
18
12
18816 8 20
18 18
20
8
16
12 8
Travaux de Brucker et Hurink
2 types de nœuds
Difficultés liées aux liensentre le transport et lepassage des pièces sur
les machines
48
Bilan sur les problèmes d’ordonnancement
Problèmes d'ordonnancement
HSP FMS Job-Shop
Modèle de simulation
Couplage Simulation/méthodesstochastiques
Contexte stochastiqueet déterministe
Modèle de simulation
Modèle linéaire
Contexte déterministe
Couplage Simulation/méthodes stochastiques
Couplage Simulation/méthodes énumératives
Modèle de graphe
Contexte déterministe
Couplage Graphe/méthodes stochastiques
Modèle de graphes Modèle linéaire
49
Conclusion
Problèmes Contexte Déterministe Contexte Stochastique
Flow-Shop Hybride X X
Job-Shop X
SFP X
HSP X X
VRP X
Multi-Objective CARP X X
CARP X X
TSP X
50
Cas général : environnement Stochastique système Stochastique
Optimisation stochastique
51
Perspectives Tournées
Flotte hétérogène Plusieurs dépôts Distribution/collecte simultanées Flotte avec camions compartimentés
Ateliers à ressources de transport Extension des modèles de graphes Extension du modèle linéaire Plusieurs chariots
Liens entre les problèmes de tournées et les problèmes d’ordonnancement dans les ateliers ?
52
Idées pour des sujets de thèse ?
Les problèmes de tournées sur arcs et leurs extensions
Problèmes de collecte/distribution simultanées Problèmes de conception de réseaux de
distribution Problèmes d’ordonnancement dans des
ateliers à ressources de transport multiples Problèmes de conception des SFP Problèmes d’ordonnancement flexibles dans
les job-shop avec extensions
53
FIN !
Recommended