Un algorithme génétique en ligne pour la résolution du PTV dynamique sous incertitudes

De
Publié par

Un algorithme génétique ?en ligne? pour la résolution du PTV dynamique sous incertitudes Mohamed DJADANE, Gilles GONCALVES et Tienté HSU Université d?Artois ? Laboratoire de Génie Informatique et d?Automatique de l?Artois Courriel : Valenciennes, le jeudi 16 novembre 2006

  • ?en ligne? pour la résolution du ptv dynamique

  • constantes temps de trajets variables

  • temps de trajet

  • limites des approches statiques


Publié le : mercredi 1 novembre 2006
Lecture(s) : 258
Source : univ-valenciennes.fr
Nombre de pages : 28
Voir plus Voir moins
Un algorithme génétique “en ligne” pour la résolution du PTV
dynamique sous incertitudes
Mohamed DJADANE, Gilles GONCALVES et Tienté HSU
Université d’Artois – Laboratoire de Génie Informatique et d’Automatique de l’Artois
Courriel :mohamed.djadane@fsa.univ-artois.fr
Valenciennes, le jeudi 16 novembre 2006
1.
2.
3.
4.
5.
6.
7.
Limites des approches statiques du VRP.
Le simulateur DVRP.
Une extension du VRP : le VRPTW.
Variantes autour du VRPTW.
Plan de la présentation
Indicateurs de mesure de qualité d’une tournée.
Résultats préliminaires.
Conclusion et perspectives.
2
Limitesdesapprochesstatiquesdu VRP
Circulation, horairesde pointes etviations.
Vitesses des véhicules non constantesTemps de trajets variables.
Itinéraires variablesTemps de trajets variables.
Production d’événementsaléatoires(aléas).
Arrivées de nouveaux clients durant la journée de service.
Fins de services prématurées.
Pannes des véhicules et accidentsCongestion de trafic.
3
Monde réel
Simulateur
Benchmark, loi de distribution
Nouveau client Fin de service
Prochain client
4
NC
SimulateurDVRP
Planification
FSGE
Graphique
Contrôleur
AG
Une extension duVRP : leVRPTW
(Potvin,Garcia etRousseau 1996,Potvin et Bengio1996, Chiang et Russel1997)
VRPTW=Vehicle RoutingProblem with TimeWindows.
Contraintes supplémentaires:contraintes temporelles surl’instant de
début de service. Chaque clientidispose d’un intervalle (fenêtre) de temps à
l’intérieur duquel (de laquelle) il souhaite être servi.
Instant de départ
Temps de trajet Attente Service
Client i
5
ej
Client j
lj
Fenêtre de temps
t
ConceptdeHard/Soft
1. VRPHTW:VehicleRoutingProblem withHardTimeWindows.
obligatoirement servi dans sa tranche horaire.Chaque client est
Conséquences:
Problème trop cotraint (contraintes dures).
Absence de solution dans certains cas.
2. VRPSTW :VehicleRoutingProblem withSoftTimeWindows.
Chaque client pourrait être servi en dehors de sa tranche horaire.
Conséquences:
Problème moins contraint (contraintes souples).
Les retards ne sont pas bornés.
6Variante 1 du problème
VRPSTW –Fenêtresstrictes (synthèse)
Satisfaction totale(100%) ounulle (0%)de lacontraintetemporelle
1
0
Attendre
En avance
12:00
Servir
À l’heure
7
15:00
Servir en pénalisant
En retard
0.8
0.5
0
Attendre
Di
11:45
VRPHTWFenêtresflexibles (synthèse)
12:00
Servir
Di
15:00
15:15
Ne pas servir
8Variante 2 du problème
0.8
0.5
0
Attendre
Di
11:45
VRPSTWFenêtresflexibles (synthèse)
12:00
Servir
D’i
15:00
Servir en pénalisant
15:15
9Variante 2 du problème
1
0
(PrzemysławWESOŁEK 2005)
Temps detrajet
Nombre floutriangulaire(TriangularFuzzyNumber, TFN)
10
imprécis
Variante 3 du problème
1
0
Sat = 100%  
1
Notremesure de satisfactionduclient
Fermeture de la fenêtre de temps
2
3
4
Sat = 0%
5
6
11
7
8
9
10
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.